program TestAB;
{
 This program is a crude implementation of the AlphaBeta
 algorithm found in Kreutzer & MacKenzie p. 233.
}
  const
    MaxNum = 2;  {node degree}
    NumPly = 4;  {search ply}
    Root = 1;    {start search at this location}
 
  type
    Index = 1..50;
    Tree = array[Index] of Real;     {simulated game tree}
    State = Index;
    Ply = Integer;
    ListIndex = 1..MaxNum;
    List = array[ListIndex] of Real; {state siblings}
 
  var
    T : Tree;
 
  procedure Init(var T : Tree);
  {
   Build dummy game tree.
  }
  var
    I : Index;
 
  begin {Init}
    for I := 16 to 31 do       {blank out 4-ply leaf nodes}
      T[I] := 0;
  end; {Init}
 
  function Eval (S : State) : Real;
  {
   Compute value of state S.
  }
  begin {Eval}
    Eval := Random(101);
  end; {Eval}
 
  function Terminal(S : State) : Boolean;
  {
   Stub function to check S for succesor states.
  }
  begin {Terminal}
    Terminal := False;
  end; {Terminal}
 
  function Max(X, Y : Real) : Real;
  {
   Returns maximum of X and Y.
  }
  begin {Max}
    if X > Y then
      Max := X
    else
      Max := Y
  end; {Max}
 
  function Min(X, Y : Real) : Real;
  {
   Returns minimum of X and Y.
  }
  begin {Min}
    if X < Y then
      Min := X
    else
      Min := Y
  end; {Min}
 
  function Child(S : State; I : ListIndex) : State;
  {
   Compute I-th successor of state S.
  }
  begin {Child}
    Child := MaxNum * S + I - 1;
  end; {Child}
 
  function MachineMove(N : Ply) : Boolean;
  {
   Checks to see if it is computer's move in this ply.
  }
  begin {MachineMove}
    MachineMove := { not } Odd(N)
  end; {MachineMove}
 
  function AlphaBeta(S : State; N : Ply; Alpha, Beta : Real) : Real;
  {
   Recusively score state S using evaluation function Eval
   and an N - Ply state space graph.
  }
    var
      Next      : State;
      I         : ListIndex;
      V, Value,
      BestScore : Real;
      L         : List; {successors of S at this level}
 
  begin {AlphaBeta}
    if (N = 0) or Terminal(S) then
      begin
        Value := Eval(S);
 
        T[S] := Value;  {record values only to confirm cut offs}
 
        if Value > 100 then         {machine win}
          AlphaBeta := MaxInt
        else if Value < -100  then  {machine loss}
          AlphaBeta := -MaxInt
        else if Value = 0 then      {draw}
          AlphaBeta := 0
        else
          AlphaBeta := Value
      end
    else
      begin
        if MachineMove(N) then            {program's move}
          BestScore := Alpha
        else
          BestScore := Beta;
 
        I := 1;
        while I <= MaxNum do
          begin
            Next := Child(S, I);
            V := AlphaBeta(Next, N - 1, Alpha, Beta);
 
            if MachineMove(N) then        {program's move}
              begin
                BestScore := Max(V, BestScore);
                Alpha := BestScore;
                if Alpha >= Beta then
                  begin
                    BestScore := Beta;
                    I := MaxNum;        {prune remaining S successors}
                  end
              end
            else
              begin
                BestScore := Min(V, BestScore);
                Beta := BestScore;
                if Alpha >= Beta then
                  begin
                    BestScore := Alpha;
                    I := MaxNum;        {prune remaining S successors}
                  end
              end;
            I := I + 1;
          end;
        AlphaBeta := BestScore;
      end
  end; {AlphaBeta}
 
begin {TestAB}
  Randomize;
  Init(T);
  WriteLn('Value = ', AlphaBeta(Child(Root, 1), NumPly - 1, -MaxInt, MaxInt));
  WriteLn('Value = ', AlphaBeta(Child(Root, 2), NumPly - 1, -MaxInt, MaxInt));
end. {TestAB}