Minimax 算法和西洋跳棋游戏

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

它开始游戏并调用下一个函数，该函数应该根据 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 算法期间编辑原始板。该条件检查获胜条件，因此是最大化玩家获胜还是最小化玩家获胜。如果其中 none 个获胜，则执行 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）或游戏是否结束。如果是，它会评估当前棋盘的情况，并且 returns 是一个保存当前棋盘分数的 Move 对象。否则，我的算法会为玩家查找所有 legal/correct 步并执行第一个。

执行后，以递归方式调用此函数，但深度增加且移动玩家发生变化。该函数再次运行并更改参数，直到执行第一个 if 条件。

一旦执行到该分支，棋盘的评估分数就会被 returned 之后，在递归调用后的 for 循环中，坐标 x、y 和一块被移动的棋子被分配给移动对象。

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

为该玩家执行所有正确的移动后，我的算法应该 return 一个 best_move。

预期结果
具有坐标 x 和 y 的 Move class 的单个对象，评估板的得分，只有在其中一名玩家获胜的情况下才为 +Infinity/-Infinity，以及 Piece class 的对象将移动到 [x, y] 坐标。

实际结果
具有坐标 x 和 y 的 Move class 的单个对象，在第一次调用 MiniMax 函数后评估板的分数等于 +Infinity。 None 个棋子改变了位置，所以游戏还没有结束。然而，分数是 +Infinity 所以函数 move_piece_minimax() 将 return False - 意味着没有更多的移动是可能的。因此，我的程序将停止执行，板上没有任何变化。这是初始和最终板状态的屏幕截图 - 在第一次调用 returns +Infinity.

时，执行期间没有任何变化

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

Answer 1

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

1. 在放置棋子之前复制你的棋盘

2.递归调用你的minimax函数后移除放置的棋子

否则，您的棋盘将被递归填满，您将收到一条错误消息，指出没有剩下的棋子。 Minimax 的意思是通过放置棋子来进行深度搜索，所以你应该实现一个方法，这样它就不会修改你的原始棋盘。

Minimax 算法和西洋跳棋游戏

Minimax algorithm and checkers game

python

algorithm

recursion

artificial-intelligence

minimax