将玩家转入 Zobrist 哈希

Question

我目前正在中国跳棋 minimax 算法中实现换位 table。在中国西洋跳棋中，没有棋子被捕获，棋盘在功能上有 81 格。玩家轮流在棋盘上移动棋子。

该过程的一部分涉及为棋盘状态创建哈希。到目前为止，我已经有了一个有效的方法，可以为每个板状态创建一个（希望如此）唯一的哈希值：

 myHash = 0;
 //randoms[81][3] is an array filled completely with pseudorandom values
 for (int x = 0; x < 81; x++) {
      myHash ^= randoms[x][board[x]]; 
      //board[x] is the piece at space x (1=player1 piece, 2=player2 piece, 0=empty)
 }

更重要的是，我在 applyMove 函数（和 undoMove 函数）中逐步执行此操作：

applyMove(int to, int from) {

   //Undo the 'from' piece in the hash
   myHash ^= randoms[from][board[from]];
   // Apply the move
   std::swap(board[from], board[to]);
   //Add the 'to' piece to the hash
   myHash ^= randoms[to][board[to]];

   // Update whose turn it is
   swapTurn();
 }

这是因为 XOR 函数的可逆性属性。

我现在遇到的问题是，散列函数不存储轮到谁。也就是说，您可以有两个相同的游戏板，但它们在 minimax 算法中会 return 不同的值，因为一个试图最大化分数，另一个试图最小化它。

基本上，我的问题是：如何将玩家的回合存储在递增生成的哈希函数中，同时保持完美（最好是廉价地）反转它的能力？假设玩家的回合是整数而不是布尔值，因为游戏最终将有 6 名玩家而不是两名玩家。

Answer 1

您可以使用 turns[6] 数组填充伪随机值：

unsigned n = 6;  // number of players;

myHash ^= turns[active_player];           // 'undo' the old active player
active_player = (active_player + 1) % n;  // new active player's index
myHash ^= turns[active_player];           // 'add' new active player

这类似于棋子位置增量更新并且适用于n ∈ [2, 6].

作为旁注...

通常 Zobrist 散列是通过扫描碎片的位置来完成的，不包括 空方块。空白方块的位置未明确散列。

因此您可以使用更小的（对缓存更友好的）数组。类似于：

std::uint64_t randoms[81][2];  // two players

for (unsigned x(0); x < 81; ++x)
  if (board[x])
    myHash ^= randoms[x][board[x]];

Answer 2

对于它的价值，您可以将转向状态存储为散列开头的一点...

inline bool GetTurn(int hash){
  return (bool)(hash & 1);
}

并且数组中的 Zobrist 散列键的最低有效位都为 0，例如。 [[0x2348dec2, 0x93857e34, ....] ...]

将玩家转入 Zobrist 哈希

Storing player turn in Zobrist hash

c++

algorithm

hash

hash-function

game-ai