人工智能系列--一些技巧心得

 #1  棋软实现的一些技巧心得

一直以来都很想把自己积累的心得发表出来，和大家一起共享，希望能够促进棋软的发展，感谢elephantbase提供这样的一个传播空间

组成棋软的几大核心:
1. 开局库
2. 计算
3. 审局

开局库对棋软的帮助非常大，很多引擎之间对战，成绩接近，但是一配合开局库，差异就拉大了，根据个人经验，开局库的质量，会影响对局的30%左右的成绩。考虑到引擎的特点不同，需要调整开局库，引导盘面进入适合自己计算的盘面，一般来说，引擎的大都有如下倾向：1.善守；2.善攻，毫无疑问，对于善守的引擎，盘面拉入双方接近的粘滞情况，对于善攻，盘面拉入双方互有机会的盘面，都是很有帮助的

计算是引擎的重要组成部分，也是大家考虑最多的，本人在理论的研究上比较肤浅，就只谈谈实现的技巧吧

1. 如何加速引擎：假如统计过引擎内访问的节点，我们很容易就知道，访问次数最多的节点是静态quiet节点，其次是fullsearch节点，那么让我们来看看，组成quiet节点和fullsearch节点最重要的函数是什么？在我的引擎里面，访问次数最多的是Incheck(), genmove(), gencap(), domove(), undomove()，如果评估函数eval()占的比例很大，评估函数的比例也是很重要的。学过计算机的一些基础理论应该知道，赋值操作>判断语句>函数调用，所以，在上面的几个函数，需要避免函数调用（如：不要用包含构建函数的数据类型，尽量内联等），减少判断，这样就可以加速引擎了。

1.1 domove()和undomove()里面的操作基本上是赋值操作，但是考虑到context，很多人习惯在domove()和undomove()里面保存每一个棋步的上下文变化，某些上下文并不是必要的，请把这些不需要的上下文去掉。

1.2 eval(), incheck(), genmove(), gencap()里面包含了大量的棋子关系判断和棋步生成判断，加速这些函数最佳的方法是，把去掉棋子关系判断以及利用棋步预生成技术。if (!colour_is_same()) addeat(); 这样的做法，可以通过idx = colour1^colour2, 生成一个标志，把对应的数据放到对应的数据空间即可. 即上面的代码可以变成 move_eat[idx];这样就可以方便区分开棋步，同时也去掉了判断

1.3 用尽量少的数据，表达更多的内容。现在bitfile, bitrank技术相当的流行(当然这离不开eleeye的开源的帮助), bitfile和bitrank技术，有效减少了车炮棋步的判断次数，对nps的提高有50%的帮助，这是一个很典型的用尽量少的数据表达更多内容的例子。表达棋盘的基本元素colour, piece, square(坐标), move都建议尽量用bit位，这种帮助是很明显的。

1.4 bitboard对eval()的帮助。bitboard本身就包含了bitfile, bitrank的信息，所以bitboard可以很方便实现车炮的预计算（bitboard可以通过维持一个按行排列，一个按列排列的组合来实现bitfile, bitrank），bitboard在表达棋子之间的模糊关系时，有强大优势。考虑到目前的机器大都是4字节对齐，32bit，建议用4个32位来表达一个bitboard，这样可以很好处理棋步

2. 保持引擎的计算的稳定，少用剪枝。现在机器已经发展到一定的高度，引擎的计算层数，已经相当的深，所以，避免因为剪枝而错失关键棋步，已经成为引擎的一个重要组成元素。在我实现的引擎中，有损剪枝法，只用nullmove，这样可以大幅度提高引擎对抗的能力。棋软也有一个木桶理论，最差的棋步，决定棋软的水平，

2.1 机器速度提高的帮助，在目前来看，机器速度的提高，才是引擎最快的提高方法，虽然有点无奈，但这是一个事实，引擎辛苦调出来5%的节点节省，随便用个好点的机器，就已经可以弥补了，不要轻视机器的差别，举个例子，在有损的情况下nullmove节省了50%的节点，但是机器提高20%~30%的速度，就完全可以达到同样的效果

2.2 避免出错。hashtable或者history, killermove的棋步，一些实现方法都会导致棋步不可用，这必须对棋步的合法性做出判断，这些一旦出错，直接导致致命错误，类似的还有内存访问的问题

2.3 提高准确度。在quiet节点的评估，可以在王被将军或者不被将军两种情况下，进行评估，我采用了一直走到王不被将军和无吃子的盘面进行评估。

2.4 nullmove，这是重点中的重点，我建议参考fruit2.1(国象引擎)中，对nullmove的实现方法，毫无疑问，fruit的实现方法非常优秀，而且很值得玩味。nullmove需要verify，这是保证nullmove质量的一个关键手段。

2.5 棋步排序，我采取的棋步排序是根据当前盘面是否被将军来排序，如果被将军，次序为hashmove->eat attacker->kingmove->left, 否则，采用hashmove->matekiller->win capture(小吃大)->goodcapture(吃没有保护的子)->killermove->capture->history->left，对棋步排序一个很有意义的指标是fhf，即第一节点返回率（参考crafty），棋步排序对计算质量的提高是非常明显的。

2.6 alpha-beta和pv节点，不同的节点，采取不同的搜索方法和剪枝方法，请参考fruit的实现方法，非常优雅。请保证自己能够理解这个概念。

2.7 延伸，将军延伸是必要的，其他的延伸有一定的帮助，但是效果未必很好，在crafty中，matethreat延伸只有3/4将军延伸的价值，recapture的价值也被降低，这部分需要大量的测试工作。

2.8 其他的一些可以加速的算法，如internal iterative deepening等，对加速未必会非常明显，所以我只使用了iid.

3 审局
审局是对盘面的评估，这就需要保证审局的知识是准确的，虽然审局可以不全面，但是，使用了错误的知识，必然会导致问题

在我的审局模型中，我对审局划分为包括棋型/倾向性引导/王威胁三种评估

3.1 审局的作用，当引擎稳定后，对杀棋棋步进行测试，我们会发现，能否搜索出杀棋，跟引擎是息息相关，跟审局则是关系不大，但是，盘面危险度的认识，却跟引擎息息相关，所以，我们得出一个结论，审局，只是评估危险度，不要让审局承担提前发现杀棋的工作，多在引擎本身找找原因

3.2 王威胁>倾向性引导>棋型。我把棋型定义为子的摆放位置，倾向性引导定义为子力组合和运子方向，王威胁是对9宫的进攻情况。三者分数如上所述。很多棋型的合理性，在使用了子力表后，在计算中是可以体现出来的，但是，单车和单车士象全这种子力组合，却是无法通过子力表得知的。

3.3 王威胁模型，考虑下图：
   |   |   |
---+--+--+---
---|---+--|---
---+--+--+---
   |   |   |
假如王所在的9宫，是在棋盘的中心，而且兵的方向可以4周移动，那么，车马炮兵对9宫的威胁，是4个方向等价的

但是在实际棋盘中，因为规则限制的原因，9宫在4个方向受到的威胁是不同的，这就表示，棋子的移动方向，对王的威胁有影响

我们知道，车炮受到的影响是较少的，而马兵则很大，分析表明，马到了两边，可以踩到的9宫点明显减少，同理，兵也是，而车炮能踩到的9宫点，则不会变化太多

所以，我们可以得出一个推论，子对9宫的攻击点越多，那么，对王的威胁越大。

我们再来看看防守子，当象挡住了车照王，车对9宫的攻击点只有一个！所以，在我的模型里面，防守子的意义，在于减少对9宫的攻击点！

即，对9宫的威胁，通过攻击点的个数和程度来表示。例如，(炮)->(车)->[士]->[王]，这样对9宫的攻击点有两个，因为车炮都双重攻击，所以被攻击的两个点的威胁度很高，(炮)->(马)->[士]->[王]可以有4个攻击点，但是威胁度都比较低，子力组合可以跟攻击点的威力有一定挂钩。

由此，抽象出一个模型，王被威胁的程度=f(进攻的子力组合,进攻的点)，对王的威胁评估，只需寻找出上述两个参数，即可查表得知目前被威胁的程度

这种评估是想相当准确的。

3.4 子力组合和运子，当无法对王造成威胁时，子力组合和运子就非常重要了，运子在特定盘面，都有一定的倾向度，所以，搜索前通过调整子力表，即可对运子造成影响，当然，需要准确评估还是eval()可靠，如兵卒的分数调整。子力组合的情况，子少时，就是残局了，中局时，车马马是不如车马炮的，这些都需要有一定提示。

3.5 评估的准确，空头炮在子力充沛时，分数很高，但是子力减少，则威力降低。很多人的空头炮就采用了上述方法进行评估，如果按我的模型来算，则是因为子力减少，导致王威胁出现的机会降低，所以，空头炮如果子力很多但是无法舒展，还强行保持空头炮，会很危险。这就涉及审局准确度的问题。即，多高概率的事件可以采用模糊评估？

上面是我对棋软的一些认识，希望能对大家有帮助。因为本人的理论水平不高，用词不准确，对此抱以万分歉意。