- Bitboard
-
Ein Bitboard (Bitmap Board) ist eine Datenstruktur, die häufig Verwendung in Computerprogrammen für Brettspiele findet, insbesondere bei Schachprogrammen.
Inhaltsverzeichnis
Übersicht
Die Grundidee der Bitboard-Struktur ist es, dass sich die Frage, ob auf einem bestimmten Spielfeld eine bestimmte Figur vorhanden ist, mit ja oder nein beantworten lässt. Aufgrund dessen kann die Belegung eines Spielplans endlicher Größe als Sequenz einzelner Dualzahlen dargestellt werden, die jeweils den Wert 0 oder 1 annehmen können.
Dualzahlen ("Bits") stellen die Basis der meisten heutigen Computersysteme dar, weshalb darauf basierende Strukturen grundsätzlich sehr effizient verarbeitet werden können. Einfluss auf den effizienten Einsatz von Bitboard-Strukturen haben insbesondere
- die Spielplangröße: am besten ist diese Größe fest und kleiner oder gleich der größten Wortgröße des Computers;
- die Anzahl unterschiedlicher Figuren, da ein einzelnes Bitboard nur die Spielplan-Belegung mit einer einzigen Figurensorte beschreiben kann.
Grundsätzlich sind Bitboard-Strukturen für verschiedene Brettspiele geeignet. So gibt es zum Beispiel auch Bitboard-Implementationen des Dame- und des Othello-Spiels[1][2]. Besondere Bedeutung haben Bitboards allerdings im Bereich des Computerschachs erlangt. Ein Schachbrett besteht aus 8x8=64 Feldern, ein zugehöriges Bitboard ist also 64 Bits lang. Diese Größe kann von modernen Computersystemen direkt als Datenwort verarbeitet werden, was einen großen potentiellen Geschwindigkeitsvorteil verspricht. Beispiele für Computerschach-Programme, welche Bitboards verwenden, stellen Crafty[3] und die aktuelle Version 5.0 von GNU Chess[4] dar.
Vor- und Nachteile
Der Hauptvorteil von Bitboard-Strukturen liegt in der potentiell sehr hohen Verarbeitungseffizienz, sowohl mit Blick auf Speicherplatz als auch vor allem mit Blick auf die Programmgeschwindigkeit. Eine komplette Schachstellung lässt sich z.B. in deutlich unter 150 Bytes kodieren, und viele Spielplan-Operationen können jeweils durch wenige Prozessorbefehle ausgeführt werden[5].
Der hauptsächliche Nachteil von Bitboards liegt in ihrer "Andersartigkeit" gegenüber älteren, weiter verbreiteten Darstellungsarten. Robert Hyatt, der Entwickler der bekannten Schachsoftware Crafty, schreibt über seine ersten Erfahrungen mit Bitboards:
“This has likely been the primary reason that bitmaps have not been widely used; they are different and take some time to "sink in" to the point where they become easy to use. I would speculate that it took me roughly a year before I was able to get past the mental gymnastics of designing an algorithm using offset representation ideas and then working out how to modify the idea to fit the bitmap approach.”
– Robert Hyatt
Da mittlerweile eine ganze Reihe von quelloffenen Bitboard-Implementationen existieren, dürfte dieses Argument gegen Bitboards allerdings nur noch schwach wiegen und in seiner Bedeutung weiter abnehmen.
Anwendungsbeispiel: Computerschach
Wie bereits erwähnt, ist ein Bitboard im Schach-Fall aufgrund der Größe des Schachbretts genau 64 Bits lang. Als Besonderheit gibt es 12 verschiedene Arten Figuren (Bauern, Türme, Springer, Läufer, Dame, König in jeweils beiden Farben). Aus diesem Grund kommen normalerweise mindestens 12, jedoch meistens noch mehr Bitboard-Strukturen gleichzeitig zum Einsatz.
Die eingangs erwähnte Software Crafty beispielsweise speichert neben den Positionen der 12 Figurensorten in weiteren Strukturen die Positionen aller weißen bzw. schwarzen Figuren zusammengenommen, und zudem gedrehte Versionen des Spielbretts für weitere Optimierungen. Eine komplette Datenstruktur, die den momentanen Zustand des Spieles vollständig beschreibt, muss zudem Informationen über den Status z.B. von Rochade-Möglichkeiten, "en passant"-Zügen, der 50-Züge-Regel und gegebenenfalls weiteren Sonderregeln enthalten.
a b c d e f g h 8 
8 7 
7 6 
6 5 5 4 4 3 3 2 
2 1 
1 a b c d e f g h Schach: Ausgangsposition 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 Die Ausgangsposition (siehe Diagramm) führt für die weißen Bauern auf folgende Bitboard-Struktur (für die anderen Figurenarten gelten entsprechende Belegungen):
00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000 2.
Auf welche Art "gezählt" wird, also welches Feld des Schachbretts welchem Index in der Bit-Darstellung zugeordnet wird, ist letztlich wahlfrei. Bei diesem Beispiel und im Folgenden wird beginnend beim Feld A1 zeilenweise gezählt, also gehört zu A1 das Bit 0, zu A2 das Bit 1, und so weiter bis schließlich zu Feld H8 und Bit 63. Wie bereits erwähnt, verwalten einige Schachprogramme sogar Bitboard-Strukturen in verschiedener Zählweise (zeilen- oder spaltenweise, bzw. auch diagonal) gleichzeitig, da hierdurch bestimmte Operationen effizienter möglich sind.
Zug-Berechnung
Ein zentrales Problem bei der Umsetzung eines Schachprogramms stellt die Berechnung der möglichen Folgezüge aus einer gegebenen Position heraus dar. Bei Benutzung von Bitboard-Strukturen erfolgt dies durch logische Operationen auf der Spielplan-Belegung. Hierbei müssen zwei Arten von Figuren unterschieden werden: bei den "springenden" Figuren wie Bauern, Springern und König ist allein die Belegung des Zielfelds entscheidend. Bei den "gleitenden" Figuren wie Türmen, Läufer und Dame ist die Zugmöglichkeit komplexer, da Figuren bestimmte Zielfelder blockieren können, ohne diese selbst zu belegen.
Bauer, Springer, König
a b c d e f g h 8 8 7 7 6 
6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Mögliche Springer-Züge vom Feld D4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 Bei diesen Figuren kommt es lediglich darauf an, ob auf dem Zielfeld eine Figur der eigenen Farbe platziert ist. Tatsächlich stellen die Bauern wiederum einen Sonderfall dar, da sie unterschiedlich ziehen, je nachdem ob sie eine gegnerische Figur schlagen oder nicht. Darauf soll hier jedoch nicht eingegangen werden.
Man betrachte als Beispiel einen Springer auf Feld D4. Die möglichen Zielfelder sind im Diagramm zu sehen. Die Frage, ob der Springer grundsätzlich auf ein bestimmtes Zielfeld ziehen kann, ist wiederum eine mit ja oder nein zu beantwortende Frage, deren Antwort als Bitboard kodierbar ist. Für jedes Feld von A1 bis H8 kann ein solches "Angriffs-Board" im Vorhinein berechnet und abgespeichert werden.
Im gewählten Beispiel ist das Feld D4 das 28. Feld zeilenweise von A1 aus gezählt, also würde in einer Liste von 64bit-Zahlen der Index 27 (wenn 0 der erste Index ist) mit folgender Zahl belegt:
00000000 00000000 00101000 01000100 00000000 01000100 00101000 00000000 2.
Wenn diese insgesamt 64 möglichen Bitboards (für den Springer) beim Programmstart bereits berechnet werden, ist der Zugriff später also als einfache Index-Operation sehr effizient möglich. Um nun zu entscheiden, auf welche Felder der Springer tatsächlich im vorliegenden Fall ziehen kann, ist noch Information über die aktuelle Spielplan-Belegung in der eigenen Farbe erforderlich. Diese liegt entweder direkt vor oder kann aus den 6 Belegungen der einzelnen Figurensorten (durch bitweise ODER-Verknüpfung) bestimmt werden. Durch ein bitweises NICHT angewendet auf diese Belegung bestimmen sich die Felder, die nicht durch Figuren der eigenen Farbe belegt sind.
Die logische Bedingung, die für einen Springer-Zug auf ein bestimmtes Feld erfüllt sein muss, ist nun gerade, dass dort keine Figur der eigenen Farbe stehen darf. In dem eben beschriebenen Komplement-Bitboard ist genau bei jedem Feld das Bit gesetzt, bei dem diese Bedingung erfüllt ist. Das gewünschte Ergebnis ergibt sich so schließlich durch bitweise UND-Verknüpfung mit dem vorberechneten "Angriffs-Board" des Springers.
Mit leichten Anpassungen kann dasselbe Verfahren verwendet werden, um die Züge für Bauern und für den König zu berechnen.
Türme, Läufer, Dame
Diese Figuren bewegen sich grundsätzlich anders als die drei vorgenannten Arten. Bei diesen "gleitenden" Figuren kommt es zusätzlich zur Belegung des Zielfelds darauf an, ob der Weg dorthin blockiert ist, sei es durch Figuren der eigenen oder der gegnerischen Farbe. Die Dame kann als Kombination aus Turm und Läufer interpretiert werden, was je nach genauer Wahl der Datenstrukturen eine Vereinfachung darstellen kann.
Siehe auch
Quellen
- ↑ Darstellung von Bitboard-Strukturen im Dame-Spiel (englisch)
- ↑ Diskussion verschiedener Implementierungsdetails von Othello, inklusive Bitboards (englisch).
- ↑ Online-Artikel von Prof. Robert Hyatt über die in Crafty verwendeten "rotated bitboard"-Strukturen.
- ↑ Dokumentation von GNU Chess 5.0
- ↑ Vergleichender Online-Artikel von R. Hyatt über Datenstrukturen für Schachprogramme
Wikimedia Foundation.
