15

我浪费了一整天的时间来尝试使用 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'
4

3 回答 3

19

第 1 步：构建游戏树

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

这看起来像一棵树，你自己在一张纸上画，当前棋盘在顶部，所有对手都在下一层移动，你所有可能的移动响应下一层等等。

第 2 步：对树底部的所有板进行评分

对于像井字游戏这样的简单游戏，如果您输了，则得分为 0，平局为 50，赢率为 100。

第 3 步：将分数向上传播

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

第 4 步：选择最佳动作

现在，从当前位置开始，在您所有可能的游戏中，采取能够产生最佳传播分数的动作。

在一张纸上试一试，如果从空白板开始对你来说太多了，请从一些高级井字游戏位置开始。

使用递归： 通常这可以通过使用递归来简化。“评分”函数在每个深度递归调用，取决于深度是奇数还是偶数，它分别为所有可能的移动选择最大值或最小值。当不可能移动时，它会评估棋盘的静态分数。递归解决方案（例如示例代码）可能有点难以掌握。

于 2010-10-18T03:01:07.357 回答
7

正如您已经知道的那样，Minimax 的想法是深入寻找最佳价值，假设对手总是以最差的价值下棋（对我们最差，对他们最好）。

这个想法是，您将尝试为每个职位赋予价值。你输的位置是负的（我们不希望这样），你赢的位置是正的。你假设你总是会争取最高价值的位置，但你也假设对手总是瞄准价值最低的位置，这对我们来说是最坏的结果，对他们来说是最好的（他们赢了，我们输了）。所以你设身处地为他们着想，尽可能地发挥他们的水平，并假设他们会那样做。
因此，如果您发现您可能有两种移动方式，一种是让他们选择输赢，一种是让他们选择输赢，一种是无论如何都会导致平局，您认为如果您让他们这样做，他们就会采取让他们获胜的行动。所以最好去抽奖。

现在来看一个更“算法”的视图。

想象一下，除了两个可能的位置之外，您的网格几乎已满。
考虑一下当你玩第一个时会发生什么：
对手将玩另一个。这是他们唯一可能的举动，因此我们不必考虑他们的其他举动。查看结果，关联一个结果值（如果获胜则为 +∞，如果平局则为 0，如果失败则为 -∞：对于井字游戏，您可以将它们表示为 +1 0 和 -1）。
现在考虑当你玩第二个时会发生什么：（
同样的事情，对手只有一个动作，看看结果位置，重视位置）。

你需要在这两个动作之间做出选择。这是我们的行动，所以我们想要最好的结果（这是极小极大中的“极大”）。选择结果较高的那一个作为我们的“最佳”动作。这就是“从末端开始移动 2 步”的示例。

现在想象你剩下的不是 2 个，而是 3 个。
原理是一样的，你要为你的 3 个可能的移动中的每一个分配一个值，这样你就可以选择最好的。
因此，您首先要考虑三个动作之一。
您现在处于上述情况，只有 2 个可能的移动，但轮到对手了。然后你开始考虑对手可能采取的行动之一，就像我们在上面所做的那样。同样，您查看每个可能的移动，并为它们找到一个结果值。这是对手的走法，所以我们假设他们会为他们下“最好”的走法，对我们来说投票率最低的走法，所以它是价值较小的走法（这是极小极大中的“最小值”）。忽略另一个；假设他们无论如何都会播放你认为最适合他们的东西。这就是您的移动将产生的结果，因此它是您分配给三个移动中的第一个的值。

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

现在考虑 4 步会发生什么。对于您的 4 个动作中的每一个，您都查看对手的 3 个动作会发生什么，并且对于每个动作，您假设他们会从剩下的 2 个动作中为您选择可能给您带来最坏结果的一个动作。

你看这会走向何方。要评估从末尾开始 n 步的移动，您需要查看 n 个可能移动中的每一个可能发生的情况，并尝试给它们一个值，以便您可以选择最好的。在此过程中，您必须尝试为 n-1 的玩家找到最佳移动：对手，并选择价值较小的一步。在评估 n-1 步的过程中，您必须在可能的 n-2 步中进行选择，这将是我们的，并假设我们在这一步会玩得尽可能好。等等。

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

对于井字游戏来说，今天的机器已经足够强大，可以从游戏开始就计算出所有可能的结果，因为只有几百个。当您希望为更复杂的游戏实现它时，您将不得不在某个时候停止计算，因为这将花费太长时间。因此，对于复杂的游戏，您还必须编写代码来决定是继续寻找所有可能的下一步行动，还是尝试为现在的位置赋值并提前返回。这意味着您还必须计算一个非最终位置的值 - 例如，对于国际象棋，您将考虑每个对手在棋盘上拥有多少材料，在没有同伴的情况下立即过牌的可能性，您控制的瓷砖数量以及所有，这使得它不是微不足道的。

于 2010-10-18T02:59:31.447 回答
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

这应该是下一步计算机的胜利。相反，它说比赛是平局。

问题是你的逻辑现在完整，检查组合中的所有方块是否都是免费的。如果其中任何一个不是，则假定无法赢得该组合。它需要做的是检查该组合中是否有任何位置被占用，只要所有这些组合都不是 None 或同一玩家，则该组合应该被认为仍然可用。

例如

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
于 2010-10-18T12:28:33.560 回答