python - 极小极大算法和跳棋游戏

问题描述

我正在使用 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 算法，我将在后面描述，它应该为玩家找到可能的最佳移动。我在这里传递了整个板的深层副本，因为我不希望在执行 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 对象。否则，我的算法会为玩家寻找所有合法/正确的移动并执行第一个。

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

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

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

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

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

实际结果
Move 类的单个对象，坐标 x 和 y，在第一次调用 MiniMax 函数后评估板的分数等于 +Infinity。没有一块棋子改变了它的位置，所以游戏还没有结束。但是，得分是 +Infinity，因此函数 move_piece_minimax() 将返回 False - 意味着无法再进行移动。因此，我的程序将停止执行，而板上没有任何变化。这是初始和最终板状态的屏幕截图 - 在执行期间没有任何更改，因为第一个调用返回 +Infinity。

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

标签： pythonalgorithmrecursionartificial-intelligenceminimax

python - 极小极大算法和跳棋游戏

问题描述

解决方案

推荐阅读