《對弈程序基本技術》專題
 
重復檢測
 
Bruce Moreland /
 
重復檢測為什么那么重要
 
  我們有必要提一下重復和局的問題。如果棋局面(同一方走的情況下)重復三次,就可以宣布和棋。如果程序領先一個車但是它陷入長將,那將是非常糟糕的,對手會在你即將取得勝利的時候宣布和棋。
  要解決這個問題,就必須檢測以前出現過的局面,并采取對策。如果程序懂得重復,它就可以根據盤面上局勢的需要,來謀求重復或避免重復。如果程序即將輸棋,那么它應該試圖尋找長將,反之應該避免。
  【譯注:中國象棋出現重復局面時,要根據雙方的著法來判斷勝負(例如單方面長將一方要被判負),規則非常復雜,因此策略也會不同。】
 
一個相當麻煩的選擇
 
  有兩種局面可能會重復:棋局的歷史局面,即在棋局中盤面上走過的局面;搜索樹局面,即程序搜索的路線上出現的局面,它們沒有在盤面上出現過,但是程序的思考中會不斷地撤消和執行著法。
  很明顯,搜索樹中的重復局面應該能被立即檢測出,并且會得到處理。一般來說會返回一個和局分值,但是我聽說有些程序會在中局遇到長將時,如果程序一方在將軍,就故意返回一個正值。這是為了說明,如果你能找到長將,那么局面通常會好些。如果搜索樹中的重復沒有被處理,那么程序就不會看到長將或其他重復和局的情況。
  對于搜索樹與棋局中局面出現的重復局面,該怎么做就不清楚了。如果某個局面在棋局中出現兩次,在搜索中出現一次,那么應該當作和局處理,因為棋局中再出現一次就會和了。困難在于某個局面只在棋局中出現一次,在搜索樹中也出現一次。
  很多程序把這些局面當作和局處理。這可以使得程序在陷入困境或對手試圖制造重復局面時,能有效地通過重復檢測來確定是否達到和局,缺點是程序有時會走出一些不正常的著法。【如果程序只檢測到兩次重復局面(即棋局中的一次和搜索樹中的一次,或者兩次都在搜索樹中)就返回和局分值,那么對搜索效率是有所提高的,因為程序節省了第二次到第三次重復之間的線路,這樣就至少在搜索樹的局部分枝上減少了4層。】
  我看過一些比賽的例子,其中一盤是GNUChess對陣我的程序。有個能贏的王兵殘局被GNUChessWinBoard自帶的程序,源代碼是公開的】錯過了,這兩個程序就進入一系列和局局面。最后,他們又走回那個被GNUChess錯過的能贏的局面。我的程序很高興看到這個重復局面,因為它是作為和局來評分的(它已經出現在棋局的歷史局面中)。當然,第二次GNUChess找到了獲勝的途徑。【第二次重復不會被判和棋(盡管原作者的程序認為已經和了),要到第三次重復才判和棋。】
  還有一盤棋是我的程序對陣一位叫Greg Kennedy的人類大師。Kennedy領先兩個兵,但是他走了一步臭棋可以導致對手一馬踏雙,并能讓對手得回一個兵。Kennedy看到他的王被將軍了,必須走他的王,他就把王走到原來待過的地方。然而我的程序走回了上一步,讓局面回到兩步前的樣子,而沒有通過吃兵來達到僅落后一個兵的局面。重復問題使得程序期待Kennedy會把王走回來,并且讓程序再對他一馬踏雙【這樣他的王就第三次回到原來的位置上了】。當然他不會這么做,這樣就讓他繼續領先兩個兵了。
  其他假設也是有可能的。一個很強的人類棋手發動了壓倒性的進攻,但是后來沒走好而讓程序逃掉了王,因此人類棋手就只有長將了,因為他子力落后并沒有殺棋。程序會樂于把王走回逃跑前原來的位置,因為這些位置是重復的并且會得到和局。【被長將會導致和局,把王走回原來危險的位置也被程序認為是和局,如果程序選擇了后者,就給了對手第二次嘗試殺棋的機會。】
  我已經在我的程序里做了修改,忽略棋局中出現一次并且搜索樹中出現一次的重復局面。這樣就解決了上面提到的問題,但是帶來了新的問題。
  程序會把一個局面重復幾次,這使得棋局有時非常煩瑣。這可能會干擾人類對手,或者在電腦國際象棋比賽中干擾對手,因為棋局到達復雜殘局時,可能不會有進展,并且可能周旋很長時間,從而離50回合限制越來越近。【人類棋手在棋局沒有進展時,第二次出現重復局面就會握手言和,而采用這種策略的程序則不肯提和,這會讓他的對手感到不舒服。】
  選擇哪種做法,是需要斟酌的。【從效率上說,第二次重復就返回和局分值的做法比較好,然而這種做法給了對手一個機會,當對手第一次犯錯誤時,第二次就有機會糾正了。】
 
可能的實現
 
  有很多方法可以檢測重復。其中一個在Tom KerriganTSCP中使用,他把這個方法歸功于John Stanback。在他的代碼中他聲明了這一點,但是沒有任何詳細的信息來告訴我們這是如何做的,因此我也不知道。如果你想知道它,就不得不到TSCP的源程序中挖掘。
  我能知道的實現方法已經在“Zobrist鍵值”一文中提到。如果你要實現“置換散列表”,那么你應該先實現Zobrist鍵值,這才能讓置換表得以實現。你需要對Zobrist鍵值作處理,從搜索樹的當前局面往回找,看有沒有和當前局面相等的鍵值。
  一個實現方法就是根據當前路線建立一個先進后出的堆棧,把鍵值加到歷史局面中。為了檢測重復,就要一層層地讀取堆棧,比較其中的鍵值,以確認當前鍵值是否已經存在于堆棧中。
  沒有必要找遍整個列表,只要往回找,直到遇到進兵或吃子的著法,因為這些著法在棋局中是不可逆的。你不可能在最后一次吃子或進兵的前面找到重復局面。
  這樣做看上去有點花時間,恐怕是吧,但是我相信有些程序就是這么做的。
  在我寫國際象棋程序的早期,我在Usenet上問了個關于散列技術的問題,得到Belle(尤物)作者Ken Thompson的回答。【貝爾實驗室的Ken Thompson,可能是影響力僅次于John Von Nouma(-諾依曼)的計算機科學家了,他是C語言的前身B語言的發明者,Unix系統的創立者之一,有關他在電腦國際象棋上作出的貢獻,可參閱譯文《電腦國際象棋簡史》。】他告訴我他用置換表來檢測重復局面,他是這樣做的:
  當探測置換表時,在表項中設置“打開”標志。這個標志一直被設置著,直到不再搜索這個局面為止,即從局面返回時才關閉。任何時刻打開的結點不是歷史局面就是在搜索樹的當前路線上,因此如果探索散列表時遇到一個打開的結點,就一定是前面發生過的局面。
  這種方法具有數據結構上的優勢,因為這樣的數據結構在典型的國際象棋中都用到,但是這個思想有一些問題。當進入一個結點時,必須寫入散列項,因此需要使用“始終替換” 的策略。對于Thompson來說這不是問題,因為他的策略包含了“始終替換”的散列表,但是其他替換策略就無法使用這種方法。另一個問題出現在散列表項沖突的情況下,這個問題必須得到處理。當兩個局面具有相同的64位鍵值時,我不討論散列鍵值的沖突問題。現在我討論過兩個局面共用一個散列項時,應該保留哪一個。如果兩個打開的結點要占用同一個散列項,除了要檢測第二個局面是否重復以外,要做什么并不清楚。可能這個問題要通過重新散列的策略來解決,但是這個方法跟散列表的主要用途沒有關系,所以要加這個功能比較麻煩【重新散列(Re-Hashing)是一個解決散列沖突的常用方法,但是在國際象棋程序中并不常用】。最后一個問題就是如何適應多處理器搜索,因為很多線程可能會讀取一個散列表。遇到打開的結點時,可能根本就不是重復局面,因為它可能屬于另一個處理器的搜索路線。這個問題解決起來看上去很復雜。【譯者認為,可以在散列項中記錄一個被打開的處理器號,每個處理器只對自己打開的結點作重復檢測。】
  另一個簡單的策略就是用一個很小的散列表【如果考慮50回合限著(100個著法),那么100200個散列項就足夠了】。進入結點時探測散列表,如果當前局面的Zobrist鍵值已經在散列表里,就返回平局分值。否則就加入這個鍵值。當結點退出時,鍵值就刪除。這看上去很直觀,并且散列項的沖突處理起來很容易,因為散列表不是滿的,散列項以先進后出的順序存取,也不存在替換策略的問題。
  我不愿說這個方法比其他方法好,因為畢竟有Ken Thompson的方法。我的這個方法有一些問題,因為它需要靠額外的數據結構和額外的函數的支持。
  當程序改成多處理器搜索時,這種方法有點令人擔憂,但是比起Thompson的策略在這方面遇到的問題,我的這個問題看上去不那么嚴重。
  如果你們想看這個第二散列表的策略,就去檢查Gerbil的源程序。這里我不準備列出源代碼的示例,這只是實現上的問題罷了。
  【中國象棋程序也可以通過探測散列表進行重復檢測,但是不能立即返回平局分值。當檢測出重復局面時,必須逐個分析兩次重復局面之間的著法,根據著法的性質來判定勝負,這一點比國際象棋麻煩得多。】
 
  原文:http://www.seanet.com/~brucemo/topics/repetition.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 其他策略——主要變例的獲取
  • 下一篇 其他策略——藐視因子
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果