例如：玩井字棋

Maxine和Minnie是真正的游戏爱好者。他们只是喜欢游戏。特别是两人完美的信息游戏，例如井字棋或国际象棋。有一天他们在玩井字棋。Maxine或者简称为MAX使用X.。Minnie或者简称为Min使用O。Min刚打完O，棋盘如下：

Max正在看着棋盘，思考她的下一步行动，因为现在轮到她了，但这时她突然绝望地捂着脸，看起来就像1997年的加里·卡斯帕罗夫(Garry Kasparov)对战深蓝。

是的，Min在第一排即将获得三个O，但Max可以轻松堵住它。那么Max为什么如此悲观呢？

游戏树

为了使用AI来解决游戏，我们将介绍游戏树的概念。游戏的不同状态由游戏树中的节点表示，与规划问题非常相似。不同的是，在游戏树中，节点按照每个玩家在游戏中的回合顺序排列，以便树的“根”节点（通常在图的顶部）是游戏中的开始位置。在井字棋中，是没有X或O的空网格。接着根下的第二级，可能由第一个玩家的落子产生的状态，无论是X还是O.我们称这些节点为根节点的“子”节点。

第二级的每个节点将根据对手下一步的落子后的状态发展下一个子节点。逐级继续，直到达到游戏结束的状态。在井字棋中，这意味着其中一个玩家可以获得三点一线并获胜，或者棋盘已满并且比赛以平局结束。

最小化值和最大化值

为了能够创建想去赢得游戏的AI，我们给每个可能的最终结果添加一个数值。对于棋盘上X有三点一线Max获胜，我们附加值+1，同样，对于Min连上三个O的情况，我们附加值-1。对于棋盘已满并且双方都没有获胜的职位，我们使用中性值0.（无论值是多少，只要按照这个顺序，Max就会尝试最大化该值，而Min会尝试最小化该值。）

游戏树示例

例如，思考下面的游戏树，它不是从根开始，而是在游戏的中盘（否则，树太大了）。请注意，这与本节开头插图中显示的那盘游戏不同。我们用数字1，2，...，14对节点进行了编号。

游戏继续在根节点中显示的棋盘位置，在顶部编号为（1），轮到Min将O放置在三个空白单元中的任何一个上。节点（2） - （4）分别显示三种选择各自产生的结果。在下一步中，每个节点有两个可能的选择让Max画X，于是树再次分支。

当从上面的起始位置开始时，这个游戏三步就结束了：在节点（7）和（9）中，获胜者是使用X的Max，节点（11） - （14）中获胜者是用O的Min。

请注意，由于玩家轮流交替，每一级标记了Max和Min用以表明轮到谁下了。

战略性思维

思考到倒数第二层上的节点（5）到（10）。在节点（7）和（9）中，游戏结束，Max赢得胜利。此时值+1。在剩下的节点（5），（6），（8）和（10）中，游戏也等于结束了，因为Min只需要将她的O放在唯一剩下的单元格中就可以获胜。换句话说，我们知道游戏如何在倒数第二层每个节点处结束。因此，我们可以确定节点（5），（6），（8）和（10）的值是-1。

有趣的部分来了。让我们思考节点（2） - （4）的值。由于我们观察到（2）的两个子节点，即节点（5）和（6）都会导致Min的胜利，我们可以毫不犹豫地将值-1附加到节点（2）。而对于节点（3），左边的子节点（7）会让Max的胜利+1，但是右边的子节点（8）会让Min的胜利-1。节点（3）的价应该是什么？这时我们要思考，谁在节点（3）做出选择。

既然轮到了Max，她当然会选择左边的子节点，节点（7）。因此，每当我们到达节点（3）中的棋盘位置，Max都可以确保胜利，并且我们可以将值+1附加到节点（3）。

节点（4）也与此相同：因为Max可以选择将X放在哪里，她总是可以确保胜利，并且我们将值+1附加到节点（4）。

确定谁赢了

本节中最重要的是如何应用上述的推理，从任何棋盘位置中提前确定游戏结果。

到目前为止，我们已经确定节点（2）的值是-1，这意味着如果我们最终处于这样一个棋盘位置，Min可以确保获胜，而节点（3）和（4）的值是+1，这意味着如果Max做出正确的选择，那么他一定能赢。

最后，我们可以推断出，由于Min是一位老玩家，她可能得出同样的结论，因此她只有一个正确的选择：在中间下O.

在下面的图表中，我们包含了每个节点的值以及从根节点开始时最优的游戏策略。

根节点的值=谁胜出

据说根节点的值是游戏的值，告诉我们谁会赢（如果结果不只是纯赢或输，也会告诉我们胜率）：Max赢得如果游戏+ 1,最小值为1,如果该值为0,那么游戏将以平局结束。在其他游戏中，值也可能为其他（例如扑克中筹码的货币价值）。

这一切都是基于这样一种假设，即双方的选择对自己最好，但对另一方最差(这就是所谓的“零和博弈”)。

Minimax算法

我们可以利用上述游戏价值的概念来理解Minimax算法。它在理论上保证了任何确定性的、双人的、完全信息的零和博弈的最佳游戏玩法。在给定游戏状态的情况下，该算法简单地计算给定状态的子节点的值，并且如果轮到Max则选择具有最大值的那个值，并且如果轮到Min则选择具有最小值的那个值。

该算法使用很少的代码就可以实现。但在这里，掌握主要思路就可以了。如果有兴趣查看实际算法（警告：需要编程），请查看（https://en.wikipedia.org/wiki/Minimax）。

听起来不错，但这就结束了吗？

如上所述，Minimax算法可用于在任何确定性的、双人的、完全信息的零和博弈中实现最佳游戏玩法。这类游戏包括井字棋，四子连珠，国际象棋，围棋等等（猜拳不属于这类游戏，因为它涉及隐藏于其他玩家的信息; 大富翁或西洋双陆棋也不是确定性的）那么，但这个主题已经结束了吗？答案是，在理论上，是的，但在实际中，没有。

更多技巧：管理大的游戏树

管理大量游戏树需要很多的技巧。其中许多是IBM深蓝计算机在1997年击败国际象棋世界冠军卡斯帕罗夫的关键因素。

如果我们只能探索游戏树的一小部分，我们需要一种方法来在到达终端节点（比如，游戏结束并且胜利者已知的节点）之前停止minimax递归。这是通过使用一个所谓的启发式评估函数来实现的，该函数以一个棋盘位置作为输入（同时包含下一个该轮到谁的信息），并返回一个分数，该分数应该是从给定棋盘位置继续进行的游戏的可能结果的估计。