Publicaciones anteriores sobre este tema: algoritmo Minimax en teoría de juegos , función de evaluación en teoría de juegos , Tic-Tac-Toe AI: encontrar el movimiento óptimo , poda alfa-beta .
Zobrist Hashing es una función hash que se usa ampliamente en juegos de mesa de 2 jugadores. Es la función hash más común utilizada en la tabla de transposición. Las tablas de transposición básicamente almacenan los valores evaluados de los estados anteriores del tablero, de modo que si se encuentran nuevamente, simplemente recuperamos el valor almacenado de la tabla de transposición. Cubriremos las tablas de transposición en un artículo posterior. En este artículo tomaremos el ejemplo del tablero de ajedrez e implementaremos una función hash para eso.
Pseudocódigo:
// A matrix with random numbers initialized once
Table[#ofBoardCells][#ofPieces]
// Returns Zobrist hash function for current conf-
// iguration of board.
function findhash(board):
hash = 0
for each cell on the board :
if cell is not empty :
piece = board[cell]
hash ^= table[cell][piece]
return hash
Explicación :
La idea detrás de Zobrist Hashing es que para un estado de tablero dado, si hay una pieza en una celda determinada, usamos el número aleatorio de esa pieza de la celda correspondiente en la tabla.
Si hay más bits en el número aleatorio, menor es la posibilidad de una colisión hash. Por lo tanto, los números de 64 bits se usan comúnmente como estándar y es muy poco probable que ocurra una colisión hash con números tan grandes. La tabla debe inicializarse una sola vez durante la ejecución del programa.
Además, la razón por la que Zobrist Hashing se usa ampliamente en los juegos de mesa es porque cuando un jugador hace un movimiento, no es necesario volver a calcular el valor hash desde cero. Debido a la naturaleza de la operación XOR, podemos simplemente usar algunas operaciones XOR para recalcular el valor hash.
Implementación:
Intentaremos encontrar un valor hash para la configuración de placa dada.
CPP
// A program to illustrate Zobrist Hashing Algorithm
#include <bits/stdc++.h>
using namespace std;
unsigned long long int ZobristTable[8][8][12];
mt19937 mt(01234567);
// Generates a Random number from 0 to 2^64-1
unsigned long long int randomInt()
{
uniform_int_distribution<unsigned long long int>
dist(0, UINT64_MAX);
return dist(mt);
}
// This function associates each piece with
// a number
int indexOf(char piece)
{
if (piece=='P')
return 0;
if (piece=='N')
return 1;
if (piece=='B')
return 2;
if (piece=='R')
return 3;
if (piece=='Q')
return 4;
if (piece=='K')
return 5;
if (piece=='p')
return 6;
if (piece=='n')
return 7;
if (piece=='b')
return 8;
if (piece=='r')
return 9;
if (piece=='q')
return 10;
if (piece=='k')
return 11;
else
return -1;
}
// Initializes the table
void initTable()
{
for (int i = 0; i<8; i++)
for (int j = 0; j<8; j++)
for (int k = 0; k<12; k++)
ZobristTable[i][j][k] = randomInt();
}
// Computes the hash value of a given board
unsigned long long int computeHash(char board[8][9])
{
unsigned long long int h = 0;
for (int i = 0; i<8; i++)
{
for (int j = 0; j<8; j++)
{
if (board[i][j]!='-')
{
int piece = indexOf(board[i][j]);
h ^= ZobristTable[i][j][piece];
}
}
}
return h;
}
// Main Function
int main()
{
// Uppercase letters are white pieces
// Lowercase letters are black pieces
char board[8][9] =
{
"---K----",
"-R----Q-",
"--------",
"-P----p-",
"-----p--",
"--------",
"p---b--q",
"----n--k"
};
initTable();
unsigned long long int hashValue = computeHash(board);
printf("The hash value is : %llu\n", hashValue);
//Move the white king to the left
char piece = board[0][3];
board[0][3] = '-';
hashValue ^= ZobristTable[0][3][indexOf(piece)];
board[0][2] = piece;
hashValue ^= ZobristTable[0][2][indexOf(piece)];
printf("The new hash value is : %llu\n", hashValue);
// Undo the white king move
piece = board[0][2];
board[0][2] = '-';
hashValue ^= ZobristTable[0][2][indexOf(piece)];
board[0][3] = piece;
hashValue ^= ZobristTable[0][3][indexOf(piece)];
printf("The old hash value is : %llu\n", hashValue);
return 0;
}
Producción :
The hash value is : 14226429382419125366 The new hash value is : 15124945578233295113 The old hash value is : 14226429382419125366
Este artículo es una contribución de Akshay L Aradhya . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA