Un tauler de bits (tauler de mapa de bits) és una estructura de dades per representar una situació de joc (posició) que s'utilitza sovint en programes d'ordinador per a jocs de taula, especialment programes d'escacs.

Visió general

La idea bàsica de l'estructura del tauler de bits és que la qüestió de si hi ha una certa figura en un determinat camp de joc es pot respondre amb sí o no. Com a resultat, l'assignació d'un pla de joc/tauler de mida finita es pot representar com una seqüència de nombres duals individuals, cadascun dels quals pot assumir el valor 0 o 1.

Els nombres duals ("bits") formen la base de la majoria dels sistemes informàtics actuals. Si la informació es pot representar com una seqüència de bits que encaixen en una paraula de dades de la màquina utilitzada, pot ser molt eficient processar-la. La influència en l'eficiència de les estructures de bitboard tenen en particular

• la mida del tauler de joc: preferiblement aquesta mida és fixa i inferior o igual a la mida de la paraula de l'ordinador;
• el nombre de figures diferents, ja que una sola paraula només pot descriure l'assignació amb un sol tipus de figura.

Bàsicament, les estructures de bitboard són adequades per a diversos jocs de taula. Per exemple, també hi ha implementacions de bitboard per a jocs com Dame^[1], Othello^[2], Four Wins^[3] o Tic-Tac-Toe^[4]. No obstant això, els taulers de bits han guanyat especial importància en el camp dels escacs per ordinador. Un tauler d'escacs consta de 8×8=64 caselles, de manera que una paraula d'un tauler de bits associat fa 64 bits de llarg. Aquesta mida pot ser processada directament com una paraula de dades pels sistemes informàtics moderns, el que promet un gran avantatge de velocitat. Exemples de programes d'escacs per ordinador que utilitzen bitboards són Crafty^[5] i la versió actual 5.0 de GNU Chess^[6].

Avantatges i desavantatges

El principal avantatge de les estructures de Bitboard rau en l'eficiència potencialment molt alta, tant en termes d'espai d'emmagatzematge com, sobretot, en termes de velocitat del programa. Una posició completa dels escacs es pot codificar e.B. bé en 64 bytes, en principi fins i tot en 32 bytes. Moltes operacions sobre les posicions representades d'aquesta manera es poden realitzar mitjançant algunes instruccions de processador. ^[7]

El principal desavantatge dels taulers de bits rau en la seva "l'altra" en comparació amb els tipus de visualització 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:

Atès que ara existeixen tota una sèrie d'implementacions de bitboard de codi obert, aquest argument contra Bitboards és probable que pesi només feblement i continuï disminuint en importància.

Exemple d'aplicació: Escacs per ordinador

Com ja s'ha esmentat, una paraula d'un tauler de bitlles en el cas dels escacs és exactament de 64 bits de llarg a causa de la mida del tauler d'escacs. Com a característica especial, hi ha 12 tipus diferents de figures (peons, torres, jerseis, corredors, dama, rei, cada blanc i negre). Per aquest motiu, necessiteu almenys quatre paraules per representar completament una posició. En la majoria dels casos, però, s'utilitza molt més per facilitar el tractament de la informació, és a dir, també es mostra explícitament la informació redundant.

El programari astut esmentat al principi, per exemple, emmagatzema les posicions de totes les figures blanques o negres, és a dir, a més de les posicions dels 12 tipus de figures preses en conjunt, així com versions girades del tauler de joc per a més optimitzacions. Una estructura de dades completa que descrigui completament l'estat actual del joc també ha de contenir informació sobre l'estat e.B de les possibilitats de Rochade, els moviments "en passant", la regla de 50 moviments i, si cal, altres regles especials.

Plantilla d'error:Tauler d'escacs: La integració amb la sintaxi antiga ja no és possible!
L'ajuda per canviar a la nova sintaxi es pot trobar a Template:Chessboard/Convert.

La posició inicial (vegeu el diagrama) condueix e.B. per als agricultors blancs a la següent estructura del tauler de bits (patró de bits d'una paraula):

00000000000000000000 11111111 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

De quina manera es "compta", és a dir, quin camp del tauler d'escacs s'assigna a quin índex (posició de bits en la paraula), és en última instància opcional. En aquest exemple i en el següent, començant pel camp A1, es compta línia per línia, de manera que A1 inclou el bit 0, A2 inclou el bit 1, i així successivament fins al camp H8 i el bit 63. Com ja s'ha esmentat, alguns programes d'escacs fins i tot gestionen estructures de bitrboard en diferents mètodes de recompte (fila per columna, o fins i tot en diagonal) al mateix temps, ja que això fa que certes operacions siguin més eficients.

Càlcul del tren

Un problema central en la implementació d'un programa d'escacs és el càlcul dels possibles moviments de seguiment des d'una posició donada. Quan s'utilitzen estructures de bitboard, això es fa mitjançant operacions lògiques a l'assignació del pla de joc. Aquí, s'han de distingir dos tipus de figures: en el cas de les figures "saltant" com peons, saltadors i reis, només l'ocupació del camp objectiu és decisiva. Amb les figures "planants" com torres, corredors i dames, la possibilitat de moure's és més complexa, ja que les figures poden bloquejar certs camps de destinació sense ocupar-los ells mateixos.

Agricultor, Springer, Rei

Plantilla d'error:Tauler d'escacs: La integració amb la sintaxi antiga ja no és possible!
L'ajuda per canviar a la nova sintaxi es pot trobar a Template:Chessboard/Convert.

Amb aquestes xifres, només depèn de si es col·loca una figura del vostre propi color al camp de destinació. De fet, els camperols tornen a ser un cas especial, ja que tiren de manera diferent en funció de si superen o no una figura contrària. Però això no es discutirà aquí.

Considereu com a exemple un saltador al camp D4. Els possibles camps de destinació es poden veure al diagrama. La pregunta de si el saltador pot bàsicament recórrer a un determinat camp de destinació és de nou una pregunta a respondre amb sí o no, la resposta a la qual es pot codificar com un tauler de bits. Per a cada camp des d'A1 fins a H8, aquest "tauler d'atac" es pot calcular i emmagatzemar amb antelació.

En l'exemple seleccionat, el camp D4 és el 28è camp comptat línia per línia des d'A1, de manera que en una llista de números de 64 bits, a l'índex 27 (si 0 és el primer índex) se li assignaria el següent número:

00000000000000000000000000000000 01000100 0000000000000000000000000000000000000000000000000000000000000 01000100 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Si aquests totals de 64 taulers de bits possibles (per al saltador) ja estan calculats a l'inici del programa, l'accés posterior és, per tant, molt eficient com una simple operació d'índex. Per decidir quins camps pot recórrer el saltador en el present cas, encara es requereix informació sobre l'assignació de planificació actual en el seu propi color. Això està directament disponible o es pot determinar a partir de les 6 assignacions dels tipus de figures individuals (mitjançant l'enllaç bit a bit o). Per un bit a bit NO aplicat a aquesta assignació, es determinen els camps, que no estan ocupats per figures del seu propi color.

La condició lògica que s'ha de complir perquè un saltador es mogui a un camp determinat és que cap figura del propi color pot estar allà. En el tauler de bits del complement que s'acaba de descriure, el bit per al qual es compleix aquesta condició s'estableix exactament per a cada camp. El resultat desitjat s'obté finalment per bit a bit i enllaçant amb el "tauler d'atac" precalculat del saltador.

Amb lleugers ajustos, es pot utilitzar el mateix procediment per calcular els moviments per als peons i per al rei.

Torres, Corredors, Senyora

Aquestes xifres es mouen fonamentalment de manera diferent de les tres espècies esmentades anteriorment. Amb aquestes figures "lliscants", a més de l'assignació del camp de destinació, depèn de si la forma en què hi ha bloquejat, ja sigui per figures pròpies o el color de l'oponent. La dama es pot interpretar com una combinació de torre i corredor, que pot ser una simplificació depenent de l'elecció exacta de les estructures de dades.

Vegeu també

• Escacs per ordinador

Referències

1. ↑ Representació de les estructures del tauler de bits en el joc de dames
2. ↑ Discussió de diversos detalls d'implementació d'Otel·lo, inclosos els taulers de bits.
3. ↑ Bitboards and Connect Four descriu en detall una implementació per a Four Wins.
4. ↑ El vídeo instructiu Bitboards for Tic-Tac-Toe explica una implementació per a Tic-Tac-Toe (alemany)
5. ↑ Robert Hyatt: Article sobre les estructures de "bitboard girat" utilitzades a Crafty.
6. ↑ Documentació de GNU Chess 5.0
7. ↑ R. Hyatt: Article comparatiu sobre estructures de dades per a programes d'escacs