MAGAZINE SOBRE HISTÒRIA (Iniciat com AUCA satírica el 1960.. per Manel Capdevila a classe de F.E.N.)
-VINCIT OMNIA VERITAS -
VOLTAIRE: "El temps fa justícia i posa a cadascú al seu lloc.."- "No aniràs mai a dormir..sense ampliar el teu magí"
"La història l'escriu qui guanya".. així.. "El poble que no coneix la seva història... es veurà obligat a repetir-la.."
.
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.
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
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].
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".
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.
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.
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.
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.
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.
Comentaris publicats
Afegeix-hi un comentari: