怎樣編制黑白棋(1)

    黑白棋程序設計是用編程的方法教會電腦下黑白棋，使之可以與對手對抗，一較棋力高下。由于黑白棋的算法設計在各種棋類游戲中是比較簡單的，所以編程相對要容易，而棋力則可以達到非常的強，一般都可以擊敗它的設計者。黑白棋程序Logistello已于1997年大比分擊敗世界冠軍Takeshi Murakami。現在，人類玩者幾乎不可能擊敗強力的黑白棋程序，如Hannibal、Logistello、Wzebra、Keyano等。看來，要想擊敗他們，只有依靠自己的程序了。：)      
　 
那么，怎樣設計黑白棋程序呢？以下將以Pascal語言為例加以說明。





    現在有如圖示的這樣一個棋局，輪到電腦下棋。現在它發現有這樣三個地方可以下：e3,c3,c5。這三種下法分別會形成三種局面：A、B、C。如果是人在下棋，就會思考：那一種下法更好呢？比如A被別人占角，B沒什么變化，C占了別人的角。當然棋手會選擇下C。電腦也是如此，它會對每一種棋局評一個分，比如它判斷，如果被別人占角，就減80分，相反占別人的角就加80分。那么A=-80分,B=0分,C=80分。電腦會選擇下C。電腦程序對棋局評分的部分，稱為“估值函數”(Evaluation Function)。真正的估值函數當然不會這么簡單。它會用到技巧篇提到的如行動力、潛在行動力、余裕手、邊角判斷、穩定子等綜合因素來判斷。具體的估值函數，我會在“估值函數”一節中詳細講述。 
　 

初始棋局(-1)

------------------+------------------

|                 |                 |

e3                c3                c5

(A)               (B)               (C) 

　 

　 

    接下來，如果人就這么判斷。那么它頂多也就是個初學者。為什么呢？因為它不會推理，碰到對手棄角之類的戰術，如“邊角判斷”中示例的一些情況，就輸得一塌糊涂了。當然，可以告訴電腦，碰到“邊角判斷”中的幾種情況，就如何如何下。但是，真實的棋局是非常復雜的，電腦（也包括人腦）幾乎不可能對動態的棋局給出靜態的評估。因為實際對局總會出現這樣那樣的情況，是無法預先估計的。碰到這些情況，人就會向后推幾步，看一看會是怎樣的一個局面。一些棋類大師往往可以推十幾步甚至更深。電腦也是如此。 

    還是剛才那一幅圖的演化。 

　 

-

-

-

電腦下棋

-

-

對手下棋

-

　
 初始棋局

------------------+------------------

|                 |                 |

e3                c3                c5

-----+-----        ----+----        -----+-----

|  |  |  |  |      |  |  |  |      |  |  |  |  |

 f2 f3 f4 f5 f6     c2 d3 e6 f5     b6 c6 d6 e6 f6 

+84+36+12 +5 -1    +11 -1 +6 +6     +6 +0 -5 +3 +5 

　
 

　 

    電腦在自己下棋以后，把對手的下棋情況也推理出來。然后加以評分。（最下一排是電腦評估的得分）這一次電腦又如何下呢？這時電腦假設對手是高手。如果電腦下e3，對手就會下對電腦最不利的情況f6。同樣，電腦下c3，對手就會下d3，電腦下c5，對手就會下d6。這三種情況，c5是最不好的(因為c5的下一步d6的得分最低)，c3與e3一樣。因此電腦會下c3或者e3。用程序化的語言這樣描述： 

    電腦從棋盤初始狀態出發，以后雙方輪流下子，形成一種倒樹狀結構。樹的層數就是電腦搜索的深度。在樹狀結構的葉子節點，對棋盤狀態進行估值，即估計形式的好壞。得出一個分值。將此分值賦給葉子節點，之后，如果父節點該電腦下棋，則將子節點的最大節點值賦給其父，如果父節點該對手下棋，則將子節點的最小節點值賦給其父。（就是說，四級節點把最大值賦給三級節點，三級節點把最小值賦給二級節點，二級節點把最大值賦給根節點...）以此類推，得到根節點的值。具有和根節點一樣值的二級節點即為電腦該下的位置。 

    這里讀者會有個疑問：電腦為什么要假設對手是高手？這是因為，如果你認為對手不是高手，但是不能說對手每一步都會下錯。比如你送對手一個角吃。對手如果吃掉了，豈非損失慘重？當然，如果你確定對手不會吃你的角，你也可以下，但是前提就是“你確定對手不會吃你的角”。也就是你完全明白對手的戰術。所以說如果一個程序完全了解另一個程序（或人）的下法，它也可以用針對性的下法，這將會更具成效。 

　 
 
　 
   如上圖所示棋局，設電腦為白棋，推理深度為2，可以形成如下的樹：（數字為節點值）

初始棋局

-

-

白棋下棋之后

-

-

黑棋下棋之后

估值
 初始棋局(-1)

------------------+------------------

|                 |                 |

e3(-1)            c3(-1)            c5(-5)

-----+-----        ----+----        -----+-----

|  |  |  |  |      |  |  |  |      |  |  |  |  |

 f2 f3 f4 f5 f6     c2 d3 e6 f5     b6 c6 d6 e6 f6 

+84+36+12 +5 -1    +11 -1 +6 +6     +6 +0 -5 +3 +5 
 
結果:應該下e3或c3 
 
具體實現的偽算法類似于經典的八皇后問題。

最大最小搜索：

var
  DepthMax: Integer;           //最大搜索深度
  max: Double;                 //最佳估值
  max_x, max_y: Integer;       //最佳值所在位置的x和y坐標

function MiniMax(Depth: Integer; Board: TBoard): Double; 
var
  I, J: Integer;
  Value, t: Double;
begin
  if Depth = 0 then                                     //根節點depth=DepthMax；葉子節點depth=0;
  begin
    Result := 估值;                                     //葉子結點估值返回
    Exit;
  end;
  if 電腦下棋 then                                      //電腦下棋的節點
    Value := -MaxInt                                    //節點賦初值,初始化為一個不可能達到的最小值
  else                                                  //對手下棋的節點
    Value := MaxInt;                                    //節點賦初值,初始化為一個不可能達到的最大值

  對于每一個合法的可下棋的位置(i,j) do
  begin
    保存棋局;
    下棋;
    t := MiniMax(depth - 1, Board);                     //遞歸調用
     
    if 電腦下棋 and (value < t) then                    //選擇節點中最大或是最小的值
      Value := t
    else if Value > t then
      Value := t;

    if (depth = DepthMax) and (Value > max) then        //如果值大于根節點值則賦值
    begin
      max := value;
      max_x := i;                                       //x坐標
      max_y := j;                                       //y坐標
    end;

    恢復棋局;
  end;
  Result := value;
end;
 
    進一步，假設從對手角度考慮形式判斷函數為g，則有g = -f。這樣，在深度優先搜索中，電腦下棋的結點時考慮取子結點中f最大的，而對手下棋的結點中取f最小的，也就是g最大的，這樣兩者就完全統一成取最大值。而在返回值時，只需要把符號改變一下，就可以把f和g值相互轉換了。這被稱為負最大搜索，它比最小最大搜索來得簡單。這樣，函數就簡化成如下形式： 
負最大搜索： 
function NegaMax(Depth: Integer; Board: TBoard): Double;
var
  I, J: Integer;
  Value, t: Double;
begin
  if Depth = 0 then                               //根節點depth=DepthMax；葉子節點depth=0;
  begin
    Result := 估值;                               //葉子結點估值返回
    Exit;
  end;
  
  Value := -MaxInt;                                //節點賦初值,初始化為一個不可能達到的最小值 
  對于每一個合法的可下棋的位置(i,j) do
  begin
    保存棋局;
    下棋;
    t := -MiniMax(depth - 1, Board);              //遞歸調用

    if t > Value then
      Value := t;

    if (depth = DepthMax) and (Value > max) then  //如果值大于根節點值則賦值
    begin
      max := value;
      max_x := i;                                 //x坐標
      max_y := j;                                 //y坐標
    end;

    恢復棋局;
  end;
  Result := value;
end;