对抗搜索和博弈

本笔记主要讨论对抗搜索和博弈，通过本笔记的内容，我们可以掌握解决井字棋、国际象棋、围棋的算法。

博弈论

MiniMax算法可以解决井字棋等状态空间不够大的双人零和博弈问题。

双人零和博弈就是两个人进行一场游戏，该游戏的结果要么是某一个人获胜、要么是平局，而不存在两个人都获胜的情况。在我的笔记算法>>动态规划中已经解决过Coin Game和井字棋游戏并介绍了Minimax思想。

AIMA将两个参与者分别称为MAX和MIN。这个很好理解，假设我们自己是参与者，那么我们自己就是MAX，对手就是MIN——这个MIN本身是从我们自己的角度来看的，对手为了最大化自己的利益，从而导致我们的利益在对方的轮次被最小化了。

对于国际象棋等状态空间巨大而不能使用朴素的Minimax方法的情况，我们使用Alpha-Beta剪枝。

对于围棋这样的超过宇宙原子数的状态空间的游戏，我们使用蒙特卡洛搜索树（Monte Carlo Tree Search，MCTS）。

这里主要介绍朴素MCTS方法下的早期围棋程序。AlphaGo在MCTS的核心基础上，增加了深度强化学习，从而解决了传统Rollout+手工规则卡死在新手水平的问题。