如何为connect 4实现换位表？

Question

我正在用python制作一个connect 4 AI，我正在使用minimax和迭代深化以及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散列方法对电路板进行散列，并且我正在使用有序dict将散列的电路板添加到。在这个hashkey中，我添加了该板的值和该板的最佳移动。不幸的是，这似乎使算法选择了错误的移动（它以前工作过），有人知道应该将BoardState放在缓存中的什么位置，以及应该从缓存中获取它们吗

Answer 1

关于你的方法有几点：

<> >如果你希望事情快速，写C或C++中的高效代码要比Python快得多。我已经看到这种搜索代码的性能提高了10-100倍，从python转到了一个好的C/C++实现。无论哪种方式，您都应该尝试编写代码，避免在搜索过程中分配内存，因为这非常昂贵。也就是说，与添加换位表相比，编码效率更高，可以获得更好的回报

1. 在游戏树搜索中对转置表使用Zobrist哈希时，通常不显式存储状态。您只需检查散列是否相等。虽然出错的可能性很小，但只存储哈希所需的内存要少得多，而使用64位哈希，对于正在执行的搜索类型而言，冲突的可能性可能非常小。（产生错误的可能性更低。）

2. 在转置表中存储值时，还需要存储搜索过程中使用的alpha和beta边界。当您在节点中间搜索时返回一个值，它要么是真值的上限（因为值=β），要么是真值的下限（因为值=α），要么是节点的实际值（α<；值<；β）。您需要将其存储在转置表中。然后，当您想要重新使用该值时，必须检查您是否可以使用给定当前alpha和beta边界的值。（在换位表中找到值后，您可以通过实际执行搜索来验证这一点，以查看从搜索中获得的值是否与在表中获得的值相同。）