我正在使用Minimax算法和Python实现Checkers游戏。有两个播放器-都是计算机。我一直在寻找类似问题的解决方案,但找不到任何解决方案,而且我已经为之苦苦挣扎了几天。我的入口点是此功能:
def run_game(board):
players = board.players
is_move_possible = True
move = 0
while is_move_possible:
is_move_possible = move_piece_minimax(board, players[move % 2])
move += 1
它开始游戏,并根据第一个玩家调用基于MiniMax算法的最佳移动的下一个函数。第一步移动后,它将为第二位玩家调用此函数,并且一旦其中一位玩家获胜,此循环将结束。该函数如下所示:
def move_piece_minimax(board, player):
best_move = minimax(copy.deepcopy(board), player, 0)
if best_move.score == +infinity or best_move.score == -infinity:
return False
move_single_piece(board.fields, player, best_move)
return True
第一行称为MiniMax algorithm,我将在后面进行描述,它应该为玩家找到最佳的移动方式。我在这里传递了整个电路板的深层副本,因为我不希望在执行MiniMax算法时对原始电路板进行编辑。该条件检查是否有获胜条件,因此是最大化玩家获胜还是最小化玩家获胜。如果没有一个获胜,则执行best_move。转到这里的主要问题,我实现了MiniMax算法,如下所示:
def minimax(board, player, depth):
best_move = Move(-1, -1, -infinity if player.name == PLAYER_NAMES['P1'] else +infinity)
if depth == MAX_SEARCH_DEPTH or game_over(board):
score = evaluate(board)
return Move(-1, -1, score)
for correct_move in get_all_correct_moves(player, board.fields):
x, y, piece = correct_move.x, correct_move.y, correct_move.piece
move_single_piece(board.fields, player, correct_move)
player_to_move = get_player_to_move(board, player)
move = minimax(board, player_to_move, depth + 1) # <--- here is a recursion
move.x = x
move.y = y
move.piece = piece
if player.name == PLAYER_NAMES['P1']:
if move.score > best_move.score:
best_move = move # max value
else:
if move.score < best_move.score:
best_move = move # min value
return best_move
我确定播放器'P1'是最大化播放器,播放器'P2'是最小化播放器。从第一行开始,best_move变量保存对Move对象的引用,该对象具有以下字段:
class Move:
def __init__(self, x, y, score, piece=None):
self.x = x
self.y = y
self.score = score
self.piece = piece
在最大化播放器的情况下,我将best_move.score初始化为-Infinity,否则初始化为+ Infinity。
第一个条件检查深度是否达到最大级别(出于测试目的,设置为2)或游戏结束。如果是,它将评估当前棋盘的状况并返回保存当前棋盘得分的Move对象。否则,我的算法会为玩家寻找所有合法/正确的举动并执行第一个。
执行后,将以递归方式调用此功能,但深度会增加,并且播放器会更改。该函数将在更改参数的情况下再次运行,直到第一个条件执行。
一旦执行转到该分支,将返回电路板的评估分数,然后,在递归调用后的for循环中,将坐标x,y和已移动的块分配给Move对象。
最后条件检查新分数是否对该特定玩家更好。如果这是一个发挥最大作用的玩家,那么在我的案例P1中,它将检查新分数是否高于上一个。在最小化播放器的情况下,算法会寻找最低分数。
在为该球员完成所有正确的举动之后,我的算法应返回一个best_move。
预期结果带有x和y坐标的Move类的单个对象,评估板的分数,仅在其中一名玩家获胜的情况下才为+ Infinity / -Infinity,而Piece类的对象将被移至[x,y ]坐标。
实际结果带有x和y坐标的Move类的单个对象,在第一次调用MiniMax函数后评估了板的分数,该分数等于+ Infinity。没有一块棋改变了位置,所以比赛还没有结束。但是,得分为+ Infinity,因此函数move_piece_minimax()将返回False-意味着无法再进行任何移动。因此,我的程序将在板上无任何更改的情况下停止执行。这是初始和最终开发板状态的屏幕截图-执行中没有任何变化,因为第一个调用返回+ Infinity。
我的问题是,在实施MiniMax算法期间错过了什么?我有没有犯错?我也欢迎任何代码改进或建议。如果您需要任何其他功能来理解我的实现,我将提供它们。谢谢!
在minimax函数中,您应该执行以下任一操作