idi的极大极小解释

Question

我浪费了一整天的时间试图使用minimax算法来制作一个无与伦比的tictactoe人工智能。一路上我错过了一些东西（脑筋急转弯）。

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

这是我当前的代码（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

正如你已经知道的，Minimax的思想是深入搜索最佳值，假设对手总是用最差的值（对我们来说最差，所以对他们来说最好）移动。

这个想法是，你将尝试给每个位置一个值。你输的位置是负的（我们不希望这样），你赢的位置是正的。你假设你总是试图获得最高价值的位置，但你也假设对手总是瞄准最低价值的位置，这对我们来说是最坏的结果，对他们来说是最好的（他们赢了，我们输了）。所以你要设身处地地为他们着想，尽可能地发挥出自己的水平，并假设他们会这么做。
因此，如果你发现你有两个可能的动作，一个让他们选择输赢，一个导致平局，你假设他们会采取行动，如果你让他们这么做，他们会赢。所以还是去抽签吧。

现在来看看更“算法”的观点。

想象一下，除了两个可能的位置外，您的网格几乎已满。
想想当你演奏第一首时会发生什么：
对手将与另一方比赛。这是他们唯一可能的行动，所以我们不必考虑他们的其他行动。看看结果，关联一个结果值（如果赢了，则为+0；如果输了，则为-0：对于tic tac toe，可以表示为+10和-1）。
现在想想当你演奏第二首时会发生什么：
（同样的道理，对手只有一个动作，看结果的位置，重视位置）。

你需要在这两个动作之间做出选择。这是我们的行动，所以我们希望得到最好的结果（这是minimax中的“max”）。选择一个结果更高的作为我们的“最佳”举措。这就是“从末端移动两步”的例子。

现在想象一下你只剩下3步了。
原则是一样的，你想给你的3个可能的移动中的每一个分配一个值，这样你就可以选择最好的。
所以你要从三个步骤中的一个开始。
你现在处于上面的情况，只有两个可能的移动，但轮到对手了。然后你开始考虑对手的一个可能的动作，就像我们在上面所做的那样。同样，你看每一个可能的动作，你会发现它们的结果值。这是对手的移动，所以我们假设他们会为他们打出“最好”的移动，对我们来说是投票率最差的移动，所以这是值较小的移动（这是minimax中的“min”）。忽略另一个；假设他们会玩你认为最适合他们的游戏。这是你的移动将产生的结果，所以这是你分配给三个移动中的第一个的值。

现在你可以考虑其他两个动作。你以同样的方式给他们一个价值。从你的三个动作中，你选择一个最大值。

现在想想4个动作会发生什么。对于你的4个动作中的每一个，你看对手的3个动作发生了什么，对于每一个，你假设他们会选择一个给你在剩下的2个动作中最好的一个给你最坏的可能结果。

你看这是怎么回事。要评估从末尾开始的n个移动步骤，请查看n个可能的移动中的每一个可能发生的情况，尝试给它们一个值，以便您可以选择最佳的。在这个过程中，你必须尝试为在n-1位置的玩家找到最佳的移动：对手，并选择值较低的步骤。在评估n-1移动的过程中，你必须在可能的n-2移动中做出选择，这将是我们的，并且假设我们在这一步将发挥出我们所能做到的最好。等等

这就是为什么这个算法本质上是递归的。不管n是什么，在步骤n，你在n-1中评估所有可能的步骤。冲洗并重复。

对于tic-tac-toe来说，今天的机器功能强大得足以从游戏一开始就计算出所有可能的结果，因为它们只有几百个。当你看着我为一个更复杂的游戏，你将不得不停止计算在某个点，因为它将花费太长时间。所以对于一个复杂的游戏，你还需要编写代码来决定是继续寻找所有可能的下一步动作，还是现在就给位置赋值并尽早返回。这意味着你还需要计算一个非最终位置的值——例如，在下棋时，你要考虑到每个对手在棋盘上有多少材料，没有配偶的情况下立即检查的可能性，你控制多少棋子，以及所有的棋子，这使得它不是微不足道的。

Answer 2

您的完整功能无法按预期工作，导致游戏在发生任何事情之前被声明为平局。例如，考虑以下设置：

>> 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 3

步骤1：构建游戏树

从当前棋盘开始，产生所有对手可能做出的移动。 然后为每一个生成所有可能的移动。 对于Tic-Tac-Toe，只要继续，直到没有人可以玩。在其他游戏中，你通常会在给定的时间或深度后停止。

这看起来像一棵树，你自己把它画在一张纸上，最上面是当前的棋盘，所有对手移动一层下面，所有你可能的移动都在下面一层等

第2步：给树底部的所有板打分

对于像Tic Tac Toe这样的简单游戏，如果你输了，50平，100胜，就得0分。

步骤3：将分数传播到树上

这就是最小最大值的作用。以前不计分的棋盘的分数取决于它的孩子和谁可以玩。假设你和你的对手总是在给定的状态下选择最好的移动。对对手来说，最好的招式是给你最差分数的招式。同样的，你最好的动作是给你最高的分数。在对手轮到你的情况下，你选择得分最低的孩子（这使他的利益最大化）。如果轮到你了，你认为你会做出最好的行动，所以你选择最大。

第4步：选择最佳移动方式

现在开始移动，在当前位置所有可能的游戏中获得最佳传播分数。

试着在一张纸上，如果从空白板开始对你来说太多了，从一些先进的井字游戏开始。

使用递归： 通常这可以通过使用递归来简化。在每个深度递归调用“scoring”函数，并根据深度是奇数还是偶数，为所有可能的移动分别选择max或min。当不可能移动时，它会评估板的静态得分。递归解决方案（例如示例代码）可能更难掌握。