Bitboard

Un bitboard (mapa de bits especial) és una estructura de dades que permet representar una situació de joc (posició) dins d'una partida jugada sobre un tauler, que s'utilitza especialment en els programes d'ordinador que simulen jocs de tauler, en particular per poder seguir els arbres de joc en els programes d'escacs, tenint com a límit el nombre de Shannon.^[1]

Visió general

La idea bàsica de l'estructura del bitboard és que la pregunta de si una determinada peça està present en una posició de joc determinada es pot respondre amb sí (1) o amb no (0). A causa d'això, l'assignació d'un tauler de joc de mida finita es pot representar com una seqüència de números binaris individuals, cadascun dels quals pot assumir el valor 1 o 0.

Les xifres binàries (" bits ") són la base de la majoria dels sistemes informàtics actuals. Si la informació es pot representar com una seqüència de bits que s'adapten a una paraula de la màquina utilitzada, llavors es pot processar de manera molt eficient. En particular, els factors que tenen un impacte en l'eficiència de les estructures de bitboard són:

• la mida del bitboard: el millor és tenir aquesta mida fixa i més petita o igual a la mida de la paraula de l'ordinador;
• el nombre de peces diferents, ja que una paraula només pot descriure l'assignació d'un sol tipus de peça.

Bàsicament, les estructures de bitboard són adequades per a diversos jocs de taula. Per exemple, hi ha implementacions de bitboards per a jocs com Dames,^[2] Othello,^[3] Quatre en ratlla ^[4] o Tres en ratlla.^[5] Els bitboards, però, han guanyat una importància especial dins l'entorn dels escacs per ordinador. Un tauler d'escacs consta de 8 × 8 = 64 quadres, de manera que una paraula d'un bitboard associat té 64 bits de longitud. Aquesta mida es pot processar directament com una paraula de dades mitjançant sistemes informàtics moderns, cosa que permet un gran avantatge de velocitat. Alguns exemples de programes d'escacs per ordinador que utilitzen bitboards són Crafty ^[6] i la versió actual 5.0 de GNU Chess.^[7]

Avantatges i inconvenients

El principal avantatge de les estructures dels bitboards rau en la seva eficiència potencialment molt alta, tant en termes d’espai de memòria com, sobretot, en termes de velocitat del programa. Una posició completa d'escacs pot ser codificada en una paraula de 64 bits, o menys eficientment, en dues de 32 bits. Moltes operacions amb els bitboards representats d'aquesta manera es poden dur a terme mitjançant unes poques instruccions del processador.^[8]

El principal inconvenient dels bitboards és que són "diferents" comparats amb els tipus de representació més antics i més estesos. Robert Hyatt, el desenvolupador del conegut programari d'escacs Crafty, escriu sobre les seves primeres experiències amb 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

«Probablement aquesta ha estat la raó principal perquè els mapes de bits no s'han utilitzat àmpliament; són diferents i es triga un temps en poder "arribar al fons" fins al punt que siguin fàcils d'utilitzar. No especularia si dic que vaig trigar aproximadament un any abans de poder superar la gimnàstica mental de dissenyar un algorisme amb idees de representació desplaçada i després esbrinar com modificar la idea per adaptar-la a l'enfocament del mapa de bits. » —Robert Hyatt

Atès que ara hi ha diverses implementacions de bitboards de codi obert, és probable que actualment, aquest argument en contra dels bitboards només tingui un feble pes i la seva importància continuï disminuint.

Exemple d'aplicació: Escacs per ordinador

Com ja s'ha esmentat, en el cas d'escacs una paraula en un bitboard és exactament de 64 bits a causa de la mida del tauler d'escacs. Com a característica especial, hi ha 12 tipus diferents de peces (peons, cavalls, rei, torres, alfils, reina, sis però cadascun d'ells de color blanc i de color negre). Per aquest motiu, es necessiten almenys quatre paraules de 16 bits per representar completament una posició. Normalment, però, s’utilitzen moltes més dades per poder processar la informació amb més facilitat, és a dir, la informació redundant també es guarda explícitament.

El programari Crafty esmentat al principi, per exemple, guarda les posicions dels 12 tipus de peces a part de les posicions de totes les peces blanques i negres amb conjunt, així com les versions girades del tauler de joc per a una millor optimització. Una estructura de dades completa que descrigui completament l'estat actual del joc també ha de contenir altres tipus d'informació per exemple: oportunitats d'enroc, captura "en passant", la regla de 50 moviments i altres possibles regles especials.

posició inicial

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

La posició inicial per exemple, (vegeu el diagrama) genera per als peons blancs un bitboard de posicions amb el següent patró de bits dins d'una paraula de 64 bits (cal tenir en compte que l'ordre creixent dels bits dins la paraula, va de dreta a esquerra):

00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000 ₂ .

La forma en què es "numera", és a dir, quin quadre del tauler d'escacs està assignat a quin índex (posició de bit dins la paraula), és en última instància opcional. En aquest exemple i en el següent, es numera línia a línia començant pl quadre A1, de manera que el bit 0 pertany a A1, el bit 1 a A2, i així successivament fins al bit 63 que pertany a H8. Com ja s'ha esmentat, alguns programes d'escacs gestionen les estructures de bitboard amb diferents maneres de numerar (per files o columnes, o fins i tot en diagonal), ja que això els permet realitzar determinades operacions de manera més eficient.

Càlcul dels moviments possibles

Un problema central en la implementació d’un programa d’escacs és el càlcul dels possibles moviments cap a posicions de destí des d’una posició determinada. Utilitzant estructures de bitboards, es fan operacions lògiques bit a bit entre el diferents mapes de bits. Cal distingir entre dos tipus de peces: en el cas de les "peces de salt” com els peons, cavalls i rei, només cal mirar si el quadre de destí està ocupat i de quin color és. En el cas de peces "lliscants" com ara torres, alfils i reina, les possibilitats de moviment són més complexes, ja que hi ha peces que poden bloquejar determinades posicions de destí sense ocupar-les físicament.

Peons, cavalls, rei (peces de salt)

Possibles salts de cavall des de 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

Amb aquests tipus de peces només cal mirar si hi ha una peça del propi color a l'espai objectiu, si n'hi ha una de l'altre color, es pot capturar. De fet, els peons tornen a ser un cas especial, ja que es mouen de manera diferent segons si capturen o no una peça contrària. Això dit, aquestes diferències de moviment no es discutiran en aquest apartat.

Com a exemple, considerem un cavall a l'espai D4. Els possibles quadres objectiu es poden veure al dibuix. bàsicament la qüestió de si el cavall es pot moure a un determinada posició de destí torna a ser una pregunta que s'ha de respondre amb sí o no, aquesta resposta es pot codificar com un bitboard o "taula d'atac" que es pot calcular i guardar-la per a cada quadre de A1 a H8.

A l'exemple escollit, el quadre D4 és el 28è quadre comptat línia per línia des de A1 cap amunt, de manera que en una llista de números de 64 bits, al bit 27 (si el primer bit és el bit 0) se li assignaria el número següent (cal tenir en compte que l'ordre creixent dels bits dins la paraula, va de dreta a esquerra):

00000000 00000000 00101000 01000100 00000000 01000100 00101000 00000000 ₂ .

La condició lògica que s’ha de complir perquè un cavall es pugui traslladar a una posició determinada és que no hi ha de contenir cap peça del seu propi color. en el bitboard complementari que s’acaba de crear, el bit que compleix aquesta condició es posa a "1" per a cada quadre. El resultat desitjat s'obté finalment mitjançant una operació AND bit a bit amb el "bitboard d'atac" del cavall pre-calculat.

Amb lleus modificacions, es pot utilitzar el mateix algorisme per calcular els moviments dels peons i del rei.

Torres, peons, reina (peces lliscants)

Aquestes peces es mouen fonamentalment de manera diferent que els tres tipus de peça esmentats anteriorment. En el cas d’aquestes peces “lliscants”, a part de veure si la posició de destí està ocupada, cal mirar si està bloquejada, ja sigui per peces pròpies o del color contrari. La reina es pot interpretar com una combinació de torre i alfil, fet que pot representar una simplificació en el moment de l'elecció exacta de les estructures de dades.

Bitboards a altres jocs

Molts altres jocs, a part dels escacs, es beneficien dels bitboards:

• Al Connect Four, permeten proves molt eficients per a quatre discos consecutius, amb només dues operacions SHIFT + AND per direcció.
• Al joc de la vida de Conway, són una possible alternativa a les matrius.
• Al Reversi/Othello (vegeu l'article de Reversi).

Referències

1. Jones, M.T.. Artificial Intelligence: A Systems Approach: A Systems Approach (en danès). Jones & Bartlett Learning, 2008, p. 110. ISBN 978-1-4496-3115-4. 
2. Darstellung von Bitboard-Strukturen im Dame-Spiel (englisch)
3. Diskussion verschiedener Implementierungsdetails von Othello, inklusive Bitboards (englisch).
4. Bitboards and Connect Four beschreibt ausführlich eine Implementierung für Vier gewinnt (englisch).
5. Das Lehrvideo Bitboards für Tic-Tac-Toe erklärt eine Umsetzung für Tic-Tac-Toe (deutsch)
6. Robert Hyatt: Artikel über die in Crafty verwendeten „rotated bitboard“-Strukturen. Arxivat 2015-07-20 a Wayback Machine.
7. Dokumentation von GNU Chess 5.0
8. R. Hyatt: Vergleichender Artikel über Datenstrukturen für Schachprogramme Arxivat 2016-06-24 a Wayback Machine.

Bibliografia

• «How DarkThought Plays Chess (Preprint of an article by Ernst A. Heinz in: ICCA Journal, Vol. 20(3), pp. 166-176, Sept. 1997)». People, 02-03-1998. [Consulta: 1r març 2022].

Enllaços externs

• «Bitboards in Board Word Games». Helps your game in Wordfeud, Words with friends and Scrabble. [Consulta: 1r març 2022].