?? 其他策略——重復(fù)檢測.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0057)http://www.elephantbase.net/computer/other_repetition.htm -->
<HTML><HEAD><TITLE>其他策略——重復(fù)檢測</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2817" name=GENERATOR></HEAD>
<BODY background=其他策略——重復(fù)檢測_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT>《對弈程序基本技術(shù)》專題 </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face=隸書 size=6>重復(fù)檢測</FONT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">Bruce Moreland (</FONT><A
href="mailto:brucemo@seanet.com"><FONT
face="Times New Roman">brucemo@seanet.com</FONT></A><FONT
face="Times New Roman">) / </FONT>文 </CENTER></DT></DIV>
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>重復(fù)檢測為什么那么重要</STRONG></FONT>
<DT>
<DT> 我們有必要提一下重復(fù)和局的問題。如果棋局面<FONT face="Times New Roman">(</FONT>同一方走的情況下<FONT
face="Times New Roman">)</FONT>重復(fù)三次，就可以宣布和棋。如果程序領(lǐng)先一個車但是它陷入長將，那將是非常糟糕的，對手會在你即將取得勝利的時候宣布和棋。
<DT> 要解決這個問題，就必須檢測以前出現(xiàn)過的局面，并采取對策。如果程序懂得重復(fù)，它就可以根據(jù)盤面上局勢的需要，來謀求重復(fù)或避免重復(fù)。如果程序即將輸棋，那么它應(yīng)該試圖尋找長將，反之應(yīng)該避免。
<DT><FONT color=#0000ff> 【譯注：中國象棋出現(xiàn)重復(fù)局面時，要根據(jù)雙方的著法來判斷勝負(fù)</FONT><FONT
face="Times New Roman" color=#0000ff>(</FONT><FONT
color=#0000ff>例如單方面長將一方要被判負(fù)</FONT><FONT face="Times New Roman"
color=#0000ff>)</FONT><FONT color=#0000ff>，規(guī)則非常復(fù)雜，因此策略也會不同。】</FONT>
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>一個相當(dāng)麻煩的選擇</STRONG></FONT>
<DT>
<DT> 有兩種局面可能會重復(fù)：棋局的歷史局面，即在棋局中盤面上走過的局面；搜索樹局面，即程序搜索的路線上出現(xiàn)的局面，它們沒有在盤面上出現(xiàn)過，但是程序的思考中會不斷地撤消和執(zhí)行著法。
<DT> 很明顯，搜索樹中的重復(fù)局面應(yīng)該能被立即檢測出，并且會得到處理。一般來說會返回一個和局分值，但是我聽說有些程序會在中局遇到長將時，如果程序一方在將軍，就故意返回一個正值。這是為了說明，如果你能找到長將，那么局面通常會好些。如果搜索樹中的重復(fù)沒有被處理，那么程序就不會看到長將或其他重復(fù)和局的情況。
<DT> 對于搜索樹與棋局中局面出現(xiàn)的重復(fù)局面，該怎么做就不清楚了。如果某個局面在棋局中出現(xiàn)兩次，在搜索中出現(xiàn)一次，那么應(yīng)該當(dāng)作和局處理，因?yàn)槠寰种性俪霈F(xiàn)一次就會和了。困難在于某個局面只在棋局中出現(xiàn)一次，在搜索樹中也出現(xiàn)一次。
<DT> 很多程序把這些局面當(dāng)作和局處理。這可以使得程序在陷入困境或?qū)κ衷噲D制造重復(fù)局面時，能有效地通過重復(fù)檢測來確定是否達(dá)到和局，缺點(diǎn)是程序有時會走出一些不正常的著法。<FONT
color=#0000ff>【如果程序只檢測到兩次重復(fù)局面</FONT><FONT face="Times New Roman"
color=#0000ff>(</FONT><FONT
color=#0000ff>即棋局中的一次和搜索樹中的一次，或者兩次都在搜索樹中</FONT><FONT face="Times New Roman"
color=#0000ff>)</FONT><FONT
color=#0000ff>就返回和局分值，那么對搜索效率是有所提高的，因?yàn)槌绦蚬?jié)省了第二次到第三次重復(fù)之間的線路，這樣就至少在搜索樹的局部分枝上減少了</FONT><FONT
face="Times New Roman" color=#0000ff>4</FONT><FONT color=#0000ff>層。】</FONT>
<DT> 我看過一些比賽的例子，其中一盤是<FONT
face="Times New Roman">GNUChess</FONT>對陣我的程序。有個能贏的王兵殘局被<FONT
face="Times New Roman">GNUChess</FONT><FONT color=#0000ff>【</FONT><FONT
face="Times New Roman" color=#0000ff>WinBoard</FONT><FONT
color=#0000ff>自帶的程序，源代碼是公開的】</FONT>錯過了，這兩個程序就進(jìn)入一系列和局局面。最后，他們又走回那個被<FONT
face="Times New Roman">GNUChess</FONT>錯過的能贏的局面。我的程序很高興看到這個重復(fù)局面，因?yàn)樗亲鳛楹途謥碓u分的<FONT
face="Times New Roman">(</FONT>它已經(jīng)出現(xiàn)在棋局的歷史局面中<FONT
face="Times New Roman">)</FONT>。當(dāng)然，第二次<FONT
face="Times New Roman">GNUChess</FONT>找到了獲勝的途徑。<FONT
color=#0000ff>【第二次重復(fù)不會被判和棋</FONT><FONT face="Times New Roman"
color=#0000ff>(</FONT><FONT color=#0000ff>盡管原作者的程序認(rèn)為已經(jīng)和了</FONT><FONT
face="Times New Roman" color=#0000ff>)</FONT><FONT
color=#0000ff>，要到第三次重復(fù)才判和棋。】</FONT>
<DT> 還有一盤棋是我的程序?qū)﹃囈晃唤?lt;FONT face="Times New Roman">Greg
Kennedy</FONT>的人類大師。<FONT
face="Times New Roman">Kennedy</FONT>領(lǐng)先兩個兵，但是他走了一步臭棋可以導(dǎo)致對手一馬踏雙，并能讓對手得回一個兵。<FONT
face="Times New Roman">Kennedy</FONT>看到他的王被將軍了，必須走他的王，他就把王走到原來待過的地方。然而我的程序走回了上一步，讓局面回到兩步前的樣子，而沒有通過吃兵來達(dá)到僅落后一個兵的局面。重復(fù)問題使得程序期待<FONT
face="Times New Roman">Kennedy</FONT>會把王走回來，并且讓程序再對他一馬踏雙<FONT
color=#0000ff>【這樣他的王就第三次回到原來的位置上了】</FONT>。當(dāng)然他不會這么做，這樣就讓他繼續(xù)領(lǐng)先兩個兵了。
<DT> 其他假設(shè)也是有可能的。一個很強(qiáng)的人類棋手發(fā)動了壓倒性的進(jìn)攻，但是后來沒走好而讓程序逃掉了王，因此人類棋手就只有長將了，因?yàn)樗恿β浜蟛]有殺棋。程序會樂于把王走回逃跑前原來的位置，因?yàn)檫@些位置是重復(fù)的并且會得到和局。<FONT
color=#0000ff>【被長將會導(dǎo)致和局，把王走回原來危險的位置也被程序認(rèn)為是和局，如果程序選擇了后者，就給了對手第二次嘗試殺棋的機(jī)會。】</FONT>
<DT> 我已經(jīng)在我的程序里做了修改，忽略棋局中出現(xiàn)一次并且搜索樹中出現(xiàn)一次的重復(fù)局面。這樣就解決了上面提到的問題，但是帶來了新的問題。
<DT> 程序會把一個局面重復(fù)幾次，這使得棋局有時非常煩瑣。這可能會干擾人類對手，或者在電腦國際象棋比賽中干擾對手，因?yàn)槠寰值竭_(dá)復(fù)雜殘局時，可能不會有進(jìn)展，并且可能周旋很長時間，從而離<FONT
face="Times New Roman">50</FONT>回合限制越來越近。<FONT
color=#0000ff>【人類棋手在棋局沒有進(jìn)展時，第二次出現(xiàn)重復(fù)局面就會握手言和，而采用這種策略的程序則不肯提和，這會讓他的對手感到不舒服。】</FONT>
<DT> 選擇哪種做法，是需要斟酌的。<FONT
color=#0000ff>【從效率上說，第二次重復(fù)就返回和局分值的做法比較好，然而這種做法給了對手一個機(jī)會，當(dāng)對手第一次犯錯誤時，第二次就有機(jī)會糾正了。】</FONT>
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>可能的實(shí)現(xiàn)</STRONG></FONT>
<DT>
<DT> 有很多方法可以檢測重復(fù)。其中一個在<FONT face="Times New Roman">Tom Kerrigan</FONT>的<FONT
face="Times New Roman">TSCP</FONT>中使用，他把這個方法歸功于<FONT
face="Times New Roman">John
Stanback</FONT>。在他的代碼中他聲明了這一點(diǎn)，但是沒有任何詳細(xì)的信息來告訴我們這是如何做的，因此我也不知道。如果你想知道它，就不得不到<FONT
face="Times New Roman">TSCP</FONT>的源程序中挖掘。
<DT> 我能知道的實(shí)現(xiàn)方法已經(jīng)在“<A
href="http://www.elephantbase.net/computer/struct_zobrist.htm"
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -