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

1/5五子棋人工智能算法实现研究五子棋人工智能算法实现研究五子棋是一种两人对弈的纯策略型棋类游戏，是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连珠”，英译为“RENJU”，英文称之为“GOBANG”或“FIR”，亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”等多种称谓1。因其规则简单，变化多端，容易上手，而广受大众喜爱。五子棋游戏不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋游戏规则比较简单，棋盘通常采用类似围棋盘的15路或19路的棋盘，两人分别执黑白两色棋子，轮流在棋盘上选择一个无子的交叉点落子，无子的交叉点又被称为空点或合法点，当黑白一方有五个棋子在横、竖或斜方向上连接成一线即为该方赢。人工智能，是计算机科学的一个分支，是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的综合性的技术科学。该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等，而博弈是人工智能研究的一个重要分支。它不仅存在于游戏、下棋之中，也存在于政治、经济、军事和生物竞争中。与其他棋类游戏相比，五子棋游戏每一层棋局搜2/5索节点数量庞大，规则简单，更便于深入研究博弈算法。本文以五子棋游戏为研究对象，采用ALPHABETA剪枝和最大最小树原理，优化了博弈树搜索过程，通过控制搜索深度，实现了初级和高级的人机对弈。此外，本文还对优化五子棋智能算法的思路做出了初步探讨。一、五子棋传统算法1人机博弈传统算法。解决博弈问题的传统算法是搜索树法，也叫博弈树法。以甲乙两人对弈五子棋为例，假定现在该甲走棋且甲有若干种走法，而对甲的任一走法，乙也可以有与之对应的不同的多种走法，然后又轮到甲走棋，而对乙的走法甲又有若干种方法应对，如此反复。显然，可以从当前棋局状态出发，找出所有可能的乙的走法，再从每个子节点出发找出甲对应于每个乙的走法的所有应对，直到出现一方赢局。由此构成的树，就称为博弈树。对于1919的棋盘而言，显然这是一个典型的指数复杂度问题，其计算量之大是目前所有的计算机都无法承受的。因此，用搜索树法来解决人机博弈时，通常只能搜索到一个非常有限的深度，并根据此有限深度的形势来判断每种走法的优劣，从而选择较优位置下子。2极小极大值算法。极小极大算法3是考虑双方对弈本文由论文联盟3/5HTTP/收集整理若干步之后，从可能的走法中选一步相对好的来走。若最大节点为己方下的棋，此时选择估值最大的点走。最小节点为对方下的棋，此时选择估值最小的点行走。因此MIN节点的父节点所赋的倒推值等于端节点估值中的最大值。另一方面，MAX节点的父节点所赋的倒推值等于端节点估值中的最小值。这样一级一级地计算倒推值，直至起始节点的后继节点也被赋以倒推值为止，即从下往上逐层交替使用极小极大的选值方法。但当搜索深度增加时，搜索节点快速大幅增加，时间和内存空间消耗太大，且利用先前信息的效率较低。于是人们在极小极大的基础上提出了剪枝技术。3剪枝算法。剪枝算法2是在极大极小算法的基础上，当甲向下搜索节点时发现走第一个子节点就可以赢了，则剩下的节点就不需要再搜索，甲的值就是第一个子节点的值。即可以将甲的其余后继节点抛弃，此过程称为剪枝。如果甲所在的层是MAX节点的层，则称此剪枝为剪枝，否则成为剪枝。如图1左半部所示的一棵极大极小树的片断。其中节点下方数字为该节点的值，方形框节点代表计算机走，圆形框节点代表人走。A节点表示计算机走，由于A是极大值点，根据极小极大搜索原理它要从B和C当中选最大的值。假设目前已经通过估值得出B为18，当搜索C节4/5点时，因为C是该人走，所以根据极小极大搜索原理要从D、E、F中选取最小的值。此时如果估出D为16，那么C的值必小于或等于16。又因为已经得出B的值为18，说明节点A的值为MAX18，也就是说无须求出节点C的其他子节点如E、F的值就可以得出父节点A的值。这种将节点D的后继兄弟节点剪去的方法称为ALPHA剪枝。同理，在图1右半部一棵极大极小树的片段中，将节点D的后继兄弟节点剪去称为BETA剪枝。与极小极大算法相比，剪枝需要遍历的节点远远减少，它能在较短的时间内找到最佳的走法节点。二、五子棋智能算法实现及优化1估值函数。为使用极大极小算法，需要对一个估值函数EVAL对当前棋局进行估值，P是当前局面。即由这个估值函数确定哪个局面更好，如果EVAL2算法实现及优化使用以上定义的估值函数和描述的算法，可以实现基本的人机对弈。但是在实现中，由于搜索深度增加后运算量呈指数级数增加，运算效率急剧下降。为提高搜索效率，增进用户体验，提出以下优化改进方法减少搜索范围。对于1919的五子棋棋盘而言，传统算法中计算机每走一步都要遍历整个棋盘，对棋面上所有空位都进行试探性下子并估值，大大影响了算法的效率。5/5本文采用在某个时只要考虑距以棋子为中心边长为4的正方形区域即可，这样便缩小了搜索空间，提高搜索效率。减少计算量。为进一步减少计算量，提高计算机反应速度，通过以空间换时间的方法，在游戏过程中维持一个棋盘所有位置的估值信息的数组。每次对棋盘上的每个位置的当前估值进行计算后，存储在当前棋局信息中。当新的棋局产生时，只需更新计算新下子位置和相关位置的估值，而对其他可下子位置的估值只需查询上步棋局信息即可。这样保持的估值表虽然增大了空间需求，但可以大大减少搜索算法的估值计算时间，提高了算法执行效率。三、结论及后续工作本文主要论述了五子棋游戏的基本游戏规则，传统五子棋人机对弈游戏的基本算法，描述了算法实现的MINMAX算法和ALPHABETA剪枝算法，并描述了算法实现的估值函数定义、数据结构等，并通过减少搜索范围、减少计算量和设置对弈等级的