minimax解释了一个白痴

Question

我浪费了整天尝试使用Minimax算法来制作无与伦比的Tictactoe AI。我一路错过了一些东西（脑炸）。

我不是在这里寻找代码，只是更好地解释我出错的地方。

这是我当前的代码（Minimax方法总是出于某种原因返回0）：

from copy import deepcopy


class Square(object):
    def __init__(self, player=None):
        self.player = player

    @property
    def empty(self):
        return self.player is None


class Board(object):
    winning_combos = (
        [0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6],
    )

    def __init__(self, squares={}):
        self.squares = squares
        for i in range(9):
            if self.squares.get(i) is None:
                self.squares[i] = Square()

    @property
    def available_moves(self):
        return [k for k, v in self.squares.iteritems() if v.empty]

    @property
    def complete(self):
        for combo in self.winning_combos:
            combo_available = True
            for pos in combo:
                if not pos in self.available_moves:
                    combo_available = False
            if combo_available:
                return self.winner is not None
        return True

    @property
    def player_won(self):
        return self.winner == 'X'

    @property
    def computer_won(self):
        return self.winner == 'O'

    @property
    def tied(self):
        return self.complete == True and self.winner is None

    @property
    def winner(self):
        for player in ('X', 'O'):
            positions = self.get_squares(player)
            for combo in self.winning_combos:
                win = True
                for pos in combo:
                    if pos not in positions:
                        win = False
                if win:
                    return player
        return None

    @property
    def heuristic(self):
        if self.player_won:
            return -1
        elif self.tied:
            return 0
        elif self.computer_won:
            return 1

    def get_squares(self, player):
        return [k for k,v in self.squares.iteritems() if v.player == player]

    def make_move(self, position, player):
        self.squares[position] = Square(player)

    def minimax(self, node, player):
        if node.complete:
            return node.heuristic
        a = -1e10000
        for move in node.available_moves:
            child = deepcopy(node)
            child.make_move(move, player)
            a = max([a, -self.minimax(child, get_enemy(player))])
        return a


def get_enemy(player):
    if player == 'X':
        return 'O'
    return 'X'

Answer 1

您的完整功能无法正常工作，导致游戏在发生任何事情之前被绑定。例如，考虑此设置：

>> oWinning = {
 1: Square('X'),
 3: Square('O'), 4: Square('X'),
 6: Square('O'), 8: Square('X'),
}
>> nb = Board(oWinning)
>> nb.complete
True
>> nb.tied
True

在下一步行动中，这应该是计算机的胜利。相反，它说游戏是绑扎的。

问题在于，您的逻辑现在就完成，检查以查看组合中的所有正方形是否免费。如果没有任何一个，它假定该组合将无法赢得。它需要做的是检查该组合中的任何位置是否被占用，只要所有这些连击都不是一个或同一玩家，则应将组合视为仍然可用。

例如

def available_combos(self, player):
    return self.available_moves + self.get_squares(player)

@property
def complete(self):
    for player in ('X', 'O'):
        for combo in self.winning_combos:
            combo_available = True
            for pos in combo:
                if not pos in self.available_combos(player):
                   combo_available = False
            if combo_available:
                return self.winner is not None
    return True

现在，我使用更新的代码对此进行了适当的测试，我在此测试案例上获得了预期的结果：

>>> nb.minimax(nb, 'O')
-1
>>> nb.minimax(nb, 'X')
1

Answer 2

步骤1：建造游戏树

从当前板开始生成对手可以做出的所有可能移动。然后，对于每个生成所有可能的动作。对于Tic-Tac-toe，直到没有人可以玩。在其他游戏中，通常会在给定时间或深度后停止。

这看起来像一棵树，自己在一张纸上绘制它，当前板上的木板在下方移动一层，所有可能的移动都以下面的一层响应等。

步骤2：在树底部为所有木板分数

对于像TIC-TAC-TOE这样的简单游戏，如果输掉了50次领带，100胜。

步骤3：在树上传播分数

这是Min-Max发挥作用的地方。以前未经评估的董事会的得分取决于孩子和谁可以玩。假设您和您的对手总是在给定状态下选择最佳的举动。对手的最好举动是给予的举动 你 最糟糕的分数。同样，您最好的举动是使您得分最高的举动。在转弯的情况下，您可以选择最低分数的孩子（这可以最大程度地利用他的利益）。如果轮到您，您假设您会尽力而为，因此您可以选择最大的动作。

步骤4：选择您的最佳动作

现在，在您当前位置的所有可能比赛中，在所有可能的比赛中取得最佳传播得分。

如果从空白板开始，则可以在一张纸上尝试一下。

使用递归：通常，可以通过使用递归来简化这一点。 “评分”函数在每个深度处递归地称为，并取决于深度是否奇数，甚至分别为所有可能的移动选择最大或最小值。如果不可能，它会评估板的静态得分。递归解决方案（例如示例代码）可能更棘手。

Answer 3

众所周知，Minimax的想法是深入寻找最佳价值，假设对手总是会以最糟糕的价值发挥作用（对我们来说最糟糕的是，那么对他们来说是最好的）。

这个想法是，您将尝试为每个职位赋予价值。您输掉的位置是负面的（我们不想要那个），而获胜的位置是积极的。您假设您将始终尝试最高价值的位置，但是您还假设对手将始终瞄准最低价值的位置，这对我们来说是最糟糕的结果，对他们来说是最好的（他们赢了，我们输了）。因此，您将自己穿上鞋子，尽量尽可能出色，并假设他们会做到这一点。
因此，如果您发现自己有可能采取两次动作，一个让他们选择获胜或输掉，一个导致抽奖，您认为他们会采取行动，如果您让他们这样做，他们将获胜。因此，最好进行抽奖。

现在，要获得更“算法”的视图。

想象一下，除了两个可能的位置外，您的电网几乎已经饱满。
考虑一下您玩第一个时会发生什么：
对手将扮演另一个。这是他们唯一的可能举动，因此我们不必考虑其他动作。查看结果，将结果值关联（如果won， +∞，则为0，如果draw，如果丢失：对于tic tac toe，您可以将它们表示为+1 0和-1）。
现在考虑一下您播放第二个时会发生什么：
（在这里，对手只有一个动作，查看最终位置，重视位置）。

您需要在这两个动作之间进行选择。这是我们的举动，因此我们想要最好的结果（这是Minimax中的“最大”）。选择较高结果的一个作为我们的“最佳”动作。就是这样，“从终端移动2”示例。

现在想象您没有2个，但还剩3个动作。
原理是相同的，您想为3个可能的动作中的每个动作分配一个值，以便您可以选择最佳。
因此，您首先考虑三个动作之一。
您现在处于上述情况，只有2个可能的动作，但这轮到对手了。然后，您开始考虑对对手的可能举动之一，就像我们上面一样。同样，您会查看每个可能的动作，并为他们俩找到结果值。这是对手的举动，因此我们假设他们会为他们发挥“最佳”动作，这对我们来说是最糟糕的投票率，因此它是价值较小的人（这是Minimax中的“ Min”）。忽略另一个；假设他们会演奏您发现的最适合他们的东西。这就是您的举动会产生的目标，因此，这是您分配给三个动作中的第一个的价值。

现在，您考虑了其他可能的2个动作。您以相同的方式给他们一个价值。从您的三个动作中，您可以选择具有最大值的一个动作。

现在考虑4个动作会发生什么。对于您的四个动作中的每一个，您都会查看对手的三个动作发生的情况，对于每个动作，您都会假设他们会选择一个为您提供最糟糕的结果的最佳结果，其中剩下的2个动作中最好的结果是您的。

您会看到它的发展方向。为了评估从末端的移动n步骤，您可以查看n可能的每一个动作中可能发生的事情，试图给他们一个值，以便您可以选择最好的。在此过程中，您将不得不尝试为在N-1：对手玩耍的玩家找到最佳的动作，并以较小的价值选择步骤。在评估N-1移动的过程中，您必须在可能的N-2移动之间进行选择，这将是我们的，并假设我们将在此步骤中尽可能地发挥作用。等等。

这就是为什么该算法本质上是递归的原因。无论n，在步骤n上，您都会在N-1上评估所有可能的步骤。冲洗并重复。

对于TIC-TAC-TOE TODAYS机器的功能足够强大，可以从游戏开始时立即计算所有可能的结果，因为只有几百个。当您希望实现它以进行更复杂的游戏时，您将不得不在某个时候停止计算，因为这会花费太长时间。因此，对于一个复杂的游戏，您还必须编写代码，以决定是否继续寻找所有可能的下一步动作或试图立即为该位置赋予价值并提早返回。这意味着您还必须计算一个不是最终的位置的价值 - 例如，对于国际象棋，您会考虑到每个对手在董事会上有多少材料，没有伴侣的检查的直接可能性，您控制了多少瓷砖和全部，这并不容易。