博弈论中的极小极大算法|集5（Zobrist Hashing）-yiteyi-C++库

之前关于这个话题的帖子：博弈论中的极小极大算法 , 博弈论中的评价函数 , Tic Tac Toe AI–寻找最佳移动 , α-β修剪 . Zobrist散列是一个散列函数，广泛用于2人棋盘游戏。它是转置表中最常用的哈希函数。换位表基本上存储之前电路板状态的评估值，因此如果再次遇到它们，我们只需从换位表中检索存储的值。我们将在后面的文章中介绍转置表。在本文中，我们将以国际象棋棋盘为例，实现一个哈希函数。

null

伪代码：

// A matrix with random numbers initialized onceTable[#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

说明：

Zobrist散列背后的思想是，对于给定的电路板状态，如果给定单元上有一个片段，我们使用表中相应单元中该片段的随机数。如果随机数中有更多位，则哈希冲突的可能性较小。因此，64位数字通常被用作标准，并且对于如此大的数字，发生哈希冲突的可能性非常小。在程序执行期间，该表只需初始化一次。 Zobrist散列在棋盘游戏中被广泛使用的另一个原因是，当玩家移动时，不需要从头开始重新计算散列值。由于XOR操作的性质，我们可以简单地使用几个XOR操作来重新计算哈希值。

实施：

我们将尝试为给定的电路板配置找到一个哈希值。

CPP

                         // A program to illustrate Zobeist 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", 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", 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", hashValue);                       
           
                                                 return                                     0;                       
                         }                       

输出：

The hash value is     : 14226429382419125366The new hash value is : 15124945578233295113The old hash value is : 14226429382419125366

本文由 阿克谢阿拉迪亚酒店 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章