怎样编制黑白棋(1).txt

c语言的常用函数以及一些小游戏代码,如文曲星小游戏、五子棋游戏等

怎样编制黑白棋(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;