如何实现connect 4的转置表？

Question

我在用python做一个connect 4的AI，我用minimax与迭代深化和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哈希法对板子进行哈希处理 我用一个有序的dict来添加哈希板的内容 在这个hashkey中，我添加了棋盘的值和该棋盘的bestMove。不幸的是，这似乎使算法选择了不好的棋子（以前是可以的），有人知道你应该把板子的状态放在缓存中的哪里，以及你应该从缓存中获取它们？

Answer 1

关于你的方法有几点。

1. 如果你想让事情变得更快，用C或C++写高效的代码会比python快得多。我见过这种搜索代码通过从python转到好的CC++实现，性能提高了10-100倍。无论哪种方式，你都应该尽量写出避免在搜索过程中分配内存的代码，因为这是非常昂贵的。也就是说，你可以从更高效的编码中看到比增加转置表更好的回报。

2. 当在游戏树搜索中使用Zobrist哈希进行转置表时，你通常不会显式存储状态。你只检查哈希值是否相等。虽然出错的几率很小，但只存储哈希值所需要的内存要少得多，而且对于64位哈希值来说，碰撞的几率对于你正在进行的搜索类型来说可能是微乎其微的。(产生错误的几率更低)。

3. 当你在转置表中存储值时，你还需要存储搜索过程中使用的α和β边界。当你在搜索中间的一个节点处得到一个值时，它要么是真值的上界（因为value = beta），要么是真值的下界（因为value = alpha），要么是节点的实际值（alpha < value < beta）。你需要把这些存储在你的转置表中。然后，当你想重新使用该值时，你必须检查是否可以使用给定你当前alpha和beta边界的值。(你可以在转置表中找到值后实际进行搜索来验证这一点，看看你从搜索中得到的值是否与表中的值相同)。