​

五子棋游戏规则比较大略，棋盘常日采取类似围棋盘的15路或19路的棋盘，两人分别执黑白两色棋子，轮流在棋盘上选择一个无子的交叉点落子，无子的交叉点又被称为空点或合法点，当黑白一方有五个棋子在横、竖或斜方向上连接成一线即为该方赢。

人工智能（Artificial Intelligence，AI），是打算机科学的一个分支，是研究、开拓用于仿照、延伸和扩展人的智能的理论、方法、技能及运用系统的一门新的综合性的技能科学。
该领域的研究包括机器人、措辞识别、图像识别、自然措辞处理和专家系统等，而博弈是人工智能研究的一个主要分支。
它不仅存在于游戏、下棋之中，也存在于政治、经济、军事和生物竞争中。
与其他棋类游戏比较，五子棋游戏每一层棋局搜索节点数量弘大，规则大略，更便于深入研究博弈算法。
本文以五子棋游戏为研究工具，采取Alpha-Beta剪枝和最大最小树事理，优化了博弈树搜索过程，通过掌握搜索深度，实现了低级和高等的人机对弈。
本文还对优化五子棋智能算法的思路做出了初步磋商。

一、 五子棋传统算法

1.人机博弈传统算法。

办理博弈问题的传统算法是搜索树法，也叫博弈树法。
以甲乙两人对弈五子棋为例，假定现在该甲走棋且甲有多少种走法，而对甲的任一走法，乙也可以有与之对应的不同的多种走法，然后又轮到甲走棋，而对乙的走法甲又有多少种方法应对，如此反复。
显然，可以从当前棋局状态（根节点）出发，找出所有可能的乙的走法（子节点），再从每个子节点出发找出甲对应于每个乙的走法的所有应对（子子节点），直到涌现一方赢局。
由此构成的树，就称为博弈树。
对付1919的棋盘而言，显然这是一个范例的指数繁芜度问题，其打算量之大是目前所有的打算机都无法承受的。
因此，用搜索树法来办理人机博弈时，常日只能搜索到一个非常有限的深度，并根据此有限深度的形势来判断每种走法的利害，从而选择较优位置下子。

2. 极小极大值算法（MinMax 算法）。

极小极大算法[3]是考虑双方对弈本文由论文同盟http://www.LWlm.cOm网络整理多少步之后， 从可能的走法中选一步相对好的来走。
若最大（MAX）节点为己方下的棋，此时选择估值最大的点走。
最小（MIN）节点为对方下的棋，此时选择估值最小的点行走。
因此MIN节点的父节点（MAX节点）所赋的倒推值即是端节点估值中的最大值。
另一方面，MAX节点的父节点（MIN节点）所赋的倒推值即是端节点估值中的最小值。
这样一级一级地皮算倒推值，直至起始节点的后继节点也被赋以倒推值为止，即从下往上逐层交替利用极小极大的选值方法。
但当搜索深度增加时，搜索节点快速大幅增加，韶光和内存空间花费太大，且利用先前信息的效率较低。
于是人们在极小极大的根本上提出了α-β剪枝技能。

3. α-β剪枝算法。

α-β剪枝算法[2]是在极大极小算法的根本上，当甲向下搜索节点时创造走第一个子节点就可以赢了，则剩下的节点就不须要再搜索，甲的值便是第一个子节点的值。
即可以将甲的别的后继节点抛弃，此过程称为剪枝。
如果甲所在的层是MAX 节点的层，则称此剪枝为α剪枝，否则成为β剪枝。
如图1左半部所示的一棵极大极小树的片断。
个中节点下方数字为该节点的值，方形框节点代表打算机走，圆形框节点代表人走。
A节点表示打算机走，由于A是极大值点，根据极小极大搜索事理它要从B和C当中选最大的值。
假设目前已经通过估值得出B为18，当搜索C节点时，由于C是该人走，以是根据极小极大搜索事理要从D、E、F中选取最小的值。
此时如果估出D为16，那么C的值必小于或即是16。
又由于已经得出B的值为18，解释节点A的值为Max（B，C）=18，也便是说无须求出节点C的其他子节点如E、F的值就可以得出父节点A的值。
这种将节点D 的后继兄弟节点剪去的方法称为Alpha剪枝。

同理，在图1右半部一棵极大极小树的片段中，将节点D 的后继兄弟节点剪去称为Beta 剪枝。
与极小极大算法比较，α-β剪枝须要遍历的节点远远减少，它能在较短的韶光内找到最佳的走法节点。

二、 五子棋智能算法实现及优化

1. 估值函数。

为利用极大极小算法，须要对一个估值函数Eval （p）对当前棋局进行估值，p是当前局势。
即由这个估值函数确定哪个局势更好，如果Eval（p1）<eval（p2），我们就有情由相信，p2比p1更好。
对付五子棋而言，由其胜负剖断规则可以很随意马虎设定不同的棋型的优先级，从而得到比较合理的估值函数。
例如，四个棋子连成一线且还能连续落子的棋型（活四）显然要比只有三个棋子连成一线（活三或去世三）好。
其余，为了尽可能地加快搜索速率，估值函数应设计的越仔细越好。
估值时，须要从四个方向上来考虑所下棋子对当前盘面的影响。
这四个方向分别因此该棋子为出发点，水平、竖直和两条为45度角和135度角的线。
算法中关于棋子去世活的规定如下：一方落子后，它的落子连成的一条线有两条不损伤的出路，则称该棋型是活的。
否则称该棋型是去世的。
比如关于活三的定义：不论对手如何落子，仍旧至少有一种方法可以冲四。
因此，b？aaa？ B中的三个A，不能算是活三；B？AAAB中的三个A，也不是活三，只管它有可能成为活四。
这样，棋型的估值设计才能比较细致。
本文算法对特定棋型的估值如表1所示。
=\"大众\"大众

2. 算法实现及优化

利用以上定义的估值函数和描述的算法，可以实现基本的人机对弈。
但是在实现中，由于搜索深度增加后运算量呈指数级数增加，运算效率急剧低落。
为提高搜索效率，匆匆进用户体验，提出以下优化改进方法：

减少搜索范围。
对付1919的五子棋棋盘而言，传统算法中计算机每走一步都要遍历全体棋盘，对棋面上所有空位都进行试探性下子并估值，大大影响了算法的效率。
本文采取在某个时只要考虑距以棋子为中央边长为4的正方形区域即可，这样便缩小了搜索空间，提高搜索效率。

减少打算量。
为进一步减少打算量，提高打算机反应速率，通过以空间换韶光的方法，在游戏过程中坚持一个棋盘所有位置的估值信息的数组。
每次对棋盘上的每个位置确当前估值进行打算后，存储在当前棋局信息中。
当新的棋局产生时，只需更新打算新下子位置和干系位置的估值，而对其他可下子位置的估值只需查询上步棋局信息即可。
这样保持的估值表虽然增大了空间需求，但可以大大减少搜索算法的估值打算韶光，提高了算法实行效率。

传统五子棋人机对弈游戏的基本算法，描述了算法实现的MinMax算法和Alpha-Beta剪枝算法，并描述了算法实现的估值函数定义、数据构造等，并通过减少搜索范围、减少打算量和设置对弈等级的方法，对算法进行初步优化，提高了算法性能，匆匆进了人机对弈的用户体验。
下步事情紧张是通过改进算法和增加搜索赞助手段的办法，探索剖析优化搜索性能的方法。
比如，结合利用启示式搜索，利用五子棋游戏开局阶段现成的棋谱，进行启示式搜索，或者加入自学习功能等。

在不久的将来，多智时期一定会彻底走入我们的生活，有兴趣入行未来前沿家当的朋友，可以收藏多智时期，及时获取人工智能、大数据、云打算和物联网的入门知识和资讯信息，让我们一起携手，引领人工智能的未来