Representació del tauler (escacs)
Dins l'entorn dels escacs per ordinador els programadors han de triar una estructura de dades per a representar les posicions de les peces dels escacs. Existeixen diverses estructures de dades; el conjunt d'aquestes estructures s'anomena representació del tauler. Els programes d'escacs poden fer servir més d'una representació del tauler per raons d'eficiència. Dins la memòria de l'ordinador el tauler es sol emmagatzemar en un format anomenat "bitboard", que permet als programes d'escacs seguir els arbres de joc, tenint com a límit el nombre de Shannon.[1]
Requeriments
[modifica]Una completa descripció d'una posició d'escacs, hauria de contenir com a mínim els següents elements:
- El lloc que ocupa cada peça en el tauler
- El jugador que té el torn de moure
- L'estat de la regla dels 50 moviments
- L'estat de l'enroc de tots dos jugadors
- Si és possible que una peça pugui capturar al pas, i de quina peça es tracta.
La representació del tauler típicament no inclou la regla d'empat dels 3 moviments repetits. Per determinar aquesta regla, es necessita mantenir un historial complet del joc, i per tant, això s'emmagatzema en una estructura de dades diferent.
Tipus
[modifica]Llista de peces
[modifica]Alguns dels primers programes d'ordinador de la història havien de treballar amb molt poca memòria, per tant, allotjar les 64 caselles del tauler en memòria representava molt. Llavors, aquests programes emmagatzemaven una llista dels llocs de cadascuna de les 16 peces dels dos jugadors. En lloc de buscar en cadascuna de les 64 caselles del tauler per trobar les peces, la llista de peces donava accés instantani a la posició de les peces en cada moment.
Basat en arranjaments
[modifica]Una de les formes més simples de representar un tauler és crear un arranjament de mida 8x8 (o de forma equivalent un arranjament unidimensional de 64 elements). A cada element de la reparació correspondria la peça que conté la casella, o donat cas, si la casella està buida. Una possible codificació seria considerar 0 com buit, positiu com a peça blanca, i negatiu com a peça negra. Per exemple:[2]
| 0 | Buit |
| 1 | Peó blanc |
| 2 | Cavall blanc |
| 3 | Alfil blanc |
| 4 | Torre blanca |
| 5 | Dama blanca |
| 6 | Rei blanc |
| -1 | Peó negre |
| -2 | Cavall negre |
| -3 | Alfil negre |
| -4 | Torre negra |
| -5 | Dama negra |
| -6 | Rei negre |
Un problema en utilitzar aquesta forma és la generació de la llista de moviments. Cada moviment s'ha de comprovar per assegurar que la peça és al tauler, disminuint significativament el procés. Una solució seria usar un arranjament de 12x12, omplint les caselles no pròpies del tauler amb un valor fora del rang, diguem, un 99. Durant la generació del moviment, l'operació per determinar la peça que ocupa una determinada casella sempre ens indicarà que tal casella està fora del tauler.
Es pot obtenir una millora en la memòria amb un arranjament de 10x12, el qual proveeix la mateixa que un 12x12, sobreposant les caselles dels costats de totes les files, les quals són marcades com a «fora del tauler». Alguns programes utilitzen arranjaments de 16x16 per millorar la velocitat en la conversió de les files i columnes i també per permetre trucs especials de codificació.
Els programadors de codi màquina tenen una altra alternativa. Utilitzant 4 bits per casella, una columna sencera pot ser representada en 32 bytes, i el tauler en 8 registres (amb un addicional per la informació que falta). Amb ajuda d'una «taula de salts» (jump table) i afegint el valor de la peça a un programa comptador es pot anar directament al codi per generar moviments del tipus de peça de tal casella. Tot i que el programa és més gran que els mètodes de generació de moviments convencionals, no es necessita txeca les caselles fora del tauler, la qual cosa incrementa la velocitat de la generació de moviments.
El mètode 0x88
[modifica]El mètode 0x88 utilitza un arranjament de mida 16x8 = 128, numerat de 0 a 127. Bàsicament són 2 taulers, un al costat de l'altre. El tauler real està a l'esquerra i el tauler de la dreta representa els moviments il·legals. Quan es generen els moviments del tauler real, es pot comprovar que la casella de destinació és al tauler real utilitzant simplement l'operador AND del número de la casella amb 0x88. Un resultat diferent de zero indica que la casella està fora del tauler principal i que per tant és una casella il·legal. Això afavoreix la velocitat.
Taula de bits (Bitboard)
[modifica]Una representació comunament usada és la que empra una taula de bits (bitboard). Una taula de bits és una seqüència de 64 bits, els quals indiquen absència o presència d'algun estat sobre posicions en el tauler. Una sèrie de taules de bits per cada tipus de peça de cada jugador podria representar completament la posició del tauler.[3]
L'avantatge d'aquest tipus de representació rau en l'habilitat d'usar operacions a nivell de bits sobre les entitats de 64 bits en lloc de realitzar cicles per manipular i derivar informació sobre l'estat del tauler. Això aprofita al màxim l'ús de maquinari possible, especialment en aels exòtics processadors de 64 bits.
Codificació Huffman
[modifica]Les posicions del tauler d'escacs poden ser representades com a patrons de bits, de manera que els elements més comuns (caselles buides i peons) són emmagatzemats amb menys bits que un element menys comú.
| Casella buida | 0 |
| Peó | 10C |
| Alfil | 1100c |
| Cavall | 1101c |
| Torre | 1110c |
| Dama | 11110c |
| Rei | 11111c |
On c és el bit que representa el color de la peça (1 = BLANC, 0 = NEGRE).
Es necessiten alguns bits addicionals:
- La regla dels 50 moviments (6 bits)
- La columna de possible captura al pas (4 bits)
- El torn del jugador (1 bit)
- Els drets d'enroc (4 bits)
La codificació Huffman és més intensa en l'ús de la CPU, en comparació amb altres representacions del tauler que minimitzen els requeriments del processador i els cicles de memòria. De tota manera, la mida final de la representació fa que aquesta sigui ideal per emmagatzemar posicions a llarg termini. S'usa, per exemple, per portar un llibre d'obertures perquè en aquest cas és més important disminuir la mida que no pas minimitzar els cicles de la CPU.[4]
Referències
[modifica]- ↑ 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.
- ↑ R. Hyatt: Vergleichender Artikel über Datenstrukturen für Schachprogramme Arxivat 2016-06-24 a Wayback Machine.
- ↑ Robert Hyatt: Artikel über die in Crafty verwendeten „rotated bitboard“-Strukturen. Arxivat 2015-07-20 a Wayback Machine.
- ↑ Dokumentation von GNU Chess 5.0