?? 基本搜索方法——最小-最大搜索.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/search_minimax.htm -->
<HTML><HEAD><TITLE>基本搜索方法——最小-最大搜索</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=基本搜索方法——最小-最大搜索_files/background.gif>
<DL dir=ltr>
<DIV align=center>
<CENTER>
<DT>《對弈程序基本技術》專題 </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face=隸書 size=6>最小</FONT><FONT face=Arial size=6>-</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">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>從淺顯的地方開始</STRONG></FONT>
<DT>
<DT> 在國際象棋里，雙方棋手都知道每個棋子在哪里，他們輪流走并且可以走任何合理的著法。下棋的目的就是將死對方，或者避免被將死，或者有時爭取和棋是最好的選擇。
<DT> 國際象棋程序通過使用“搜索”函數來尋找著法。搜索函數獲得棋局信息，然后尋找對于程序一方來說最好的著法。
<DT> 一個淺顯的搜索函數用“樹狀搜索”<FONT
face="Times New Roman">(Tree-Searching)</FONT>來實現。一個國際象棋棋局通?？梢钥醋饕粋€很大的<FONT
face="Times New Roman"><EM>n</EM></FONT>叉樹<FONT
face="Times New Roman">(</FONT>“<FONT
face="Times New Roman"><EM>n</EM></FONT>叉樹”意思是樹的每個結點有任意多個分枝通向其他結點<FONT
face="Times New Roman">)</FONT>，棋盤上目前的局面就是“根局面”<FONT
face="Times New Roman">(Root Position)</FONT>或“根結點”<FONT
face="Times New Roman">(Root Node)</FONT>。從根局面走一步棋，局面就到達根局面的“分枝”<FONT
face="Times New Roman">(Branch)</FONT>，這些局面稱為“后續局面”<FONT
face="Times New Roman">(Successor Position)</FONT>或“后續結點”<FONT
face="Times New Roman">(Successor
Nodes)</FONT>。每個后續局面后面還有一系列分枝，每個分枝就是這個局面的一個合理的著法。
<DT> 國際象棋的樹非常龐大<FONT face="Times New Roman">(</FONT>通常每個局面有<FONT
face="Times New Roman">35</FONT>個分枝<FONT face="Times New Roman">)</FONT>，又非常深。
<DT> 每盤棋局都是一棵巨大的<FONT
face="Times New Roman"><EM>n</EM></FONT>叉樹，如果能通過樹狀搜索找到棋局中對雙方來說都最好的著法就好了。這個淺顯的算法在這里稱為“最小<FONT
face="Times New Roman">-</FONT>最大搜索”<FONT face="Times New Roman">(Min-max
Search)</FONT>。
<DT> 用最小<FONT face="Times New Roman">-</FONT>最大搜索來解諸如井字棋的簡單棋局是可行的<FONT
face="Times New Roman">(</FONT>即完全了解每一種變化<FONT
face="Times New Roman">)</FONT>。井字棋的博弈樹既不煩瑣也不深，所以整個樹可以遍歷，棋局的所有變化都可以知道，任何局面都可以保證找到一步最佳著法。
<DT> 數學上用這種方法處理國際象棋也是可以的，但是目前和不久的將來用計算機去實現，卻是不可行的。即便如此，我們仍然可以用基于最小<FONT
face="Times New Roman">-</FONT>最大搜索的程序來下國際象棋。相比最小<FONT
face="Times New Roman">-</FONT>最大地搜索整個樹，在一個給定的局面下搜索前幾步則是可能的。由于葉子結點的局面沒能搜索出殺棋或和棋，所以要用一個稱為“評價”<FONT
face="Times New Roman">(Evaluate)</FONT>的啟發函數給這些局面賦值。盡管程序設計師希望這些值能夠通過知識來得到，但它們確實都是猜的。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>基于最小-最大的評價函數</STRONG></FONT>
<DT>
<DT> 我不打算在這里談很多關于評價函數的細節。這里我只說明它是怎樣確定的，在以后的章節中會詳細展開。評價函數首先應該返回局面的準確值，在沒辦法得到準確值的情況下，如果可能的話啟發值也可以。它可以由兩種方法來決定：
<DT> <FONT face="Times New Roman">(1)
</FONT>如果黑方被將死了，那么評價函數返回一個充分大的正數；如果白方被將死了，那么返回一個充分大的負數；如果棋局是和棋<FONT
face="Times New Roman">(</FONT>例如某一方逼和，或者雙方都只有王<FONT
face="Times New Roman">)</FONT>，那么返回一個常數，通常是零或接近零。如果不是棋局結束局面，那么它返回一個啟發值。我將不詳細介紹這個啟發值是如何確定的，但是我有把握說子力平衡是首先要考慮的<FONT
face="Times New Roman">(</FONT>如果白方盤面上多子的話，這個值就大<FONT
face="Times New Roman">)</FONT>，而其他位置上的考慮<FONT
face="Times New Roman">(</FONT>兵型、王的安全性、重要的子力等等<FONT
face="Times New Roman">)</FONT>也需要加上。如果白方是贏棋或者很有希望贏，那么啟發函數通常會返回正數；如果黑方是贏棋或者很有希望贏，那么返回負數；如果棋局是均勢或者是和棋，那么返回在零左右的數值。
<DT> <FONT face="Times New Roman">(2)
</FONT>這個函數的工作原理跟第一個一樣，只是如果當前局面要走子的一方優勢，那么它返回正數，反之是負數。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>最小</STRONG></FONT><FONT face=Arial
size=5><STRONG>-</STRONG></FONT><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>最小<FONT
face="Times New Roman">-</FONT>最大函數，代碼如下：
<DD>
<DD>int MinMax(int depth) {
<DD> if (SideToMove() == WHITE) { // 白方是“最大”者
<DD> return Max(depth);
<DD> } else { // 黑方是“最小”者
<DD> return Min(depth);
<DD> }
<DD>}
<DD>
<DD>int Max(int depth) {
<DD> int best = -INFINITY;
<DD> if (depth <= 0) {
<DD> return Evaluate();
<DD> }
<DD> GenerateLegalMoves();
<DD> while (MovesLeft()) {
<DD><FONT face=宋體> </FONT>MakeNextMove();
<DD> val = Min(depth - 1);
<DD><FONT face=宋體> </FONT>UnmakeMove();
<DD> if (val > best) {
<DD> best = val;
<DD> }
<DD> }
<DD> return best;
<DD>}
<DD>
<DD>int Min(int depth) {
<DD> int best = INFINITY; // 注意這里不同于“最大”算法
<DD> if (depth <= 0) {
<DD> return Evaluate();
<DD> }
<DD> GenerateLegalMoves();
<DD> while (MovesLeft()) {
<DD> MakeNextMove();
<DD> val = Max(depth - 1);
<DD> UnmakeMove();
<DD> if (val < best) { // 注意這里不同于“最大”算法
<DD> best = val;
<DD> }
<DD> }
<DD> return best;
<DD>}
<DT>
<DT> 上面的代碼可以這樣調用：
<DD>
<DD>val = MinMax(5);
<DT>
<DT> 這樣可以返回當前局面的評價，它是向前看<FONT face="Times New Roman">5</FONT>步的結果。
<DT> 這里的“評價”函數用的是我上面所說第一種定義，它總是返回對于白方來說的局面。
<DT> 我簡要描述一下這個函數是如何運作的。假設根局面<FONT face="Times New Roman">(</FONT>棋盤上當前局面<FONT
face="Times New Roman">)</FONT>是白方走，那么調用的是“<FONT
face="Times New Roman">Max</FONT>”函數，它產生白方所有合理著法。在每個后續局面中，調用的是“<FONT
face="Times New Roman">Min</FONT>”函數，它對局面作出評價并返回。由于現在是白走，因此白方需要讓評價盡可能地大，能得到最大值的那個著法被認為是最好的，因此返回這個著法的評價。
<DT> “<FONT face="Times New Roman">Min</FONT>”函數正好相反，當黑方走時調用“<FONT
face="Times New Roman">Min</FONT>”函數，而黑方需要盡可能地小，因此選擇能得到最小值的那個著法。
<DT> 這兩個函數是互相遞歸的，即它們互相調用，直到達到所需要的深度為止。當函數到達最底層時，它們就返回“<FONT
face="Times New Roman">Evaluate</FONT>”函數的值。
<DT> 如果在深度為<FONT face="Times New Roman">1</FONT>時調用“<FONT
face="Times New Roman">MinMax</FONT>”函數，那么“<FONT
face="Times New Roman">Evaluate</FONT>”函數在走完每個合理著法之后就調用，選擇一個能達到最佳值的那個著法導致的局面。如果層數大于<FONT
face="Times New Roman">1</FONT>，那么另一方有權選擇局面，并找一個最好的。
<DT> 以上內容應該不難理解，但是代碼很長，下面有個更好的辦法。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>負值最大函數</STRONG></FONT>
<DT>
<DT> 負值最大只是對最小-最大的優化，“評價”函數返回我所說的第二種定義，對于當前結點上要走的一方，占優的情況返回正值，其他結點也是對于要走的一方而言的。這個值返回后要加上負號，因為返回以后就是對另一方而言了。代碼如下：
<DD>
<DD>int NegaMax(int depth) {
<DD> int best = -INFINITY;
<DD> if (depth <= 0) {
<DD> return Evaluate();
<DD> }
<DD> GenerateLegalMoves();
<DD> while (MovesLeft()) {
<DD> MakeNextMove();
<DD> val = -NegaMax(depth - 1); // 注意這里有個負號。
<DD> UnmakeMove();
<DD> if (val > best) {
<DD> best = val;
<DD> }
<DD> }
<DD> return best;
<DD>}
<DT>
<DT> 在這個函數里，當走子一方改變時就要對返回值取負值，以反映當前局面評價的更改。就根結點是白先走的情況，如果沒有剩下的層數，那么“評價”返回的值是就白方而言的，如果有剩下的層數，就產生后續局面，函數對這些局面逐一做遞歸，每個次遞歸都得到就黑方而言的評價，黑方走得越好值就越大。當評價值返回時，它們被取負數，變成就白方而言的評價。
<DT> 該函數在遍歷時結點的順序同“最小<FONT
face="Times New Roman">-</FONT>最大”搜索的函數是一樣的，產生的返回值也一樣。它的代碼更短，同時減少了移植代碼時出錯的可能，代碼維護起來也比較方便。
<DT>
<DT> 原文：<A href="http://www.seanet.com/~brucemo/topics/minmax.htm"
target=_blank><FONT
face="Times New Roman">http://www.seanet.com/~brucemo/topics/minmax.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/search_intro3.htm">基本搜索方法——簡介<FONT
face="Times New Roman">(</FONT>三<FONT face="Times New Roman">)</FONT></A>
<LI>下一篇 <A
href="http://www.elephantbase.net/computer/search_alphabeta.htm">基本搜索方法——<FONT
face="Times New Roman">Alpha-Beta</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="基本搜索方法——最小-最大搜索_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>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -