- 中国象棋程序设计探索
-
- 2005年6月初稿，2007年5月修订
-
- (六) 并行搜索技术探索
-
- 在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
- (1) 高级搜索方法——期望窗口(Bruce Moreland)；
- (2) 高级搜索方法——主要变例搜索(Bruce Moreland)。
- 并行搜索是博弈搜索技术中最复杂的组成部分，这就是ElephantEye没有采用并行技术的原因。尽管如此，笔者还是在这里简单地谈一下对并行搜索的认识。
-
- 6.1 并行计算的基本操作
-
- 并行计算有两种体系，一是单机体系，即一个程序在单机的多个处理器上运行，简称SMP(对称多处理器)，二是分布式体系，即一个程序在多个计算机联成的网络上运行，简称Cluster(计算机集群)。两者最大的区别是，单机体系的多个处理器可以共享存储器(并且共享同一地址的存储单元)，而分布式体系则必须通过网络来交换信息(尽管传输速度非常高，通常在1000MBPS以上)。
- 由于博弈搜索需要用到置换表，所以特别适合以SMP的方式作并行计算。Windows、UNIX等多任务操作系统都有线程(Thread)这个概念，线程是处理器任务的最小单位，一个线程是不可能同时在两个处理器上运行的，建立线程后，操作系统就会自动把新建的线程分配到空闲的处理器上。Windows下建立线程的方法是：
-
- #include <windows.h>
- ……
- DWORD ThreadId;
- CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)
ThreadEntry, (LPVOID) &ArgList, 0, &ThreadId);
-
- UNIX下建立线程的方式是：
-
- #include <pthread.h>
- ……
- pthread_t pthread;
- pthread_attr_t pthread_attr;
- pthread_attr_init(&pthread_attr);
- pthread_attr_setscope(&pthread_attr, PTHREAD_SCOPE_SYSTEM);
- pthread_create(&pthread, &pthread_attr, (void
*(*)(void *)) ThreadEntry, (void *) &ArgList);
-
- 这里ThreadEntry仅仅是某个线程的入口，以便整理参数ArgList并且在线程中调用其他函数。例如，一个用递归函数来计算斐波那契数列的并行程序(Windows版本)：
-
- static volatile int IdleThreads;
-
- struct ArgListStruct {
- volatile bool Active;
- volatile int Value;
- };
-
- static void *ThreadEntry(ArgListStruct *ArgListPtr);
-
- static int Fibonacci(int Arg) {
- if (Arg < 2) {
- return 1;
- } else {
- return Fibonacci(Arg - 2) + Fibonacci(Arg - 1);
- }
- }
-
- static int FibonacciSMP(int Arg) {
- DWORD ThreadId;
- int Result;
- ArgListStruct ArgList;
- if (Arg < 2) {
- return 1;
- } else {
- if (Arg > 30) {
- if (Decrement(&IdleThreads) < 0) {
- Increment(&IdleThreads);
- return FibonacciSMP(Arg - 2) + FibonacciSMP(Arg
- 1);
- } else {
- ArgList.Value = Arg - 2;
- ArgList.Active = true;
- CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)
ThreadEntry, (LPVOID) &ArgList, 0, &ThreadId);
- Result = FibonacciSMP(Arg - 1);
- while (ArgList.Active) {
- Idle();
- }
- return Result + ArgList.Value;
- }
- } else {
- return Fibonacci(Arg - 2) + Fibonacci(Arg - 1);
- }
- }
- }
-
- static void *ThreadEntry(ArgListStruct *ArgListPtr) {
- ArgListPtr->Value = FibonacciSMP(ArgListPtr->Value);
- ArgListPtr->Active = false;
- Increment(&IdleThreads);
- return NULL;
- }
-
- 由于Fibonacci()函数的递归形式如同二叉树一样扩展开来，所以当处理器有空闲时，就可以把其中一个分枝交给另一个线程，这个操作称为递归树的分割(Split)。为此程序需要维护变量IdleThreads来判断是否还有空闲的处理器，对该变量的操作必须用Increment()和Decrement()函数(即Intel处理器的INC和DEC原子指令，参阅<x86asm.h>)，以保证不会因为有两个线程同时对该变量操作而发生错误，这样的共享变量都应该标记为volatile属性，以避免编译器对这些变量作优化。
- 由于线程的维护需要消耗额外的处理器资源，所以并非每个递归结点要作分割的尝试，以上这段程序的核心问题尽管是FibonacciSMP()的递归，但当递归树不太大(参数不超过30)时，调用单纯的递归函数Fibonacci()会得到更高的效率。
-
- 6.2 加锁技术和非加锁技术
-
- 如果两个线程同时存取同一存储单元，就有可能产生错误，为此必须建立预防错误的机制，通常的措施是加锁(Lock)。一个比较简单的加锁方法是调用函数Exchange()(即Intel处理器的XCHG原子指令，参阅<x86asm.h>)，因为两个线程的原子语句是不可能同时存取同一存储单元的(正因为如此，处理器对存储单元作INC、DEC、XCHG等操作就需要考虑冲突，所以比较耗时)。在某块共享的存储单元中，第一个变量就是加锁标志，false表示未加锁，true表示加锁。加锁时只要用true和加锁标志交换，换出false就表示加锁成功(原来加锁标志是false，交换后变成true)，该线程就获得对共享单元的操作权，换出true则表示加锁失败(原来加锁标志是true，交换后仍旧是true)。对共享单元操作完毕后，再将加锁标志设成false来解锁。
- 并行计算的博弈程序会偶尔出现一种情况，即两个线程同时存取同一置换表项，为避免错误可以使用加锁技术：
-
- struct HashRecord {
- volatile int Lock;
- ……
- };
-
- void RecordHash / ProbeHash (……) {
- HashRecord *HashPtr = HashList + ZobristKey % HashSize;
- while (Exchange(&HashPtr->Lock, true)) {
- }
- ……
- HashPtr->Lock = false;
- }
-
- 但是，并行国际象棋程序的典范Crafty并没有这样做，而是采用了不加锁的技术，来避免置换表的存取冲突。简而言之，该算法的思想是当置换表项的校验码存取正确时，必须保证局面信息也存取正确(但允许校验码存取不正确，此时探索置换表的例程就会跳过以后的操作而不会引发错误)。
- 为此Crafty的128位置换表项定义为两个64位数W1和W2，W1是局面信息，而W2存储了W1和校验码的异或值，探测置换表项时，校验码必须由W1和W2的异或值求得，这样一旦W1读取错误，就得不到正确的校验码，换句话说，校验码的正确就保证了局面信息的正确。
- Crafty的这种不加锁算法是针对64位处理器而设计的，这种技术当然也适用于32位处理器，而笔者认为32位处理器还有更为简单的处理方式，即设计如下的置换表项：
-
- struct HashRecord {
- long CheckSum1, PositionInfo1, PositionInfo2, CheckSum2;
- };
-
- 以上128位的置换表项由4个32位单元组成，存取置换表时四个单元依次读取或写入。只要位于首尾的校验码都能存取正确，就确保了中间两个局面信息单元的正确。
-
- 6.3 搜索树的分割策略
-
- Alpha-Beta搜索是递归式的，因此作并行计算时可以仿照上面提到的Fibonacci()递归的例子，但这里有两个问题需要解决，一是某个子线程产生Beta截断时，如何通知其他子线程中止搜索，二是考虑什么样的结点需要分割，什么样的结点不需要分割。这两个问题都是并行搜索技术的难点，为此Crafty花了大量的代码来解决这些问题，其作者Robert Hyatt对Crafty的并行算法DTS(Dynamic Tree Split，即搜索树的动态分割算法)有专门的介绍。这里笔者只简单地介绍第二个问题，即搜索树的分割策略。
- 通常Alpha-Beta搜索树的结点可分为三个类型，即PV结点、Beta结点和Alpha结点，并且有明确的定义——搜索值在窗口(Alpha, Beta)之间的是PV结点(根据最小-最大原理，最佳着法的搜索值必须落在窗口内)，搜索值达到或超过Beta(即高出边界)的是Beta结点(仅需要有一个着法超过Beta即可)，搜索值未能超过Alpha(即低出边界)的是Alpha结点(所有着法都不能超过Alpha)。由此可以看出，PV结点和Alpha结点都需要搜索所有的着法，而Beta结点在最好的情况下只要搜索一个着法即可。
- 如果能在搜索之前预测出结点的类型，就可以决定是否对该结点作分割了，在Crafty及其相关论文中，预测的三类结点命名为PV结点、Cut结点和All结点，分别对应刚才提到的PV结点、Beta结点和Alpha结点。显然，PV结点和All结点是有分割价值的，只要预测正确，这些结点下的全部着法都要搜索，不会因为产生截断而浪费搜索时间，而对Cut结点作分割是没有意义的，因为目前的搜索技术使得Cut结点的第一着法截断率高达80%以上，对结点作分割只会浪费处理器资源。
- 至于如何来预测结点类型，在Crafty及其相关论文也有介绍，但是另一个国际象棋程序Fruit则描绘得更加明确，其分类策略是：
- (1) 根结点总是PV结点。
- (2) PV结点采用PVS算法，即第一个着法以后首先尝试零窗口的搜索，由于期望每个着法都低出边界(即子结点都高出边界)，所以预测这些零窗口的结点为Cut结点。
- (3) Cut结点和All结点是互相交替的，即Cut结点的子结点是All结点，All结点的子结点是Cut结点，空着裁剪同样这么处理。
- (4) Cut结点的第一个子结点(All结点)如果不能产生截断，就说明原来预测的Cut结点是错的，应该是All结点，那么以后的子结点都预测为Cut结点。换句话说，不管预测是否正确，Cut结点的第一个子结点(不包括空着裁剪)是All结点，其余的结点(如果有必要搜索的话)仍旧是Cut结点。
- (5) PV结点不采用各种形式的向前裁剪(Null-Move、History、Futility等)。
- 由于Fruit不支持并行搜索，所以Cut结点和All结点没有区别，但给并行搜索留下了伏笔。
- 我们关注的是PV结点的分割，显然PV结点是有必要分割的，因为分割越早，新的线程所处理的搜索树就越大，并行效率就越高。(注意Fibonacci()递归的例子，为保证效率只有参数充分大时才会分割，Alpha-Beta递归也一样。)但是PV结点的分割会遇到一个问题——窗口宽度可能会变窄，如果让所有的子结点都作相同窗口的搜索，就无法体现Alpha-Beta算法的效率了。为此，Crafty对根结点的迭代加深过程用了期望窗口(Aspiration Window)，即让所有的子结点都搜索一个较窄的窗口，这要比直接分割(-MATE_VALUE, MATE_VALUE)有效得多。而另一个极端的做法是MTD(f)的零窗口，根结点从一开始就预测为Cut或All结点，即可实施有效的分割，这就是MTD(f)算法在并行计算上的优势。
上一篇 中国象棋程序设计探索(五)：克服水平线效应
下一篇 中国象棋程序设计探索(七)：开局库
返 回 象棋百科全书——电脑象棋
