アルファ ベータ プルーニングを使用したミニマックス アルゴリズムを実装しました。最良の動きを得るために、関数でアルファ ベータ アルゴリズムを呼び出しrootAlphaBeta
ます。しかし、rootAlphaBeta
関数内で、非常に奇妙な動作を見つけました。rootAlphaBeta
4 の関数を呼び出すと、ply
約 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