怎样编制黑白棋(1)

基础

   如上图所示棋局，设电脑为白棋，推理深度为2，可以形成如下的树：（数字为节点值）

具体实现的伪算法类似于经典的八皇后问题。

最大最小搜索：

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;

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