Minimax-Algorithmus in der Spieltheorie | Set 5 (Zobrist-Hashing)
Frühere Beiträge zu diesem Thema: Minimax-Algorithmus in der Spieltheorie Bewertungsfunktion in der Spieltheorie Tic-Tac-Toe AI – Den optimalen Zug finden Alpha-Beta-Beschneidung .
Zobrist Hashing ist eine Hashing-Funktion, die häufig in Brettspielen für 2 Spieler verwendet wird. Dies ist die am häufigsten in Transpositionstabellen verwendete Hashing-Funktion. Transpositionstabellen speichern grundsätzlich die ausgewerteten Werte früherer Platinenzustände, sodass wir bei erneutem Auftreten einfach den gespeicherten Wert aus der Transpositionstabelle abrufen. Wir werden Transpositionstabellen in einem späteren Artikel behandeln. In diesem Artikel nehmen wir das Beispiel eines Schachbretts und implementieren dafür eine Hashing-Funktion.
Pseudocode:
// 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
Erläuterung :
Die Idee hinter Zobrist Hashing besteht darin, dass wir für einen bestimmten Spielbrettstatus, wenn sich auf einer bestimmten Zelle eine Figur befindet, die Zufallszahl dieser Figur aus der entsprechenden Zelle in der Tabelle verwenden.
Wenn die Zufallszahl mehr Bits enthält, ist die Wahrscheinlichkeit einer Hash-Kollision geringer. Daher werden üblicherweise 64-Bit-Zahlen als Standard verwendet und es ist höchst unwahrscheinlich, dass es bei so großen Zahlen zu einer Hash-Kollision kommt. Die Tabelle muss während der Programmausführung nur einmal initialisiert werden.
Auch der Grund, warum Zobrist Hashing in Brettspielen weit verbreitet ist, liegt darin, dass es nicht notwendig ist, den Hash-Wert von Grund auf neu zu berechnen, wenn ein Spieler einen Zug macht. Aufgrund der Art der XOR-Operation können wir einfach nur wenige XOR-Operationen verwenden, um den Hash-Wert neu zu berechnen.
Umsetzung:
Wir werden versuchen, einen Hashwert für die gegebene Platinenkonfiguration zu finden.
// 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.
Ausgabe :
The hash value is : 14226429382419125366 The new hash value is : 15124945578233295113 The old hash value is : 14226429382419125366
