13-现实世界的应用

8.5　现实世界的应用

极小化极大算法外加α-β剪枝之类的扩展，是大多数现代国际象棋引擎的基础。这已被广泛应用于各种策略游戏中并取得了巨大的成功。事实上，计算机上的大多数棋盘游戏类人工棋手可能都用到了某种形式的极小化极大算法。

极小化极大算法（带有α-β剪枝之类的扩展）在国际象棋中如此有效以致导致了著名的1997年发生的“深蓝”（Deep Blue）事件，由IBM公司制造的国际象棋计算机选手“深蓝”击败人类国际象棋世界冠军加里·卡斯帕罗夫（Gary Kasparov）。这场比赛是备受期待和改变游戏规则的事件。国际象棋曾被视为最顶尖的智能领域。计算机在国际象棋中超越了人类的能力，这个事实意味着人工智能在某种程度上应该被认真对待。

20多年后的今天，绝大多数国际象棋引擎仍然基于极小化极大算法。今天，基于极小化极大算法的国际象棋引擎的实力已远超世界上最好的人类国际象棋选手。新的机器学习技术正在开始挑战纯粹基于极小化极大算法（带扩展）的国际象棋引擎，但还没有明确的证据表明机器学习技术在国际象棋中的优势。

游戏的支化因子（branching factor）越高，极小化极大算法的效果就会越差。支化因子是指游戏的一个棋局中可能走法数量的平均值。正因为如此，围棋中的计算机棋手最近取得的一些进步有赖于机器学习之类的其他领域的研究。现在，基于机器学习的围棋AI已经击败了最好的人类围棋棋手。围棋的支化因子（也就是搜索空间）对于极小化极大算法来说简直太庞大了，因为这种算法需要尝试生成包含未来棋局的决策树。但围棋只是一个例外，而不是一定之规。大多数传统棋盘游戏（如跳棋、国际象棋、四子棋、拼字游戏等）的搜索空间都比较小，基于极小化极大算法的技术可足以应对了。

若要新实现一个棋盘游戏人工棋手，甚至是回合制的纯计算机游戏AI，极小化极大算法可能是你首先应该接触的算法。极小化极大算法还可用于经济和政治领域的模拟，以及博弈论实验。α-β剪枝应该能适用于任何形式的极小化极大算法。