python - 如何实现连接 4 的转置表？

问题描述

我在 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 散列方法对板进行散列，并且我正在使用有序 dict 将散列板添加到其中。在这个哈希键中，我添加了该板的值和该板的 bestMove。不幸的是，这似乎使算法选择了错误的动作（它以前工作过），有谁知道你应该将棋盘状态放在缓存中的什么位置，以及你应该从缓存中的哪个位置获取它们？

标签： pythonartificial-intelligencehashtableminimaxiterative-deepening

关于您的方法的几点：

如果你想让事情变得更快，用 C 或 C++ 编写高效的代码将比 python 快得多。通过从 python 切换到良好的 C/C++ 实现，我已经看到这种搜索代码的性能提高了 10-100 倍。无论哪种方式，您都应该尝试编写避免在搜索期间分配内存的代码，因为这非常昂贵。也就是说，与添加转置表相比，您可以更有效地从编码中获得更好的回报。
在博弈树搜索中对转置表使用 Zobrist 散列时，您通常不会显式存储状态。您只检查哈希是否相等。虽然出错的可能性很小，但仅存储散列所需的内存要少得多，而且对于 64 位散列，对于您正在执行的搜索类型，冲突的可能性可能非常小。（导致错误的可能性更低。）
在转置表中存储值时，还需要存储搜索期间使用的 alpha 和 beta 边界。当您在搜索中间的节点处获得一个值时，它要么是真值的上限（因为 value = beta），要么是真值的下限（因为 value = alpha）或节点的实际值（阿尔法 < 值 < 贝塔）。您需要将其存储在转置表中。然后，当您想重新使用该值时，您必须检查是否可以使用给定当前 alpha 和 beta 边界的值。（您可以通过在转置表中找到值后实际执行搜索来验证这一点，以查看您从搜索中获得的值是否与您在表中获得的值相同。）

python - 如何实现连接 4 的转置表？

问题描述

解决方案

推荐阅读