首页 > 论文范文 > 社会科学论文 > 艺术论文 > 文艺观察论文 > 五子棋落子算法的研究

五子棋落子算法的研究

2021-10-08 225 上传者：管理员

摘要：五子棋做为热门的棋类游戏,深受人们的喜爱。五子棋本身含有丰富的趣味性,玩法的多样性。同时也是人工智能领域的研究对象之一。通过解决五子棋博弈中遇到的问题从而可以解决实际中的一些问题。文章立足于关于计算机落子算法中的现状,对计算机落子的算法进行探索,从而让计算机近似模拟人类的智慧。

关键词：
五子棋
人工智能
数据处理
职业围棋
评分表
加入收藏

随着计算机的飞快发展，机器博弈越来越受到人们的关注，也成为人工智能领域重要的具有挑战性的研究方向。在机器博弈的这个领域也出现了很多让人大开眼界的AI，比如近几年谷歌的AlphaGo击败了人类的职业围棋选手。这也体现了机器博弈可以实现人类可以做到的事，并且在一些方面可以做的比人更加的好。五子棋最早出现在中国的尧舜时期，距今已经有4000多年的历史。在这段时间中五子棋的演变出了很多的规则和玩法。现在国际规定的五子棋规则有，26种指定开局、三手交换、五手N打、禁手等。也正是五子棋规则的复杂性，所以在人工智能发展的潮流种具有很深的研究价值。

1、五子棋棋盘及棋盘状态的表示

棋类游戏棋盘的状态表示也是需要进行设计的，一个好的棋盘表示方法可以使得数据处理和算法检索更加的便利和快捷。在现在棋类游戏中，大多数时候都是使用数组来储存棋盘，在五子棋的棋盘设计中，一般是使用一个15*15的二维数组来储存棋盘，这样每一个点就对应了每一个棋盘的每一个位置。而棋盘中的每个点都有3个不同的状态，分别是：黑子，白子，无子，分别使用1、-1、0来表示这三种状态。比如一个白子冲四（白子已经形成3连珠，但是其中有一头被黑子阻挡）。使用二维数组可表示为：

2、估值算法的设计

估值算法可以说是所有棋类游戏的核心，设计一个好的估值算法可以让程序在后续的处理中更加的智能。一个比较主流的设计思路是让棋类专家或者是计算机模拟出所有可能出现的局面，并且将这些局面加载进一个数据库里面，计算机决策的时候只需要在这个数据库里面找到这个局面并且进行落子即可。这是一个不错的设计思想，但是耗费的资源也是巨大的，并且模拟棋局本身具有一定的缺陷，因为可能会出现专家或者是计算机遗漏的局面。这个对数据库的设计也有一定的要求，如何才能在那么大的数据量面前找到这个棋面呢？而且这仅仅是一个回合所需要付出的代价。

棋类游戏和牌类游戏不一样，棋类游戏是信息对称的游戏，不存在信息不对称的情况，因为对战双方都能够轻松的获得当前棋盘和棋盘状态的信息。而牌类游戏是信息不对称的游戏，因为对战双方不能清楚的看到整个局面，具有很强的不确定性。并且五子棋具有“零和博弈”的特点，对战双方有输赢，不存在双赢的局面，换而言之，如果对战双方有一方得分，那么就意味着另一方失分，并且得失的总和为零。所以可以根据零和的这个特点，可以设计出估值算法。

即使五子棋有很多的局面，但是如果对一个局面进行细分的话，可以分为长连、五连、活四、冲四、活三、眠三，活二，眠二，八种情况。

不管是黑棋或者是白棋都离不开这些情况。并且根据这些情况的危机程度不同可以定制出一个评分表。计算机落子的依据都是根据这个评分表。在所给出的评分中选择一个评分最高的进行落子。因此可以设计出如下的评分表，见表1。

在这个表中可以看出，计算机的得分情况一直比玩家的得分少，这是为了能够防守住玩家的棋子而设定的，并且根据棋型的不同可以看出越是危险的棋型它的分值越高，这是避免在因为分值过近导致计算机在决策的时候做出重大的错误。这跟前面所说的“零和”有所出入，是为了不设置负值，通过黑棋和白棋的对比可以直接决策落点的位置。但是他们的原理也是一样的。如果这个同时出现了相同的分值最大值点，那么在这些最大值点中随机选取一个进行落子。

跟棋盘的设计一样，评分表的存储也是使用一个15*15的二维数组，模拟整个棋盘上的点，并且这些点不再是储存棋盘黑白或者是无子的状态，而是储存一些未落子的点的分值。如果这个点已经被一颗棋子占据，无论是黑子还是白子，则设置该点的分值为0。

使用评分表的优点就是不需要有大量的数据，就可以使计算机能够落子，并且可以通过调整评分表的分值就可以调整出计算机攻防的风格，如果你想挑战一位进攻为主的对手，那么你只需要将计算机的分值拉高，这样计算机就能表现出攻击的姿态，但是这样也降低了防御能力。当然，一个好的分值设计可以让这个系统表现优异，这需要长期的实验。

3、搜索算法的设计

搜索算法在人工智能中占据重要的地位，在一定程度上决定了程序执行的效率。一个好的搜索算法可以降低算法的时间复杂度，从而提高程序的运行效率。现在主流的搜索算法有深度优先搜索、广度优先搜索等等。在棋类游戏中大多都使用极大极小搜索和α-β剪枝来提高搜索效率。就像周洋在《一种五子棋博弈算法的分析》论文中指出：“五子棋对弈中如果采用暴力搜索得到最终结果，则会使搜索树的深度非常大，尽管计算机的计算性能在不断加快，但还是不能满足需要，主要是因为耗时太长”。也正是因为这个缺点，所以设计一个优秀的搜索算法至关重要，因为它决定了计算机决策的快慢。常见的解决策略是使用树的结构，并且将分值加入到各个结点中，使用极大极小搜索到树结点的最大值，如果整个树的深度很深的话则会影响到搜索效率，所以可以使用α-β剪枝剪去枝叶中的其它结点，这样可以提高搜索效率。详情可以参见周洋《一种五子棋博弈算法的分析》。

我们使用的是评分表，在棋盘中的每个点都有分值，在计算机落子的时候需要遍历整个棋盘，并且在每一回合都要遍历，如果使用暴力搜索那么这个算法时间复杂度可以达到O(n5)，这是一个很高的复杂度。所以我们可以使用深度优先搜索遍历整个棋盘上的分值选择一个最大的进行落子。

4、结束语

为了能够使计算机落子，需要考虑到各方面的效率的同时也需要考虑到程序投入的成本问题。使用评分表可以有效的代替数据库，让程序更加的智能化而不是重复搜索数据库的机械化，同时也减少了程序对外界的依赖。为了提高程序的执行效率也需要选取一个合适的搜索算法，这也是计算机落子中所需要解决的问题。本文立足于对计算机落子的探讨，充分的说明了评分表的优越性，以及搜索算法的重要性。

参考文献：

[1]StanleyB.Lippman.C++Primer(第五版)[M].电子工业出版社，2015.

[2]周洋,邓莉,谢煜.—种五子棋博弈算法的分析[D]J.现代计算机(专业版).2017,(10):8-10.

[3]沈大旺.基于人工智能的五子棋搜索算法[G]产业与科技论坛2020,19(01):73-74.

文章来源：陈树彬,和昱旻,原菊梅.五子棋落子算法的研究[J].电脑与信息技术,2021,29(05):49-51+94

网友评论

加载更多

我要评论

期刊名称：艺术市场

期刊人气：1926

期刊详情

主管单位：中华人民共和国文化和旅游部

主办单位：中国文化传媒集团

出版地方：北京

专业分类：经济

国际刊号：1671-7910

国内刊号：11-4804/J

邮发代号：82-112

创刊时间：2002年

发行周期：月刊

期刊开本：大16开

见刊时间：7-9个月

论文导航

五子棋落子算法的研究

相关论文

大数据时代背景下皮影艺术传承的建议

关键词