这个游戏是大学本科二年级时(1998年)修人工智能课程的功课 。这个游戏的「棋力」并不高,主要是因为没有花时间在调整的工作上。比较满意的部分是使用 OpenGL 做的使用者介面。本文将简单介绍制作本游戏的过程及当中用到的算法。你可以先(1049KiB)试试,但现时已找不到源码了,将来找到的话再分享。
约在接到这项功课前的一个月,刚开始自学 OpenGL,因此便考虑利用 OpenGL 做使用者接口。
以前写程式都是会先写使用者接口,用来显示程式的一些资料,之后再写算法,游游戏也不例外。我利用Photoshop 及 Illustrator 绘制棋子及棋盘,再尝试写程序 (Visual C++ 6.0) 以立体方式显示它们。由于太想试一试 OpenGL 的能力,在制作初期已加上了棋盘反射的效果。
之后便建构程序的重要资料结构,为每种棋子设定可行走法,有些棋子是颇麻烦的,例如炮除了可四方向移动外,还能隔子吃棋。做好了这些规则,便加入使用者介面的输入部分,可以进行人对人的游戏。
至于人工智能部分,首先写最简单的搜寻演算法──极大极小搜索 (Minimax search) 。最初使用的评估函数(Evaluation function)只是双方余下棋子的数目的差,那么电脑会避免自己的棋子被吃,又会尽量去吃对方的棋子,可谓已有一点「智能」了。 然后着手改良搜寻方法,使搜寻的速度提高。与此同时,参考了吴身润先生的作品,去编写评估函数。之后更加入了二千个棋谱走法 (book moves)。
接着得到各方好友的帮助,替它进行测试,以改善评估函数。我同时制作其余的使用者接口部分,包括左上方的选单、右方的按钮及棋局资料显示。
整个制作过程历时两个月,幸好在功课期限前的一个星期是假期,能通宵达旦去完成。
这里简介这游戏中用到的人工智能相关的算法。
游戏树
如同大部份中国象棋程序,这游戏也是从(Game Tree)中找出{zh0}的走法(Move)。
在游戏树中,每个节点代表游戏的一个状态(State),而每条边是一个合法的走法。因为象棋是双方轮交替下棋(红 -> 黑 -> 红 -> ...),所以树中每对相邻的层阶都是双方各自可走的走法。下图()显示了打井游戏的部份游戏树。
在打井游戏中,由于最多是 9 步,它的游戏树深度为 9,每一步之后,合法的走法变少了一个。因此,这个游戏树的总节点数目为 1 + 9 + 9 * 8 + 9 * 8 * 7 + ... = 986410。假设有了这个游戏树,我们只要从树中找出目前状态的节点,再往下搜索到任何一个获胜的叶节点(我方胜利终局),从当前节点走到该叶节点就是「必胜之道」,所以只要按「必胜之道」的{dy}步去走就会胜利了。事实上,写一个不会输的打井游戏搜索 AI 只需要十数行代码左右。
最小{zd0}搜索
不过,中国象棋的游戏树是非常大的(虽然比围棋小),不可把整个树储存或搜索至叶节点(终局除外)。因此,只能搜到某个深度,并在该深度的节点进行 (Heuristic Evaluation),这估值反映了该节点棋局对我方的优势。
由于在我方下棋的层数,我们会在每个节点选择子节点中{zd0}评估值,作为本节点的评估值;在对方的层数,我们会假设他选择最小启评估值的节点;这就是(Minimax Search)的原理。
为了简化程序,不用按层数选择用 min 或 max,Minimax 通常在实现的时候会采用 方式。其原理就是每层都是取下一层结果的负值的{zd0}值。
所有 Minimax 搜索都可以做到安全的上下界剪枝,称为 (Alpha-Beta Pruning),这里不详述了。
以下是这游戏中用到的方式:
AlphaBeta(alpha, beta, depth) { if (depth == 0) return Quiescence(alpha, beta); succ = generate all move from current board sort succ by estimate function for each node n in succ { makeMove(n); x = -AlphaBeta(alpha, beta, depth - 1); takeBack(); if (x > alpha) { if (x >= beta) return beta; alpha = x; // update principal variation here } } if (no legal move) return -10000 + ply; return alpha; }
平静搜索
当搜索到{zd0}深度的时候,有机会在下一步会产生很大的评估值变化(例如被吃子)。(Quiescence Search)就是在{zd0}深度的时候继续搜索,直至局势变得稳定。
迭代深化
在Alpha-Beta 剪枝中,如果能尽快缩小上下界,将会减少搜索的节点数目。这就产生了(Iterative Deepening) 的优化方法。相对于直接搜索深度为N的树,先搜索深度为i,并用其结果来优化深度为 i + 1 的搜索。
所谓结果,是指在Alpha-Beta 剪枝发生时去记录,并利用这个来排序下迭代里产生的走法。
游戏树中会有很多相同的节点。为免重覆计算节点,这游戏也使用了技术。
走法产生
在搜索中,产生合法走法占很大的时间。因此,游戏状态的表示方式和走法产生是非常重要的。而产生的走法也用在使用者接口上:
因为没有源代码,我记忆中,这游戏同时采用了"棋子->位置"及"位置->棋子"两个数组去表达棋盘的状态。例如车的移动要向四个方向产生走法,就可以用"位置->棋子"的数组去检查某位置是否有其他棋子。
在开局时,会首先寻找开局库有没有记录,这时候会用到一个更紧凑的棋盘表达方法。
评估方式
一个象棋的「智能」就在于其评估棋局的能力,上面提到的各种搜索优化只是用来加速搜寻(但在同等时限里增加搜索的节点也能增加「棋力」)。评估方法花费的时间也大大影响整体速度,所以必须平衡评估函数的能力及花费时间。
这个游戏采用的静态评估分数为(在结合其他评估时, 把这值乘以系数 10):
- 士 6
- 象 6
- 马 13
- 车 52
- 炮 22
- 兵 2
如前文提及,只是按棋盘余下的棋子,按这个分数来计算评估值,已可以有不少的「棋力」。这么简单的评估已令到计算机懂得「将军抽车」,我这个象棋门外汉会输给深度4的搜索。
我按照 [1],加入了单独棋子位置的分数,及一些全局分析的分数,例如:
- 车迟开步 -13
- 车在马后 -8
- 炮在马后 +8
- 马路被封 -4
要获得更好的评估方式,可以靠人的经验、分析专业棋谱、人工智能自动学习等等方法。
这个程式是我比较喜欢的作品,从外表(使用者接口)到内函(人工智能)都颇满意。而在开发过程中也真正地学会了课堂和课本的知识。
在开发这个游戏中,我也学习了象棋的一些规则,例如胜利条件不是吃了对方的将军,而是对手没步可走。但平手的规则并没有完成。
没想到十二年后,这个程序依然可以在Windows 7上运行自如(NT/2000/XP/Vista也沒問題),这要赞一下微软。外表上,大概是用了比较简单而独特一点的设计,包括渲染和GUI等也不会感到很落后。不过,当年应该没有使用系统时钟,使现在棋子移动得太快,这算是一个缺憾吧。
在进入社会工作以后,我很少有机会自己一个人写程序,编程的热情也不如当天。但我会继续在家里编程,希望能回复一点当日的热血。
- [1] 吴身润, 人工智慧程式设计:象棋, 旗标出版股份有限公司, 1996.
- [2] George F. Luger, William A. Stubblefield, Artificial Intelligence: Structures and Strategies for Complex Problem Solving 2nd Edition, The Benjamin/Cummings Publishing Co. Inc., 1992.
2010-03-16 21:46
十二年前就能做出来了,很不错。2010-03-16 22:06
牛X呀2010-03-16 22:27
输了2盘......2010-03-16 22:38
看完标题,我先拜三拜然后在看内容!大学二年级的作品!我那时候在做什么呢?
2010-03-16 22:42
必须尊敬这样的作品!呵呵大学有这样的经历令人羡慕。
12年前……楼主是前辈中的前辈啊,呵呵
2010-03-16 22:46
请允许我叫你一声——大师!2010-03-16 23:00
我被将军抽车了,不过抽我之前崩溃了……win7的问题?[楼主] 2010-03-16 23:05
DiryBoy不肯定是否兼容問題,還是本身的問題。現在暫時沒代碼,也沒辦法了。對不起。
2010-03-16 23:09
好是好,就是看不到源码啊,试着做了下,有点困难! 关注源码Ing...2010-03-16 23:11
很好2010-03-16 23:12
能看到这样高质量的文章,必须感谢楼主2010-03-16 23:13
膜拜下我对计算机开发是半路出家的,所以於算法一路原就生疏得很,看到就油然起敬
况且还是12年前大二的时候,赞下
现在人越来越浮躁,大学里面混日子混考试的人太多了,叹下,社会上真正潜心做技术的不多了
2010-03-16 23:18
12年前,偶在读小学。大学时候C语言课程设计,记得是网上download了一个贪吃蛇的游戏交得差 。楼主真是强人加前辈,值得学习。楼主的每篇文章,我都是点推荐的。
2010-03-16 23:51
呵呵,我大一的时候曾经写过一个五子棋的程序,比象棋简单多了,也想到了极大极小值算法,不过没往下实现...有一本<PC 游戏编程(人机博弈)>倒是很全面的讲解了Milo这篇文章后面的内容,有兴趣的也可以参考下.
大二就能做出这样的作品,实在是值得膜拜.我现在也是大二,也只有写写简单2D游戏的水准...唉,路漫漫啊~
[楼主] 2010-03-17 00:22
忘了說,這個遊戲有個很不小心的"bug",「帥」寫成「師」了 :)2010-03-17 00:26
楼主是在香港上的大学。不是内地哦。内地12年前估计也少有这个机会,教育体制也有问题,直到现在。[楼主] 2010-03-17 00:35
以我聽到內地朋友的經驗,覺得有一個顯著不同,在此分享。
我諗本科的時候一個學期(半年)只要上4個課程,每個課程每星期太約5~6個小時,一周上課時間大約20~25小時左右。所以會比較多時間去自修及做課外的事。我之後的一屆改為學分制,上課時間也變多了。
內地本科生的課程好像很繁忙。
2010-03-17 01:51
希望楼主 尽早开源2010-03-17 08:30
支持一下。治学态度上,香港人还是比大陆人靠谱~。~当然本质上还是大陆人过分不靠谱,上梁不正下梁歪,扯远了会扯到政治上,就打住吧。2010-03-17 08:33
太厉害了2010-03-17 08:47
好东西,收藏了2010-03-17 09:10
大二时我在干吗呢,让我想想...哦对了,那个时候整个宿舍在狂打魔兽。2010-03-17 10:20
很好。2010-03-17 10:52
赞···2010-03-17 13:48
牛人!2010-03-17 14:47
不错!2010-03-17 15:43
OpenGL,12年前楼主就这么关注,现在境界应该很高。期待这方面的文章。2010-03-17 16:03
楼主很强,相当强!2010-03-17 16:39
Mark2010-03-17 18:03
佩服到肝脑涂地2010-03-17 18:45
这个不是真正的bug,表示“帅”得可以当老“师”了:)
2010-03-17 19:43
汗一个……似乎每个人都在感慨自己大二时在做什么……而我也不能幸免……
2010-03-17 22:17
真是人比人气死人,你大二就能做出这样的东西,哎2010-03-17 22:50
就是因为算法因为数学的原因不知打碎多少程序员的梦2010-03-17 23:54
苦苦挣扎到这里,down掉了