节点的静态排序

17.1.1　节点的静态排序

在博弈树节点的展开过程中，如果不采用任何先验的知识，其子节点在展开时多是随机的。为了避免这种盲目性，将适当的知识引入到节点展开过程中，来对各个子节点的重要性有个大致认识，由此来指引其子节点的展开，使之在展开和搜索过程中具有更高的效率。

关于这个静态排序的工作，是在搜索节点需要展开之前完成的，也就是我们前面章节介绍搜索节点中谈到的sort_playable函数。在排序时，由于排序是为蒙特卡洛树搜索来服务，所以在注重准确性的同时也要兼顾时间效率。

Listing17.1中就是关于sort_playable的实现伪码，其中，通过使用不同的生成器来达到给可选点排序的目的。对于各种不同的生成器，我们根据其重要性的不同而赋予不同的权重，对于某个可选点而言，通过将其不同生成器得到的权重进行累加，来得到该可选点的一个总的评分。

Listing17.1　搜索节点的静态排序

关于sort_playable中使用的生成器，我们只是以GeneratorPolicyA和GeneratorPolicyB为例，在具体使用中，我们可以选择很多生成器，前面讲述程序结构时提到的Nakade_Genrator就是一个效果很好的生成器，本章后面讲述生成器的时候，我们还会介绍到较复杂的逃跑生成器（Rescue_Generator）和吃子生成器（Capture_Generator），这些都是在程序中会使用到的，至于权值的选择，因每个人对围棋感觉的不同而不尽相同，也因生成器实现的不同而不尽相同。需要强调的是，在程序中有些时候我们并不追求绝对的准确，程序的效率也是不得不考虑的，如果从100%的准确性到99%的准确性可以获得速度上10倍的提升，那么我们就很可能会在准确性上做妥协。