#define ALPHA_MIN -200000 //the starting alpha value
#define BETA_MAX -ALPHA_MIN //the starting beta value

#define LOST -10000 //score for loosing

long COMPUTER::Search(int depth, long alpha, long beta, MOVE *bestmove)
{
  /*
  detph- if it is 0 we must stop
  alpha- beta
  bestmove if it is not NULL it should return the best move
  */

  LIST_MOVE *moves, *t; //linked list of possible moves
  long val, best_val=ALPHA_MIN;
  
  if(depth==0)
    {
    val=Evaluate(); //evalute the board
    return val;
    }
      
  //bord is a global class
  moves=board->GetPossibleMoves();
  if(!moves) //we can not move, we have lost
    return LOST;
  
  //stop is a global variable
  while(moves && !stop)
    {
    board->MakeMove(moves->move);
    
    val=-Search(depth-1,-beta,-alpha,NULL);
    
    board->UndoMove();
    
    if(val>best_val)
      {
      best_val=val;
      if(bestmove)
        *bestmove=moves->move;
      }
    
    if(best_val>alpha)
      alpha=best_val;
    
    if(alpha>=beta)
      {
      //free the linked list
      while(moves)
       {
       t=moves;
       moves=moves->next;
       delete t;
       }

      return alpha;
      }
    
    //change to the next move
    t=moves;
    moves=moves->next;
    delete t;
    }

  while(moves)
    {
    //free the list
    t=moves;
    moves=moves->next;
    delete t;
    }
  
  return best_val;
}