imported>Nina: keine sinnvolle Zwischenüberschrift, siehe WP:WSIGA#INTRO

2026-03-01T15:57:07Z

keine sinnvolle Zwischenüberschrift, siehe WP:WSIGA#INTRO

Neue Seite

Ein '''Bitboard''' (Bitmap Board) ist eine [[Datenstruktur]] zur Darstellung einer Spielsituation (Stellung), die häufig Verwendung in Computerprogrammen für [[Brettspiel]]e findet, insbesondere bei [[Schachprogramm]]en.

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 [[Spielplan (Spiel)|Spielplans/-bretts]] endlicher Größe als Sequenz einzelner [[Dualsystem|Dualzahlen]] dargestellt werden, die jeweils den Wert 0 oder 1 annehmen können.

Dualzahlen („[[Bit]]s“) stellen die Basis der meisten heutigen [[Computer]]systeme 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 (Spiel)|Dame]]<ref>[https://www.3dkingdoms.com/checkers/bitboards.htm Darstellung von Bitboard-Strukturen] im Dame-Spiel (englisch)</ref>, [[Othello (Spiel)|Othello]]<ref>[http://www.radagast.se/othello/ Diskussion verschiedener Implementierungsdetails] von Othello, inklusive Bitboards (englisch).</ref>, [[Vier gewinnt]]<ref>[https://github.com/denkspuren/BitboardC4/blob/master/BitboardDesign.md Bitboards and Connect Four] beschreibt ausführlich eine Implementierung für [[Vier gewinnt]] (englisch).</ref> oder auch [[Tic-Tac-Toe]]<ref>Das Lehrvideo [https://www.youtube.com/watch?v=5t5jzkO0t7w Bitboards für Tic-Tac-Toe] erklärt eine Umsetzung für [[Tic-Tac-Toe]] (deutsch)</ref>. 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]]<ref>{{Literatur |Autor=[[Robert Hyatt]] |Titel=Rotated bitmaps, a new twist on an old idea |Sammelwerk=Journal of the International Computer Chess Association |Band=22 |Nummer=4 |Datum=1999-12 |Seiten=213–222 |Sprache=en |Online=https://craftychess.com/hyatt/bitmaps.html |Abruf=2023-11-15}}</ref> und die aktuelle Version 5.0 von [[GNU Chess]]<ref>Dokumentation von GNU Chess 5.0</ref>.

== 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.<ref>{{Internetquelle |autor=[[Robert Hyatt]] |url=https://craftychess.com/hyatt/hyatt.html |titel=Chess program board representations |werk=craftychess.com |sprache=en |abruf=2023-11-15 |kommentar=Vergleichender Artikel über Datenstrukturen für Schachprogramme}}</ref>

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:

{{Zitat
|Text=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.
|Sprache=en
|Autor=Robert Hyatt
|Übersetzung=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.}}

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 ([[Bauer (Schach)|Bauern]], [[Turm (Schach)|Türme]], [[Springer (Schach)|Springer]], [[Läufer (Schach)|Läufer]], [[Dame (Schach)|Dame]], [[König (Schach)|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.

{{Schachbrett-klein
| Ausrichtung=rechts
| Titel=

| Z8=rd/nd/bd/qd/kd/bd/nd/rd/
| Z7=pd/pd/pd/pd/pd/pd/pd/pd/
| Z6=--/--/--/--/--/--/--/--/
| Z5=--/--/--/--/--/--/--/--/
| Z4=--/--/--/--/--/--/--/--/
| Z3=--/--/--/--/--/--/--/--/
| Z2=pl/pl/pl/pl/pl/pl/pl/pl/
| Z1=rl/nl/bl/ql/kl/bl/nl/rl/

| Beschreibung=Schach: Ausgangsposition
}}
{| class="wikitable float-left"
| 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 <sub>2</sub>.

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.

<div style="clear:both;"></div>

=== 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 [[Bitweiser Operator|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 ====
{{Schachbrett-klein
| Ausrichtung=links
| Titel=

| Z8=--/--/--/--/--/--/--/--/
| Z7=--/--/--/--/--/--/--/--/
| Z6=--/--/xo/--/xo/--/--/--/
| Z5=--/xo/--/--/--/xo/--/--/
| Z4=--/--/--/nl/--/--/--/--/
| Z3=--/xo/--/--/--/xo/--/--/
| Z2=--/--/xo/--/xo/--/--/--/
| Z1=--/--/--/--/--/--/--/--/

| Beschreibung=Mögliche Springer-Züge vom Feld D4
}}
{| class="wikitable float-right"
| 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 64-bit-Zahlen der Index 27 (wenn 0 der erste Index ist) mit folgender Zahl belegt:

00000000 00000000 00101000 01000100 00000000 01000100 00101000 00000000 <sub>2</sub>.

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 [[Bitweiser Operator#ODER|''ODER'']]-Verknüpfung) bestimmt werden. Durch ein bitweises [[Bitweiser Operator#NICHT|''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 [[Bitweiser Operator#UND|''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 ==
<references />

[[Kategorie:Datenstruktur]]
[[Kategorie:Computerschach]]

Bitboard - Versionsgeschichte

imported>Nina: keine sinnvolle Zwischenüberschrift, siehe WP:WSIGA#INTRO