Python3中的Minimax算法实现

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

我一直在尝试用Python构建一个Tic-Tac-Toe机器人。我试图避免使用Minimax算法，因为我很懊恼如何实现它。到现在。我（最后）编写了一个算法，它可以很容易地丢失并且很容易丢失，这有点打败了让电脑玩Tic-Tac-Toe的目的。所以我终于鼓起勇气去实现算法。我偶然发现了this StackOverflow的帖子。我试着在那里实现所选答案，但我无法理解大部分内容。该答案中的代码如下：

def minimax(self, player, depth = 0) :
    if player == "o":
        best = -10
    else:
        best = 10
    if self.complete():
        if self.getWinner() == "x": # 'X' is the computer
            return -10 + depth, None
        elif self.getWinner() == "tie":
            return 0, None
        elif self.getWinner() == "o" : # 'O' is the human
            return 10 - depth, None
    for move in self.getAvailableMoves() :
        self.makeMove(move, player)
        val, _ = self.minimax(self.getEnemyPlayer(player), depth+1)
        print(val)

        self.makeMove(move, ".")

        if player == "o" :
            if val > best :
                best, bestMove = val, move
        else :
            if val < best :
                best, bestMove = val, move

    return best, bestMove

首先，为什么我们在计算机获胜时返回-10 + depth，当人类获胜时返回10 - depth？ （我知道为什么我们在抽签时返回0）。其次，depth参数是做什么的？有没有办法省略它？我们应该省略吗？

我可能遗漏了一些关于算法的基本知识，但我认为我理解得很好。请记住，我对递归算法很新...

编辑

所以，现在我自己做了这个功能：

def minimax(self, player):
    won = 10
    lost = -10
    draw = 0

    if self.has_won(HUMAN):
        return lost, None
    elif self.has_won(BOT):
        return won, None

    if not(self.board_is_empty()):
        return draw, None

    moves = self.get_available_moves()

    for move in moves:
        self.play_move(move[0], move[1], player)
        make_board(self.board)

        if self.board_is_empty():
            val, _ = self.minimax(self.get_enemy_player(player))
        self.rewind_move(move)

        if val==won:
            return val, move

但现在的问题是我无法理解当移动以平局或亏损（对于计算机）结束时会发生什么。我认为它正在做的是它通过一个移动的后果来看看SOMEONE是否获胜（这可能是发生了什么，因为我测试了它）然后如果SOMEONE获胜则返回该移动。如何修改此代码才能正常工作？

注意：

  • 这个函数在class中，因此是self关键字。
  • moves是一个包含元组的列表。例如。 moves = [(0, 1), (2, 2)]等。所以，移动包含所有空方块。因此每个moves[i][j]是一个3的整数。
  • 我正在使用Jacques de Hooge在下面的答案中提出的详尽算法。
python algorithm implementation tic-tac-toe minimax
1个回答
0
投票

首先注意10 - 深度= - （-10 +深度）。因此，计算机胜利与人类获胜有相反的迹象。通过这种方式，可以添加它们来评估游戏板状态的值。虽然使用tictactoe这并不是真正需要的，但在像国际象棋一样的游戏中，因为它太耗费时间来尝试所有可能的组合直到将死，因此游戏板状态必须以某种方式在损失和胜利方面进行评估（失败并赢得国际象棋）碎片，每个都值得一定数量的积分，从经验中得出的价值）。

假设现在我们只看10 - 深度（所以人类获胜）。最有吸引力的胜利是那些需要最少的层次（移动）。由于每次移动或反向导致深度增加，因此更多移动将导致参数深度更大，因此10 - 深度（优势的“量”）更小。如此快速的胜利优于长度的胜利。 10是足够的，因为在3×3的运动场中总共只有9次移动。

简而言之：由于tictactoe非常简单，实际上胜利组合可以在详尽的递归搜索中找到。但是minimax算法适用于像国际象棋这样的更复杂的情况，其中必须根据损失（负）和增益（正数）的总和来评估中间情况。

是否应省略深度参数？如果你关心最快的胜利：不。如果你只关心胜利（使用tictactoe）：它确实可以省略，因为可以进行详尽的搜索。

[编辑]

完全用tictactoe意味着搜索9层深，因为游戏永远不会持续更长时间。

使用参数播放器（o或x）和返回值win或loss创建递归函数，该函数首先在最深递归级别决定，然后通过递归树向上移动。让它用相反的播放器作为所有自由字段的参数。如果任何续集导致机器赢得人类在每个级别上可能采取的所有分支，那么机器的移动是正确的。

注意：我做的假设是有一个获胜策略。如果不是这种情况（可能有关系），那么您拥有的算法可能是最佳选择。我记得使用tictactoe，开始游戏的人总能以上述方式执行胜利。因此该算法将在至少50％的游戏中获胜。对于非完美的人类玩家，如果计算机没有启动，如果人类玩家做了次优的事情，它也可能获胜

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.