?? 基本搜索方法——簡介(二).htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/search_intro2.htm -->
<HTML><HEAD><TITLE>基本搜索方法——簡介(二)</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="" name=Owner>
<META content="" name=Reply-To>
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=基本搜索方法——簡介(二)_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT>《對弈程序基本技術》專題 </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face=Arial size=6><STRONG>Alpha-Beta</STRONG></FONT><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">David Eppstein */</FONT>文
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">* </FONT>加州愛爾文大學<FONT
face="Times New Roman">(UC Irvine)</FONT>信息與計算機科學系 </CENTER></DT></DIV>
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>淺的裁剪</STRONG></FONT>
<DT>
<DT> 假設你用最小<FONT face="Times New Roman">-</FONT>最大搜索<FONT
face="Times New Roman">(</FONT>前面講到的<FONT
face="Times New Roman">)</FONT>來搜索下面的樹：
<DD>
<DIV align=center>
<CENTER></DIV>
<DT><IMG height=285 src="基本搜索方法——簡介(二)_files/search_intro2.gif" width=346>
</CENTER>
<DIV></DIV>
<DT>
<DT> 你搜索到<FONT face="Times New Roman">F</FONT>，發現子結點的評價分別是<FONT
face="Times New Roman">11</FONT>、<FONT face="Times New Roman">12</FONT>、<FONT
face="Times New Roman">7</FONT>和<FONT
face="Times New Roman">9</FONT>，在這層是棋手甲走，我們希望他選擇最好的值，即<FONT
face="Times New Roman">12</FONT>。所以，<FONT
face="Times New Roman">F</FONT>的最小<FONT
face="Times New Roman">-</FONT>最大值是<FONT face="Times New Roman">12</FONT>。
<DT> 現在你開始搜索<FONT face="Times New Roman">G</FONT>，并且第一個子結點就返回<FONT
face="Times New Roman">15</FONT>。一旦如此，你就知道<FONT
face="Times New Roman">G</FONT>的值至少是<FONT
face="Times New Roman">15</FONT>，可能更高<FONT
face="Times New Roman">(</FONT>如果另一個子結點比<FONT
face="Times New Roman">G</FONT>更好<FONT
face="Times New Roman">)</FONT>。這就意味著我們不指望棋手乙走<FONT
face="Times New Roman">G</FONT>這步了，因為就棋手乙看來，<FONT
face="Times New Roman">F</FONT>的評價<FONT
face="Times New Roman">12</FONT>要比<FONT face="Times New Roman">G</FONT>的<FONT
face="Times New Roman">15(</FONT>或更高<FONT
face="Times New Roman">)</FONT>好，因此我們知道<FONT
face="Times New Roman">G</FONT>不在主要變例上。我們可以裁剪<FONT
face="Times New Roman">(Prune)</FONT>結點<FONT
face="Times New Roman">G</FONT>下面的其他子結點，而不要對它們作出評價，并且立即從<FONT
face="Times New Roman">G</FONT>返回，因為對<FONT
face="Times New Roman">G</FONT>作更好的評價只是浪費時間。
<DT> 一般來說，像<FONT face="Times New Roman">G</FONT>一樣只要有一個子結點返回比<FONT
face="Times New Roman">G</FONT>的兄弟結點更好的值<FONT
face="Times New Roman">(</FONT>對于結點<FONT
face="Times New Roman">G</FONT>要走棋的一方而言<FONT
face="Times New Roman">)</FONT>，就可以進行裁剪。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>深的裁剪</STRONG></FONT>
<DT>
<DT> 我們來討論更復雜的可能裁剪的情況。例如在同一棵搜索樹中，我們評價的<FONT
face="Times New Roman">G</FONT>、<FONT face="Times New Roman">H</FONT>和<FONT
face="Times New Roman">I</FONT>都比<FONT
face="Times New Roman">12</FONT>好，因此<FONT
face="Times New Roman">12</FONT>就是結點<FONT
face="Times New Roman">B</FONT>的評價?，F在我們來搜索結點<FONT
face="Times New Roman">C</FONT>，在下面兩層我們找到了評價為<FONT
face="Times New Roman">10</FONT>的結點<FONT face="Times New Roman">N</FONT>：
<DIV align=center>
<CENTER></DIV>
<DT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><IMG height=370 src="基本搜索方法——簡介(二)_files/search_intro3.gif" width=373>
</CENTER>
<DIV></DIV>
<DT>
<DT> 我們能用更為復雜的路線來作裁剪。我們知道<FONT face="Times New Roman">N</FONT>會返回<FONT
face="Times New Roman">10</FONT>或更小<FONT
face="Times New Roman">(</FONT>輪到棋手乙走棋，需要挑最小的<FONT
face="Times New Roman">)</FONT>。我們不知道<FONT
face="Times New Roman">J</FONT>能否返回<FONT
face="Times New Roman">10</FONT>或更小，也不知道<FONT
face="Times New Roman">J</FONT>的哪個子結點會更好。如果從<FONT
face="Times New Roman">J</FONT>返回到<FONT face="Times New Roman">C</FONT>的是<FONT
face="Times New Roman">10</FONT>或者更小的值，那么我們可以在結點<FONT
face="Times New Roman">C</FONT>上作裁剪，因為它有更好的兄弟結點B。因此在這種情況下，繼續找<FONT
face="Times New Roman">N</FONT>的子結點就毫無意義?？紤]其他情況，<FONT
face="Times New Roman">J</FONT>的其他子結點返回比<FONT
face="Times New Roman">10</FONT>更好的值，此時搜索<FONT
face="Times New Roman">N</FONT>也是毫無意義的。所以我們只要看到<FONT
face="Times New Roman">10</FONT>，就可以放心地從<FONT
face="Times New Roman">N</FONT>返回。
<DT>
<DT><FONT face=Arial size=5><STRONG>Alpha-Beta</STRONG></FONT><FONT
face=楷體_GB2312 size=5><STRONG>的偽代碼</STRONG></FONT>
<DT>
<DT> 一般來說，如果返回值比偶數層的兄弟結點好，我們就可以立即返回。如果我們在搜索過程中，把這些兄弟結點的最小值<FONT
face="Times New Roman">Beta</FONT>作為參數來傳遞，我們就可以進行非常有效的裁剪。我們還用另一個參數<FONT
face="Times New Roman">Alpha</FONT>來保存奇數層的結點。用這兩個參數來進行裁剪是非常有效的，代碼就寫在下邊。像上次一樣，我們用負值最大<FONT
face="Times New Roman">(Negamax)</FONT>的形式，即搜索樹的層數改變時取負值。
<DT>
<DD>double alphabeta(int depth, double alpha, double beta) {
<DD> if (depth <= 0 || 棋局結束) {
<DD> return evaluation();
<DD> }
<DD> 就當前局面，生成并排序一系列著法;
<DD> for (每個著法 m) {
<DD> 執行著法 m;
<DD> double val = -alphabeta(depth - 1, -beta, -alpha);
<DD> 撤消著法 m;
<DD> if (val >= beta) {
<DD> return val;
<DD> }
<DD> if (val > alpha) {
<DD> alpha = val;
<DD> }
<DD> }
<DD> return alpha;
<DD>}
<DT>
<DT> 下次我們會解釋為什么排序這一步是很重要的。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>期望搜索</STRONG></FONT>
<DT>
<DT> 在根結點上我們如何為<FONT face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>設定初值？
<DT> <FONT face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>定義了一個評價的實數區間<FONT
face="Times New Roman">(Alpha, Beta)</FONT>，這個區間是我們“感興趣的”。如果某值比<FONT
face="Times New Roman">Beta</FONT>大我們就會做裁剪并立即返回，因為我們知道它不是主要變例的一部分，我們對它的準確值不感興趣，只需要知道它比<FONT
face="Times New Roman">Beta</FONT>大。如果某值比<FONT
face="Times New Roman">Alpha</FONT>小，我們不作裁剪，但是仍然對它不感興趣，因為我們知道搜索樹里肯定有一個著法會更好。
<DT> 但是在搜索樹的根結點，我們不知道感興趣的評價是在哪個范圍內，如果我們要保證不會因為意外而裁剪掉重要的部分，我們就設<FONT
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -