傻瓜版的Minimax解释

Question

我今天整整花了一天时间想用极小极大算法做一个无敌的井字棋AI，但我在过程中搞错了什么（脑袋都快炸了）。

我不是想要代码，只是想要更清楚地知道我哪里出错了。

这是我现在的代码（极小极大方法总是返回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，输了是-∞：在井字棋中可以用+1、0和-1来表示）。
现在考虑当你选择第二个位置时会发生什么：
（这里也是一样，对手只有一个选择，看看结果，给这个位置一个分值）。

你需要在这两个选择中做出决定。现在轮到我们出手，所以我们想要最好的结果（这就是Minimax中的“max”）。选择那个结果更高的作为我们的“最佳”选择。这就是“从两个选择开始”的例子。

现在想象一下，你不是有两个选择，而是有三个选择。
原则是一样的，你想给你三个可能的选择都赋值，以便选择最好的。
所以你先考虑其中一个选择。
你现在处于上面的情况，只有两个可能的选择，但轮到对手出手。然后你开始考虑对手的一个可能选择，就像我们之前做的那样。你查看每个可能的选择，并为它们找到一个结果值。因为是对手的回合，所以我们假设他们会选择对他们最好的选择，也就是对我们结果最糟糕的那个，所以选择值最低的（这就是Minimax中的“min”）。忽略其他选择；假设他们会选择你认为对他们最好的那个。这就是你为你的三个选择中的第一个赋的值。

现在你考虑其他两个可能的选择。用同样的方法给它们赋值。然后从你的三个选择中，选择那个值最大的。

现在考虑一下四个选择的情况。对于你的每个四个选择，你查看对手的三个选择，并假设他们会选择给你带来最糟糕结果的那个，基于你剩下的两个选择。

你可以看到这是什么样的思路。为了评估距离结束n步的选择，你查看每个n个可能的选择，试图给它们赋值，以便你可以选择最好的。在这个过程中，你需要找到n-1步的最佳选择：对手的选择，并选择那个值最低的。在评估n-1步的过程中，你还需要在可能的n-2步中做出选择，这些都是我们的选择，并假设我们会尽力去玩。等等。

这就是为什么这个算法本质上是递归的。无论n是多少，在第n步你都要评估所有可能的n-1步。重复这个过程。

对于井字棋，今天的机器足够强大，可以从游戏开始时计算出所有可能的结果，因为只有几百种情况。当你想把它应用到更复杂的游戏时，你必须在某个时刻停止计算，因为会花费太长时间。所以对于复杂的游戏，你还需要编写代码来决定是继续寻找所有可能的下一步，还是尝试给当前位置一个值并提前返回。这意味着你还需要为非最终的位置计算一个值——例如在国际象棋中，你需要考虑每个对手在棋盘上有多少棋子、是否有将军但没有将死的立即可能性、你控制了多少个格子等等，这使得问题变得不简单。

Answer 2

第一步：建立你的游戏树

从当前的棋盘开始，列出对手可以做的所有可能的动作。然后，对于每一个对手的动作，再列出你可以做的所有可能的动作。以井字棋为例，继续这个过程直到没有人可以再下棋。在其他游戏中，通常会在达到一定的时间或深度后停止。

这就像一棵树，你可以在纸上画出来，最上面是当前的棋盘，下面一层是对手的所有动作，再下面一层是你对每个对手动作的回应等等。

第二步：给树底部的每个棋盘打分

对于像井字棋这样简单的游戏，如果你输，就给分数0；如果平局，给50分；如果赢，给100分。

第三步：将分数向上传播

这时候就要用到最小最大算法了。一个之前没有打分的棋盘的分数取决于它的子棋盘和谁来下棋。假设你和对手总是选择在当前状态下最好的动作。对手的最佳动作是让你得到最差的分数。同样，你的最佳动作是让你得到最高的分数。如果轮到对手下棋，你就选择分数最低的子棋盘（这样可以最大化他的收益）。如果轮到你下棋，你就假设自己会做出最好的选择，所以你选择分数最高的。

第四步：选择你最好的动作

现在，从当前的位置中，选择一个能带来最佳分数的动作来进行游戏。

可以在纸上试试，如果从一个空棋盘开始对你来说太难，可以从一个复杂的井字棋局面开始。

使用递归： 通常可以通过使用递归来简化这个过程。在每一层深度上，"打分"函数会被递归调用，根据深度是奇数还是偶数，分别选择最大或最小的分数来评估所有可能的动作。当没有可能的动作时，就会评估棋盘的静态分数。递归的解决方案（例如示例代码）可能会有点难以理解。

Answer 3

你的完整函数现在工作得不太对，导致游戏在任何事情发生之前就被判定为平局。比如，看看这个情况：

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