Minimax algoritmus v teorii her | Sada 5 (Zobrist hašování)
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 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 & lt ; unsigned long long int & gt ; 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 & lt ; 8 ; i ++ ) for ( int j = 0 ; j & lt ; 8 ; j ++ ) for ( int k = 0 ; k & lt ; 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 & lt ; 8 ; i ++ ) { for ( int j = 0 ; j & lt ; 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 ] = { & quot ; --- K ----& quot ; & quot ; - R ---- Q -& quot ; & quot ; --------& quot ; & quot ; - P ---- p -& quot ; & quot ; ----- p --& quot ; & quot ; --------& quot ; & quot ; p --- b -- q & quot ; & quot ; ---- n -- k & quot ; }; initTable (); unsigned long long int hashValue = computeHash ( board ); printf ( & quot ; The hash value is : % llu n & quot ; 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 ( & quot ; The new hash value is : % llu n & quot ; 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 ( & quot ; The old hash value is : % llu n & quot ; hashValue ); return 0 ; }
Java // 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 = 0 L ; 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
Python3 # 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 ))
C# 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.
JavaScript // 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
