/*****************************************************************************\
 * FILE: computerSearch.cpp
 *
 * PURPOSE: Implementation of the computerSearch class.
 *
 * Created by Eric Akers, 24 Dec 2003
 *
 * ChangeLog:
 *     ELA - <Date> - Initial Working Version
 *
 *
 *
 *   
 *   Copyright (C) 2003 Eric Akers
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
\*****************************************************************************/



// Header Files #############################################################
#include <stdlib.h>
#include <stdio.h>

#include "computerSearch.h"

// Macros ###################################################################
#define EARLY_MOVES 10

// Structures ###############################################################


// Class Function Definitions ###############################################
computerSearch::computerSearch()
{
  isWinningState = hasLost = false;
  plySearchLevel = 2;
  numMoves = 0;

  boardState = new SimpleHeuristic();
  if( boardState == NULL ) {
    printf( "Error allocating memory\n" );
    exit( -1 );
  }
}


computerSearch::computerSearch( int numPly )
{
  plySearchLevel = numPly;
  isWinningState = hasLost = false;
  numMoves = 0;

  boardState = new SimpleHeuristic();
  if( boardState == NULL ) {
    printf( "Error allocating memory\n" );
    exit( -1 );
  }
}


bool computerSearch::setOtherPlayerMove( int row, int col ) 
{
  // Increase the total number of moves
  numMoves++;

  boardState->setPlayerMove( row, col, Board::PLAYER_TWO );
  if( boardState->isWinningState() ) {
    return true;
  }
  else {
    return false;  
  }
}



// Determine if the current state is a winner
bool computerSearch::isWinner() const
{
  return isWinningState;
}


// ------------- Alpha beta search
bool computerSearch::getNextMove( int & row, int & col )
{
/*
  bool isEarly = false;; // Determines whether it is too early to filter moves
  // Increase the total number of moves
  if( numMoves++ > EARLY_MOVES ) {
    isEarly = true;
  }
*/

  // Do the alpha beta search up to the given ply
  long int alpha = -65000;
  long int beta = 65000;
  long int curAlpha;

  // Get the list of possible moves from here
  //  printf( "Get possible plays\n" );
  list<Move> spotsToTry = boardState->getOpenAdjacentPositions();
  list<Move>::iterator iter = spotsToTry.begin();

  Move curBest;
  curBest.row = curBest.col = -1;
  for( unsigned int i=0; i<spotsToTry.size(); i++, iter++ ) {
    Move curMove = *iter;
/*
    // Try to filter the move before doing any processing
    if( isEarly && filterMove(curMove, boardState, Board::PLAYER_ONE) ) {
      // Try the next move
      continue;
    }
*/

    // Create the next state
    SimpleHeuristic * newNode = (SimpleHeuristic*)
      boardState->getNextBoard( curMove.row, curMove.col, Board::PLAYER_ONE );

    // Make sure this new node is not a winner
    if( newNode->isWinningState() ) {
      // Just set the new move
      row = curMove.row;
      col = curMove.col;
      boardState->setPlayerMove( row, col, Board::PLAYER_ONE );

      // Remove the new state
      delete newNode;

      // We have found a winning location
      return true;
    }

    // Send it on
    curAlpha = doSearchMin( alpha, beta, 1, newNode );

    // Delete the old state
    delete newNode;

    if( curAlpha > alpha ) {
      // We have a new best value. Set the move
      curBest.row = curMove.row;
      curBest.col = curMove.col;
      alpha = curAlpha;
    }
  }

  // Set the move to use
  boardState->setPlayerMove( curBest.row, curBest.col, Board::PLAYER_ONE );

  // Return the new move
  row = curBest.row;
  col = curBest.col;
  return false;
}


long int computerSearch::doSearchMin( int alpha, int beta, int level,
				      SimpleHeuristic * currentNode )
{
/*
  bool isEarly = false;; // Determines whether it is too early to filter moves
  // Increase the total number of moves
  if( numMoves++ > EARLY_MOVES ) {
    isEarly = true;
  }
*/

  // First make sure we haven't hit the end of the search
  if( level == plySearchLevel ) {
    // Simply return the heuristic value
    long int val =  currentNode->getHeuristicValue( Board::PLAYER_ONE );
    return val;
  }

  // Get a list of the next possible moves
  list<Move> spotsToTry = currentNode->getOpenAdjacentPositions();
  list<Move>::iterator iter = spotsToTry.begin();

  long int curBeta;
  for( unsigned int i=0; i<spotsToTry.size(); i++, iter++ ) {
    Move curMove = *iter;
/*    // Try to filter the move before doing any processing
    if( isEarly && filterMove(curMove, currentNode, Board::PLAYER_TWO) ) {
      // Try the next move
      continue;
    }
*/
    // Get the next state
    SimpleHeuristic * newNode = (SimpleHeuristic*)
      currentNode->getNextBoard( curMove.row, curMove.col, Board::PLAYER_TWO );

    // Make sure this new node is not a winner
    if( newNode->isWinningState() ) {
      // Delete the state first
      delete newNode;

      return -64999;
    }

    // Send it on to get the next beta
    curBeta = doSearchMax( alpha, beta, level + 1, newNode );

    // Delete the old board
    delete newNode;

    // See if this was a better move for min
    if( curBeta < beta ) {
      // We have a worse value
      beta = curBeta;
    }

    // See if we can prune
    if( beta <= alpha ) {
      return alpha;
    }
  }

  // The beta is the value it needs
  return beta;
}

long int computerSearch::doSearchMax( int alpha, int beta, int level,
				      SimpleHeuristic * currentNode )
{
/*
  bool isEarly = false;; // Determines whether it is too early to filter moves
  // Increase the total number of moves
  if( numMoves++ > EARLY_MOVES ) {
    isEarly = true;
  }
*/
  // Make sure we are not ready to return
  if( level == plySearchLevel ) {
    // Simply return the heuristic value
    long int val =  currentNode->getHeuristicValue( Board::PLAYER_ONE );
    return val;
  }

  // Get a list of the next possible moves
  list<Move> spotsToTry = currentNode->getOpenAdjacentPositions();
  list<Move>::iterator iter = spotsToTry.begin();

  long int curAlpha;
  for( unsigned int i=0; i<spotsToTry.size(); i++, iter++ ) {
    Move curMove = *iter;
/*    // Try to filter the move before doing any processing
    if( isEarly && filterMove(curMove, currentNode, Board::PLAYER_ONE) ) {
      // Try the next move
      continue;
    }
*/
    // Get the next state
    SimpleHeuristic * newNode = (SimpleHeuristic*)
      currentNode->getNextBoard( curMove.row, curMove.col, Board::PLAYER_ONE );

    // Make sure this new node is not a winner
    if( newNode->isWinningState() ) {
      // Delete the new state first
      delete newNode;

      return 64999;
    }

    // Send it on to get the next alpha
    curAlpha = doSearchMin( alpha, beta, level + 1, newNode );

    // Delete the old board as it is no longer of any use to us
    delete newNode;

    // See if we have a new best move
    if( curAlpha > alpha ) {
      // We have a worse value
      alpha = curAlpha;
    }

    // See if we can prune
    if( alpha >= beta ) {
      // Continuing here is useless because there is a worse move on this
      // branch that the other player would choose.
      return beta;
    }
  }

  // Return the alpha value since we are finished
  return alpha;
}



// Filters the move so that pointless (hopefully) moves are not
// processed
bool computerSearch::filterMove( Move & curMove, SimpleHeuristic * board,
				 int player )
{
  // The adjoining positions
  int rowDelta[] = { 1, -1, 0,  0,  1, 1, -1, -1 };
  int colDelta[] = { 0,  0, 1, -1, -1, 1, -1,  1 };

  int pieceCount = 0;
  for( int i=0; i<8; i++ ) {
    int curRow = curMove.row + rowDelta[i];
    int curCol = curMove.col + colDelta[i];

    // Make sure the new location is in bounds
    if( curRow < 0 || curRow > 18 || curCol < 0 || curCol > 18 ) {
      // Out of bounds
      continue;
    }
    else {
      // make sure the location is empty
      int piece;
      if( (piece = board->getPlayerAt(curRow, curCol)) != Board::BLANK ) {
	if( ++pieceCount > 1 || piece == player ) {
	  // This move cannot be filtered
	  return false;
	}

	// Get the opposite piece
	int pieceOpposite;
	if( piece == Board::PLAYER_ONE ) {
	  pieceOpposite = Board::PLAYER_TWO;
	}
	else {
	  pieceOpposite = Board::PLAYER_ONE;
	}
	
	// See if nothing exists for four more pieces or the piece is blocked
	for( int j=2; j<5; j++ ) {
	  int blockRow = j * rowDelta[i] + curMove.row;
	  int blockCol = j * colDelta[i] + curMove.col;
	  if( blockRow < 0 || blockRow > 18 || blockCol < 0 || blockCol > 18 ) {
	    // This piece is at the end
	    break;
	  }

	  // Check to see if the first piece (only) is blocked
	  int blockPiece = board->getPlayerAt( blockRow, blockCol );
	  if( j == 2 && blockPiece == pieceOpposite ) {
	    // The piece is blocked
	    break;
	  }
	  else if( j == 2 && blockPiece == player ) {
	    // Do not ignore this as it is the same piece
	    return false;
	  }
	  else if( blockPiece != Board::BLANK ) {
	    // this piece cannot be ignored
	    return false;
	  }
	} // for int j
      } // if piece != Board::BLANK
    }
  } // for int i

  // If it made it here, then there is nothing out there
  //  printf( "Ignore move: (%d,%d)\t%d\n", curMove.row, curMove.col, pieceCount );
  return true;
}