北京大赛终于过去了, 在这场盛事前后这段时间, 静下心来回顾了走过的象棋研究的路子,心得感触良多.为了纪念这段时间的美好, 我决定把这段时间积累的对象棋引擎的心得, 总结分享出来

我个人希望通过这篇文章,把一些顶尖棋软的知识普及开来,提高开源象棋软件的水平.

1. 搜索引擎和审局之间的关系, 如何建立

阅读下面的内容时, 首先需要了解几个背景知识

a. 人工智能的博弈搜索树和PVS搜索之间的关系

b. PVS搜索是无损搜索

c. PVS的搜索效率和搜索次序的关系

首先明确几点:

a. 做一个全PVS的搜索, 在限定了层数的情况下, 如果基于不正确的知识(比如子力表),并不能保证一定能把杀棋找出来(可能会跑去吃子)

b. 为了提高棋力, 无损搜索PVS是不足够的, 还是需要剪枝的

c. 搜索树和审局之间的关系, 首先知识必须能够引导搜索到正确盘面(这个地球人应该都知道), 第二是避免搜索把正确的分支剪除掉(这个谈论得少一些,我以前曾经有很长一段时间不知道)

我认为, 审局和搜索之间的关系的建立, 在于

a. 知识是带有正确的倾向性的(只能说是倾向性,因为知识很难做到全面准确)

b. 搜索是根据知识而采取剪枝方式的(这个下面详细分析)

下面我举一个简单的例子, 来说明知识和搜索之间的关系

帅

_____

| | |

马 _| 将_|_兵

| _ |_ |_ |_象

在这个盘面, 兵只要靠近王一步, 就可以将死了对方, 但是基于子力表做depth=1的PVS搜索,只会选择: 兵吃象, 有利, 而且评估子力分数很高, 所以吃象

那么, 有什么办法避免这种情况呢?

a. depth=1的时候不做剪枝

b. 给予引擎审局的知识, 告诉引擎保持"马非底线兵"这种组合对将才具有杀伤力

这样就给出了两种选择, 哪种更好?

实际上, b这种选择有两种局限

a. 局限于现在对审局模型建立的水平, b这种情况需要花费大量的人力功夫来维护完整的知识, 而且很难做到准确

b. 目前的引擎的搜索棋步排序, 大都是基于最近访问->杀棋步->吃子步这样的棋步排序方法, 我们可以很容易想象到, 使用全面复杂的知识, 会引起搜索结果冲突(凑着一个吃子或者杀棋的步子去走, 但是最后发现达不到预期的效果), 大大降低了搜索的效率

正是因为上面的原因, 现在我所了解到的高端引擎, 大都是通过控制剪枝的危险程度, 来弥补知识的不足, 比如, 在nullmove中限制depth>=2, 或者, 在lmr(late move reduction)--如变种:fruit的history pruning, 控制depth>=3, 都是利用控制剪枝来弥补知识的缺陷.

我们很清楚知道, depth<=2的时候, 都限制了不能剪枝的话, 那么刚才的盘面, 并不需要任何知识,就可以找出杀棋步, 但是, 这个是不是我们需要的呢? 我想不是的, 如果限制了depth<=2不能剪枝的话, 我们会发现我们的搜索, 产生了大量的节点, 啊, 天啊, 可怕的搜索浪费

当然, 最理想的方法是, 搜索排序的次序是基于知识的, 而且盘面评估是基于知识的, 如果我们能够达到这样的效果, 嗯, 我想depth<=1不剪枝的限制也可以去掉了, 这样的引擎肯定效率更高吧

现在, 让我们想想, 哪些分支我们是不想被错误剪掉的? 当然是杀棋步, 杀棋>吃子, 基于子力表的搜索PVS, 很可能漏掉的棋步是杀棋步, 而这个恰恰是我们不想见到的

对于攻杀激烈的中国象棋,可以说两个引擎的差别在于,谁能更快更准确找到杀棋步.

口语化一点来说,给你多搜索两层的能耐,你能保证绝对能通过蚕食我的大子把我变成光棍司令? 尤其是随着高层效应的出现(引擎和硬件的发展,搜索的层数越来越大), 这种可能更是趋向于零, 所以, 我们应该尽量避免漏掉杀棋步

我知道有很多引擎的做法是, 对有潜在攻势的局面做出模糊判断, 并且赋予高分, 如越容易发生杀棋的棋步, 给予越高的分数, 例如三子归边的分数>马炮的分数, 这样就可避免因为吃马炮而漏掉杀棋, 但是这种模糊判断有些致命的缺点

a. 模糊知识,会造成大量的搜索浪费(条件越不准确, 越容易造成搜索浪费)

b. 模糊知识会造成错误的判断, 导致乱弃子

c. 引擎发展需要更长的发展周期, 需要大量的对局来积累知识

一种比较适中的解决方案是, 采取depth<=1不剪枝的搜索方法, 并且给予depth=1时候, 可以形成杀棋的棋型知识的判断

这种方法的原理是, depth=1的搜索,可以达到depth==2的效果, 并且可以避免模糊知识判断带来的误搜索的缺陷

这种解决方案的优点在于

a. depth=1可以生成杀棋的知识可以穷举

b. 知识准确度高,可以大幅度减少搜索浪费

缺点在于, depth=1可以形成的杀型, 覆盖面有限, 剩下的知识, 还是需要通过一些模糊判断来补充, 当然, 这种补充少很多了, 而且完善起来也难度降低很多

上面的介绍可以说是知识模型的缺陷造成的对搜索的依赖, 下面我再来说说, 知识对搜索产生的影响

我们假设有一个盘面, depth=11的PVS全搜索才能发现杀棋, 那么下面的知识, 做depth=10搜索时,哪种才能走出正确的棋步呢?

a. 对depth=1情况可杀棋的知识评估

b. 对depth>=2情况可杀棋的知识评估

c. 子力组合(如单车单王胜单王)和子力优势

d. 位置分(不是子力表,只是位置的分数,如灵活度等)

实际上我们很容易就可以判断出来, depth=1的知识评估,能走出正确的棋步,情况b也可能走出正确的棋步, 但是会有一定的误判, c, d大都情况下, 走不出正确的棋步

我们现在对所有的知识打分, 这个分数依赖的因素应该是(depth, 准确度, 搜索浪费), 即score=形势*(准确度/(depth*搜索浪费))

因为用评估盘面希望得到的分数等于depth>3的棋步, 准确度是相当低甚至会引起大量错误的, 所以我们对盘面评估会有一定的限度,同理,评估depth=1变化内的盘面,我们可以做到非常精确,这个时候可以给一个准确的分数

上面提到的a,b,c,d四种知识,对中国象棋软件的知识覆盖面是相当广了, 我们可以很简单看出, a可以奖励>马炮的分数, 而b因为可能走入误区, 常常只是奖励>士相的分数, 子力组合不会产生误区,但是需要搜索很深才能得出正解,所以分数也是不会太高,位置分则更小了

但是, 给予引擎全面而准确的知识是否恰当呢? 即, 知识是不是越全面, 棋力越强呢? 很多朋友都问过这个问题, 并且认为恰当的知识会减少搜索量, 而且这也是很多朋友追求的方向. 我实践的答案是否. 搜索其实是追求一种性价比, 单位搜索量内, 能得到最好的搜索结果, 才是好的搜索. 简单说说原理, 当盘面有两三个知识倾向都可以产生PV路径的时候, 只会带来引擎的左右徘徊, 尤其在杀棋的盘面, 会大大降低搜索的效率, 这部分的实践结果, 我会在"6. 建立以kingsafety为核心的审局, 以及审局模型的详细分析"再进一步详细分析

这里我想纠正一个错误的想法,常常有一些不了解搜索引擎原理的朋友,拿一些盘面,让棋软去判断,看谁能更快更准找到正解,要尽快解出这种盘面,往往需要大量的模糊知识,或者足够的深度,前者无疑是把棋软送上绝路的一种做法.这种评估只是有一定的意义,但绝对不是衡量棋软水平的标准.

2. fruit引擎分析, fruit引擎能达到2600的高度的原因 (对比crafty进行阐述)

fruit引擎并不追求速度,实际上,fruit并没有使用流行的bitfile,bitrank技术或者bitboard,所以fruit的nps在国际象棋引擎中并不算高(我想比起crafty应该比不上),如果说两者的差异在于评估的话,嗯,那不在我所了解的范围,我只谈谈两者引擎上面的差别

a. fruit的pv节点的意义以及基于pv节点搜索剪枝的效率

能够在搜索中, 把PV节点区分出来, 并且根据节点类型进行剪枝, fruit可以说对PVS理解是非常深刻的.

PV节点的定义大家可以查查相关资料, 既然PV节点表示正确的搜索结果, 那么就肯定不应该剪掉. 同样,对于不是PV节点的, 就不会找出正确的搜索路径, 这就应该剪掉.这个也是fruit剪枝的理论依据。

道理是这样说, 但是我们一开始并不知道每一个节点的类型, 所以在搜索的时候, 会假设某个节点不是PV节点, 然后看它是否会fail, 如果fail,再做PV节点的搜索.

假如这种假设是成立的, 那么就成功完成了对该非PV节点路径的剪枝,否则,需要重新搜索,因为对PV节点假设判断的搜索是做windows=1的搜索,所以耗费的代价是很低的.

下面来看看fruit的实现方法,我认为fruit对PV节点理解的实现方法非常优雅.

int search_root()

{

本节点做PV搜索

if (树根节点并且首节点)

下一层节点为PV节点 // 这个时候还没有找出PV路径,所以必须做PV节点搜索

else

{

下一层节点做假设不是PV节点的搜索

if (fail)

下一层节点做PV节点的搜索

}

int search_full()

{

根据上一层对该节点的判断, 进行节点搜索

if (首节点 || 假设不是PV节点的搜索) // 当假设不是PV节点时, windows=1这个时候不应该假设,应该直接计算了,否则就是重复计算浪费时间

下一节点的节点类型跟本节点类型一致

else

{

下一层节点做假设不是PV节点的搜索

if (fail)

下一层节点做PV节点的搜索

}