#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include <values.h>

// This program is a crude implementation of the AlphaBeta
// algorithm found in Kreutzer & MacKenzie p. 233.

  const True = 1;
  const False = 0;
  const MaxNum = 2;  //node degree
  const NumPly = 4;  //search ply
  const Root = 1;    //start search at this location
  const Index = 51;

  typedef float Tree[Index];    //simulated game tree
  typedef int State;
  typedef int Ply;
  typedef int ListIndex;
  typedef float List[MaxNum];   //state siblings

  Tree T;                       //game tree declaration

  void Init(Tree &T)
  // Build dummy game tree.
  {
    int I;

    for (I = 16; I <= 31; I++)   //blank out 4-ply leaf nodes
      T[I] = 0.0;
  }

  float Eval(State S)
  //Compute value of state S.
  {
    int x;
    x = (int) rand( );
    x = x % 100;
    return (float) x;
  }

  int Terminal(State S)
  //Stub function to check S for succesor states.
  {
    return False;
  }

  float Max(float X, float Y)
  // Returns maximum of X and Y.
  {
    if (X > Y)
      return X;
    else
      return Y;
  }

  float Min(float X, float Y)
  //Returns minimum of X and Y.
  {
    if (X < Y)
      return X;
    else
      return Y;
  }

  State Child(State S, ListIndex I)
  //Compute I-th successor of state S.
  {
    return MaxNum * S + I - 1;
  }

  int MachineMove(Ply N)
  //Checks to see if it is computer's move in this ply.
  {
    return !(N % 2); //odd moves are computers
  }

  float AlphaBeta(State S, Ply N, float Alpha, float Beta)
  //Recusively score state S using evaluation function Eval
  //and an N - Ply state space graph.
  {
    State Next;
    ListIndex I;
    float V, Value, BestScore;
    List L;                   //successors of S at this level

    if ((N == 0) || Terminal(S))
    {
      Value = Eval(S);
      T[S] = Value;    //record values only to confirm cut offs

	if (Value > 100)            //machine win
	  return MAXINT;
	else if (Value < -100)      //machine loss
	  return  -MAXINT;
	else if (Value == 0)        //draw
	  return 0;
	else
	  return Value;
    }
    else
    {
      if (MachineMove(N))         //program's move
	BestScore = Alpha;
      else
	BestScore = Beta;

      I = 1;
      while (I <= MaxNum)
      {
	Next = Child(S, I);
	V = AlphaBeta(Next, N - 1, Alpha, Beta);

	if (MachineMove(N))       //program's move
	{
	  BestScore = Max(V, BestScore);
	  Alpha = BestScore;
	  if (Alpha >= Beta)
	  {
	    BestScore = Beta;
	    I = MaxNum;           //prune remaining S successors
	  }
	}
	else
	{
	  BestScore = Min(V, BestScore);
	  Beta = BestScore;
	  if (Alpha >= Beta)
	  {
	    BestScore = Alpha;
	    I = MaxNum;           //prune remaining S successors
	  }
	}
	I = I + 1;
      }
      return BestScore;
    }
  }

void main( )
{
  // seed rand function
  srand( (unsigned)time( NULL ) );
  Init(T);
  cout << "Value = "
       << AlphaBeta(Child(Root, 1), NumPly - 1, -MAXINT, MAXINT)
       << "\n";
  cout << "Value = "
       << AlphaBeta(Child(Root, 2), NumPly - 1, -MAXINT, MAXINT)
       << "\n";
}