基于α-β剪枝算法实现的AI五子棋游戏

Pullarla

发布日期: 2019-06-20 11:17:32 浏览量: 2662
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

一、对抗问题

对抗问题:顾名思义,博弈双方是带有对抗性质的。博弈的任何一方都希望局面尽量对自己有利,同时局面也应该尽量令对方不利。通常这一类问题可以通过 Minimax 算法解决。

Minimax 算法又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。Minimax 算法常用于棋类等由两方较量的游戏和程序,这类程序由两个游戏者轮流,每次执行一个步骤。为了执行 Minimax 算法,我们可以通过穷举的方式,枚举所有的状态空间,从而使得我们可以在游戏刚一开始,就预测到输赢。但是,在实际情况下,游戏的状态空间都是异常庞大的。很显然,我们不能将以穷举方式实现的 Minimax 算法用于实际应用。

二、α-β减枝

通过分析可以发现,在利用穷举方法执行 Minimax 算法中有许多的无效搜索,也就是说,许多明显较劣的状态分支我们也进行搜索了。我们在进行极大值搜索的时候,我们仅仅关心,下面最大的状态,对于任何小于目前值的分支也都是完全没有必要进行进一步检查的。(α减枝)

通过上图,我们可以发现,我们可以减去大量无用的状态检查,从而降低我们的运算量。

同时,我们在进行极小值搜索的时候,我们仅仅关心,下面最小的状态,对于任何大于目前值的分支都是完全没有必要进行进一步检查的。(β 减枝)

通过上图,我们可以发现,我们可以减去大量无用的状态检查,从而降低我们的运算量。

将上述所提到的 α 减枝与 β 减枝进行综合就可以得到 α-β 减枝。对于对抗搜索而言,我们需要精心设计其估值函数,不然我们的 α-β 减枝将毫无用武之地。

三、五子棋问题

五子棋:是一种两人对弈的纯策略型棋类游戏,通常双方分别使用黑白两色的棋子,下在棋盘直线与横线的交叉点上,先形成 5 子连线者获胜。

这里,我们采用了极大极小博弈树(MGT),来实现 AI。这里用一张井字棋的搜索示意图来说明。

上图很清晰的展示了对局可能出现的所有情况(已经去除了等价的情况),如果让这个图延展下去,我们就相当于穷举了所有的下法,如果我们能在知道所有下法的情况下,对这些下法加以判断,我们的 AI自然就可以选择具有最高获胜可能的位置来下棋。极大极小博弈树就是一种选择方法,由于五子棋以及大多数博弈类游戏是无法穷举出所有可能的步骤的(状态会随着博弈树的扩展而呈指数级增长),所以通常我们只会扩展有限的层数,而 AI 的智能高低,通常就会取决于能够扩展的层数,层数越高,AI 了解的信息就越多,就越能做出有利于它的判断。

为了让计算机选择那些获胜可能性高的步骤走,我们就需要一个对局面进行打分的算法,越有利,算法给出的分数越高。在得到这个算法过后,计算机就可以进行选择了,在极大极小博弈树上的选择规则是这样的:

  • AI 会选择子树中具有最高估值叶子节点的路径

  • USER 会选择子树中具有最小估值叶子节点的路径

这样的原则很容易理解,作为玩家,我所选择的子一定要使自己的利益最大化,而相应的在考虑对手的时候,也不要低估他,一定要假设他会走对他自己最有利,也就是对我最不利的那一步。

接下来,我们实现关键的局面评分步骤:直接分析整个棋面是一件很复杂的事情,为了让其具备可分析性,我们可以将其进行分解,分解成易于我们理解和实现的子问题。

对于一个二维的期面,五子棋不同于围棋,五子棋的胜负只取决于一条线上的棋子,所以根据五子棋的这一特征,我们就来考虑将二维的棋面转换为一维的,下面是一种简单的思考方式,对于整个棋盘,我们只需要考虑四个方向即可,所以我们就按照四个方向来将棋盘转换为 15 * 6 个长度不超过 15 的一维向量(分解斜向的时候,需要分为上下两个半区),参考下图:

我们的目的是为了为其评分,那么我们就还需要评估每个线状态,将每个线状态的评分进行汇总,当做我们的棋面评分:

接下来我们所要做的就是评价每一条线状态,根据五子棋的规则,我们可以很容易穷举出各种可能出现的基本棋型,我们首先为这些基本棋型进行识别和评价,并且统计每个线状态中出现了多少种下面所述的棋型,并据此得出评价值,得到如下图所示的静态估值表:

根据这个表以及我们之前所谈到的规则,我们就可以得到一个可以运行的AI了。

四、进一步的优化

注意到,如果我们搜索到第四层,总共需要搜索:224 + 224 223 + 224 223 222 + 224 223 222 221 = 2 461 884 544 个状态节点,搜索如此多的状态节点的开销是十分可观的,因此,我们提高效率的方式就锁定到了:如何减少需要搜索的状态节点。

我们可以采取以下方法来减少需要搜索的状态节点:

  • 我们可以利用经典的α-β剪枝算法对博弈树剪枝

  • 我们可以每次搜索仅搜索落子点周围 2*2 格范围内存在棋子的位置,这样可以避免搜索一些明显无用的节点,而且可以大幅度提升整体搜索速度

  • 避免对必胜/负局面搜索,当搜索过程中出现了必胜/负局面的时候直接返回不再搜索,因为此时继续搜索是没有必要的,直接返回当前棋局的估价值即可

  • 加入随机化AI的下棋方式,普通的AI算法对于给定的玩家下棋方式会给出固定的回应,这就导致玩家获胜一次之后只要此后每次都按此方式下棋,都能够获胜。为了避免这种情况,可以在 AI选择下子位置的时候,在估值相差不多的几个位置中随机挑选一个进行放置,以此增加 AI的灵活性

规划搜索顺序,有很多有价值的下子点存在于更靠近棋盘中央的地方,如果从棋盘中央向外搜索的话,则能够提高α-β剪枝的效率,让尽可能多的分支被排除

五、实验成果

六、实验总结

通过本次实验,加强了组员之间的沟通协调能力,同时也提高了我们对αβ减枝算法的了解。我们更了解了五子棋相关的游戏规则以及一些技巧,拓宽了我们的知识面,有助于我们在未来的生活中更好的与人交流。

同时,经过此次实验,我们深入了解了棋类人工智能算法,进一步的提升了我们的专业水平,有助于我们在未来的就业与科研岗位上走的更远。

虽然α-β减枝实现起来非常容易,但是五子棋的局势估计却十分的有挑战性,其局势估计的准确与否直接影响了程序的运行结果是否令人满意,AI是否能够展现出足够的智能。

上传的附件 cloud_download 基于α-β剪枝算法实现的AI五子棋游戏.7z ( 806.22kb, 133次下载 )
error_outline 下载需要12点积分

keyboard_arrow_left上一篇 : 基于QT的网络五子棋游戏程序的设计与实现 基于Spring+Struts+Hibernate+Oracle实现的健康管理平台 : 下一篇keyboard_arrow_right



Pullarla
2019-06-20 11:17:15
基于α-β剪枝算法实现的AI五子棋游戏
叶问
2019-12-21 22:43:23
大佬
昨天过后
2020-06-19 20:44:40
大佬,这是啥软件实现的??
fsdfsd
2020-10-08 16:39:30
很强!
csy
2020-11-08 19:39:02
厉害了
csy
2020-11-08 19:39:07
厉害了
aqiu
2020-11-29 11:34:15
用的是什么语言

发送私信

你在背后说我,因为我走在你前面

15
文章数
8
评论数
最近文章
eject