?? 解剖大象的眼睛——中國象棋程序設(shè)計(jì)探索(六)：并行搜索技術(shù)探索.htm
字號:
face="Times New Roman">false</FONT>表示未加鎖，<FONT
face="Times New Roman">true</FONT>表示加鎖。加鎖時(shí)只要用<FONT
face="Times New Roman">true</FONT>和加鎖標(biāo)志交換，換出<FONT
face="Times New Roman">false</FONT>就表示加鎖成功<FONT
face="Times New Roman">(</FONT>原來加鎖標(biāo)志是<FONT
face="Times New Roman">false</FONT>，交換后變成<FONT
face="Times New Roman">true)</FONT>，該線程就獲得對共享單元的操作權(quán)，換出<FONT
face="Times New Roman">true</FONT>則表示加鎖失敗<FONT
face="Times New Roman">(</FONT>原來加鎖標(biāo)志是<FONT
face="Times New Roman">true</FONT>，交換后仍舊是<FONT
face="Times New Roman">true)</FONT>。對共享單元操作完畢后，再將加鎖標(biāo)志設(shè)成<FONT
face="Times New Roman">false</FONT>來解鎖。
<DT> 并行計(jì)算的博弈程序會偶爾出現(xiàn)一種情況，即兩個(gè)線程同時(shí)存取同一置換表項(xiàng)，為避免錯(cuò)誤可以使用加鎖技術(shù)：
<DD>
<DD>struct HashRecord {
<DD> volatile int Lock;
<DD> ……
<DD>};
<DD>
<DD>void RecordHash / ProbeHash (……) {
<DD> HashRecord *HashPtr = HashList + ZobristKey % HashSize;
<DD> while (Exchange(&HashPtr->Lock, true)) {
<DD> }
<DD> ……
<DD> HashPtr->Lock = false;
<DD>}
<DT>
<DT> 但是，并行國際象棋程序的典范<FONT
face="Times New Roman">Crafty</FONT>并沒有這樣做，而是采用了不加鎖的技術(shù)，來避免置換表的存取沖突。簡而言之，該算法的思想是當(dāng)置換表項(xiàng)的校驗(yàn)碼存取正確時(shí)，必須保證局面信息也存取正確<FONT
face="Times New Roman">(</FONT>但允許校驗(yàn)碼存取不正確，此時(shí)探索置換表的例程就會跳過以后的操作而不會引發(fā)錯(cuò)誤<FONT
face="Times New Roman">)</FONT>。
<DT> 為此<FONT face="Times New Roman">Crafty</FONT>的<FONT
face="Times New Roman">128</FONT>位置換表項(xiàng)定義為兩個(gè)<FONT
face="Times New Roman">64</FONT>位數(shù)<FONT face="Times New Roman">W1</FONT>和<FONT
face="Times New Roman">W2</FONT>，<FONT
face="Times New Roman">W1</FONT>是局面信息，而<FONT
face="Times New Roman">W2</FONT>存儲了<FONT
face="Times New Roman">W1</FONT>和校驗(yàn)碼的異或值，探測置換表項(xiàng)時(shí)，校驗(yàn)碼必須由<FONT
face="Times New Roman">W1</FONT>和<FONT
face="Times New Roman">W2</FONT>的異或值求得，這樣一旦<FONT
face="Times New Roman">W1</FONT>讀取錯(cuò)誤，就得不到正確的校驗(yàn)碼，換句話說，校驗(yàn)碼的正確就保證了局面信息的正確。
<DT> <FONT face="Times New Roman">Crafty</FONT>的這種不加鎖算法是針對<FONT
face="Times New Roman">64</FONT>位處理器而設(shè)計(jì)的，這種技術(shù)當(dāng)然也適用于<FONT
face="Times New Roman">32</FONT>位處理器，而筆者認(rèn)為<FONT
face="Times New Roman">32</FONT>位處理器還有更為簡單的處理方式，即設(shè)計(jì)如下的置換表項(xiàng)：
<DD>
<DD>struct HashRecord {
<DD> long CheckSum1, PositionInfo1, PositionInfo2, CheckSum2;
<DD>};
<DT>
<DT> 以上<FONT face="Times New Roman">128</FONT>位的置換表項(xiàng)由<FONT
face="Times New Roman">4</FONT>個(gè)<FONT
face="Times New Roman">32</FONT>位單元組成，存取置換表時(shí)四個(gè)單元依次讀取或?qū)懭搿Ｖ灰挥谑孜驳男ｒ?yàn)碼都能存取正確，就確保了中間兩個(gè)局面信息單元的正確。
<DT>
<DT><FONT face=Arial size=4><STRONG>6.3 </STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>搜索樹的分割策略</STRONG></FONT>
<DT>
<DT> <FONT
face="Times New Roman">Alpha-Beta</FONT>搜索是遞歸式的，因此作并行計(jì)算時(shí)可以仿照上面提到的<FONT
face="Times New Roman">Fibonacci()</FONT>遞歸的例子，但這里有兩個(gè)問題需要解決，一是某個(gè)子線程產(chǎn)生<FONT
face="Times New Roman">Beta</FONT>截?cái)鄷r(shí)，如何通知其他子線程中止搜索，二是考慮什么樣的結(jié)點(diǎn)需要分割，什么樣的結(jié)點(diǎn)不需要分割。這兩個(gè)問題都是并行搜索技術(shù)的難點(diǎn)，為此<FONT
face="Times New Roman">Crafty</FONT>花了大量的代碼來解決這些問題，其作者<FONT
face="Times New Roman">Robert Hyatt</FONT>對<FONT
face="Times New Roman">Crafty</FONT>的并行算法<FONT
face="Times New Roman">DTS(Dynamic Tree Split</FONT>，即搜索樹的動(dòng)態(tài)分割算法<FONT
face="Times New Roman">)</FONT>有專門的介紹。這里筆者只簡單地介紹第二個(gè)問題，即搜索樹的分割策略。
<DT> 通常<FONT face="Times New Roman">Alpha-Beta</FONT>搜索樹的結(jié)點(diǎn)可分為三個(gè)類型，即<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)、<FONT
face="Times New Roman">Beta</FONT>結(jié)點(diǎn)和<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)，并且有明確的定義——搜索值在窗口<FONT
face="Times New Roman">(Alpha, Beta)</FONT>之間的是<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)<FONT
face="Times New Roman">(</FONT>根據(jù)最小<FONT
face="Times New Roman">-</FONT>最大原理，最佳著法的搜索值必須落在窗口內(nèi)<FONT
face="Times New Roman">)</FONT>，搜索值達(dá)到或超過<FONT
face="Times New Roman">Beta(</FONT>即高出邊界<FONT
face="Times New Roman">)</FONT>的是<FONT
face="Times New Roman">Beta</FONT>結(jié)點(diǎn)<FONT
face="Times New Roman">(</FONT>僅需要有一個(gè)著法超過<FONT
face="Times New Roman">Beta</FONT>即可<FONT
face="Times New Roman">)</FONT>，搜索值未能超過<FONT
face="Times New Roman">Alpha(</FONT>即低出邊界<FONT
face="Times New Roman">)</FONT>的是<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)<FONT
face="Times New Roman">(</FONT>所有著法都不能超過<FONT
face="Times New Roman">Alpha)</FONT>。由此可以看出，<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)和<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)都需要搜索所有的著法，而<FONT
face="Times New Roman">Beta</FONT>結(jié)點(diǎn)在最好的情況下只要搜索一個(gè)著法即可。
<DT> 如果能在搜索之前預(yù)測出結(jié)點(diǎn)的類型，就可以決定是否對該結(jié)點(diǎn)作分割了，在<FONT
face="Times New Roman">Crafty</FONT>及其相關(guān)論文中，預(yù)測的三類結(jié)點(diǎn)命名為<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)、<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)和<FONT
face="Times New Roman">All</FONT>結(jié)點(diǎn)，分別對應(yīng)剛才提到的<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)、<FONT
face="Times New Roman">Beta</FONT>結(jié)點(diǎn)和<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)。顯然，<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)和<FONT
face="Times New Roman">All</FONT>結(jié)點(diǎn)是有分割價(jià)值的，只要預(yù)測正確，這些結(jié)點(diǎn)下的全部著法都要搜索，不會因?yàn)楫a(chǎn)生截?cái)喽速M(fèi)搜索時(shí)間，而對<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)作分割是沒有意義的，因?yàn)槟壳暗乃阉骷夹g(shù)使得<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)的第一著法截?cái)嗦矢哌_(dá)<FONT
face="Times New Roman">80%</FONT>以上，對結(jié)點(diǎn)作分割只會浪費(fèi)處理器資源。
<DT> 至于如何來預(yù)測結(jié)點(diǎn)類型，在<FONT
face="Times New Roman">Crafty</FONT>及其相關(guān)論文也有介紹，但是另一個(gè)國際象棋程序<FONT
face="Times New Roman">Fruit</FONT>則描繪得更加明確，其分類策略是：
<DT> <FONT face="Times New Roman">(1) </FONT>根結(jié)點(diǎn)總是<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)。
<DT> <FONT face="Times New Roman">(2) PV</FONT>結(jié)點(diǎn)采用<FONT
face="Times New Roman">PVS</FONT>算法，即第一個(gè)著法以后首先嘗試零窗口的搜索，由于期望每個(gè)著法都低出邊界<FONT
face="Times New Roman">(</FONT>即子結(jié)點(diǎn)都高出邊界<FONT
face="Times New Roman">)</FONT>，所以預(yù)測這些零窗口的結(jié)點(diǎn)為<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)。
<DT> <FONT face="Times New Roman">(3) Cut</FONT>結(jié)點(diǎn)和<FONT
face="Times New Roman">All</FONT>結(jié)點(diǎn)是互相交替的，即<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)的子結(jié)點(diǎn)是<FONT
face="Times New Roman">All</FONT>結(jié)點(diǎn)，<FONT
face="Times New Roman">All</FONT>結(jié)點(diǎn)的子結(jié)點(diǎn)是<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)，空著裁剪同樣這么處理。
<DT> <FONT face="Times New Roman">(4) Cut</FONT>結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)<FONT
face="Times New Roman">(All</FONT>結(jié)點(diǎn)<FONT
face="Times New Roman">)</FONT>如果不能產(chǎn)生截?cái)啵驼f明原來預(yù)測的<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)是錯(cuò)的，應(yīng)該是<FONT
face="Times New Roman">All</FONT>結(jié)點(diǎn)，那么以后的子結(jié)點(diǎn)都預(yù)測為<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)。換句話說，不管預(yù)測是否正確，<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)<FONT
face="Times New Roman">(</FONT>不包括空著裁剪<FONT
face="Times New Roman">)</FONT>是<FONT
face="Times New Roman">All</FONT>結(jié)點(diǎn)，其余的結(jié)點(diǎn)<FONT
face="Times New Roman">(</FONT>如果有必要搜索的話<FONT
face="Times New Roman">)</FONT>仍舊是<FONT face="Times New Roman">Cut</FONT>結(jié)點(diǎn)。
<DT> <FONT face="Times New Roman">(5) PV</FONT>結(jié)點(diǎn)不采用各種形式的向前裁剪<FONT
face="Times New Roman">(Null-Move</FONT>、<FONT
face="Times New Roman">History</FONT>、<FONT
face="Times New Roman">Futility</FONT>等<FONT face="Times New Roman">)</FONT>。
<DT> 由于<FONT face="Times New Roman">Fruit</FONT>不支持并行搜索，所以<FONT
face="Times New Roman">Cut</FONT>結(jié)點(diǎn)和<FONT
face="Times New Roman">All</FONT>結(jié)點(diǎn)沒有區(qū)別，但給并行搜索留下了伏筆。
<DT> 我們關(guān)注的是<FONT face="Times New Roman">PV</FONT>結(jié)點(diǎn)的分割，顯然<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)是有必要分割的，因?yàn)榉指钤皆纾碌木€程所處理的搜索樹就越大，并行效率就越高。<FONT
face="Times New Roman">(</FONT>注意<FONT
face="Times New Roman">Fibonacci()</FONT>遞歸的例子，為保證效率只有參數(shù)充分大時(shí)才會分割，<FONT
face="Times New Roman">Alpha-Beta</FONT>遞歸也一樣。<FONT
face="Times New Roman">)</FONT>但是<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)的分割會遇到一個(gè)問題——窗口寬度可能會變窄，如果讓所有的子結(jié)點(diǎn)都作相同窗口的搜索，就無法體現(xiàn)<FONT
face="Times New Roman">Alpha-Beta</FONT>算法的效率了。為此，<FONT
face="Times New Roman">Crafty</FONT>對根結(jié)點(diǎn)的迭代加深過程用了期望窗口<FONT
face="Times New Roman">(Aspiration
Window)</FONT>，即讓所有的子結(jié)點(diǎn)都搜索一個(gè)較窄的窗口，這要比直接分割<FONT
face="Times New Roman">(</FONT><FONT face=Symbol>-</FONT><FONT
face="Times New Roman">MATE_VALUE, MATE_VALUE)</FONT>有效得多。而另一個(gè)極端的做法是<FONT
face="Times New Roman">MTD(<EM>f</EM>)</FONT>的零窗口，根結(jié)點(diǎn)從一開始就預(yù)測為<FONT
face="Times New Roman">Cut</FONT>或<FONT
face="Times New Roman">All</FONT>結(jié)點(diǎn)，即可實(shí)施有效的分割，這就是<FONT
face="Times New Roman">MTD(<EM>f</EM>)</FONT>算法在并行計(jì)算上的優(yōu)勢。 </DT></DL>
<DIR>
<LI>上一篇 <A
href="http://www.elephantbase.net/computer/eleeye_horizon.htm">中國象棋程序設(shè)計(jì)探索<FONT
face="Times New Roman">(</FONT>五<FONT
face="Times New Roman">)</FONT>：克服水平線效應(yīng)</A>
<LI>下一篇 <A
href="http://www.elephantbase.net/computer/eleeye_book.htm">中國象棋程序設(shè)計(jì)探索<FONT
face="Times New Roman">(</FONT>七<FONT face="Times New Roman">)</FONT>：開局庫</A>
<LI>返 回 <A href="http://www.elephantbase.net/computer.htm">象棋百科全書——電腦象棋</A>
</LI></DIR>
<DIV align=center>
<CENTER>
<TABLE border=0>
<TBODY>
<TR>
<TD>
<P align=center><A href="http://www.elephantbase.net/" target=_blank><IMG
height=31 src="解剖大象的眼睛——中國象棋程序設(shè)計(jì)探索(六)：并行搜索技術(shù)探索_files/elephantbase.gif"
width=88 border=0></A></P></TD></TR>
<TR>
<TD><A href="http://www.elephantbase.net/" target=_blank><FONT face=Arial
size=2><STRONG>www.elephantbase.net</STRONG></FONT></A></TD></TR></TBODY></TABLE></CENTER></DIV></BODY></HTML>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -