如何为四连棋实现置换表？

Question

我正在用Python制作一个连四人工智能，并且我正在使用迭代加深和Alpha-Beta剪枝的最小化最大算法。在更深的深度上，它仍然很慢，所以我想实现一个置换表。经过阅读，我认为我明白了一般的想法，但我还没有能够使它完全运作。这是我的代码的一部分（最小化最大算法中的最大化部分）：

    if(isMaximizing):
    maxEval = -99999999999
    bestMove = None
    # cache.get(hash(board)) Here's where i'd check to see if the hash is already in the table 
    # if so i searched for the best move that was given to that board before.

    # loop through possible moves
    for move in [3,2,4,1,5,0,6]:
        if moves[move] > -1:
            # check if time limit has been reached for iterative deepening
            if startTime - time.time() <= -10:
                timeout = True
                return (maxEval, bestMove, timeout)

            if timeout == False:
                board = makeMove((moves[move],move), True, board) # make the move 
                eval = minimax(depth - 1, board, False, alpha, beta, cache, zobTable, startTime, timeout)[0]

                if eval > maxEval:
                    maxEval = eval
                    bestMove = (moves[move]+1,move)

                board[moves[move] + 1][move] = '_'  # undo the move on the board
                moves[move] = moves[move] + 1 # undo the move in the list of legal moves

                alpha = max(alpha, maxEval)
                if alpha >= beta:
                    break
                # cache.set(hash(board), (eval, value)) Here's where i would set the value and bestmove for the current boardstate
    return (maxEval, bestMove, timeout)

我现在正在使用Zobrist哈希方法来进行棋盘的哈希，并使用有序字典将哈希棋盘添加到其中。对于这个哈希键，我已经添加了棋盘值和该棋盘的最佳移动值。不幸的是，这似乎导致算法选择了不好的移动（之前它有用）。请问有人知道应该将棋盘状态放在缓存中的哪里，以及从缓存中获取它们的位置吗？

- Tr33hugger

Answer 1

您的方法有几点需要注意：

1. 如果您想让程序快速运行，用C或C++编写高效代码比使用Python要快得多。我曾经通过从Python转向优秀的C/C++实现，在这种搜索代码中看到了10-100倍的性能提升。无论哪种方式，您都应该尽量编写避免在搜索过程中分配内存的代码，因为这很昂贵。也就是说，您可以通过更高效的编码获得更好的回报，而不是添加置换表。

2. 在游戏树搜索中使用Zobrist哈希算法来构建置换表时，通常不会明确地存储状态。您只需检查哈希值是否相等即可。虽然存在一定的误差可能性，但仅存储哈希值所需的内存要少得多，并且对于您正在进行的搜索类型，64位哈希的冲突机率可能非常小。（产生错误的机率甚至更低。）

3. 当您将值存储在置换表中时，还需要存储在搜索过程中使用的alpha和beta边界。当您在搜索过程中在一个节点处获得一个值时，它可能是真实值的上限（因为value = beta），真实值的下限（因为value = alpha），或者是节点的实际值（alpha < value < beta）。您需要将这些信息存储在置换表中。然后，在您想要重新使用该值时，您必须检查是否可以在当前的alpha和beta边界下使用该值。（您可以通过在找到置换表中的值后执行搜索来验证此操作，以查看是否从搜索中获得了与表中相同的值。）

- Nathan S.

---

+1，但我不同意第一点。我建议先用Python使其更高效，然后再用更好的语言重写整个程序。 - 6502