蒙特卡洛树搜索$(MCTS)$
对围棋来说，$\alpha $-$\beta $启发式树搜索有两个主要缺点：首先，围棋的分支因子开始时为 361，这意味着$\alpha $-$\beta $搜索被限制在 4～5 层。其次，很难为围棋定义一个好的评价函数，因为子力价值并不是一个强有力的指标，而且大多数状态直到最后阶段都在不断变化。为了应对这两个挑战，现代围棋程序已经放弃了$\alpha $-$\beta $搜索，而是使用一种称为蒙特卡罗树搜索（Monte Carlo tree search，MCTS）的策略。
基本的$MCTS$策略不使用启发式评价函数。相反，状态值是根据从该状态开始的多次完整博奕模拟的平均效用值估算的。一次模拟先为一个参与者选择移动，接着为另一个参与者选择，重复上述操作直到到达某个终止局面。这时，博弈规则（而非不可靠的启发式）决定输赢以及比分。对于那些只有输赢两种结果的博弈，“平均效用值”为“获胜百分比”。
在模拟中如果只是随机选择要采取的移动，那么多次模拟之后，能得到仅是“如果两个参与者都随机选择，那么最佳移动是什么？”这一问题的答案。对于一些简单游戏，这恰好是最佳移动是什么的答案。但对大多数游戏却并非如此。为了从模拟中获得有用信息，需要一个模拟策略，使其偏向于好的行动。对围棋和其他游戏来说，人们已经使用神经网络成功地从自我对弈中学习到了模拟策略。有时还会根据游戏的不同，使用不同的启发式方法，如国际象棋中的“考虑吃子”，或黑白棋中的“占据角落”。
在有一个模拟策略以后还需要确定从什么局面开始模拟，以及分配给每个局面多少次模拟。最简单的答案是纯蒙特卡罗搜索，即从博弈当前状态开始做$N$次模拟，并记录从当前局面开始哪一种可能移动胜率最高。
对于一些随机游戏，随着$N$的增加，这一策略会收敛到最优策略，但对大多数博弈来说，这还不够，搜索仍然需要一个选择策略，有选择地将计算资源集中在博弈树的重要部分上。选择策略需要平衡两个因素以做出更准确的估计：对那些模拟次数很少的状态的探索，以及对那些在过去的模拟中表现良好的状态的利用。
蒙特卡罗树搜索维护一个搜索树，它在每次迭代（包含以下 4 个步骤）中不断增长：
1、选择：从搜索树的根节点开始，选择一个移动（在选择策略的指导下），到达一个后继节点，然后重复该过程，沿着树向下移动到叶节点。
2、扩展：通过为所选叶子节点生成一个新的子节点的方式增长搜索树。
3、模拟：从新生成的子节点开始执行一次模拟，根据模拟策略为两个参与者选择移动。这些移动不会记录在搜索树中。
4、反向传播：我们现在使用模拟结果自底向上地更新所有搜索树节点。
在固定次数的迭代中重复这 4 个步骤，或者迭代到所分配的时间耗尽，然后返回模拟次数最多的移动（通常是目前取得较好结果且在未来可能取得更大成功的节点）。一种非常有效的选择策略称为“应用于树搜索的置信上界”，即$UCT$。它根据称为$UCB1$的置信上界公式对每个可能的移动排序。对节点$n$来说，公式为：
$$
UCB1\left( n \right) =\frac{U\left( n \right)}{N\left( n \right)}+C\times \sqrt{\frac{\log _N\left( Parent\left( n \right) \right)}{N\left( n \right)}}
$$
其中$U(n)$为经过节点$n$的所有模拟的总效用值，$N(n)$是经过节点$n$的模拟次数，$Parent(n)$是树中 n 的父节点。因此$\frac{U\left( n \right)}{N\left( n \right)}$为利用项，即节点$n$的平均效用值。带有平方根的项是探索项：分母为$N(n)$，这意味着对只探索过几次的节点来说，这一项的值比较高；分子记录了对$n$的父节点的探索次数，这意味着，如果选择$n$的概率不是$0$，那么随着计数的增加，探索项会趋于零，最终模拟次数将被分配给平均效用值最高的节点。$C$是一个平衡利用和探索的常数。有一种理论认为$C$应该是$\sqrt{2} $，但在实践中，程序员会尝试多个$C$值，从中选择一个表现最好的。
在任何情况下，$UCB1$公式确保模拟次数最多的节点几乎总是拥有最高的获胜概率，因为随着模拟次数的增加，选择过程将越来越偏向获胜概率。
计算一次模拟结果的时间对博弈树的深度来说是线性的，而不是指数级的，因为在每个选择点上只采用一个移动。这样就有足够的时间进行多次模拟。例如，假设有一个分支因子为 32 的博弈，博弈平均持续 100 步。如果有足够的计算能力可以在执行移动前考虑 10 亿个博弈状态，那么极小化极大算法可以搜索 6 层深度，具有完美行动顺序的$\alpha $-$\beta $算法可以搜索 12 层深度，蒙特卡罗搜索算法可以搜索 1000 万次模拟。哪种方法更好呢？这取决于所用的启发式函数与选择策略、模拟策略的准确性的高下。
传统观点认为，对于围棋这种分支因子非常高（因此$\alpha $-$\beta $搜索不够深）或者很难定义一个好的评价函数的游戏，蒙特卡罗搜索要优于$\alpha $-$\beta $搜索。考虑到对手的目标是最小化得分，$\alpha $-$\beta $搜索将选择指向可实现评价函数得分最高的节点的路径。因此，如果评价函数不准确，$\alpha $-$\beta $搜索也会不准确。对单个节点的错误计算可能导致$\alpha $-$\beta $搜索错误地选择（或避开）指向该节点的路径。而蒙特卡罗搜索依赖于多次模拟的聚合，因此不容易受到单次错误的影响。也可以将$\alpha $-$\beta $搜索和蒙特卡罗搜索结合，对一定数量的移动进行模拟，然后截断模拟，并在截断的节点上应用评价函数。
蒙特卡罗搜索可以应用于没有任何经验可以用来定义评价函数的全新博弈。只要知道博弈规则，蒙特卡罗搜索不需要任何附加信息。选择和模拟策略可以充分利用人工制定的专家知识，也可以通过仅仅使用自我对弈训练得到的神经网络来学习好的策略。当单步移动可以改变游戏进程时，蒙特卡罗搜索存在缺陷，因为蒙特卡罗搜索的随机性意味着它可能不会考虑这一移动。换句话说，蒙特卡罗搜索中的 B 型剪枝意味着它可能根本没有探索关键路线。当博弈状态“明显”是一方或另一方获胜时（根据人类的知识和评价函数），蒙特卡罗搜索也存在缺陷，它仍然需要模拟很多步来验证获胜者。
随机博弈
包含随机因素（例如掷骰子）的随机博弈使博弈搜索更接近现实生活的不可预测性。这意味着黑方无法构建标准博弈树，这种情况下的博弈树除了$max$和$min$节点外，还必须包括机会节点。由于局面没有明确的极小化极大值，因此只能计算局面的期望值：机会节点所有可能结果的平均值。
可以将确定性博弈的极小化极大值推广为包含机会节点的博弈的期望极小化极大值。终止节点、$max$节点和
$min$节点的工作方式与之前完全相同（注意，$max$和$min$的合法移动取决于前一个机会节点的掷骰子结果）。对于机会节点，则计算期望值，即用每个机会动作的概率加权的所有结果的值之和：
$$
Expectiminimax\left( s \right) =\begin{cases}
Utility\left( s,Max \right)& Is\,\,Terminal\left( s \right)\\
\underset{a}{max}Expectiminimax\left( \text{Re}sult\left( s,a \right) \right)& To\,\,Move\left( s \right) =Max\\
\underset{a}{min}Expectiminimax\left( \text{Re}sult\left( s,a \right) \right)& To\,\,Move\left( s \right) =Min\\
\sum_n{P\left( r \right) \cdot Expectiminimax\left( \text{Re}sult\left( s,r \right) \right)}& To\,\,Move\left( s \right) =Chance\\
\end{cases}
$$
其中，$r$表示可能的掷骰子结果（或其他概率事件），而$Result(s,r)$仍表示状态$s$，附加了掷骰子结果$r$。
和极小化极大算法一样，可以通过在某点截断搜索并对每个叶节点应用评价函数来近似估计期望极小化极大值。机会节点的存在意味着必须更加仔细地定义评价函数值，因为如果更改一些评估值，即使优先顺序保持不变，程序的选择也会完全不同。为了避免这一问题，评价函数应该返回获胜概率（对于结果非输或赢的博弈返回的是期望效用值）的正线性变换值，这是在不确定性下非常重要和普遍的性质。
如果程序事先知道游戏接下来的所有掷骰子结果，那么求解有骰子的游戏和求解没有骰子的游戏是一样的，即极小化极大算法的时间复杂度为$O(b^m)$，其中$b$为分支因子，$m$为博弈树的最大深度。因为期望极小化极大值还要考虑所有可能的掷骰子序列，它的时间复杂度为$O(b^mn^m)$，其中$n$是掷骰子的不同结果的数目。即使将搜索深度限制在某个很小的值$d$内，与极小化极大算法相比，额外代价的存在也使得在大多数机会博弈中向前看很远是不现实的。
对抗搜索的局限性
计算复杂博弈中的最优决策是非常困难的，因此所有算法都必须做出一些假设和近似。$\alpha $-$\beta $搜索使用启发式评价函数作为近似，而蒙特卡罗搜索计算随机选择的模拟的近似平均值。选择哪种算法在一定程度上取决于每种博弈的特征：当分支因子较高或评价函数难以定义时，首选蒙特卡罗搜索。但这两种算法都存在其基本的局限性。
$\alpha $-$\beta $搜索的一个局限性是它容易受到启发式函数的近似误差的影响。如果所有的评估值都是精确的，那么就是正确的选择。但假设每个节点的评估值都有一个独立于其他节点的随机分布的误差，那么实际上有较大概率的情况下是其他分支更好。如果评价函数中的误差不是独立的，那么发生错误的可能性更大。这是很难避免的，因为没有一个很好的兄弟节点值之间依赖关系的模型。
$\alpha $-$\beta $搜索和蒙特卡罗搜索的第二个局限性是，它们都是设计用于计算合法移动的（边界）值的。但有时其中一种移动显然是最佳的，在这种情况下，浪费时间计算它的值是没有意义的——最好是直接选择该移动。更好的搜索算法应该使用节点扩展的效用值的思想，选择效用值高的节点扩展，所谓高效用值的节点是指，有可能导致算法发现一个明显更好的移动。如果没有一个节点扩展的效用值高于它的代价（从时间上考虑），那么算法应该停止搜索并执行一个移动。这不仅适用于存在明显更好移动的情况，也适用于对称情况，在这种情况下，再多的搜索也无法证明一种移动比另一种更好。
第三个局限性是$\alpha $-$\beta $搜索和蒙特卡罗搜索都是在单步移动的层级上进行所有推理的。显然，这与人类玩游戏的方式不同：人类可以在更抽象的层级上进行推理，会考虑更高层级的目标（例如，诱捕对方的后），并使用该目标有选择地生成看似合理的规划。
第四个问题是能否将机器学习融入博弈搜索过程。早期的游戏程序依靠人类的专业知识人为制定评价函数、开局库、搜索策略和高效技巧。像 AlphaZero 这样的程序依赖于自我对弈的机器学习，而非人类在特定游戏上的专业知识。
