五子棋人工智能算法设计与实现

发布时间：2021-07-13 07:53

　　博弈是人工智能的主要研究领域之一，它涉及人工智能中的推理技术、搜索方法和决策规划。人工智能之父图灵在1950年曾说过：下棋是很抽象的活动，是机器可以和人竞争的纯智能领域之一。自此以后的半个世纪中，人机对弈就成了人工智能研究的热门领域。而人们对五子棋人机对弈的研究也有很长的历史了。如今，博弈树搜索算法，更是五子棋人机对弈的热门研究方向。本文主要研究了博弈树搜索算法和alpha-beta剪枝技术，改进了棋局评估函数，并提出连续冲四搜索算法的概念。本文设计了一个改进的评估函数。传统的评估函数，只考虑了单一直线上的棋形。这种评估函数虽然实现起来比较简单，但在两直线交叉的复合棋形下，往往不能很好地评判。本文设计的评估函数，在单一直线评估的基础上，加入了交叉组合分值加成。改进的评估函数能有效避免计算机程序错过三三或三四组合等必胜的情况，增强了程序的棋力。本文通过研究专业五子棋知识，提出了连续冲四搜索算法。在五子棋游戏中，冲四是一种很强的进攻手段，除非对手能在下一步连成五颗，否则他必须选择进行封锁的那一步。连续冲四取胜，就是通过连续冲四进攻，最终构造出制胜的三四。连续冲四搜索即是搜索连续冲四取胜的步... 

【文章来源】：华南理工大学广东省 211工程院校 985工程院校 教育部直属院校

【文章页数】：61 页

【学位级别】：硕士

【部分图文】：

特殊情况

21图 2-5 连续冲四例子图 2-5 所示，这是一个连续冲四的例子。假设现在轮到黑棋下子，在这个棋局中，白棋已经形成一个活三。在一般情况下，黑方很可能选择封锁白方的活三，即 a 位置或b 位置。而在两个位置中，a 更为有利，因为在封锁对方活三的同时，给自己形成了活三。若此时黑棋落在 a 点，而白方回应下一步肯定是阻止黑活四形成，并形成新的白活三，黑棋仍处于被动的状态，在可预见的几步内，黑棋将失败。但如果此时黑棋置白活三不顾，落在 A 处形成冲四，白棋则不得不防住这冲四。黑棋紧接着走 B、C 连续冲四，进而连接 A、B、C 三点形成活四，黑棋获胜。从上面的例子可以看到，连续冲四获胜也是一种重要的获胜手段。虽然在连续冲四步数不多的情况下，依靠博弈树搜索也能找到胜利的方法，但连续冲四的步数在多数情况下仍是比较多的。就像上面这个简单的例子，从开始连续冲四到真正取胜，需要黑白

第二章 算法描述3 连续冲四搜索优化但即使连续冲四搜索较博弈树搜索更高效，其算法的时间复杂度依然很高。不化的博弈树搜索的时间复杂度为 O(MN)，其中 M 为分支个数，N 为搜索深度，连续冲四取胜对冲四的顺序也是有一定要求的，连续冲四搜索可近似看成一搜索的问题，故其时间复杂度为 O(M!)，其中 M 为可冲四五元组的个数。当!)是这个算法的时间复杂度上界，实际情况下其复杂度会小很多。针对最坏情况下的连续冲四搜索，可以考虑加入一些优化以降低计算时间。如元组进行分组，使位置较近的五元组分在一组进行搜索。这样做可以减小 M虽然算法的时间复杂度不变，但计算时间会小很多。这个优化考虑的是，并不四五元组都能为取胜作出贡献的。考虑 0 的情况，两个冲四五元组并不能构成。如果将无关的冲四五元组一起搜索，会大大增加运算时间。


本文编号：3281673