//AlphaBetaTree.h

#include <cstdlib>
#include <ctime>
#include <utility>
#include <vector>
#include <algorithm>
#include <iostream>
#include "coord.h"
#include "chessAuxFunctions.h"

typedef std::pair<coord, coord> move;
typedef std::pair<int, move> solution;


class alphaBetaTree
{
  public:
    alphaBetaTree(const int& gen): MAX_GENERATION(gen) {std::srand(std::time(0));}
    void generateTree(const chessBoard&);
    move getBestMove() const;
    enum {MAX, MIN};

  private:
    class chessNode
    {
      public:
        chessNode(const chessBoard&, const move&, bool);
        chessNode(const chessBoard&);
        const chessBoard& getBoard() const;
      private:
        chessNode();
        chessBoard board;
        move m;
    };
   
    alphaBetaTree();
    int maxNode(chessNode node, int alpha, int beta, int generation);
    int minNode(chessNode node, int alpha, int beta, int generation);
    int chessEvaluator(const chessBoard&, bool);
    int scorePiece(chessPiece*);
    std::vector<move> generateMoves(const chessBoard&, bool);
    
    const int MAX_GENERATION;
    move bestMove;
    int rootNodeBestScore;
};

inline move alphaBetaTree::getBestMove() const
{
  return bestMove;
}

inline alphaBetaTree::chessNode::chessNode(const chessBoard& b, const move& m, bool owner): board(b)
{
  board.movePiece(m.first, m.second, owner);
}

inline alphaBetaTree::chessNode::chessNode(const chessBoard& b): board(b) { }

const chessBoard& alphaBetaTree::chessNode::getBoard() const
{
  return board;
}

std::vector<move> alphaBetaTree::generateMoves(const chessBoard& b, bool owner)
{
  std::vector<move> ret;
  for(int i = 0; i < 8; ++i)
    for(int j = 0; j < 8; ++j)
      if(b.getPiece(coord(i, j)) != 0 && b.getPiece(coord(i, j))->getOwner() == owner)
        for(int k = 0; k < 8; ++k)
          for(int l = 0; l < 8; ++l)
            if(b.threaten(coord(i, j), coord(k, l)))
              ret.push_back(std::make_pair(coord(i, j), coord(k, l)));
  return ret;
}

inline int alphaBetaTree::maxNode(alphaBetaTree::chessNode node, int alpha, int beta, int generation)
{
  std::vector<move> moves = generateMoves(node.getBoard(), MAX);

  if(generation == MAX_GENERATION || moves.size() == 0)
    return chessEvaluator(node.getBoard(), MAX);
  
  else {
    for(std::vector<move>::iterator i = moves.begin(); i != moves.end(); ++i) {
      alpha = std::max(alpha, minNode(chessNode(node.getBoard(), *i, MIN), alpha, beta, generation + 1));
      if(generation == 0 && alpha >= rootNodeBestScore) {
        if(std::rand() % 2) {
          bestMove = *i;
          rootNodeBestScore = alpha;
        }
      }
      if(alpha > beta)
	    return beta;
    }
  }
  return alpha;
}


inline int alphaBetaTree::minNode(alphaBetaTree::chessNode node, int alpha, int beta, int generation)
{
  std::vector<move> moves = generateMoves(node.getBoard(), MIN);

  if(generation == MAX_GENERATION || moves.size() == 0) 
    return chessEvaluator(node.getBoard(), MIN);
  
  
  else {
    for(std::vector<move>::iterator i = moves.begin(); i != moves.end(); ++i) {
      beta = std::min(beta, maxNode(chessNode(node.getBoard(), *i, MAX), alpha, beta, generation + 1));
      if(alpha > beta)
	    return alpha;
    }
  }
  return beta;
}

inline void alphaBetaTree::generateTree(const chessBoard& b)
{
  rootNodeBestScore = -99999999;
  maxNode(chessNode(b), -99999999, 99999999, 0);
}

inline int alphaBetaTree::chessEvaluator(const chessBoard& b, bool who)
{
  //keep track of score
  int score = 0;

  //find a piece on the board
  //use an iterator to go through board
  for(int i = 0; i < 64; ++i){
    if(b != 0 && b->getOwner() == who) {
      //check to see what piece *i points to and increment score accordingly
      score += scorePiece(b);
    }
  }
  //check to see if the piece that *j points to is a valid piece
  //and how many points its worth if *i threatens it
  if(b.check(!who))
    score += 10;

  //check to see if the opponents king is in checkmate
  if(b.checkMate(!who))
    score += 40;

  //return score according to who it is
  //negative for who == false
  //positive for who == true
  if(who)
    return score;
  else return score*-1;
}

inline int alphaBetaTree::scorePiece(chessPiece* p)
{
  //make sure that *p is a valid piece
  if(p == 0)
    return 0;

  //get the ID of the piece
  int ID = p->getID();

  // IDs are as follows
  // 1 = pawn
  // 2 = rook
  // 3 = knight
  // 4 = bishop
  // 5 = queen
  // 6 = king

  switch(ID){
  case 1:
    return 1;
  case 2:
    return 2;
  case 3:
    return 2;
  case 4:
    return 2;
  case 5:
    return 5;
  case 6:
    return 6;
  default:
    return 0;
  }
}



Here are the times I've gotten so far with testing it:

Search Depth      Time in Seconds
1 move               0 sec
2 moves              0 sec
3 moves              11 sec
4 moves              353 sec

inline int alphaBetaTree::scorePiece(chessPiece* p){  //make sure that *p is a valid piece  if(p == 0)    return 0;  //get the ID of the piece  int ID = p->getID();  // IDs are as follows  // 1 = pawn  // 2 = rook  // 3 = knight  // 4 = bishop  // 5 = queen  // 6 = king  switch(ID){  case 1:    return 1;  case 2:    return 2;  case 3:    return 2;  case 4:    return 2;  case 5:    return 5;  case 6:    return 6;  default:    return 0;  }}

inline int alphaBetaTree::scorePiece(chessPiece* p){  //make sure that *p is a valid piece  if(p == 0)    return 0;  return p->getID();}

inline int alphaBetaTree::scorePiece(chessPiece* p){  if(p == 0)    return 0;  int ID = p->getID();  if(ID == 2 || ID == 3 || ID == 4)    return 2;  else return ID;}