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

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

怎样编制黑白棋(2)
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的值）。在搜索过程中，α 值递增， β值递减，两者构成了一个区间。这个区间被称为窗口，而对手下棋的结点最终的最优值将落在这个窗口中。一旦在电脑下棋的结点得到其子结点的返回值大于β 值，则发生剪枝。

　 
初始棋局(-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 
 

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;