int MaxMoveFirst(stateT state, moveT &bestMove)
{
  if(GameIsOver(state))
    return EvaluateStaticPosition(state);
 
  vector<moveT> moveList;
  GenerateMoveList(state, moveList);
  int nMoves = moveList.size();
  int v = -1000;

  #pragma omp parallel for 
  for(int i = 0 ;i<nMoves; i++) {
    moveT move = moveList[i];
    MakeMove(state, move);
    moveT opponentsBestMove;
    int curRating = -MaxMove(state,opponentsBestMove);
    if (curRating > v)
    {
      v = curRating;
      bestMove = move;
    }
    RetractMove(state, move);
  }
  return v;
}


int MaxMove(stateT state, moveT &bestMove)
{
  if(GameIsOver(state))
    return EvaluateStaticPosition(state);
 
  vector<moveT> moveList;
  GenerateMoveList(state, moveList);
  int nMoves = moveList.size();
  int v = -1000;

  for(int i = 0 ;i<nMoves; i++) {
    moveT move = moveList[i];
    MakeMove(state, move);
    moveT opponentsBestMove;
    int curRating = -MaxMove(state,opponentsBestMove);
    if (curRating > v)
    {
      v = curRating;
      bestMove = move;
    }
    RetractMove(state, move);
  }
  return v;
}

moveT MiniMax(stateT state)
{
  moveT bestMove;
  int i = 0;
  i = MaxMoveFirst(state, bestMove);
  return bestMove;
}