///////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//         This example code is from the book:
//
//           Object-Oriented Programming with C++ and OSF/Motif, 2nd Edition
//         by
//           Douglas Young
//           Prentice Hall, 1995
//           ISBN 0-13-20925507
//
//         Copyright 1995 by Prentice Hall
//         All Rights Reserved
//
//  Permission to use, copy, modify, and distribute this software for 
//  any purpose except publication and without fee is hereby granted, provided 
//  that the above copyright notice appear in all copies of the software.
///////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////
// MoveGenerator.C
//////////////////////////////////////////////////////
#include "MoveGenerator.h"
#include "Board.h"
#include "unistd.h"
#include "math.h"

#define CENTER 4

MoveGenerator::MoveGenerator()
{
    srand48( (long) getpid());
}

int MoveGenerator::getNextMove ( Board *board )
{
    int randomIndex, movesLeft, nextMove;
    
    // Get the list of free squares on the Board
    
    const int *freeSquares = board->freeSquares ( movesLeft );
    
    if ( movesLeft == 0 )
	return ( -1 );
    
    // See if we can win with this move
    
    if ( ( nextMove = board->winningMove ( OO )) >= 0 )
    {
	return nextMove;
    }
    
    // See if X could win in one move. If so, block the move
    
    if ( ( nextMove = board->winningMove ( XX )) >= 0 )
    {
	return nextMove;
    }
    
    for (int pos = 0; pos < movesLeft; pos++)
    {
	Board tmp;
	
	// Clone it
	
	for(int sq = 0; sq < 9; sq++)
	    tmp.recordMove(sq, (markType) board->value(sq));
	
	// Fake the move
	
	tmp.recordMove(freeSquares[pos], OO);
	
	if(tmp.winningPositions(OO) > 1)
	{
	    return  freeSquares[pos];
	}
    }
    
    // Grab the middle, if it is available
    
    if ( board->value ( CENTER ) == NOBODYYET )
    {
	return CENTER;
    }
    
    int numPossible = 0;
    int possible[9];
    
    for (pos = 0; pos < movesLeft; pos++)
    {
	Board tmp;
	
	// Clone it
	
	for(int sq = 0; sq < 9; sq++)
	    tmp.recordMove(sq, (markType) board->value(sq));
	
	// Fake the move
	
	tmp.recordMove(freeSquares[pos], OO);
	
	if(tmp.winningPositions(OO) >= 1)
	{
	    possible[numPossible++] =  freeSquares[pos];
	}
    }
    
    if(numPossible)
    {
	randomIndex = ( int ) ( (numPossible -1) *  drand48() );

	return possible[randomIndex];
    }
    
    
    // If all else fails, pick one of the free squares at random and return it
    
    randomIndex = ( int ) ( (movesLeft -1) * drand48() );

    return ( freeSquares[randomIndex] );
}













