Minimax算法和跳棋游戏

问题描述 投票:0回答:1

我正在使用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。

Initial and final board's states

我的问题是,在实施MiniMax算法期间错过了什么?我有没有犯错?我也欢迎任何代码改进或建议。如果您需要任何其他功能来理解我的实现,我将提供它们。谢谢!

python algorithm recursion artificial-intelligence minimax
1个回答
0
投票

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

© www.soinside.com 2019 - 2024. All rights reserved.