【AI】对抗搜索：Alpha

  对抗搜索也称为博弈搜索，在一个竞争的环境中，智能体之间通过竞争实现相反的利益，一方最大化这个利益，另外一方最小化这个利益。   最小最大搜索(Minimax Search)是对抗搜索中最为基本的方法，给定一个游戏搜索树，Minimax算法通过每个节点的Minimax值来决定最优策略，当然，MAX希望最大化Minimax值，而MIN则相反。Minimax是一种简单有效的对抗搜索手段 ，但是如果搜索树极大，则无法在有效时间内返回结果。   Alpha-Beta剪枝搜索(Pruning Search)是一种对Minimax进行改进的算法，即在搜索过程中可剪除无需搜索的分支节点，且不影响搜索结果。

   α {\alpha} α：玩家MAX目前得到的最高收益；假设 n {n} n 是MIN节点，如果 n {n} n 的一个后续节点可提供的收益小于𝛼，则 n {n} n 及其后续节点可被剪枝。    β {\beta} β：玩家MIN目前给对手的最小收益；假设 n {n} n 是MAX节点，如果 n {n} n 的一个后续节点可获得收益大于𝛽，则 n {n} n 及其后续节点可被剪枝。    α {\alpha} α 和 β {\beta} β 的值初始化分别设置为 − ∞ {-\infty} −∞和 + ∞ {+\infty} +∞。   搜索过程即为：每个节点有两个值，分别是 α {\alpha} α 和 β {\beta} β 。节点的 α {\alpha} α 和 β {\beta} β 值在搜索过程中不断变化。其中， α {\alpha} α 从负无穷大( − ∞ {-\infty} −∞)逐渐增加、 β {\beta} β 从正无穷大( + ∞ {+\infty} +∞)逐渐减少。如果一个节点中 α {\alpha} α > β {\beta} β ，则该节点的后续节点可剪枝。

  上面的规则可能有点抽象，下面我将从人机井字棋对战来图解Alpha-Beta剪枝搜索；   首先我们需要进行一些设置：   (1)电脑：Max玩家，其落子符号表示为“O”，落子数值表示为“1”；   (2)人类：Min玩家，其落子符号表示为“X”，落子数值表示为“-1”；   (3)棋盘最终为电脑赢，则得分为1，若为人类赢，则得分为-1，若为平局，得分为0；   (4)由于棋盘最终得分只有三种情况-1、0、1，那么 α {\alpha} α 初始值可设为-2， β {\beta} β 初始值可设为2；

  假设我们的棋局到了图中蓝色九宫格的情况，现在还剩三个空位置：3、5、6号位可以落子，下一步该Max玩家(电脑)落子，此时，电脑就要思考了，我下哪一个位置更有利呢？   如果电脑落子为3，交换玩家后，人类落子为5，那么电脑最后落子为6，那么电脑将会胜利，如此电脑将会计算之后所有的落子情况。如下图所示，我们可以看到，当电脑这一步落子为6时，最后的结果是电脑胜利或者平局，相比于其他两种存在人类胜利的情况来说，落子为6当是最佳选择，但是怎么样让电脑知道6是最佳选择呢？   图中方框代表Max节点，圆圈代表Min节点，绿色数字代表此时选择落子的位置，蓝色数字代表最终棋盘得分，-1代表Min玩家胜利，1代表Max玩家胜利，0代表平局。

  此时我们的 α {\alpha} α 和 β {\beta} β 就派上用场了！   每个节点设置有 α {\alpha} α 和 β {\beta} β 值，在搜索中不断更新。   更新规则为：   (1)Max节点，只更新 α {\alpha} α 值，更新为Max(当前 α {\alpha} α ，下一节点 α {\alpha} α，下一节点 β {\beta} β )；   (2)Min节点，只更新 β {\beta} β 值，更新为Min(当前 β {\beta} β ，下一节点 α {\alpha} α，下一节点 β {\beta} β )；   (3)更新顺序为先左支向下传递，后左支向上更新，再右支向下传递，后右支向上更新；

如图，展示的是左边第一棵树的更新，紫色虚线表示逐步的更新流程。 [1]、[2]步表示左支向下传递，直接将 α {\alpha} α 和 β {\beta} β 值向下传递到最后一个节点； [3]、[4]步表示左支向上更新：   Max节点只更新 α {\alpha} α，Max(当前 α {\alpha} α=-2，下一层只有1) = 1 ——> α {\alpha} α =1 ， β {\beta} β =2   Min节点只更新 β {\beta} β，Min(当前 β {\beta} β=2，下一层 α {\alpha} α=1，下一层 β {\beta} β=2) = 1 ——> α {\alpha} α =-2 ， β {\beta} β =1 [5]、[6]步表示右支向下传递，直接父节点 α {\alpha} α 和 β {\beta} β 更新后的值向下传递到最后一个节点； [7]、[8]步表示右支向上更新：   Max节点只更新 α {\alpha} α，Max(当前 α {\alpha} α=-2，下一层只有-1) = -1 ——> α {\alpha} α =-1 ， β {\beta} β =1   Min节点只更新 β {\beta} β，Min(当前 β {\beta} β=1，下一层 α {\alpha} α=-1，下一层 β {\beta} β=1) = -1 ——> α {\alpha} α =-2 ， β {\beta} β =-1

图中，红色框为第一次更新结果，黄色框中为节点第二次更新结果。

  同理，我们可以按照上面的流程得到所有节点的更新值，最后得到Min层，三个节点的黄色更新框。   对于最顶层的Max节点来说，它需要选择Min层中 β {\beta} β最大的那个节点对应的选项，这样可以给对手造成最小的收益。   (1)选择3号位： β {\beta} β= -1   (2)选择5号位： β {\beta} β= -1   (3)选择6号位： β {\beta} β= 0   由于对手是Min玩家，需要 β {\beta} β 值越小越好，那么Max玩家要使Min玩家收益最小，就应当选择 β {\beta} β 最大的节点，即电脑此时应当选择6号位。    图中的青色方框显示的是 α {\alpha} α ≥ β {\beta} β 的情况，如果该节点下面还有节点，就可以进行剪枝，即，其下面的节点不必再进行搜索了。

   按照上述的搜索流程，我们就可以进行人机井字棋对战了。实际搜索树会更复杂一些，上面的图解是简化到只剩3步的情况，方便大家理解 α {\alpha} α 和 β {\beta} β更新的过程。

运行一盘试试：

让电脑赢一局：

参考资料 浙江大学吴飞老师：《人工智能：模型与算法》 Alpha-Beta剪枝算法（人工智能）