如何实现连接4的换位表？

Question

我正在用python制作一个连接4 AI，并且我正在使用带有迭代深化和alpha beta修剪的minimax。对于更深的深度，它仍然很慢，所以我想实现一个换位表。阅读后，我想我得到了大致的想法，但我无法完全使其工作。这是我代码的一部分：（最小最大值的最大化部分）：

    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散列方法散列板，我使用有序的判决将散列板添加到。在这个哈希键中，我添加了板的值和该板的最佳移动。不幸的是，这似乎让算法选择了糟糕的动作（它以前有效），有人知道你应该把板状态放在缓存的哪里，以及你应该从缓存的哪里获取它们吗？

Answer 1

关于您的方法的几点：

> < li>

如果你希望事情变得更快，用C或C编写高效的代码将比python快得多。我已经看到，通过从python转向良好的C/C实现，这类搜索代码的性能提高了10-100倍。无论哪种方式，您都应该尝试编写避免在搜索期间分配内存的代码，因为这是非常昂贵的。也就是说，与添加转置表相比，更高效的编码会带来更好的回报。

在游戏树搜索中对换位表使用 Zobrist 哈希时，通常不会显式存储状态。您只检查哈希值是否相等。虽然出错的可能性很小，但它需要的内存要少得多，仅存储哈希值，并且对于 64 位哈希值，对于您正在执行的搜索类型，发生冲突的可能性可能微乎其微。（导致错误的几率甚至更低。

当您在转置表中存储值时，您还需要存储搜索期间使用的alpha和beta边界。当您在节点搜索中期返回一个值时，它要么是真值的上限（因为值=beta），要么是真值的下限（因为值=alpha），要么是节点的实际值（alpha