[转帖]怎样编制黑白棋

Eastsun

剪枝
Alpha-Beta剪枝(Alpha-Beta Purning)
    新的问题出现了：对于一般的最大最小搜索，即使每一步只有很少的下法，搜索位置的数目也会随着搜索深度呈级数级增长。在大多数的中局棋形中，每步平均有十种下法，假设电脑搜索九步(程序术语称为搜索深度为九)，就要搜索十亿个位置(十的九次方)，这样极大地限制了电脑的棋力：我们总不能忍受电脑棋手一年才下一步棋。减少搜索结点的最简单的方法是减小搜索深度，但这大大影响了电脑棋手的棋力。是否有办法在不减小搜索深度的前提下将需要搜索的结点减小一些？幸运的是，可以证明，程序不需要考虑所有的位置而找到最佳点，于是人们采用了一个方法，叫"alpha-beta剪枝"，它大为减少了检测的数目，提高电脑搜索的速度。所有的强力黑白棋程序都用到了各种各样的这种算法。(同样用于其他棋类游戏，如国际象棋和跳棋)。为了搜索九步，一个好的程序只用搜索十万到一百万个位置，而不是没用前的十亿次。
    还有几种alpha-beta算法的改进型，最广泛采用的是NegaScout，(Alexander Reinefeld发明)，但它和一般的alpha-beta剪枝算法没有根本的不同。其他的还有PVS和SSS*。下面举例说明。
    还是基于刚才的棋形，假设先搜索e3-f2 f3 f4 f5 f6、再c3-c2 d3 e6 f5、再c5-b6 c6 d6 e6 f6，即从左至右的顺序的深度优先搜索。则搜索到d3分枝之后，就不用搜索e6和f5了。因为如果接下来的值比d3大，就不会赋值给c3，如果比d3小，赋值给c3后，也不会赋给根节点，因为根节点取最大的值，现在根节点的值是-1，不会取更小的值。同样的，搜索d6后，也不用搜索e6、f6了，也就是说，搜索到比-1还小的值之后，就不用搜索了。


    在搜索过程中，电脑下棋结点的当前最优值被称为α 值（即初始棋局的值），对手下棋结点的当前最优值被称为 β值（即例子中C3的值）。在搜索过程中，α 值递增， β值递减，两者构成了一个区间。这个区间被称为窗口，而对手下棋的结点最终的最优值将落在这个窗口中。一旦在电脑下棋的结点得到其子结点的返回值大于β 值，则发生剪枝。

　

Alpha-Beta搜索：
function AlphaBeta(Depth: Integer; Alpha, Beta: Double; Board: TBoard): Double;
var
  I, J: Integer;
  t: Double;
begin
  if Depth = 0 then                                   //根节点depth=DepthMax；叶子节点depth=0;
  begin
    Result := 估值;                                   //叶子结点估值返回
    Exit;
  end;
  对于每一个合法的可下棋的位置(i,j) do
  begin
    保存棋局;
    下棋;
    t := -AlphaBeta(Depth - 1, -Beta, -Alpha, Board); //递归调用
    if t > Alpha then
      if t >= Beta then
      begin
        Result := t;
        Exit;
      end
      else
        Alpha := t;
    if (Depth = DepthMax) and (t > Alpha) then        //如果值大于根节点值则赋值
    begin
      max := t;
      max_x := i;                                     //x坐标
      max_y := j;                                     //y坐标
    end;
    恢复棋局;
  end;
  Result := Alpha;
end;

Eastsun

估值函数
    这是一个程序中最重要的部分，如果这个模块太弱，则就算算法再好也没有用。这里将要叙述三种不同的估值函数范例。大多数的黑白棋程序都可以归结于此。
棋格表
    这种算法的意思是，不同的棋格有不同的值，角的值大而角旁边的格子值要小。忽视对称的话，棋盘上有10个不同的位置，每个格子根据三种可能性赋值：黑棋、白棋和空。更有经验的逼近是在游戏的不同阶段对格子赋予不同的值。例如，角在开局阶段和中局开始阶段比终局阶段更重要。
    一般认为，采用这种算法的程序总是很弱，但另一方面，它很容易实现，于是许多程序开始采用这种逼近。并且，对于许多程序设计者来说，它有能力使程序强到击败它的创造者...
基于行动力的估值
    这种更久远的接近有很强的全局观，而不像棋格表那样局部化。观察表明，许多人类玩者努力获得最大的行动力(可下棋的数目)和潜在行动力(临近对手棋子的空格，见技巧篇)。如果代码有效率的话，可以很快发现，它们提高棋力很多。和另一种人类的策略一样，许多基于行动力估值的程序同时还有一些边角配置的知识，试图在中盘早期使棋子最少。
基于模版的估值
    正如上面提及的，许多中等力量的程序经常合并一些边角判断的知识，最大行动力和潜在行动力是全局特性，但是他们可以被切割成局部配置，再加在一起。棋子最少化也是如此。 这导致了以下的概括：在估值函数中仅用局部配置(模版)，通常单独计算每一行、一列、斜边和角落的模板，再线性叠加在一起来实现。并且，配置情况的值非常依赖于游戏的不同阶段。比如，一条边有3321种配置情况((3^8-3^4)/2+3^4)，每种情况的分值好坏在游戏的不同阶段都不相同。分值基于强力玩者和程序的游戏结果统计，他们存于数据库中，游戏启动时自动调入。
常见的有这样一些模板： 名称类似区域配置数去掉对称后的配置数
corner5x2a1:e23^10=59049(3^10-3^5)/2+3^5 = 29646
diag5a5:e13^5 =243(3^5 -3^3)/2+3^3 = 135
diag6a6:f13^6 =729(3^6 -3^3)/2+3^3 = 378
diag7a7:g13^7 =2187(3^7 -3^4)/2+3^4 = 1134
diag8a8:h13^8 =6561(3^8 -3^4)/2+3^4 = 3321
edge2xa1:h1 + b2 + g23^10=59049(3^10-3^5)/2+3^5 = 29646
hor2a2:h23^8 =6561(3^8 -3^4)/2+3^4 = 3321
hor3a3:h33^8 =6561(3^8 -3^4)/2+3^4 = 3321
hor4a4:h43^8 =6561(3^8 -3^4)/2+3^4 = 3321
trianglea1:a4:d13^10=59049(3^10-3^5)/2+3^5 = 29646

估值合并
    一般程序的估值基于许多的参数，如行动力、潜在行动力、余裕手、边角判断、稳定子(见技巧篇)。但是怎么样将他们合并起来得到一个估值呢？为了提高速度，一般的程序采用线性合并。设a1，a2，a3，a4为参数，则估值s：=n1*a1+n2*a2+n3*a3+n4*a4。其中n1，n2，n3，n4为常数，术语叫“权重”(weight)，它决定了参数的重要性，来自于统计值。
一个基于棋格表和行动力估值的例子
function Evalution: Double;
var
  i, j: Integer;
  oppMobility, compMobility: Integer;          //双方行动力
  oppValue, compValue: Integer;                //双方棋格表值
  temp: Double;
  Final: Boolean;
begin
  oppValue := 0;
  compValue := 0;
  if Final then                                //如果是终局搜索
  begin
    for i := 1 to 8 do
      for j := 1 to 8 do
      begin
        if Board[i, j] = compColor then
          Inc(compValue);                      //电脑的棋子数
        if Board[i, j] = oppColor then
          Inc(oppValue);                       //对手的棋子数
      end;
    Result := compValue - oppValue;
    Exit;
  end;
  oppMobility := 0;
  compMobility := 0;
  changeCost;                                  //动态修正棋格表的值
  for i := 1 to 8 do
    for j := 1 to 8 do
    begin
      if (Board[i, j] = compcolor) then
        compValue := compValue + cost[i, j];   //电脑的棋格表值
      if (Board[i, j] = oppColor) then
        oppValue := oppValue + cost[i, j];     //对手的棋格表值
    end;
  for i := 1 to 8 do
    for j := 1 to 8 do
    begin
      if chessable(i, j, compColor) then       //电脑在位置[i,j]可以下棋
        inc(compMobility);                     //增加电脑的行动力
      if chessable(i, j, oppColor) then        //对手在位置[i,j]可以下棋
        inc(oppMobility);                      //增加对手的行动力
    end;
  temp := sqrt(compMobility * 100) - sqrt(oppMobility * 100);
  if compValue - oppValue >= 0 then            //估值合并，不过这里用的并不是线性合并法
    Result := round((sqrt(compValue - oppValue) * 2 + temp) * 100) / 100
  else
    Result := -round((sqrt(oppValue - compValue) * 2 - temp) * 100) / 100;
end;

Eastsun

开局及终局
开局
    所有的强力程序都采用了开局定式，许多顶级程序的定式大多来自IOS游戏。对于强力的程序而言，他会在每一次对局结束以后升级定式，因此，对于有自学习功能的电脑来说，用上一次击败电脑的战术对付电脑是不会管用的。另一方面，具有自学习功能的电脑的中局棋力也会越来越强，原因是电脑会通过不断升级估值函数的权重来提高棋力。TD(Temporal Difference)就是一个实用的强化学习技术。一个应用了该技术的国际象棋程序在国际互联网上进行了300多局对局后，其等级分从1650分（一般水平）上涨到了2110分（美国大师水平）。
终局
    终局是电脑的强项，它的搜索比中局快得多，主要有这样几个理由：
1.终局的估值函数很简单，他只用看双方谁胜了，估值就等于电脑的棋子减去对手的棋子。而不用判断行动力、潜在行动力、余裕手、边角判断和稳定子。
2.终局的搜索由于空格越来越少，使得搜索节点很少。如深度为5的搜索，中盘时叶子节点平均为10*10*10*10*10=100000，而终局时最大为5*4*3*2*1=120。
3.哈希表在终局时效率更高。
    因为随着游戏向终局接近，玩者可下的位置逐渐减少，在终局阶段程序可以搜索得更深。这使得他们在终局比人类下得更好。看计算机在终局下棋经常感到不可思议，因为双方都在游戏结束20步以前知道了游戏的结果。对计算机而言，终局早在人类玩家中局结尾时就开始了，离游戏结束还有20-30步。
　

haydn

好啊 介绍的非常的详细

Eastsun

基础
  首先感谢那些在我研究程序算法时给我帮助的人，如Zebra的作者Gunnar Andersson，微软亚洲研究院的李聪，台湾大学的许舜钦教授等。正是由于站在了无数前辈们多年研究成果的肩膀上，电脑人工智能才得以一步步的成长。我编辑这篇文章的目的在于，希望使更多的人了解人工智能的基本原理，激起大家的兴趣，能有更多有志者研究它，并推动人工智能的发展。这篇文章中部分引用了Gunnar Andersson/李聪/许舜钦教授的文章，在此表示感谢。
    黑白棋程序设计是用编程的方法教会电脑下黑白棋，使之可以与对手对抗，一较棋力高下。由于黑白棋的算法设计在各种棋类游戏中是比较简单的，所以编程相对要容易，而棋力则可以达到非常的强，一般都可以击败它的设计者。黑白棋程序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)。真正的估值函数当然不会这么简单。它会用到技巧篇提到的如行动力、潜在行动力、余裕手、边角判断、稳定子等综合因素来判断。具体的估值函数，我会在“估值函数”一节中详细讲述。
　
    接下来，如果人就这么判断。那么它顶多也就是个初学者。为什么呢？因为它不会推理，碰到对手弃角之类的战术，如“边角判断”中示例的一些情况，就输得一塌糊涂了。当然，可以告诉电脑，碰到“边角判断”中的几种情况，就如何如何下。但是，真实的棋局是非常复杂的，电脑（也包括人脑）几乎不可能对动态的棋局给出静态的评估。因为实际对局总会出现这样那样的情况，是无法预先估计的。碰到这些情况，人就会向后推几步，看一看会是怎样的一个局面。一些棋类大师往往可以推十几步甚至更深。电脑也是如此。
    还是刚才那一幅图的演化。
　


　
    电脑在自己下棋以后，把对手的下棋情况也推理出来。然后加以评分。（最下一排是电脑评估的得分）这一次电脑又如何下呢？这时电脑假设对手是高手。如果电脑下e3，对手就会下对电脑最不利的情况f6。同样，电脑下c3，对手就会下d3，电脑下c5，对手就会下d6。这三种情况，c5是最不好的(因为c5的下一步d6的得分最低)，c3与e3一样。因此电脑会下c3或者e3。用程序化的语言这样描述：
    电脑从棋盘初始状态出发，以后双方轮流下子，形成一种倒树状结构。树的层数就是电脑搜索的深度。在树状结构的叶子节点，对棋盘状态进行估值，即估计形式的好坏。得出一个分值。将此分值赋给叶子节点，之后，如果父节点该电脑下棋，则将子节点的最大节点值赋给其父，如果父节点该对手下棋，则将子节点的最小节点值赋给其父。（就是说，四级节点把最大值赋给三级节点，三级节点把最小值赋给二级节点，二级节点把最大值赋给根节点...）以此类推，得到根节点的值。具有和根节点一样值的二级节点即为电脑该下的位置。
    这里读者会有个疑问：电脑为什么要假设对手是高手？这是因为，如果你认为对手不是高手，但是不能说对手每一步都会下错。比如你送对手一个角吃。对手如果吃掉了，岂非损失惨重？当然，如果你确定对手不会吃你的角，你也可以下，但是前提就是“你确定对手不会吃你的角”。也就是你完全明白对手的战术。所以说如果一个程序完全了解另一个程序（或人）的下法，它也可以用针对性的下法，这将会更具成效。
　
　

具体实现的伪算法类似于经典的八皇后问题。
最大最小搜索：
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;