AI-五子棋
核心算法及基本原理
本题核心算法是极大极小值算法以及α-β剪枝算法。极大极小值算法又称MinMax算法，是一种找出失败的最大可能性中的最小值的算法（即最小化对手的最大得益）。通常以递归形式来实现。在阐述极大极小值算法的核心思想之前，我们先探讨一下博弈树的概念。
在博弈过程中, 任何一方都希望自己取得胜利。因此,当某一方当前有多个行动方案可供选择时, 他总是挑选对自己最为有利而对对方最为不利的那个行动方案。 此时,如果我们站在A方的立场上,则可供A方选择的若干行动方案之间是“或”关系, 因为主动权操在A方手里,他或者选择这个行动方案, 或者选择另一个行动方案, 完全由A方自己决定。当A方选取任一方案走了一步后,B方也有若干个可供选择的行动方案, 此时这些行动方案对A方来说它们之间则是“与”关系，因为这时主动权操在B方手里，这些可供选择的行动方案中的任何一个都可能被B方选中, A方必须应付每一种情况的发生。 这样,如果站在某一方(如A方,即在A要取胜的意义下), 把上述博弈过程用图表示出来, 则得到的是一棵“与或树”。 描述博弈过程的与或树称为博弈树,它有如下特点：
(1) 博弈的初始格局是初始节点。
(2) 在博弈树中, “或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系, 对方扩展的节点之间是“与”关系。双方轮流地扩展节点。
(3) 所有自己一方获胜的终局都是本原问题, 相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。
在二人博弈问题中,为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案, 就需要对当前的情况以及将要发生的情况进行分析,从中选出最优的走步。最常使用的分析方法即为极大极小值算法。其基本思想是：
(1) 设博弈的双方中一方为A,另一方为B。然后为其中的一方(例如A)寻找一个最优行动方案。
(2) 为了找到当前的最优行动方案, 需要对各个可能的方案所产生的后果进行比较。具体地说, 就是要考虑每一方案实施后对方可能采取的所有行动, 并计算可能的得分。
(3) 为计算得分,需要根据问题的特性信息定义一个估价函数, 用来估算当前博弈树叶子节点的得分。此时估算出来的得分称为静态估值。
(4) 当叶子节点的估值计算出来后, 再推算出父节点的得分, 推算的方法是：对“或”节点, 选其子节点中一个最大的得分作为父节点的得分（这是为了使自己在可供选择的方案中选一个对自己最有利的方案）；对“与”节点, 选其子节点中一个最小的得分作为父节点的得分（这是为了立足于最坏的情况）。这样计算出的父节点的得分称为倒推值。
(5) 如果一个行动方案能获得最大的倒推值, 则它就是当前最好的行动方案。
在博弈问题中,每一个格局可供选择的行动方案都有很多, 因此会生成十分庞大的博弈树，试图利用完整的博弈树来进行极小极大分析是困难的。可行的办法是只生成一定深度的博弈树, 然后进行极小极大分析,找出当前最好的行动方案。在此之后再在已选定的分支上扩展一定深度, 继续选择最好的行动方案，如此进行下去，直到取得输赢的结果为止。
由于受到计算机存储空间的限制，直接使用极大极小值搜索并不能达到很深的深度，因此博弈效果也就不理想。为了解决这个问题，人们又在极小极大分析法的基础上,提出了α-β剪枝算法。 这一技术的基本思想是,边生成博弈树边计算评估各节点的倒推值, 并且根据评估出的倒推值范围,及时停止扩展那些已无必要再扩展的子节点, 即相当于剪去了博弈树上的一些分枝, 从而节约了机器开销, 提高了搜索效率，扩大了搜索深度。具体的剪枝方法如下:
(1) 对于一个与节点MIN, 若能估计出其倒推值的上确界β,并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α,即α≥β, 则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。
(2) 对于一个或节点MAX, 若能估计出其倒推值的下确界α,并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β,即α≥β,则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。 这一过程称为β剪枝。
在实现α-β剪枝算法时，对于搜索树中每一个节点对应有一个α和一个β，α表示目前该节点的最好下界，β表示目前该节点的最好上界。在最开始时，α为负无穷，β为正无穷。然后开始搜索过程，max层节点每搜索它的一个子节点，就要更新自己的α（下界），而min层节点每搜索它的一个子节点，就要更新自己的β（上界）。如果更新后发现α>=β，则说明后面的子节点已经不需要进行搜索了，直接break跳出循环，将余下的子结点均剪枝掉。这就是α-β剪枝算法的全部含义。