我在 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。不幸的是,这似乎使算法选择了错误的动作(它以前工作过),有谁知道你应该将棋盘状态放在缓存中的什么位置,以及你应该从缓存中的哪个位置获取它们?