实现alpha-beta剪枝算法时函数中的奇怪行为
实现alpha-beta剪枝算法时函数中的奇怪行为
提问于 2012-09-25 00:46:12
我已经实现了一个带有alpha-beta剪枝的极大极小算法。为了获得最佳走法，我使用rootAlphaBeta函数调用了α-beta算法。然而，在rootAlphaBeta函数中，我发现了一些非常奇怪的行为。当我使用ply 4调用rootAlphaBeta函数时，它进行了大约20000次调用，但当我直接调用alphaBeta函数时，它只进行了大约2000次调用。我似乎找不到有什么问题，因为呼叫的数量应该是相同的。
两种算法最终找到的移动应该是相同的，对吧？我想是的，至少移动的分数是相同的，当我不使用rootAlphaBeta直接调用alphaBeta时，我无法知道它选择的移动。
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回答 1
Stack Overflow用户
回答已采纳
发布于 2012-09-25 01:04:33
您的rootAlphaBeta不会更新alpha值。它使用(-inf，inf)的完整范围调用其所有子节点，而它本可以缩小除第一个子节点之外的所有子节点的范围。这将防止修剪一些对最终分数没有影响的分支，并增加节点数量。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12569392
复制相关文章
相似问题
腾讯云开发者
