英语原文共 8 页
基于遗传算法的五子棋求解进化
Junru Wanga , Lan Huangb,* Computer Science Department Yangtze University Jingzhou, Hubei, China a jkserge@163.com, b lanhuang@yangtzeu.edu.cn
摘要
五子棋，也被称为五子棋，是一种流行的双人战略棋盘游戏。给定一个15times;15的正方形棋盘，两名玩家争取首先在水平、垂直或对角方向上形成连续的五个棋子。这类游戏的经典解决方法是基于博弈树理论，例如极大极小树。这些方法有一个明显的缺点:搜索深度一直是一个瓶颈。本文提出了一种求解五子棋游戏的遗传算法。我们研究了将遗传算法应用于战略游戏的一般框架，并从游戏的不同相关方面设计了适应度函数。实验结果表明，与传统的基于博弈树的求解器相比，被提出的遗传求解器能够进行更深层次的搜索，能得到更好、更让人喜欢的解，并且搜索效率更高。
关键词：人工智能；五子棋；游戏；遗传算法；适应度函数；
- 引言
制造像人类一样聪明的人工制品是人类永恒的梦想，它推动了研究和一般IT行业的巨大进步。游戏是研究最广泛的领域之一，特别是战略游戏类型。研究人员研究使计算机游戏解决方案更智能和更高效的方法。博弈树已经成为主流方法，例如基于极大极小树搜索的象棋求解器成功的击败了人类最好的棋手[1]。从本质上讲，这些方法通过列举所有可能的步骤并选择能够带来最有利解决方案的步骤来找到最佳的下一步。求解器在博弈树中搜索得越深，效果就越明显。一般来说，三层结构接近人脑，足以做出简单的推理和反应：在战略游戏中攻击或防御。然而，随着搜索深度的增加，时间和空间的复杂度呈指数级增长，这限制了基于博弈树的求解器的实时性能，特别是考虑到公众可用的计算资源有限。
遗传算法（GA）是Holland[2]提出的一种基于启发式的搜索方法，广泛应用于优化问题。近年来，遗传算法在游戏中的应用越来越多。与基于树的算法相比，基于遗传算法的求解器不需要枚举所有的可能性。因此，他们可以在较短的时间内搜索更深入的步骤。换句话说，它们比传统的求解器更智能、更高效。本文探讨了将遗传算法应用于游戏的一般框架，并研究了典型的双机战略棋盘游戏五子棋的关键组成部分。本文所设计的遗传求解器采用了一个通用而有效的框架，在七个层次的深度上寻找最佳的运动，并能与人类的玩家进行比较。
下一节介绍相关工作，然后第三节描述我们基于遗传算法的五子棋求解器。第四节介绍了实验装置并讨论了结果。第五节对论文进行了总结。
- 相关工作
五子棋历史悠久；这是一个两个玩家得失相抵的完全信息游戏。这个游戏通常在一个有15*15个交叉点的棋盘上进行。黑子和白子玩家在一个空的交叉点交替放置单个棋子。获胜者是首先在水平、垂直或对角方向上形成五 (或更多)连子的玩家。
自由风格的五子棋也被称为五子棋、五子棋或Connect5。它的棋盘大小与围棋大致相同，搜索空间复杂度非常大。但是自由式五子棋(对黑子没有任何限制)众所周知偏爱黑子而不是白子，因此很久以前它就被认为是一种不公平的游戏。随着计算机算法的进步，1994年，Allis用“威胁范围研究”[1]和“数据取样研究”[2-3]证明了自由风格五子棋是一款黑子获胜游戏。因此，有许多新的游戏规则被提出来反对这种情况，例如连珠，Swap2。然而，游戏规则变得越来越复杂，以至于大多数玩家无法记住所有的规则。据我们所知，这种奇怪的现象在其他游戏中没有出现。2001年，Wagner和 Virag证明新规则“连珠”[4]也是不公平的——它也让黑子赢了。因此，自由风格的五子棋和连珠不能成为大多数人或电脑比赛的比赛项目。
针对五子棋面临的严重困难，五子棋公开赛被提出希望给五子棋一个新生的机会。对外开放的五子棋是由林教授于2011年提出的，并在2012年人工智能技术与应用会议[5]上正式提出。林的规则有三个目标:“保持五连子”、“规则简单”和“公平”，试图挽救五子棋的命运。该规则仅限制黑色在第一次移动时在棋盘的两个外侧行(即第1、2、14或15行)或列(即第A、B、N或O列)玩。从第二步开始，双方都没有被禁止的动作。如果棋盘被填满，并且没有创建5块石头的水平、垂直或对角线，游戏就是平局。根据这个规则，它减少了对黑子玩家的偏爱，并且比那些需要在黑子和白子之间切换角色的规则更加直观。
极小极大搜索及其改进alpha;-beta;搜索[3]可以说是解决战略性计算机游戏的最经典和最著名的基于博弈树的方法。基本上，在每个回合中，这些方法为求解者选择最有利的移动，为其竞争对手选择最不利的移动。alpha;-beta;剪枝进一步提高了搜索效率，并已广泛应用于游戏中。
遗传算法以类似于自然选择过程的方式执行搜索。每个可能的解决方案都被编码为一个单独的解决方案。个体的进化是通过与其他个体的杂交和部分基因组的变异。进化过程由一个适应度函数指导，该函数表示个体的质量。更好的个体有更大的机会让他们的基因组被后代选择和遗传。
结果表明，遗传算法不需要枚举整个搜索空间，但具有良好的适应度函数，可以很好地进行搜索。实际上，遗传算法可以看作是适应度函数的优化过程。将遗传算法应用到游戏中引起了越来越多的关注[4]。Han [5]应用遗传算法优化了棒球队的击球顺序。Cardamone、 Loiacono 和 Lanzi [6]使用遗传算法在赛车游戏中生成轨迹。Mitsuta和Schmitt[7]利用遗传算法提高了GNU象棋的性能，并使用了位置评估适应度函数。Elyasaf、Hauptman和Sipper[8]使用遗传算法来帮助解决新接龙游戏，能够减少搜索节点的数量和时间成本，缩短解决方案的长度，并且胜过人类玩家。Salge等人[9]利用遗传算法增强游戏乐趣和用户体验。在本文中，我们考虑了有效性，效率和有趣的因素，设计了基于遗传算法的五子棋求解器。
- 方法论
一个成功的遗传算法游戏求解器的关键是为手头的问题设计一个有效的架构。这种体系结构由五个部分组成：个体编码方案、原始种群规模、杂交和变异操作以及适应度函数。本节首先描述总体架构，然后详细解释每个部分。
1.结构
图1显示了遗传算法-五子棋求解器的总体架构。每当计算机要采取下一步行动时，它首先生成一个原始的个体群体，每个个体对应一个候选解。这些个体然后通过适应度函数进行评估。显著的那些被选为种子，将被用来进化种群，即通过杂交和变异。将再次评估产生的一代，进化过程将继续，直到找到最佳的下一步，即当种群稳定时。
图1 适应度函数的计算过程
2.编码方案
经典的五子棋板是15times;15，总共有225个可能的位置。在遗传算法框架中，候选解决方案被编码为字符串。我们使用一个棋子的坐标，并考虑从当前布局开始的七个连续步骤。换言之，我们在七个层次的深度搜索以选择下一步的最佳行动。这比传统的三层博弈树结构要深得多。
让A成为计算机解决方案，B成为人类玩家。假设人类在（7,5）处下了一子，然后计算机下下一子，那么下面两个序列对应于图1中所示的布局：
顺序：B（7,5）A（9,4）B（7,6）A（6,4）B（7,7）A（8,4）B（7,4）A（7,8）
表示：（9,4），（7,6），（6,4），（7,7），（8,4），（7,4），（7,8）
在这种情况下，人类在（7,5）处下了一子，基于遗传算法的求解器生成随后的七个步骤，从计算机在（9,4）处下子开始。玩家符号A和B可以省略以简化但同样有效的表示，这在其余部分会采用。
图2 .五子棋的一个示例解决方案
3.原始种群
原始种群的多样性和规模对于遗传算法快速找到一个好的解决方案至关重要。通常个体是随机产生的。然而对五子棋来说，有一些限制。例如，当所有其他现有棋子都集中在板的中心时，将一个棋子放在板的边界是没有意义的。
给定当前布局，让(xl,xr)和(yb, yt)为板上现有件的水平和垂直尺寸范围。我们将接下来的七个棋子限制在(xl minus;1, xr 1)和(yb minus;1, yt 1)的扩展边界内。棋子必须放在空位上。
原始群体随后由适应度函数进行评估。具有高适应值的显著个体被保留，而其它个体被丢弃。原始群体需要多样化，因此通常由成千上万的个体组成。
4.杂交和变异
为了进化，被选择的个体相互杂交。基本上，更好的个体更有可能被选择并与其他个体结合，类似于自然选择过程。轮盘选择算法通常被应用。杂交点是随机选择的。例如，以下两个个体在其第四基因型杂交:
父母1: (7，6) (5，5) (5，4) (2，2) (6，5) (7，7) (4，4)
父母2: (5，7) (5，5) (2，4) (7，7) (3，5) (4，4) (3，3)，
并生成以下组合:
儿童1: (7，6) (5，5) (5，4) (7，7) (3，5) (4，4) (3，3)
儿童2: (5，7) (5，5) (2，4) (2，2) (6，5) (7，7) (4，4)。
突变点也是随机选择的，突变个体的总数不超过总群体的百分之一。值得注意的是，杂交和突变都可能产生无效个体:单个个体的基因型重复。这意味着一块被放置在一个非空的位置。虽然通过对生成的候选对象进行双重检查可以避免这种情况，但效率会得到补偿。因此，我们将其留给评估步骤，在该步骤中，这些候选项最终将被适应度函数丢弃。
5.适应度函数
适应度函数评估候选解决方案的质量，是基于遗传算法的程序的最重要的组成部分。与其他搜索问题不同，战略游戏更复杂，因为它们涉及多个玩家。我们从五个方面设计了五子棋适应度函数，如下所述。
首先，我们将可能的布局分为12种类型，并根据获胜的可能性为每种类型分配值。具体来说，所有模式首先按照其可能性的升序排序，并使用以下公式计算其值：
v(pn) = 2 times; v(pnminus;1) 1, （1）
其中pn和pnminus;1是连续模式，函数v（p）计算模式值。表1列出了12种模式及其值。模式9、10和11有着相同的价值，仅仅是因为它们离胜利只有一步之遥：无论竞争对手下一步采取什么行动，计算机都能保证赢得比赛。不能划分为这12种模式的布局被分配为零值。
表1 布局模式和值
其次，除了上面计算的攻击值外，我们还通过假设竞争对手采取下一步行动来计算防御值。例如，在图3所示的布局中，假设计算机为黑色，并且正在评估用数字标记的三个位置。对于位置1，攻击值只是上面描述的结果模式值，即63（模式6）。它的防御值是模式值，考虑到它的竞争对手在这个位置，它是511（模式9）。因此，位置1的总值等于其攻击和防御价值的总和，即574。同样，位置2和3的攻击值分别为0和63，防御值分别为511和0，总值分别为511和63。显然，位置1是最好的。这也是为什么后续模式的值是基于公式（1）中先前模式值的两倍来定义的。
图3 攻击和防御价值示例
根据上述定义，我们可以将原始适应度函数定义为
, （2）
其中i索引到每个个体考虑的七个步骤中，atk（p）和def（p）分别是模式p的攻击和防御值。
考虑的第三个方面是支持早期的胜利。当一行中有五个出现时，后续步骤将变为冗余。例如，考虑到图4中的情况，对于使用白色棋子的玩家，标记出最有利的两个位置。对于位置1，它直接结束了游戏，但它的价值是1023的攻击，0的防御。相比之下，2号位置进攻得分511，防守得分1023，总计1534分。因此，不希望选择位置2。因此，为了确认早期胜利的价值，我们直接将最大值分配给其余的步骤。因此，电脑越快取得胜利，适应值就越高。
图4 早期胜利的例子
第四个方面是关于接近胜利的案例。例如，当模式9、10或11出现时，拥有白色棋子的玩家就一定会赢。因此，我们也将最大值分配给后续步骤，以确保遗传算法求解器将选择此类接近的胜利案例。
最后但同样重要的是，我们考虑到一个人的总体倾向：它是对计算机更有利还是对竞争对手更有利。公式（2）不区分两个参与者；换句话说，它也可能为实际有利于竞争对手的情况赋予高价值。因此，我们使用以下公式来量化总体趋势
, （3）
其中，如果计算机执行第i步，函数l（i）等于1，否则为minus;1。负值意味着当前的情况不利于计算机求解。因此，求解者应该采取其竞争对手的下一步行动，即将下一个棋子放在第二个基因型建议的位置，而不是第一个基因型建议的位置。这对提高求解器的智能性，从而提高游戏乐趣特别有帮助。
- 实验与分析
我们在Delphi中实现了基于遗传算法的五子棋求解器，并在此处提供（http://sourceforge.net/projects/gagomuku/）。在本节中，我们通过将其解决方案和搜索成本与基于博弈树的经典求解器进行比较来评估它。所有实验都在同一台计算机上进行。
原始种群大小设置为2000，最大种群大小为3500。在每一次迭代中，拥有最大适应值的前200名个体被保留下来，以产生下一代。百分之一的群体有变异基因型。每一代中最好的个体被保持（即迭代），如果这些最好
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
