对抗搜索和博弈

我们探讨了各种各样的博弈，以理解什么是最佳玩法以及如何在实际中玩好游戏，还了解了智能体在任意类型的对抗性环境中应该如何行动。最重要的思想如下。

● 博弈可以由初始状态（棋盘如何设置）、每个状态下的合法动作、每个动作的结果、终止测试（说明什么时候博弈结束）以及应用于终止状态表明输赢和最终比分的效用函数定义。

● 在具有完美信息的离散、确定性、轮流的双人零和博弈中，极小化极大算法可以通过对博弈树的深度优先枚举选出最优移动。

●alpha-beta搜索算法可以计算出与极小化极大算法相同的最优移动，通过消除可证明与结果无关的子树来提高效率。

● 通常，考虑整个博弈树是不可行的（即使是alpha-beta搜索），所以我们需要在某个点截断搜索，然后应用启发式评价函数估计状态的效用值。

● 蒙特卡罗树搜索(MCTS)则是另一种方法，它不是通过应用启发式函数来评估状态，而是通过将游戏模拟到结束使用游戏规则来判断输赢。因为在模拟过程中选择的移动可能不是最优移动，所以这个过程需要重复多次，对结果求平均值作为评估值。

● 许多游戏程序会预先计算开局和残局的最佳移动表，这样它们就可以直接查表而不用搜索。● 机会博弈可以通过期望极小化极大算法（极小化极大算法的扩展）来处理，该算法通过计算所有子节点的平均效用值并按每个子节点的概率加权来估计机会节点的平均效用值。

● 在不完美信息博弈中，例如四国军棋和扑克，最佳玩法需要对每个玩家当前和将来的信念状态进行推理。可以通过对缺失信息的每种可能配置上的动作值取平均得到一个简单的近似。

● 在国际象棋、跳棋、黑白棋、围棋、扑克及许多其他游戏中，程序已经彻底击败了人类冠军选手。在一些不完美信息博弈中人类仍然保持优势，如桥牌和四国军棋。在像《星际争霸》和《刀塔2》这样的电子游戏中，程序可以与人类专家媲美，但它们的成功可能一部分要归功于它们可以快速执行许多动作的能力。