怎样编制黑白棋(2)

剪枝

    新的问题出现了：对于一般的最大最小搜索，即使每一步只有很少的下法，搜索位置的数目也会随着搜索深度呈级数级增长。在大多数的中局棋形中，每步平均有十种下法，假设电脑搜索九步(程序术语称为搜索深度为九)，就要搜索十亿个位置(十的九次方)，这样极大地限制了电脑的棋力：我们总不能忍受电脑棋手一年才下一步棋。减少搜索结点的最简单的方法是减小搜索深度，但这大大影响了电脑棋手的棋力。是否有办法在不减小搜索深度的前提下将需要搜索的结点减小一些？幸运的是，可以证实，程序不需要考虑所有的位置而找到最佳点，于是人们采用了一个方法，叫"alpha-beta剪枝"，它大为减少了检测的数目，提高电脑搜索的速度。所有的强力黑白棋程序都用到了各种各样的这种算法。(同样用于其他棋类游戏，如国际象棋和跳棋)。为了搜索九步，一个好的程序只用搜索十万到一百万个位置，而不是没用前的十亿次。

    还有几种alpha-beta算法的改进型，最广泛采用的是NegaScout，(Alexander Reinefeld发明)，但它和一般的alpha-beta剪枝算法没有根本的不同。其他的还有PVS和SSS*。下面举例说明。

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

  对于每一个合法的可下棋的位置(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;