距离上次写这个系列已经过去很久了,非常抱歉,现在呢我重新拾笔来填我自己挖下的这个坑。
在上一次的文章中,我们已经制作了整个游戏的最核心的框架,也就是说我们得到一个可以进行游戏的交互界面并且对游戏规则进行掌控的一个游戏类,在此前的文章中,我尽可能的让大家回避我所写的代码,因为这样会限制大家对整个游戏架构的思考,毕竟构建一个游戏的方式是多种多样的,我所想的方法并不一定是最好的,所以我希望大家自己去构建游戏的核心部分,我的文章仅作为一些提示。不过从这一篇文章开始,情况将有所转变,在完成的游戏核心部分之后,我希望让大家了解到的是,让游戏获得智能本身是一件又简单但又不简单的事情。
简单,是因为我们其实只是需要一个算法,能够替代两个玩家中的其中之一,这个算法的框架显而易见:

1

算法的输入数据就是当前棋局,算法通过分析棋局来计算并得出一个最佳的行棋位置。算法的需求是明朗简单的,但是难点就在于如何实现这个算法。
好在,有无数的人身先士卒,已经研究出了一类算法来应对这种博弈类问题,而且这种方法易于理解和实现,那就是博弈树的搜索。对于我们这种游戏,选用极大极小博弈树(MGT)是最为合适的,这种树用于描绘两个玩家交替进行游戏的过程,这里引用一张来自网络的图片[1]

2

这是我们都非常熟悉的三子棋游戏,上图很清晰的展示了对局可能出现的所有情况(图的制作者已经去除了等价的情况),如果让这个图延展下去,我们就相当于穷举了所有的下法,如果我们能在知道所有下法的情况下,对这些下法加以判断,我们的AI自然就可以选择具有最高获胜可能的位置来下棋。
极大极小博弈树就是一种选择方法,由于五子棋以及大多数博弈类游戏是无法穷举出所有可能的步骤的(状态会随着博弈树的扩展而呈指数级增长),所以通常我们只会扩展有限的层数,而AI的智能高低,通常就会取决于能够扩展的层数,层数越高,AI了解的信息就越多,就越能做出有利于它的判断。
为了让计算机选择那些获胜可能性高的步骤走,我们就需要一个对局面进行打分的算法,越有利,算法给出的分数越高。在得到这个算法过后,计算机就可以进行选择了,在极大极小博弈树上的选择规则是这样的:

AI会选择子树中具有最高估值叶子节点的路径;
USER会选择子树中具有最小估值叶子节点的路径。

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

由于我们通常设定的层数不会很多,所以我们使用递归来实现是最为直观方便的,每一层递归就是一个节点扩展其子节点的过程,并且我们要根据每层所代表的行棋方来选择最大或是最小的一个。
博弈树的构造是简单的,那困难的地方就是评价函数的构造,因为AI的智商除了取决于递归的层数外,最根本的,还是要看评价函数的好坏,那对于五子棋,我们又该如何去做呢?
要知道,直接分析整个棋面是一件很复杂的事情,为了让其具备可分析性,我们可以将其进行分解,分解成易于我们理解和实现的子问题。
对于一个二维的期面,五子棋不同于围棋,五子棋的胜负只取决于一条线上的棋子,所以根据五子棋的这一特征,我们就来考虑将二维的棋面转换为一维的,下面是一种简单的思考方式,对于整个棋盘,我们只需要考虑四个方向即可,所以我们就按照四个方向来将棋盘转换为15 * 4个长度不超过15的一维向量,参考下图:

3

根据这个图,我们来写分解棋盘的算法,下面不再是伪代码,而是C#代码,请仔细看:

唯一需要注意的一点就是,在分解斜向的时候,需要分为上下两个半区,所以我在分解的时候总共会有六个数组。
仅仅是分解为了线性状态还不够,我们的目的是为了为其评分,那么我们就还需要评估每个线状态,将每个线状态的评分进行汇总,当做我们的棋面评分:
4 进行到了这里,我们已经把二维的问题化简为了一维问题,那么接下来我们所要做的就是评价每一条线状态,根据五子棋的规则,我们可以很容易穷举出各种可能出现的基本棋型,我们首先为这些基本棋型进行识别和评价,并且统计每个线状态中出现了多少种下面所述的棋型,并据此得出评价值,那下表就是所谓的静态估值函数表:

1

根据这个表以及我们之前所谈到的规则,我们就可以得到下面的算法:

通过这个算法,我们就可以解决整个游戏的局面评价问题,结合之前已经阐明了的博弈树算法,我们的五子棋游戏的AI,就已经具备智能了!如果你进行了实践,那么这时候,你就可以和自己编写的AI来进行对弈了~
那么本篇文章就到此结束了,下一次的博客将会讲解如何优化博弈树搜索的过程,使我们的AI在智商不变的情况下思考得更快:)
[1] 什么是极大极小博弈树? http://www.nowamagic.net/librarys/veda/detail/948

1
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
  Subscribe  
最新 最旧 得票最多
提醒

你好,有几个问题想问你,我思考了很久很久,关于五子棋方面的,请你加我qq,邮箱号码便是qq邮箱,很急的,请你帮我解答一个疑问,谢谢