?? 高級(jí)搜索方法——期望窗口.htm
字號(hào):
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0060)http://www.elephantbase.net/computer/advanced_aspiration.htm -->
<HTML><HEAD><TITLE>高級(jí)搜索方法——期望窗口</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=高級(jí)搜索方法——期望窗口_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT size=3>《對(duì)弈程序基本技術(shù)》專題</FONT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face=隸書 size=6>期望窗口</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> 期望窗口是對(duì)迭代加深的改進(jìn)。迭代加深的最簡(jiǎn)單的實(shí)現(xiàn)方法是這樣的：
<DD>
<DD>for (depth = 1; ; depth ++) {
<DD> val = AlphaBeta(depth, -INFINITY, INFINITY);
<DD> if (TimedOut()) {
<DD> break;
<DD> }
<DD>}
<DD>
<DT> 這里調(diào)用了一個(gè)“窗口”為正負(fù)無窮大的<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索，以假定返回值可能是很大的正數(shù)或負(fù)數(shù)。
<DT> 假設(shè)下一次迭代時(shí)，搜索的值不會(huì)比上一次有太多的變動(dòng)，那么就可以對(duì)以上的程序作改進(jìn)，代碼如下：
<DD>
<DD>#define valWINDOW 50 // <FONT
color=#0000ff>【譯注：valWINDOW是窗口的半寬，在國際象棋中通常是半個(gè)兵的價(jià)值。】</FONT>
<DD>alpha = -INFINITY;
<DD>beta = INFINITY;
<DD>for (depth = 1; ; ) {
<DD> val = AlphaBeta(depth, alpha, beta);
<DD> if (TimedOut()) {
<DD> break;
<DD> }
<DD> if ((val <= alpha) || (val >= beta)) {
<DD> alpha = -INFINITY;
<DD> beta = INFINITY;
<DD> continue;
<DD> }
<DD> alpha = val - valWINDOW;
<DD> beta = val + valWINDOW;
<DD> depth ++;
<DD>}
<DT>
<DT> 這個(gè)代碼有點(diǎn)爛，如果可能的話你可以把“<FONT
face="Times New Roman">continue</FONT>”前面的部分改一下試試。這個(gè)思想是用前一次<FONT
face="Times New Roman">Alpha-Beta</FONT>迭代的值來作用到這次的迭代中。大多數(shù)情況下你得到的返回值會(huì)在<FONT
face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>之間。如果沒有，那么你可以嘗試一個(gè)寬一些的窗口。
<DT> 我的重新搜索并不那么有效，但是我相信你可以做得更好。一個(gè)很明顯的思想是，如果返回值大于或等于<FONT
face="Times New Roman">Beta</FONT>，你就擴(kuò)展<FONT
face="Times New Roman">Beta</FONT>，如果返回值小于等于<FONT
face="Times New Roman">Alpha</FONT>，你就擴(kuò)展<FONT
face="Times New Roman">Alpha</FONT>，而不是我所做的<FONT
face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>都擴(kuò)展。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>搜索不穩(wěn)定性的問題</STRONG></FONT>
<DT>
<DT> 這是你要小心搜索不穩(wěn)定性的另一個(gè)地方。當(dāng)我首次在我的國際象棋程序中加入期望窗口時(shí)，我設(shè)想如果返回值大于或等于<FONT
face="Times New Roman">Beta</FONT>，那么重新搜索的結(jié)果就應(yīng)該得到更大的值。完全錯(cuò)了，我的程序陷入了非常嚴(yán)重的故障！下面是它的代碼：
<DT>
<DD>alpha = -INFINITY;
<DD>beta = INFINITY;
<DD>for (depth = 1; ; ) {
<DD> val = AlphaBeta(depth, alpha, beta);
<DD> if (TimedOut()) {
<DD> break;
<DD> }
<DD> if (val <= alpha) { // 錯(cuò)！
<DD> alpha = -INFINITY;
<DD> beta = val + 1; // <FONT color=#0000ff>【這行沒有就對(duì)了，但效率會(huì)低很多。】</FONT>
<DD> continue;
<DD> }
<DD> if (val >= beta) { // 錯(cuò)！
<DD> beta = INFINITY;
<DD> alpha = val - 1;
<DD> continue;
<DD> }
<DD> alpha = val - valWINDOW;
<DD> beta = val + valWINDOW;
<DD> depth++;
<DD>}
<DT>
<DT> 如果你能確認(rèn)重新搜索會(huì)有結(jié)果，那么上面的代碼會(huì)非常有效的。但是在我這里情況卻是：
<DT> <FONT face="Times New Roman">1. </FONT>搜索<FONT
face="Times New Roman">(Alpha, Beta)</FONT>時(shí)高出邊界；
<DT> <FONT face="Times New Roman">2. </FONT>重新搜索<FONT
face="Times New Roman">(Beta - 1, INFINITY)</FONT>時(shí)低出邊界；
<DT> <FONT face="Times New Roman">3. </FONT>重新搜索<FONT
face="Times New Roman">(-INFINITY, Alpha + 1)</FONT>時(shí)高出邊界；
<DT> <FONT face="Times New Roman">4. </FONT>等等，等等……
<DT> 無論如何你必須避免發(fā)生這種情況。
<DT>
<DT><FONT
color=#0000ff> 【譯者研究認(rèn)為，在用了后面要談到的“主要變例搜索”以后，期望窗口就幾乎沒有作用了，因此很多程序都沒有使用這個(gè)技術(shù)，盡管它的思想非常明顯，看上去似乎可以起到好的效果。】</FONT>
<DT>
<DT> 原文：<A href="http://www.seanet.com/~brucemo/topics/aspiration.htm"
target=_blank><FONT
face="Times New Roman">http://www.seanet.com/~brucemo/topics/aspiration.htm</FONT></A>
<DT> 譯者：黃晨 <FONT face="Times New Roman">(</FONT><A
href="mailto:webmaster@elephantbase.net"><FONT
face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT
face="Times New Roman">)</FONT>
<DT> 類型：全譯加譯注 </DT></DL>
<DIR>
<LI>上一篇 <A
href="http://www.elephantbase.net/computer/advanced_nullmove.htm">高級(jí)搜索方法——空著裁剪</A>
<LI>下一篇 <A
href="http://www.elephantbase.net/computer/advanced_pvs.htm">高級(jí)搜索方法——主要變例搜索</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="高級(jí)搜索方法——期望窗口_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
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -