银行 社区服务 每日签到 会员排行 网站地图
  • 6880阅读
  • 21回复

象棋软件之引擎核心搜索和剪接算法

楼层直达
级别: 宣传大使
[棋中红钻2级]发帖数量≥100篇 [棋中黄钻1级]金币数量≥100枚 [棋中蓝钻2级]乐币数量≥50枚 [棋中粉钻6级]贡献值数量≥100点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
172
金币
335
威望
2
贡献值
140
乐币
51
主题
65

— 本帖被 棋中论坛 从 棋软知道 移动到本区(2012-08-26) —

             计算机引擎棋步搜索,是“引擎”的核心,它驱动着整个引擎程序,是人工智能博弈在实践中的典型应用。但就中国象棋博弈树的搜索而言,博弈节点相当庞大(它会成指数增长),因而搜索(限定层数以内的)整棵树是一件相当费时的工作——其时间复杂度为O(bn)。其中b是分枝因子,即针对各种局面的合法着法的数目的平均值,n是搜索的深度。中国象棋在中盘时平均着法数目大约是40种左右,那么搜索4层需要检查250万条路线,搜索5层需要检查1亿条路线,搜索6层需要检查40亿条路线……我们以现在比较典型的16核机,超频3.5G,按照中局搜索速度20M/秒个节点,同时不经“裁剪”采取蛮力搜索(穷尽)的方式。搜索7层以上所需的时间,是你难以想象的。具体每层所需搜索的节点数和所需时间见下表:       如果按照每一步平均有40种可行着法,每局棋平均走90步,那从开始局面展开到分出胜负,则要考虑 4090=1.5× 10144  种局面。这一天文数字要比地球上的原子数目还要多,即使用世界上最快的计算机进行计算,直到地球毁灭也无法算出第一步的着法。由于完整的博弈树过于庞大,蛮力搜索所能达到的层数十分有限,在象棋博弈中几乎没有实用价值。若想在指定时间内将搜索深度加以提高,一方面需要改进硬件与优化程序代码,提高单位时间内搜索的节点数;另一方面就需要像人类棋手一样有选择性地进行搜索,即对博弈树进行必要的裁剪-------搜索裁剪算法。
       搜索算法对于整个下棋引擎来说都是至关重要的。搜索算法的好坏直接影响着程序执行的效率,它影响着计算机的下棋水平。因为计算机必须在有限的时间内完成思考,搜索速度快意味着在相同的时间内程序可以“看”得更远,“想”的更多。下面用传统的Alpha-Beta搜索算法为例讲讲“裁剪”的实现。       在中国象棋里,双方棋手获得相同的棋盘信息。他们轮流走棋,目的就是将死对方,或者避免被将死。由此,我们可以用一棵“博弈树”(一棵n叉树)来表示下棋的过程——树中每一个结点代表棋盘上的一个局面,对每一个局面根据不同的走法又产生不同的局面,如此不断直到再无可选择的走法,即到棋局结束。幸运的是,搜索算法使得我们能在不影响搜索精度的前提下大幅减少工作量。因为,如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向,那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时,你应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了,如果你选择了它,那么你必将得到那个很糟糕的局面,甚至可能更糟……这样一来便可以在很大程度上减少搜索的工作量,提高搜索效率,这称为“搜索树的裁剪”。下面用图来进一步说明“搜索树的裁剪”。为了简便起见,我将博弈树进行了简化——每个结点只有三个分支,实际情况中,刚才讲过在中盘应有大约40个分支。我们假定棋盘上的局面发展到了结点A(见下图),现在轮到你走棋了,你是“最大的一方”——即你希望棋局的分值尽可能的高。让我们试着搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。                   图中 口表示该结点要取子结点中的最大值; O表示该结点要取子结点中的最小值              首先,我们考察结点A的子结点B。结点B所属的这一层是轮到你的对手——“最小者”来走棋了,他的目的是使得棋局的分值尽可能的小。依次考察结点B的各个子结点,查看它们的分值(因为我们事先约定好了搜索两层,现在已达到搜索深度的要求了,所以就停下来调用局面评估函数来给它打分)。结点B的第一个子结点(从左到右算起)返回5,第二个子结点返回了8,第三个子结点返回了4。由于结点B这层是你的对手来做选择,我们假设他一定会做出明智的选择(你不能寄希望于你的对手会走出一步“昏招”),那么他会选择返回值为4的那个结点。4最终也就成了从结点B传递回的值,即倘若你(现在位于结点A)选择了产生结点B的走法,使得局面发展到了结点B。那么下一步,你的对手的选择就会使得棋局发展成为分值为4的那个结点所表示的局面。我们再来分析结点A的第二个子结点C,结点C与结点B同属一层,它依然是轮到你的对手作选择。依次查看结点C的各个子结点的分值,其第一个子结点返回了6、第二个子结点返回了2、……好了,该是“裁剪”登场的时候了。你已经不必再继续考察结点C的剩余子结点了,因为结点C已经够糟糕的了,不管结点C的剩余子结点有怎样的分值,它最多只能传回2(有可能其剩余子结点中还有分值更小的结点,因而结点C还有可能传回更小的值)。而与前面已经分析过的结点B所传回4相比较,作为“最大一方”的你显然更不愿意看到2的局面。所以,你当然不会选择相应的着法使得局面发展成为结点C。因为那样的话,下一步你的对手就会带给你一个分值不高于2的局面。同理,我们再来分析结点A的第三个子结点D,结点D与结点B、C同属一层,它依然是轮到你的对手作选择。依次查看结点D的各个子结点的分值,其第一个子结点返回了3……不管结点D的剩余子结点有怎样的分值,它最多只能传回3(有可能其剩余子结点中还有分值更小的结点,因而结点D还有可能传回更小的值)。而与前面已经分析过的结点A所传回4相比较,作为“最大一方”的你显然也不愿意看到3的局面,所以D分支“裁剪”掉。          由此,我们就在不影响搜索质量的前提下避免了搜索“无价值的”结点C和D的剩余子结点的大量工作,从而节省了宝贵时间,为在同样机器配置下搜索更多的层数提供了可能。有了好的搜索算法,才是“引擎“在有限时间内找到”正着“。提高了搜索的效率,才使”引擎“的应用有了实际价值。 希望各位从中认识到“裁剪”的必要性。                                                                                       by 天剑出击        2012-8-23
[ 此帖被天剑出击在2012-08-24 16:08重新编辑 ]
本帖最近评分记录: 5 条评分 金币 +14
级别: 论坛检查
[棋中红钻5级]发帖数量≥2000篇 [棋中黄钻3级]金币数量≥2000枚 [棋中蓝钻4级]乐币数量≥500枚 [棋中粉钻2级]贡献值数量≥5点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
3741
金币
2796
威望
6
贡献值
6
乐币
529
主题
0

只看该作者 一楼  发表于: 2012-08-26
非常专业的文章,只有专业人仕才看得明白。
坦白地说,我看不明。呵呵!
级别: 少尉
[棋中红钻2级]发帖数量≥100篇 [棋中黄钻1级]金币数量≥100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
213
金币
390
威望
0
贡献值
0
乐币
0
主题
1
只看该作者 二楼  发表于: 2012-08-26
支持1楼的看法, 的确很难懂
级别: 少校
[棋中红钻5级]发帖数量≥2000篇 [棋中黄钻3级]金币数量≥2000枚 [棋中蓝钻3级]乐币数量≥100枚 [棋中粉钻3级]贡献值数量≥10点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
2569
金币
3442
威望
2
贡献值
10
乐币
427
主题
119

只看该作者 三楼  发表于: 2012-08-26
意思明白  但看的有点不明白  
级别: 论坛检查
[棋中红钻6级]发帖数量≥5000篇 [棋中黄钻4级]金币数量≥5000枚 [棋中蓝钻2级]乐币数量≥50枚 [棋中粉钻6级]贡献值数量≥100点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
6414
金币
7124
威望
6
贡献值
147
乐币
79
主题
304

只看该作者 4楼 发表于: 2012-08-26
感谢您的分享,棋中有你更精彩
级别: 少尉
[棋中红钻2级]发帖数量≥100篇 [棋中黄钻1级]金币数量≥100枚 [未点亮棋中蓝钻]乐币数量<10枚 [棋中粉钻2级]贡献值数量≥5点 [棋中彩钻1级]精华帖数量≥1篇
发帖
156
金币
175
威望
1
贡献值
5
乐币
-1
主题
2
只看该作者 5楼 发表于: 2012-08-26
感谢您的分享,棋中有你更精彩
级别: 少校
[棋中红钻4级]发帖数量≥1000篇 [棋中黄钻2级]金币数量≥1000枚 [棋中蓝钻1级]乐币数量≥10枚 [棋中粉钻5级]贡献值数量≥50点 [棋中彩钻1级]精华帖数量≥1篇
发帖
1576
金币
1790
威望
6
贡献值
57
乐币
42
主题
17

只看该作者 6楼 发表于: 2012-08-26
感觉跟数学的关系很大!如果真的是每步棋都是那么繁琐的搜索,估计下棋是一件很痛苦的事情!
级别: 上尉
[棋中红钻2级]发帖数量≥100篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
372
金币
0
威望
1
贡献值
0
乐币
5
主题
82
只看该作者 7楼 发表于: 2012-08-26
他意思是A4能量最大的Ô値
复杂度为O(bn)
16核机O(512x3)
级别: 少尉
[棋中红钻2级]发帖数量≥100篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [棋中粉钻2级]贡献值数量≥5点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
234
金币
0
威望
0
贡献值
5
乐币
0
主题
1
只看该作者 8楼 发表于: 2012-08-26
象棋软件之引擎核心搜索和剪接算法
级别: 中尉
[棋中红钻3级]发帖数量≥500篇 [棋中黄钻2级]金币数量≥1000枚 [未点亮棋中蓝钻]乐币数量<10枚 [棋中粉钻1级]贡献值数量≥1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
755
金币
1522
威望
0
贡献值
1
乐币
1
主题
7
只看该作者 9楼 发表于: 2012-08-26
这个应该跟陈朝营等去讨论。
_仯帥軟件象棋群
级别: 司令员
[棋中红钻6级]发帖数量≥5000篇 [未点亮棋中黄钻]金币数量<100枚 [棋中蓝钻3级]乐币数量≥100枚 [棋中粉钻2级]贡献值数量≥5点 [棋中彩钻1级]精华帖数量≥1篇
发帖
5629
金币
75
威望
6
贡献值
5
乐币
178
主题
188

只看该作者 10楼 发表于: 2012-08-26
谢谢您的支持,棋中有你更精彩
级别: 上尉
[棋中红钻4级]发帖数量≥1000篇 [棋中黄钻1级]金币数量≥100枚 [未点亮棋中蓝钻]乐币数量<10枚 [棋中粉钻2级]贡献值数量≥5点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
1287
金币
613
威望
0
贡献值
7
乐币
0
主题
20
只看该作者 11楼 发表于: 2012-08-26
看看什么意思     
级别: 中尉
[棋中红钻3级]发帖数量≥500篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
564
金币
7
威望
0
贡献值
0
乐币
0
主题
5
只看该作者 12楼 发表于: 2012-08-26
比較偏向理論的帖子

老實說一般人看了並無太大收穫
级别: 中尉
[棋中红钻3级]发帖数量≥500篇 [棋中黄钻2级]金币数量≥1000枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
560
金币
1030
威望
0
贡献值
0
乐币
2
主题
19
只看该作者 13楼 发表于: 2012-08-26
感谢您的分享,棋中有你更精彩
级别: 首席版主
[棋中红钻2级]发帖数量≥100篇 [棋中黄钻1级]金币数量≥100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
414
金币
185
威望
1
贡献值
0
乐币
7
主题
33

只看该作者 14楼 发表于: 2012-08-26
这个对于专业人士来说已经过时好多年了 对我们这些业余来说还很新鲜,因为这是根据“对策论”原理编写的数据结构,在没有软件的年代,黄大师(少龙)曾用它来编写程序,而如今有了软件,我们只需要把它用好就够了,其它的不重要
级别: 超级版主
[棋中红钻5级]发帖数量≥2000篇 [棋中黄钻5级]金币数量≥10000枚 [棋中蓝钻3级]乐币数量≥100枚 [棋中粉钻2级]贡献值数量≥5点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
4985
金币
19907
威望
6
贡献值
9
乐币
293
主题
139

只看该作者 15楼 发表于: 2012-08-27
这些软件修枝剪叶的工作还是留给作者和专业人士去搞吧,我们只是伸手拿他们的产品来测试,把结果反馈上来相互交流就可以了。
级别: 列兵
[未点亮棋中红钻]发帖数量<10篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
2
金币
16
威望
0
贡献值
0
乐币
0
主题
0
只看该作者 16楼 发表于: 2012-09-01
这个对于编象棋软件来说是入门知识,对于使用软件的人来说则没必要懂多少。个人觉得,开发和测试是可以分成两拨人来做。
级别: 三级士官
[棋中红钻1级]发帖数量≥10篇 [棋中黄钻2级]金币数量≥1000枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
89
金币
1000
威望
0
贡献值
0
乐币
0
主题
1
只看该作者 17楼 发表于: 2012-11-13
这种思维模式对于纯人下棋有参考价值,高手实际上就是这样对弈的,楼主用科学的方法总结出来了。
级别: 中尉
[棋中红钻2级]发帖数量≥100篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [棋中粉钻2级]贡献值数量≥5点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
370
金币
13
威望
0
贡献值
9
乐币
0
主题
1
只看该作者 18楼 发表于: 2013-11-08
很专业的文章 这是软件技术的吧
级别: 上尉
[棋中红钻3级]发帖数量≥500篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
809
金币
2
威望
0
贡献值
0
乐币
5
主题
20
只看该作者 19楼 发表于: 2013-11-08
恩恩,看看也不错啊。
快速回复

限56 字节
请不要在回贴只采用字母:“ PP、asdfhjkl、HAO、OK、ddddddd ......”。  请不要在回贴过于简单的内容:“不错、顶、支持、厉害、呵呵、靠、晕........”
 
验证问题: 本站网址是?不带http://
上一个 下一个