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

1、五子棋人工智能算法实现研究五子棋人工智能算法实现研究五子棋是一种两人对弈的纯策略型棋类游戏，是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为连珠，英译为Renju，英文称之为Gbang或FIRFiveinaR的缩写，亦有连五子、五子连、串珠、五目、五目碰等多种称谓1。因其规那么简单，变化多端，容易上手，而广受群众喜欢。五子棋游戏不仅能增强思维才能，进步智力，而且富含哲理，有助于修身养性。五子棋游戏规那么比拟简单，棋盘通常采用类似围棋盘的15路或19路的棋盘，两人分别执黑白两色棋子，轮流在棋盘上选择一个无子的穿插点落子，无子的穿插点又被称为空点或合法点，当黑白一方有五个棋子在横、竖或斜方

2、向上连接成一线即为该方赢。人工智能ArtifiialIntelligene，AI，是计算机科学的一个分支，是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的综合性的技术科学。该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等，而博弈是人工智能研究的一个重要分支。它不仅存在于游戏、下棋之中，也存在于政治、经济、军事和生物竞争中。与其他棋类游戏相比，五子棋游戏每一层棋局搜索节点数量庞大，规那么简单，更便于深化研究博弈算法。本文以五子棋游戏为研究对象，采用Alpha-Beta剪枝和最大最小树原理，优化了博弈树搜索过程，通过控制搜索深度，实现了初级和高级的

3、人机对弈。此外，本文还对优化五子棋智能算法的思路做出了初步讨论。一、五子棋传统算法1.人机博弈传统算法。解决博弈问题的传统算法是搜索树法，也叫博弈树法。以甲乙两人对弈五子棋为例，假定如今该甲走棋且甲有假设干种走法，而对甲的任一走法，乙也可以有与之对应的不同的多种走法，然后又轮到甲走棋，而对乙的走法甲又有假设干种方法应对，如此反复。显然，可以从当前棋局状态根节点出发，找出所有可能的乙的走法子节点，再从每个子节点出发找出甲对应于每个乙的走法的所有应对子子节点，直到出现一方赢局。由此构成的树，就称为博弈树。对于19*19的棋盘而言，显然这是一个典型的指数复杂度问题，其计算量之大是目前所有的计算机都无

4、法承受的。因此，用搜索树法来解决人机博弈时，通常只能搜索到一个非常有限的深度，并根据此有限深度的形势来判断每种走法的优劣，从而选择较优位置下子。2.极小极大值算法inax算法。极小极大算法3是考虑双方对弈本文由论文联盟.Ll.搜集整理假设干步之后，从可能的走法中选一步相对好的来走。假设最大AX节点为己方下的棋，此时选择估值最大的点走。最小IN节点为对方下的棋，此时选择估值最小的点行走。因此IN节点的父节点AX节点所赋的倒推值等于端节点估值中的最大值。另一方面，AX节点的父节点IN节点所赋的倒推值等于端节点估值中的最小值。这样一级一级地计算倒推值，直至起始节点的后继节点也被赋以倒推值为止，即从下

5、往上逐层交替使用极小极大的选值方法。但当搜索深度增加时，搜索节点快速大幅增加，时间和内存空间消耗太大，且利用先前信息的效率较低。于是人们在极小极大的根底上提出了-剪枝技术。3.-剪枝算法。-剪枝算法2是在极大极小算法的根底上，当甲向下搜索节点时发现走第一个子节点就可以赢了，那么剩下的节点就不需要再搜索，甲的值就是第一个子节点的值。即可以将甲的其余后继节点抛弃，此过程称为剪枝。假如甲所在的层是AX节点的层，那么称此剪枝为剪枝，否那么成为剪枝。如图1左半部所示的一棵极大极小树的片断。其中节点下方数字为该节点的值，方形框节点代表计算机走，圆形框节点代表人走。A节点表示计算机走，由于A是极大值点，根据

6、极小极大搜索原理它要从B和当中选最大的值。假设目前已经通过估值得出B为18，当搜索节点时，因为是该人走，所以根据极小极大搜索原理要从D、E、F中选取最小的值。此时假如估出D为16，那么的值必小于或等于16。又因为已经得出B的值为18，说明节点A的值为axB，=18，也就是说无须求出节点的其他子节点如E、F的值就可以得出父节点A的值。这种将节点D的后继兄弟节点剪去的方法称为Alpha剪枝。同理，在图1右半部一棵极大极小树的片段中，将节点D的后继兄弟节点剪去称为Beta剪枝。与极小极大算法相比，-剪枝需要遍历的节点远远减少，它能在较短的时间内找到最正确的走法节点。二、五子棋智能算法实现及优化1.估

7、值函数。为使用极大极小算法，需要对一个估值函数Evalp对当前棋局进展估值，p是当前场面。即由这个估值函数确定哪个场面更好，假如Evalp1evalp2，我们就有理由相信，p2比p1更好。对于五子棋而言，由其胜负断定规那么可以很容易设定不同的棋型的优先级，从而得到比拟合理的估值函数。例如，四个棋子连成一线且还能继续落子的棋型活四显然要比只有三个棋子连成一线活三或死三好。另外，为了尽可能地加快搜索速度，估值函数应设计的越仔细越好。估值时，需要从四个方向上来考虑所下棋子对当前盘面的影响。这四个方向分别是以该棋子为出发点，程度、竖直和两条为45度角和135度角的线。算法中关于棋子死活的规定如下：一方

8、落子后，它的落子连成的一条线有两条不损伤的出路，那么称该棋型是活的。否那么称该棋型是死的。比方关于活三的定义：不管对手如何落子，仍然至少有一种方法可以冲四。因此，b？aaa？B中的三个A，不能算是活三；B？AAAB中的三个A，也不是活三，尽管它有可能成为活四。这样，棋型的估值设计才能比拟细致。本文算法对特定棋型的估值如表1所示。=br=2.算法实现及优化使用以上定义的估值函数和描绘的算法，可以实现根本的人机对弈。但是在实现中，由于搜索深度增加后运算量呈指数级数增加，运算效率急剧下降。为进步搜索效率，增进用户体验，提出以下优化改良方法：减少搜索范围。对于19*19的五子棋棋盘而言，传统算法中计算

9、机每走一步都要遍历整个棋盘，对棋面上所有空位都进展试探性下子并估值，大大影响了算法的效率。本文采用在某个时只要考虑距以棋子为中心边长为4的正方形区域即可，这样便缩小了搜索空间，进步搜索效率。减少计算量。为进一步减少计算量，进步计算机反响速度，通过以空间换时间的方法，在游戏过程中维持一个棋盘所有位置的估值信息的数组。每次对棋盘上的每个位置的当前估值进展计算后，存储在当前棋局信息中。当新的棋局产生时，只需更新计算新下子位置和相关位置的估值，而对其他可下子位置的估值只需查询上步棋局信息即可。这样保持的估值表虽然增大了空间需求，但可以大大减少搜索算法的估值计算时间，进步了算法执行效率。三、结论及后续工作本文主要阐述了五子棋游戏的根本游戏规那么，传统五子棋人机对弈游戏的根本算法，描绘了算法实现的inax算法和Alpha-Beta剪枝算法，并描绘了算法实现的估值函数定义、数据构造等，并