Bitboard

Ein Bitboard (Bitmap Board) ist eine Datenstruktur zur Darstellung einer Spielsituation (Stellung), die häufig Verwendung in Computerprogrammen für Brettspiele findet, insbesondere bei Schachprogrammen.

Ü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/-bretts 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. Kann man eine Information als Sequenz von Bits darstellen, die in ein Datenwort der verwendeten Maschine passen, lässt sie sich möglicherweise sehr effizient verarbeiten. Einfluss auf die Effizienz von Bitboard-Strukturen haben insbesondere

die Spielbrettgröße: am besten ist diese Größe fest und kleiner oder gleich der Wortgröße des Computers;
die Anzahl unterschiedlicher Figuren, da ein einzelnes Wort nur die Belegung mit einer einzigen Figurenart beschreiben kann.

Grundsätzlich sind Bitboard-Strukturen für verschiedene Brettspiele geeignet. So gibt es zum Beispiel auch Bitboard-Implementationen für Spiele wie Dame[1], Othello[2], Vier gewinnt[3] oder auch Tic-Tac-Toe[4]. Besondere Bedeutung haben Bitboards allerdings im Bereich des Computerschachs erlangt. Ein Schachbrett besteht aus 8×8=64 Feldern, ein Wort eines zugehörigen Bitboards ist also 64 Bit lang. Diese Größe kann von modernen Computersystemen direkt als Datenwort verarbeitet werden, was einen großen Geschwindigkeitsvorteil verspricht. Beispiele für Computerschach-Programme, die Bitboards verwenden, sind Crafty[5] und die aktuelle Version 5.0 von GNU Chess[6].

Vor- und Nachteile

Der Hauptvorteil von Bitboard-Strukturen liegt in der potentiell sehr hohen Effizienz, sowohl mit Blick auf Speicherplatz als auch vor allem mit Blick auf die Programmgeschwindigkeit. Eine komplette Schachstellung lässt sich z. B. gut in 64 Bytes kodieren, im Prinzip sogar in 32 Bytes. Viele Operationen auf den so repräsentierten Stellungen können jeweils durch wenige Prozessorbefehle ausgeführt werden.[7]

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.”

„Das ist wahrscheinlich der Hauptgrund, wieso Bitboards nicht weit verbreitet waren; sie sind anders, und es braucht einige Zeit, bis das soweit ‚sackt‘, dass sie einfach anzuwenden sind. Ich schätze, es hat grob ein Jahr gedauert, bis ich gelernt hatte, den gedanklichen Umweg zu vermeiden, erstmal einen Algorithmus zu entwerfen, der mit Feld-Indizes arbeitet, und dann herauszufinden, wie die Idee auf den Bitboard-Ansatz übertragen werden kann.“

– 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 Wort eines Bitboards im Schach-Fall aufgrund der Größe des Schachbretts genau 64 Bit lang. Als Besonderheit gibt es 12 verschiedene Arten Figuren (Bauern, Türme, Springer, Läufer, Dame, König, jeweils Weiß und Schwarz). Aus diesem Grund braucht man mindestens vier Wörter, um eine Stellung vollständig zu repräsentieren. Meist verwendet man aber deutlich mehr, um die Informationen einfacher verarbeiten zu können, d. h. es werden auch redundante Informationen explizit dargestellt.

Die eingangs erwähnte Software Crafty beispielsweise speichert neben den Positionen der 12 Figurensorten in weiteren Wörtern 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 z. B. für die weißen Bauern auf folgende Bitboard-Struktur (Bitmuster eines Worts):

00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000 ₂.

Auf welche Art „gezählt“ wird, also welches Feld des Schachbretts welchem Index (Bitposition im Wort) 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	1	1	0
1	0	0	1
0	0	0	0
1	0	0	1
0	1	1	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 ₂.

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

Computerschach

Einzelnachweise

Darstellung von Bitboard-Strukturen im Dame-Spiel (englisch)
Diskussion verschiedener Implementierungsdetails von Othello, inklusive Bitboards (englisch).
Bitboards and Connect Four beschreibt ausführlich eine Implementierung für Vier gewinnt (englisch).
Das Lehrvideo Bitboards für Tic-Tac-Toe erklärt eine Umsetzung für Tic-Tac-Toe (deutsch)
Robert Hyatt: Artikel über die in Crafty verwendeten „rotated bitboard“-Strukturen.
Dokumentation von GNU Chess 5.0
R. Hyatt: Vergleichender Artikel über Datenstrukturen für Schachprogramme

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[1] Darstellung von Bitboard-Strukturen im Dame-Spiel (englisch)

[2] Diskussion verschiedener Implementierungsdetails von Othello, inklusive Bitboards (englisch).

[3] Bitboards and Connect Four beschreibt ausführlich eine Implementierung für Vier gewinnt (englisch).

[4] Das Lehrvideo Bitboards für Tic-Tac-Toe erklärt eine Umsetzung für Tic-Tac-Toe (deutsch)

[5] Robert Hyatt: Artikel über die in Crafty verwendeten „rotated bitboard“-Strukturen.

[6] Dokumentation von GNU Chess 5.0

[7] R. Hyatt: Vergleichender Artikel über Datenstrukturen für Schachprogramme