Странное поведение в функции при реализации алгоритма отсечения альфа-бета
Я реализовал минимаксный алгоритм с отсечкой альфа-бета. Чтобы получить лучший ход, я называю алгоритм альфа-бета с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