2

我正在为 Android 制作一个 Connect 4 应用程序，现在我正在使用 minimax 算法以及叶节点的 alpha-beta 修剪和启发式评估函数。我还下令采取措施进一步最大化修剪过程。不幸的是，使用这种策略，算法在深度 7 中花费了太多时间，导致我放弃它，转而使用转置表。

现在，我已经阅读了有关转置表的信息，并对它们的工作原理有了大致的了解，但我不确定如何在代码中进行实际的实现。我不是 Java 专家，所以我需要你能给我的任何帮助。

在我的游戏中，我使用 int[42] 数组作为棋盘位置。我想过使用哈希映射并存储某种数据结构对象，其中每个对象都将包括棋盘位置（数组）和一个 int“分数”变量（实际上是由评价函数）。但是，这意味着每次我想在表中放置一个新的棋盘位置时，我都需要执行某种检查以查看该位置是否已经不存在（？？）。如果没有，只有插入到表中？

我会很高兴你们能在这个问题上给我任何技术帮助。如果需要，我可以放一些代码示例，但这是一个普遍的问题，我认为此时它们并不是真正必要的。

提前致谢。

4

1 回答 1

2

您可以使用国际象棋转置表中的一种技术：Zobrist 散列法。基本上，不是存储整个棋盘，而是计算long用作位置的哈希键的 a，并将其与相关数据一起存储。它具有能够增量更新的额外好处。在进行移动时，无需从头开始生成密钥，您可以使用单个按位 XOR 操作（非常快）更新密钥。

基本上，为每个正方形（插槽？）生成一些随机数。每边都需要一个。我假设是为了black = 0方便red = 1索引。初始化看起来像

long[][] zobrist = new long[42][2];
for (int square = 0; square < zobrist.length; square++) 
   for (int side = 0; side < zobrist[i].length; side++)
      zobrist[square][side] = RandomLong();

您将需要找到一个long为RandomLong(). 确保在查看位时它具有良好的随机性。我建议不要使用 LCG。

要从头开始计算某个位置的哈希键，您只需要将所有 zobrist 值异或。

long computeKey(int[] board) {
   long hashKey = 0;
   for (int square = 0; square < board.length; square++)
      if (hasPiece(board[square])) {
         int side = getColour(board[square]);
         hashKey ^= zobrist[square][side];
      }
}

要增量更新，只需对移动的效果进行异或运算。这是您想要采取行动并仅更新密钥的时候。

long updateKey(long oldKey, int moveSquare, int moveSide) {
   return oldKey ^ zobrist[moveSquare][moveSide];
}

要取消移动并获取旧密钥，上述功能也可以！XOR 在逻辑上的行为类似于否定，因此应用它两次可以让您恢复原始密钥。

于 2013-05-28T05:48:37.977 回答