五子棋人工智能算法实现研究

《五子棋人工智能算法实现研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、五子棋人工智能算法实现研究五子棋人工智能算法实现研究五子棋是一种两人对弈的纯策略型棋类游戏，是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为连珠，英译为Renju，英文称之为Gobang或FIR（FiveinaRo.收集整理若干步之后，从可能的走法中选一步相对好的来走。若最大（MAX）节点为己方下的棋，此时选择估值最大的点走。最小（MIN）节点为对方下的棋，此时选择估值最小的点行走。因此MIN节点的父节点（MAX节点）所赋的倒推值等于端节点估值中的最大值。另一方面，MAX节点的父节点（MIN节点）

2、所赋的倒推值等于端节点估值中的最小值。这样一级一级地计算倒推值，直至起始节点的后继节点也被赋以倒推值为止，即从下往上逐层交替使用极小极大的选值方法。但当搜索深度增加时，搜索节点快速大幅增加，时间和内存空间消耗太大，且利用先前信息的效率较低。于是人们在极小极大的基础上提出了α-β剪枝技术。　　3.α-β剪枝算法。　　α-β剪枝算法[2]是在极大极小算法的基础上，当甲向下搜索节点时发现走第一个子节点就可以赢了，则剩下的节点就不需要再搜索，甲的值

3、就是第一个子节点的值。即可以将甲的其余后继节点抛弃，此过程称为剪枝。如果甲所在的层是MAX节点的层，则称此剪枝为α剪枝，否则成为β剪枝。如图1左半部所示的一棵极大极小树的片断。其中节点下方数字为该节点的值，方形框节点代表计算机走，圆形框节点代表人走。A节点表示计算机走，由于A是极大值点，根据极小极大搜索原理它要从B和C当中选最大的值。假设目前已经通过估值得出B为18，当搜索C节点时，因为C是该人走，所以根据极小极大搜索原理要从D、E、F中选取最小的值。此时如果估出D为16，那么C的值

4、必小于或等于16。又因为已经得出B的值为18，说明节点A的值为Max（B，C）=18，也就是说无须求出节点C的其他子节点如E、F的值就可以得出父节点A的值。这种将节点D的后继兄弟节点剪去的方法称为Alpha剪枝。　　同理，在图1右半部一棵极大极小树的片段中，将节点D的后继兄弟节点剪去称为Beta剪枝。与极小极大算法相比，α-β剪枝需要遍历的节点远远减少，它能在较短的时间内找到最佳的走法节点。　　二、五子棋智能算法实现及优化　　1.估值函数。　　为使用极大极小算法，需要对一个估值函数E

5、val（p）对当前棋局进行估值，p是当前局面。即由这个估值函数确定哪个局面更好，如果Eval（p1）<eval（p2），我们就有理由相信，p2比p1更好。对于五子棋而言，由其胜负判定规则可以很容易设定不同的棋型的优先级，从而得到比较合理的估值函数。例如，四个棋子连成一线且还能继续落子的棋型（活四）显然要比只有三个棋子连成一线（活三或死三）好。另外，为了尽可能地加快搜索速度，估值函数应设计的越仔细越好。估值时，需要从四个方向上来考虑所下棋子对当前盘面的影响。这四个方向分别是以该棋子为出发点，水平、竖直

6、和两条为45度角和135度角的线。算法中关于棋子死活的规定如下：一方落子后，它的落子连成的一条线有两条不损伤的出路，则称该棋型是活的。否则称该棋型是死的。比如关于活三的定义：不论对手如何落子，仍然至少有一种方法可以冲四。因此，b？aaa？B中的三个A，不能算是活三；B？AAAB中的三个A，也不是活三，尽管它有可能成为活四。这样，棋型的估值设计才能比较细致。本文算法对特定棋型的估值如表1所示。=""<br="">　　2.算法实现及优化　　使用以上定义的估值函数和描述的算法，可以实现基本的人机对弈

7、。但是在实现中，由于搜索深度增加后运算量呈指数级数增加，运算效率急剧下降。为提高搜索效率，增进用户体验，提出以下优化改进方法：　　减少搜索范围。对于19*19的五子棋棋盘而言，传统算法中计算机每走一步都要遍历整个棋盘，对棋面上所有空位都进行试探性下子并估值，大大影响了算法的效率。本文采用在某个时只要考虑距以棋子为中心边长为4的正方形区域即可，这样便缩小了搜索空间，提高搜索效率。　　减少计算量。为进一步减少计算量，提高计算机反应速度，通过以空间换时间的方法，在游戏过程中维持一个棋盘所有位置的估值信息的数组。

8、每次对棋盘上的每个位置的当前估值进行计算后，存储在当前棋局信息中。当新的棋局产生时，只需更新计算新下子位置和相关位置的估值，而对其他可下子位置的估值只需查询上步棋局信息即可。这样保持的估值表虽然增大了空间需求，但可以大大减少搜索算法的估值计算时间，提高了算法执行效率。　　三、结论及后续工作　　本文主要论述了五子棋游戏的基本游戏规则，传统五子棋人机对弈游戏的基本算法，描述了算法实现的MinMax算法和Alpha-Beta剪枝算法