28-02-2022  (236 lectures) Categoria: Articles

Bitboard

.

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:

"Aquesta ha estat probablement la raó principal per la qual els mapes de bits no s'han utilitzat àmpliament; són diferents i triguen un temps a "enfonsar-se" fins al punt que es tornen fàcils d'utilitzar. Especularia que em va costar aproximadament un any superar la gimnàstica mental de dissenyar un algoritme utilitzant idees de representació offset i després treballar com modificar la idea per adaptar-se a l'enfocament de mapa de bits".

"Aquesta és probablement la raó principal per la qual els bitboards no es van utilitzar àmpliament; són diferents, i es necessita un temps perquè això "s'enfonsi" fins al punt que són fàcils d'utilitzar. Suposo que vaig trigar aproximadament un any a aprendre a evitar el desviament mental de dissenyar primer un algoritme que funcioni amb índexs de camp i, a continuació, esbrinar com aplicar la idea a l'enfocament de Bitboard".

Robert Hyatt

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.

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

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 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é

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




versió per imprimir

Comentaris publicats

    Afegeix-hi un comentari:

    Nom a mostrar:
    E-mail:
    Genera una nova imatge
    Introdu√Įu el codi de seguretat
    Accepto les condicions d'ús següents:

    Per a participar en els comentaris l'usuari es compromet a complir i acceptar les següents normes bàsiques de conducta:

    • Respectar les opinions de la resta dels participants al fòrum, tot i no compartir-les necessàriament.
    • Abstenir-se d'insultar o utilitzar un llenguatge ofensiu, racista, violent o xenòfob, i no tenir cap conducta contrària a la legislació vigent i a l'ordre públic.
    • No enviar cap contingut amb copyright sense el permís del propietari. Si es considera oportú facilitar continguts d'internet amb copyright, cal escriure la URL completa perquè els altres usuaris puguin enllaçar-hi i descarregar-se els continguts des de la pàgina propietària.
    • Publicitat: No es permet enviar continguts promocionals i/o publicitaris.