博弈树节点的表示

16.2　博弈树节点的表示

在博弈树搜索中，整棵博弈树是通过一个个的节点以父子结构连接构成的，这棵博弈树是自组织、自生长的，当搜索到达一个节点之后，如果该节点不是叶子节点的话，则会在其子节点中利用UCB1公式选择一个子节点作为当前节点，如果该节点已经是叶子节点，则调用评估器对该叶子节点进行评估和扩展。由此可见，Node类也就是整个UCT算法的核心。

在Node类中，每个节点最基本的信息就是当前节点的状态了，除此之外，则是关于树的组织结构的信息。而所谓当前节点状态也就是当前节点所处的棋盘状态的信息，为此，继承自Board作为其一个子类是自然而然的想法。

在UCT引擎类中，对于整棵博弈树，我们只需记录root节点即可，而要完成一次模拟过程，则只需告诉根节点即可，之后，便可以自动从根节点开始，通过一层一层的运用UCB1公式进行选择，进而，到达某一叶子节点，而该叶子节点则自动调用评估器进行评估，并生成子节点，这样便完成了一次模拟。而整个过程就是不断地进行模拟，直到到达某一终止条件（时间或模拟次数）为止。第17章中的Listing17.5中的simulate函数就是控制这一过程的，只要终止条件未达到，便不断调用root节点的simulate函数，使整棵博弈树不断地生长、扩展，进而使得该博弈树积累尽可能多的关于当前局面的在线知识，而使在落子位置的选择上尽可能的准确。

Listing16.4中就是节点类的伪码，在博弈树的每一节点中，主要包含两类信息，其一是当前节点所处的盘面状态的信息，其二是关于博弈树结构的相关信息。考虑到需要保存该节点所处位置的盘面的全部信息，要达到这一目的，使其继承自Board，作为Board的一个子类是不错的选择；而关于博弈树的结构，由于模拟的过程，只是一个从根节点到叶子节点的单向的过程，所以，对于每个节点而言，再额外记录指向其子节点的指针就足矣。

在前面章节介绍蒙特卡洛博弈树搜索的时候，我们也提到了采用逐渐扩展的算法来优化博弈树的搜索，在Listing16.4的伪码中，我们也进行了相关实现。为了能进行逐渐扩展，就必须首先对其叶子节点有个排序，sort_playable函数就是完成排序这个目的的；引入一个新的子节点的操作，则是通过add_child函数来实现的；而何时引入这些新的子节点，则是在simulate函数的最后，通过对该节点被访问的次数进行判断而决定其是否进行扩展的。

其中，在simulate函数中，当该节点是叶子节点时，则调用评估器对该叶子节点进行评估；sort_playable函数中，则大量采用生成器，通过给不同的生成器赋予不同的权重，并将各个生成器的影响进行累加后再做排序，由此得到其子节点逐渐扩展的一个顺序，其具体实现细节将在第17.1节中详细介绍。

Listing16.4　蒙特卡洛博弈树节点伪码