計(jì)算機(jī)博弈(六) 并行搜索技術(shù)探索(共6頁)

1、(六)并行搜索(su su)技術(shù)探索并行搜索是博弈搜索技術(shù)中最復(fù)雜的組成部分(z chn b fn)，這就是ElephantEye沒有采用并行技術(shù)的原因。盡管如此，筆者還是在這里簡單地談一下對并行搜索(su su)的認(rèn)識。6.1并行計(jì)算的基本操作并行計(jì)算有兩種體系，一是單機(jī)體系，即一個程序在單機(jī)的多個處理器上運(yùn)行，簡稱SMP(對稱多處理器)，二是分布式體系，即一個程序在多個計(jì)算機(jī)聯(lián)成的網(wǎng)絡(luò)上運(yùn)行，簡稱Cluster(計(jì)算機(jī)集群)。兩者最大的區(qū)別是，單機(jī)體系的多個處理器可以共享存儲器(并且共享同一地址的存儲單元)，而分布式體系則必須通過網(wǎng)絡(luò)來交換信息(盡管傳輸速度非常高，通常在1000MBPS以

2、上)。由于博弈搜索需要用到置換表，所以特別適合以SMP的方式作并行計(jì)算。Windows、UNIX等多任務(wù)操作系統(tǒng)都有線程(Thread)這個概念，線程是處理器任務(wù)的最小單位，一個線程是不可能同時在兩個處理器上運(yùn)行的，建立線程后，操作系統(tǒng)就會自動把新建的線程分配到空閑的處理器上。Windows下建立線程的方法是：#include DWORD ThreadId;CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) ThreadEntry, (LPVOID) &ArgList, 0, &ThreadId);UNIX下建立線程的方式是：#include pthr

3、ead_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僅僅是某個線程的入口，以便整理參數(shù)ArgList并且在線程中調(diào)用其他函數(shù)。例如，一個用遞歸函數(shù)來計(jì)算斐波那契數(shù)列的并行程序(

4、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 Th

5、readId;int Result;ArgListStruct ArgList;if (Arg 30) if (Decrement(&IdleThreads) Value = FibonacciSMP(ArgListPtr-Value);ArgListPtr-Active = false;Increment(&IdleThreads);return NULL;由于(yuy)Fibonacci()函數(shù)的遞歸形式如同二叉樹一樣擴(kuò)展開來，所以當(dāng)處理器有空閑時，就可以把其中一個分枝交給(jio i)另一個線程，這個操作稱為遞歸樹的分割(Split)。為此程序需要維護(hù)(wih)變量IdleThreads

6、來判斷是否還有空閑的處理器，對該變量的操作必須用Increment()和Decrement()函數(shù)(即Intel處理器的INC和DEC原子指令，參閱)，以保證不會因?yàn)橛袃蓚€線程同時對該變量操作而發(fā)生錯誤，這樣的共享變量都應(yīng)該標(biāo)記為volatile屬性，以避免編譯器對這些變量作優(yōu)化。由于線程的維護(hù)需要消耗額外的處理器資源，所以并非每個遞歸結(jié)點(diǎn)要作分割的嘗試，以上這段程序的核心問題盡管是FibonacciSMP()的遞歸，但當(dāng)遞歸樹不太大(參數(shù)不超過30)時，調(diào)用單純的遞歸函數(shù)Fibonacci()會得到更高的效率。6.2加鎖技術(shù)和非加鎖技術(shù)如果兩個線程同時存取同一存儲單元，就有可能產(chǎn)生錯誤，為此

7、必須建立預(yù)防錯誤的機(jī)制，通常的措施是加鎖(Lock)。一個比較簡單的加鎖方法是調(diào)用函數(shù)Exchange()(即Intel處理器的XCHG原子指令，參閱)，因?yàn)閮蓚€線程的原子語句是不可能同時存取同一存儲單元的(正因?yàn)槿绱?，處理器對存儲單元作INC、DEC、XCHG等操作就需要考慮沖突，所以比較耗時)。在某塊共享的存儲單元中，第一個變量就是加鎖標(biāo)志，false表示未加鎖，true表示加鎖。加鎖時只要用true和加鎖標(biāo)志交換，換出false就表示加鎖成功(原來加鎖標(biāo)志是false，交換后變成true)，該線程就獲得對共享單元的操作權(quán)，換出true則表示加鎖失敗(原來加鎖標(biāo)志是true，交換后仍舊是t

8、rue)。對共享單元操作完畢后，再將加鎖標(biāo)志設(shè)成false來解鎖。并行計(jì)算的博弈程序會偶爾出現(xiàn)一種情況，即兩個線程同時存取同一置換表項(xiàng)，為避免錯誤可以使用加鎖技術(shù)：struct HashRecord volatile int Lock;void RecordHash / ProbeHash () HashRecord *HashPtr = HashList + ZobristKey % HashSize;while (Exchange(&HashPtr-Lock, true) HashPtr-Lock = false;但是，并行國際象棋程序(chngx)的典范Crafty并沒有這樣(zhyng

9、)做，而是采用了不加鎖的技術(shù)，來避免置換表的存取沖突。簡而言之，該算法的思想是當(dāng)置換表項(xiàng)的校驗(yàn)碼存取正確時，必須保證局面信息也存取正確(但允許(ynx)校驗(yàn)碼存取不正確，此時探索置換表的例程就會跳過以后的操作而不會引發(fā)錯誤)。為此Crafty的128位置換表項(xiàng)定義為兩個64位數(shù)W1和W2，W1是局面信息，而W2存儲了W1和校驗(yàn)碼的異或值，探測置換表項(xiàng)時，校驗(yàn)碼必須由W1和W2的異或值求得，這樣一旦W1讀取錯誤，就得不到正確的校驗(yàn)碼，換句話說，校驗(yàn)碼的正確就保證了局面信息的正確。Crafty的這種不加鎖算法是針對64位處理器而設(shè)計(jì)的，這種技術(shù)當(dāng)然也適用于32位處理器，而筆者認(rèn)為32位處理器還有更

10、為簡單的處理方式，即設(shè)計(jì)如下的置換表項(xiàng)：struct HashRecord long CheckSum1, PositionInfo1, PositionInfo2, CheckSum2;以上128位的置換表項(xiàng)由4個32位單元組成，存取置換表時四個單元依次讀取或?qū)懭?。只要位于首尾的校?yàn)碼都能存取正確，就確保了中間兩個局面信息單元的正確。6.3搜索樹的分割策略Alpha-Beta搜索是遞歸式的，因此作并行計(jì)算時可以仿照上面提到的Fibonacci()遞歸的例子，但這里有兩個問題需要解決，一是某個子線程產(chǎn)生Beta截?cái)鄷r，如何通知其他子線程中止搜索，二是考慮什么樣的結(jié)點(diǎn)需要分割，什么樣的結(jié)點(diǎn)不需要

11、分割。這兩個問題都是并行搜索技術(shù)的難點(diǎn)，為此Crafty花了大量的代碼來解決這些問題，其作者Robert Hyatt對Crafty的并行算法DTS(Dynamic Tree Split，即搜索樹的動態(tài)分割算法)有專門的介紹。這里筆者只簡單地介紹第二個問題，即搜索樹的分割策略。通常Alpha-Beta搜索樹的結(jié)點(diǎn)可分為三個類型，即PV結(jié)點(diǎn)、Beta結(jié)點(diǎn)和Alpha結(jié)點(diǎn)，并且有明確的定義搜索值在窗口(Alpha, Beta)之間的是PV結(jié)點(diǎn)(根據(jù)最小-最大原理，最佳著法的搜索值必須落在窗口內(nèi))，搜索值達(dá)到或超過Beta(即高出邊界)的是Beta結(jié)點(diǎn)(僅需要有一個著法超過Beta即可)，搜索值未能超

12、過Alpha(即低出邊界)的是Alpha結(jié)點(diǎn)(所有著法都不能超過Alpha)。由此可以看出，PV結(jié)點(diǎn)和Alpha結(jié)點(diǎn)都需要搜索所有的著法，而Beta結(jié)點(diǎn)在最好的情況下只要搜索一個著法即可。如果(rgu)能在搜索之前預(yù)測出結(jié)點(diǎn)的類型，就可以決定是否對該結(jié)點(diǎn)作分割了，在Crafty及其相關(guān)論文(lnwn)中，預(yù)測的三類結(jié)點(diǎn)命名為PV結(jié)點(diǎn)(ji din)、Cut結(jié)點(diǎn)和All結(jié)點(diǎn)，分別對應(yīng)剛才提到的PV結(jié)點(diǎn)、Beta結(jié)點(diǎn)和Alpha結(jié)點(diǎn)。顯然，PV結(jié)點(diǎn)和All結(jié)點(diǎn)是有分割價值的，只要預(yù)測正確，這些結(jié)點(diǎn)下的全部著法都要搜索，不會因?yàn)楫a(chǎn)生截?cái)喽速M(fèi)搜索時間，而對Cut結(jié)點(diǎn)作分割是沒有意義的，因?yàn)槟壳暗乃阉?/p>

13、技術(shù)使得Cut結(jié)點(diǎn)的第一著法截?cái)嗦矢哌_(dá)80%以上，對結(jié)點(diǎn)作分割只會浪費(fèi)處理器資源。至于如何來預(yù)測結(jié)點(diǎn)類型，在Crafty及其相關(guān)論文也有介紹，但是另一個國際象棋程序Fruit則描繪得更加明確，其分類策略是：(1)根結(jié)點(diǎn)總是PV結(jié)點(diǎn)。(2) PV結(jié)點(diǎn)采用PVS算法，即第一個著法以后首先嘗試零窗口的搜索，由于期望每個著法都低出邊界(即子結(jié)點(diǎn)都高出邊界)，所以預(yù)測這些零窗口的結(jié)點(diǎn)為Cut結(jié)點(diǎn)。(3) Cut結(jié)點(diǎn)和All結(jié)點(diǎn)是互相交替的，即Cut結(jié)點(diǎn)的子結(jié)點(diǎn)是All結(jié)點(diǎn)，All結(jié)點(diǎn)的子結(jié)點(diǎn)是Cut結(jié)點(diǎn)，空著裁剪同樣這么處理。(4) Cut結(jié)點(diǎn)的第一個子結(jié)點(diǎn)(All結(jié)點(diǎn))如果不能產(chǎn)生截?cái)啵驼f明原來預(yù)測

14、的Cut結(jié)點(diǎn)是錯的，應(yīng)該是All結(jié)點(diǎn)，那么以后的子結(jié)點(diǎn)都預(yù)測為Cut結(jié)點(diǎn)。換句話說，不管預(yù)測是否正確，Cut結(jié)點(diǎn)的第一個子結(jié)點(diǎn)(不包括空著裁剪)是All結(jié)點(diǎn)，其余的結(jié)點(diǎn)(如果有必要搜索的話)仍舊是Cut結(jié)點(diǎn)。(5) PV結(jié)點(diǎn)不采用各種形式的向前裁剪(Null-Move、History、Futility等)。由于Fruit不支持并行搜索，所以Cut結(jié)點(diǎn)和All結(jié)點(diǎn)沒有區(qū)別，但給并行搜索留下了伏筆。我們關(guān)注的是PV結(jié)點(diǎn)的分割，顯然PV結(jié)點(diǎn)是有必要分割的，因?yàn)榉指钤皆纾碌木€程所處理的搜索樹就越大，并行效率就越高。(注意Fibonacci()遞歸的例子，為保證效率只有參數(shù)充分大時才會分割，Alpha-Beta遞歸也一樣。)但是PV結(jié)點(diǎn)的分割會遇到一個問題窗口寬度可能會變窄，如果讓所有的子結(jié)點(diǎn)都作相同窗口的搜索，就無法體現(xiàn)Alpha-Beta算法的效率了。為此，Crafty對根結(jié)點(diǎn)的迭代加深過程用了期望窗口(Aspiration Window)，即讓所有的子結(jié)點(diǎn)都搜索一個較窄的窗口，這要比直接分割(MATE_VALUE, MATE_VALUE)有效得多。而另一個極端的做法是MTD