我已经实现了带有 alpha-beta 修剪的极小极大算法。为了获得最佳动作,我将 alpha-beta 算法称为rootAlphaBeta
功能。然而,在rootAlphaBeta
函数时,我发现了一些非常奇怪的行为。当我打电话给rootAlphaBeta
函数与ply
共 4 个,它拨打了大约 20 000 个电话,但是当我拨打alphaBeta
直接调用函数,只调用了大约2000次。我似乎找不到问题所在,因为调用次数应该是相同的。
两种算法最终找到的走法应该是一样的吧?我想是的,至少这一步棋的分数是一样的,我无法知道这一步棋的结果alphaBeta
选择当我直接调用它而无需rootAlphaBeta
.
def alphaBeta(self, board, rules, alpha, beta, ply, player):
"""Implements a minimax algorithm with alpha-beta pruning."""
if ply == 0:
return self.positionEvaluation(board, rules, player)
move_list = board.generateMoves(rules, player)
for move in move_list:
board.makeMove(move, player)
current_eval = -self.alphaBeta(board, rules, -beta, -alpha, ply - 1,
board.getOtherPlayer(player))
board.unmakeMove(move, player)
if current_eval >= beta:
return beta
if current_eval > alpha:
alpha = current_eval
return alpha
def rootAlphaBeta(self, board, rules, ply, player):
"""Makes a call to the alphaBeta function. Returns the optimal move for a
player at given ply."""
best_move = None
max_eval = float('-infinity')
move_list = board.generateMoves(rules, player)
for move in move_list:
board.makeMove(move, player)
current_eval = -self.alphaBeta(board, rules, float('-infinity'),
float('infinity'), ply - 1,
board.getOtherPlayer(player))
board.unmakeMove(move, player)
if current_eval > max_eval:
max_eval = current_eval
best_move = move
return best_move