Předchozí příspěvky na toto téma: Minimax algoritmus v teorii her Funkce hodnocení v teorii her Tic-Tac-Toe AI – Nalezení optimálního pohybu Alfa-Beta prořezávání .
Zobrist Hashing je hašovací funkce, která je široce používána v deskových hrách pro 2 hráče. Je to nejběžnější hašovací funkce používaná v transpoziční tabulce. Transpoziční tabulky v podstatě ukládají vyhodnocené hodnoty předchozích stavů desky, takže pokud se s nimi znovu setkáme, jednoduše načteme uloženou hodnotu z transpoziční tabulky. Transpozičním tabulkám se budeme věnovat v pozdějším článku. V tomto článku si vezmeme příklad šachovnice a implementujeme k tomu hašovací funkci.
Pseudokód:
// 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
Vysvětlení:
Myšlenka Zobrist Hashing je taková, že pro daný stav desky, pokud je na dané buňce figurka, použijeme náhodné číslo této figurky z odpovídající buňky v tabulce.
Pokud je v náhodném čísle více bitů, tím menší je pravděpodobnost hašovací kolize. Proto se běžně používají 64bitová čísla jako standard a je vysoce nepravděpodobné, že by u takto velkých čísel došlo ke kolizi hash. Tabulku je třeba inicializovat pouze jednou během provádění programů.
Také důvod, proč je Zobrist Hashing široce používán v deskových hrách, je ten, že když hráč provede tah, není nutné přepočítávat hash hodnotu od nuly. Vzhledem k povaze operace XOR můžeme jednoduše použít několik operací XOR k přepočtu hodnoty hash.
Implementace:
Pokusíme se najít hash hodnotu pro danou konfiguraci desky.
// A program to illustrate Zobrist Hashing Algorithm #include
// A Java program to illustrate Zobrist Hashing Algorithm import java.util.*; public class GFG { public static List<List<List<Integer>>> ZobristTable = new ArrayList<>(); // mt19937 mt(01234567); public static void initialise() { for (int i = 0; i < 8; i++) { ZobristTable.add(new ArrayList<>()); for (int j = 0; j < 8; j++) { ZobristTable.get(i).add(new ArrayList<>()); for (int k = 0; k < 12; k++) { ZobristTable.get(i).get(j).add(0); } } } } // Generates a Random number from 0 to 2^64-1 public static long randomLong() { long min = 0L; long max = (long) Math.pow(2 64); Random rnd = new Random(); return rnd.nextLong() * (max - min) + min; } // This function associates each piece with a number public static 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 public static void initTable() { for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { for (int k = 0; k < 12; k++) { Random rnd = new Random(); ZobristTable.get(i).get(j).set(k (int) randomLong()); } } } } // Computes the hash value of a given board public static int computeHash(List<List<Character>> board) { int h = 0; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (board.get(i).get(j) != '-') { int piece = indexOf(board.get(i).get(j)); h ^= ZobristTable.get(i).get(j).get(piece); } } } return h; } public static void main(String[] args) { // Main Function // Uppercase letters are white pieces // Lowercase letters are black pieces List<List<Character>> board = new ArrayList<>(); board.add(new ArrayList<>(Arrays.asList('-' '-' '-' 'K' '-' '-' '-' '-'))); board.add(new ArrayList<>(Arrays.asList('-' 'R' '-' '-' '-' '-' 'Q' '-'))); board.add(new ArrayList<>(Arrays.asList('-' '-' '-' 'K' '-' '-' '-' '-'))); board.add(new ArrayList<>(Arrays.asList('-' '-' '-' '-' '-' '-' '-' '-'))); board.add(new ArrayList<>(Arrays.asList('-' 'P' '-' '-' '-' '-' 'p' '-'))); board.add(new ArrayList<>(Arrays.asList('-' '-' '-' '-' '-' 'p' '-' '-'))); board.add(new ArrayList<>(Arrays.asList('-' '-' '-' '-' '-' '-' '-' '-'))); board.add(new ArrayList<>(Arrays.asList('p' '-' '-' '-' 'b' '-' '-' 'q'))); board.add(new ArrayList<>(Arrays.asList('-' '-' '-' '-' 'n' '-' '-' 'k'))); initialise(); initTable(); int hashValue = computeHash(board); System.out.println('The hash value is : ' + hashValue); // Move the white king to the left char piece = board.get(0).get(3); board.get(0).set(3 '-'); hashValue ^= ZobristTable.get(0).get(3).get(indexOf(piece)); board.get(0).set(2 piece); hashValue ^= ZobristTable.get(0).get(2).get(indexOf(piece)); System.out.println('The new hash value is : ' + hashValue); // Undo the white king move piece = board.get(0).get(2); board.get(0).set(2 '-'); hashValue ^= ZobristTable.get(0).get(2).get(indexOf(piece)); board.get(0).set(3 piece); hashValue ^= ZobristTable.get(0).get(3).get(indexOf(piece)); System.out.println('The new hash value is : ' + hashValue); } } // This code is contributed by Vaibhav
# A program to illustrate Zobrist Hashing Algorithm # python code implementation import random # mt19937 mt(01234567); # Generates a Random number from 0 to 2^64-1 def randomInt(): min = 0 max = pow(2 64) return random.randint(min max) # This function associates each piece with # a number def indexOf(piece): if (piece=='P'): return 0 elif (piece=='N'): return 1 elif (piece=='B'): return 2 elif (piece=='R'): return 3 elif (piece=='Q'): return 4 elif (piece=='K'): return 5 elif (piece=='p'): return 6 elif (piece=='n'): return 7 elif (piece=='b'): return 8 elif (piece=='r'): return 9 elif (piece=='q'): return 10 elif (piece=='k'): return 11 else: return -1 # Initializes the table def initTable(): # 8x8x12 array ZobristTable = [[[randomInt() for k in range(12)] for j in range(8)] for i in range(8)] return ZobristTable # Computes the hash value of a given board def computeHash(board ZobristTable): h = 0 for i in range(8): for j in range(8): if (board[i][j] != '-'): piece = indexOf(board[i][j]) h ^= ZobristTable[i][j][piece] return h # Main Function # Uppercase letters are white pieces # Lowercase letters are black pieces board = [ '---K----' '-R----Q-' '--------' '-P----p-' '-----p--' '--------' 'p---b--q' '----n--k' ] ZobristTable = initTable() hashValue = computeHash(board ZobristTable) print('The hash value is : ' + str(hashValue)) #Move the white king to the left piece = board[0][3] board[0] = list(board[0]) board[0][3] = '-' board[0] = ''.join(board[0]) hashValue ^= ZobristTable[0][3][indexOf(piece)] board[0] = list(board[0]) board[0][2] = piece board[0] = ''.join(board[0]) hashValue ^= ZobristTable[0][2][indexOf(piece)] print('The new hash value is : ' + str(hashValue)) # Undo the white king move piece = board[0][2] board[0] = list(board[0]) board[0][2] = '-' board[0] = ''.join(board[0]) hashValue ^= ZobristTable[0][2][indexOf(piece)] board[0] = list(board[0]) board[0][3] = piece board[0] = ''.join(board[0]) hashValue ^= ZobristTable[0][3][indexOf(piece)] print('The old hash value is : ' + str(hashValue))
using System; using System.Collections; using System.Collections.Generic; using System.Linq; // C# program for the above approach // A program to illustrate Zobrist Hashing Algorithm // javascript code implementation class HelloWorld { public static List<List<List<int>>> ZobristTable = new List<List<List<int>>>(); // mt19937 mt(01234567); public static void initialise(){ for(int i = 0; i < 8; i++){ ZobristTable.Add(new List<List<int>>()); for(int j = 0; j < 8; j++){ ZobristTable[i].Add(new List<int>()); for(int k = 0; k < 12; k++){ ZobristTable[i][j].Add(0); } } } } // Generates a Random number from 0 to 2^64-1 public static int randomInt() { int min = 0; int max = (int)Math.Pow(2 64); Random rnd = new Random(); return rnd.Next() * (max - min) + min; } // This function associates each piece with // a number public static 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 public static void initTable() { for (int i = 0; i<8; i++){ for(int j = 0; j < 8; j++){ for(int k = 0; k < 12; k++){ Random rnd = new Random(); ZobristTable[i][j][k] = rnd.Next(); } } } } // Computes the hash value of a given board public static int computeHash(List<List<char>> board) { 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; } static void Main() { // Main Function // Uppercase letters are white pieces // Lowercase letters are black pieces List<List<char>> board = new List<List<char>>(); board.Add(new List<char>(){'-' '-' '-' 'K' '-' '-' '-' '-'}); board.Add(new List<char>(){'-' 'R' '-' '-' '-' '-' 'Q' '-'}); board.Add(new List<char>(){'-' '-' '-' 'K' '-' '-' '-' '-'}); board.Add(new List<char>(){'-' '-' '-' '-' '-' '-' '-' '-'}); board.Add(new List<char>(){'-' 'P' '-' '-' '-' '-' 'p' '-'}); board.Add(new List<char>(){'-' '-' '-' '-' '-' 'p' '-' '-' }); board.Add(new List<char>(){'-' '-' '-' '-' '-' '-' '-' '-'}); board.Add(new List<char>(){'p' '-' '-' '-' 'b' '-' '-' 'q'}); board.Add(new List<char>(){'-' '-' '-' '-' 'n' '-' '-' 'k'}); initialise(); initTable(); int hashValue = computeHash(board); Console.WriteLine('The hash value is : ' + 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)]; Console.WriteLine('The new hash value is : ' + 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)]; Console.WriteLine('The old hash value is : ' + hashValue); } } // The code is contributed by Nidhi goel.
// A program to illustrate Zobrist Hashing Algorithm // javascript code implementation let ZobristTable = new Array(8); for(let i = 0; i < 8; i++){ ZobristTable[i] = new Array(8); } for(let i = 0; i < 8; i++){ for(let j = 0; j < 8; j++){ ZobristTable[i][j] = new Array(12); } } // mt19937 mt(01234567); // Generates a Random number from 0 to 2^64-1 function randomInt() { let min = 0; let max = Math.pow(2 64); return Math.floor(Math.random() * (max - min) + min); } // This function associates each piece with // a number function indexOf(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 function initTable() { for (let i = 0; i<8; i++) for (let j = 0; j<8; j++) for (let k = 0; k<12; k++){ ZobristTable[i][j][k] = randomInt(); } } // Computes the hash value of a given board function computeHash(board) { let h = 0; for (let i = 0; i<8; i++) { for (let j = 0; j<8; j++) { if (board[i][j]!='-') { let piece = indexOf(board[i][j]); h ^= ZobristTable[i][j][piece]; } } } return h; } // Main Function // Uppercase letters are white pieces // Lowercase letters are black pieces let board = [ '---K----' '-R----Q-' '--------' '-P----p-' '-----p--' '--------' 'p---b--q' '----n--k' ]; initTable(); let hashValue = computeHash(board); console.log('The hash value is : ' + hashValue); //Move the white king to the left let piece = board[0][3]; board[0] = board[0].split(''); board[0][3] = '-'; board[0] = board[0].join(''); hashValue ^= ZobristTable[0][3][indexOf(piece)]; board[0] = board[0].split(''); board[0][2] = piece; board[0] = board[0].join(''); hashValue ^= ZobristTable[0][2][indexOf(piece)]; console.log('The new hash value is : ' + hashValue); // Undo the white king move piece = board[0][2]; board[0] = board[0].split(''); board[0][2] = '-'; board[0] = board[0].join(''); hashValue ^= ZobristTable[0][2][indexOf(piece)]; board[0][3] = piece; hashValue ^= ZobristTable[0][3][indexOf(piece)]; console.log('The old hash value is : ' + hashValue); // The code is contributed by Nidhi goel.
výstup:
The hash value is : 14226429382419125366 The new hash value is : 15124945578233295113 The old hash value is : 14226429382419125366