极大极小算法与跳棋博弈

Question

我正在使用Minimax算法和Python实现跳棋游戏。有两个玩家——都是电脑。我一直在寻找类似问题的解决方案，但我找不到任何解决方案，我已经为此挣扎了几天。我的切入点是这个函数：

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

它启动游戏并调用下一个函数，该函数根据极大极小算法为第一个玩家执行最佳移动。在第一步之后，它会为第二个玩家调用此函数，一旦其中一个玩家赢了游戏，此循环将结束。此函数如下所示：

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算法时编辑原始电路板。该条件检查是否存在赢的条件，以便最大化玩家赢或最小化玩家赢。如果他们中没有一人获胜，则执行最佳移动。转到这里的主要问题，我实现了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变量保存对具有以下字段的移动对象的引用：

class Move:
    def __init__(self, x, y, score, piece=None):
        self.x = x
        self.y = y
        self.score = score
        self.piece = piece

我正在初始化最佳移动。在玩家最大化的情况下，将分数设置为-无穷大，否则设置为+无穷大

第一个条件检查深度是否达到最大水平（出于测试目的，设置为2）或游戏结束。如果是，它将评估当前板的情况并返回包含当前板分数的移动对象。否则，我的算法会为玩家查找所有合法/正确的移动，并执行第一个移动

执行此函数后，将以递归方式调用此函数，但深度会增加，移动播放器也会改变。该函数再次运行并更改参数，直到执行第一个if条件

执行到该分支后，返回电路板的评估分数，然后在递归调用后的for循环中，坐标x、y和移动的工件被指定给移动对象

最后一个条件检查新分数是否是该特定玩家的更好分数。如果这是一个最大化的玩家，那么在我的例子P1中，它检查新的分数是否高于前一个。在最小化玩家的情况下，该算法寻找最低分数

在为该玩家执行所有正确的移动之后，我的算法应该返回一个最佳移动

预期结果
坐标为x和y的移动类的单个对象，评估棋盘得分，仅在其中一名玩家获胜的情况下为+Infinity/-Infinity，以及将移动到[x，y]坐标的棋子类对象

实际结果
坐标为x和y的Move类的单个对象，在第一次调用MiniMax函数后，评估板的分数等于+无穷大。所有棋子都没有改变位置，所以比赛还没有结束。然而，分数是+无穷大，所以函数move_piece_minimax（）将返回False-这意味着不可能再移动了。因此，我的程序将停止执行，板上没有任何更改。这是初始和最终板状态的屏幕截图-在执行过程中没有任何变化，因为第一次调用返回+无穷大

我的问题是，在实现MiniMax算法的过程中，我遗漏了什么？我犯了什么错误吗？我也愿意接受任何代码改进或建议。如果您需要任何其他功能来理解我的实现，我将提供它们。谢谢大家!

Answer 1

在minimax函数中，您应该执行以下任一操作

1。在放置棋子之前，复制一份棋盘

2.递归调用minimax函数后移除放置的工件

否则，你的棋盘将被递归填满，你将收到一个错误，说明没有移动了。Minimax的意思是通过放置块来进行深入搜索，所以您应该实现一种方法，这样它就不会修改原始板