VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 9547|回复: 26

【原创教程】VB AI 中国象棋之三——博弈树、极小极大思想和估值函数

[复制链接]
 楼主| 发表于 2010-2-15 23:47:58 | 显示全部楼层 |阅读模式
本帖最后由 VBProFan 于 2010-2-16 18:47 编辑

为什么需要估值函数?根据人类目前的计算数学的水平,可以将二人零和完全信息分为两类:已解决的和未解决的。所谓已解决的就是如果双方都是 Perfect play(按最好的走法走),那么我们就可以说出是先手必胜、后手必胜、还是先手可逼和或后手可逼和。如三子棋、四子棋、五子棋都已被证明是先手必胜的游戏,都是已解决的。
让我们先看一个简单的游戏:甲乙两人从1开始数数,每人轮流数,每人只能数1~2个,例如甲开始可以数“1”,也可以数“1、2”,甲数了“1”以后,乙可以数“2”或“2、3”,谁先数到4谁就赢。博弈树如下:

数字游戏的博弈树.jpg

红色节点是甲取得胜利的节点,蓝色节点是乙取得胜利的节点,1、3层是甲选择的节点,2、4层是乙选择的节点,双方的节点交替出现,每个人的选择都建立在上一个人的选择形成的局面状态的基础上。第一步甲选择1,则后续的棋局只能在树的左半支发展,反之,如果选择1、2,则后续的棋局只能在树的右半支发展。虽然第一步甲选择1、2也有可能取得胜利,但你认为对手会那么傻吗?他会选择3而不是“3、4”?他做出考虑时应该把对手看做最聪明的看还是最傻的来看?当然是前者了。即使对手做出最强回击,自己也不能受太大的打击。选择左侧分支则不管乙做出怎样的选择都可以使自己立即达到胜利节点。乙数2时自己是数3还是数“3、4”?当然是后者了。自己选择时,应该选择对自己最有利的着法。这个游戏是可解的,因为先手只需数“1”,就可以必胜,无论后手是数2还是“2、3”。
然而黑白棋、国际/中国象棋、围棋之类的游戏每一步的走法(称为分歧因子)很多,由排列组合的乘法原理,整个棋局的节点数比宇宙中已知的粒子总数还多,即使全世界的计算机一起运算到太阳系毁灭也无法将博弈树扩展完毕找出所有的胜、负、和节点,何况像象棋这种东西还有互相解将还将的循环重复局面的情况。
如何解决这一难题呢?答案就是只将博弈树扩展至一定的深度,在末端的叶子节点处用一个分数来对局面的优劣进行评价,这样“如何选择分支才能得到胜利节点”(如果只有负、和那就尽量争取“和”的节点)的问题就变为了“如何选择分支才能得到分数最大的节点”。
但是这样做就有一个问题:对于胜负节点来说,是根据规则的,双方都无异议的,确定的,但估值函数就不同了,它是否真的能反映当前局面双方的优劣呢?有可能双方都认为自己的局面比对方的更优,也有可能看3步以内是优,但看到5步以后时就是劣势了。所以估值函数越接近真实情况,电脑的判断就越准确,AI也就越强大。但什么是真实情况呢?谁也不知道,你对这种棋的理解越深,就越能设计出好的估值函数。
在这里我们认为估值函数是准确的,而且双方对局面的看法是相同的,一方认为自己大优,对方就认为自己大劣;一方认为自己略优,对方就认为自己略劣。我们用己方的分数减去对方的分数作为局面函数,这样双方的局面函数就互为相反数,即红方是 +7 时黑方就是 -7.
回到前面的一个思想----总是把对手按最聪明的来对待,认为对手总会选择对自己最不利的一步棋,也就是说此时自己的局面函数取极小值(本层节点的最小值)。博弈树的奇数层节点是自己的选择,可以选这个也可以选那个,只需考虑其中一种就可以了,叫做“或”节点,显然要选择局面函数最大的节点,偶数层节点是对方的选择,要考虑所有情况,叫做“与”节点,选择极小值。极大值(或)节点和极小值(与)节点交替出现,形成一个博弈树。我们要从最底层的叶子节点的分数往上倒推出第一层节点的分数,然后选择最大分数的那个节点来走棋。用计算机语言,就是从根节点开始向下递归扩展博弈树至一定深度后对局面进行静态估值,然后回溯倒推出第一层节点的分值。

练习:
以下是一个不完全博弈树,其叶子节点都已经被估值,请计算出其根节点的分数:
ans.JPG

答案:
游客,如果您要查看本帖隐藏内容请回复


中国象棋如何来判断局面的优劣呢?当然首先是子力价值,我们都知道车、马、炮是强子,车又是最强子,然而同一个子在不同的位置,其价值又是不同的,所以我们要在基本价值的基础上根据其位置加上一个附加价值。这有点类似于商品的价格 = 价值 + 供求关系。用不用考虑棋子直接的威胁和保护关系呢?不用。因为往后动态搜索了几步后经过一系列的子力交换其局面函数就被倒推出来了,再进行复杂的估值就变得多余了。用不用考虑棋子的灵活度呢?也不用。因为根据中国象棋的知识,我们知道某些点的灵活度一般都是比较大的,即使暂时被封锁,也是有潜力的,例如肋道和河头,还有中心地带。另外灵活度的高低也会影响动态搜索后的估值函数。如果把灵活度算进估值函数,就会导致开局时走巡河炮的怪招,表面上看起来好像威胁挺大,但违背了基本的开局规则,稍微对象棋有点研究的爱好者都可在顶过了几番进攻后轻易把电脑打得落花流水。你们在我第一版的程序或者其他比较弱智的中国象棋程序也许都能见到巡河炮。

估值函数的另一个作用是决定了电脑的下棋风格,引导棋局的发展方向。例如,当局面比较平稳时为什么电脑会知道往前进兵和跳马?因为这些棋子走到前面的位置会使估值函数增大。为什么电脑遇到的人的绝杀或送车去自杀将军?因为局面函数被设计为最小值+杀棋步数,所以延缓杀棋的走法的分数比较高?为什么有几种杀法时电脑不会慢慢地虐人,而是选择最短的杀棋路线?也是一样的道理。为什么电脑知道即使没有好棋走也不能长将?因为长将的分数被设计为了最小值,长将将被直接判负。

这里我们列出中国象棋的子力价值位置数组,大家可以看看它是否符合中国象棋的知识(由于不是 100% 显示,所以看起来比较模糊,欲看真切者请点击图片然后放大到100%):
兵.jpg
车.jpg
老头.jpg
马.jpg
炮.jpg
士.jpg
相.jpg

评分

参与人数 1威望 +6 收起 理由
sunfrank + 6 很给力!

查看全部评分

发表于 2010-2-16 00:08:12 | 显示全部楼层
呵呵,又沙发……泡饭你这个例子似乎举得不好我建议的例子是吃井字……
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-2-16 11:36:03 | 显示全部楼层
呵呵,这个例子比较简单,能画出整颗博弈树,井字棋的博弈树比较大,画完不容易。
回复 支持 反对

使用道具 举报

发表于 2010-2-17 21:10:59 | 显示全部楼层
本帖隐藏的内容需要回复才可以浏览
回复 支持 反对

使用道具 举报

发表于 2010-2-18 22:46:51 | 显示全部楼层
唉!近一年研究平面设计,程序设计已成天书。
回复 支持 反对

使用道具 举报

发表于 2010-2-19 17:55:28 | 显示全部楼层
博弈树的小杠杠是什么意思?剪枝?
回复 支持 反对

使用道具 举报

发表于 2010-2-19 17:55:53 | 显示全部楼层
5# icecept

呵呵,你应该帮泡饭设计一下象棋程序的界面……
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-2-19 21:31:44 | 显示全部楼层
博弈树的小杠杠是什么意思?剪枝?
acme_pjz 发表于 2010-2-19 17:55


正确!后面讲α-β的时候还是用这张图。这里应该在意念中屏蔽小红杠和灰色格的颜色。
回复 支持 反对

使用道具 举报

发表于 2010-2-20 00:09:29 | 显示全部楼层
8# VBProFan

那为什么要剪掉呢?难道是那个走法显然不合理(是个臭棋)?依据是什么?
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-2-20 10:24:22 | 显示全部楼层
8# VBProFan

那为什么要剪掉呢?难道是那个走法显然不合理(是个臭棋)?依据是什么?
acme_pjz 发表于 2010-2-20 00:09


这个问题问得好,欲知后事如何,请听下回分解。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2019-8-25 23:47

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表