////////////////////////////////////////////////////////////////////
/// reversi.js
/// © 2007 Carl Johansen
/// 
/// Routines for Reversi computer player.
////////////////////////////////////////////////////////////////////

//These are really constants
var BOARD_SIZE = 8;
var IllegalSquare = -1;
var EmptySquare = 0;
var WhitePlayer = 1;
var BlackPlayer = 2;

var theBoard = new Array();
var evalWeight;

//---------------------------------------------------------------------------------------

function GetOpponent(player)
{
    return (player == WhitePlayer) ? BlackPlayer : WhitePlayer;
}

//---------------------------------------------------------------------------------------

function GetInitializedBoard()
{
    var i, j;
    var theBoard = new Array(BOARD_SIZE + 2);
    for(i = 0; i <= (BOARD_SIZE + 1); i++)
    {
        theBoard[i] = new Array(BOARD_SIZE + 2);
        for(j = 0; j <= (BOARD_SIZE + 1); j++)
            if(i == 0 || i == (BOARD_SIZE + 1) || j == 0 || j == (BOARD_SIZE + 1))
                theBoard[i][j] = IllegalSquare;
            else
                theBoard[i][j] = EmptySquare;
    }
    theBoard[4][4] = WhitePlayer;
    theBoard[5][5] = WhitePlayer;
    theBoard[4][5] = BlackPlayer;
    theBoard[5][4] = BlackPlayer; 
    
    return theBoard;       
}

//---------------------------------------------------------------------------------------

function GetInitializedEvaluator()
{
    var currRow, currCol;

    var evalWeight = new Array(BOARD_SIZE + 1);

    for(currRow = 1; currRow <= BOARD_SIZE; currRow++)
    {
        evalWeight[currRow] = new Array(BOARD_SIZE + 1);
        for(currCol = 1; currCol <= BOARD_SIZE; currCol++)
            if(currRow == 1 || currRow == BOARD_SIZE || currCol == 1 || currCol == BOARD_SIZE)
                evalWeight[currRow][currCol] = BOARD_SIZE;
            else if(currRow == 2 || currRow == (BOARD_SIZE - 1) || currCol == 2 || currCol == (BOARD_SIZE - 1))
                evalWeight[currRow][currCol] = 1;
            else if(currRow == 3 || currRow == (BOARD_SIZE - 2) || currCol == 3 || currCol == (BOARD_SIZE - 2))
                evalWeight[currRow][currCol] = 5;
            else if(currRow == 4 || currRow == (BOARD_SIZE - 3) || currCol == 4 || currCol == (BOARD_SIZE - 3))
                evalWeight[currRow][currCol] = 3;
    }
    
    evalWeight[1][1] = 15;
    evalWeight[1][BOARD_SIZE] = 15;
    evalWeight[BOARD_SIZE][1] = 15;
    evalWeight[BOARD_SIZE][BOARD_SIZE] = 15;
    evalWeight[2][2] = -1;
    evalWeight[2][BOARD_SIZE - 1] = -1;
    evalWeight[BOARD_SIZE - 1][2] = -1;
    evalWeight[BOARD_SIZE - 1][BOARD_SIZE - 1] = -1;
    evalWeight[1][2] = 1;
    evalWeight[1][BOARD_SIZE - 1] = 1;
    evalWeight[BOARD_SIZE][2] = 1;
    evalWeight[BOARD_SIZE][BOARD_SIZE - 1] = 1;
    
    return evalWeight;
}

//---------------------------------------------------------------------------------------

function IsValidMove(theBoard, moveRow, moveCol, player)
{
    var opponent = GetOpponent(player);
    var offset, checkSquare, i, j;
    
    for(i = -1; i <= 1; i++)
        for(j = -1; j <= 1; j++)
            if(i != 0 || j != 0)
            {
                if(theBoard[moveRow + i][moveCol + j] == opponent)
                {
                    offset = 2;
                    do {
                        checkSquare = theBoard[moveRow + i * offset][moveCol + j * offset];
                        if(checkSquare == player)
                            return true;
                        offset++;
                    } while(checkSquare == opponent);
                }
            }
    return false;            
}
    
//---------------------------------------------------------------------------------------

function ApplyMove(theBoard, moveRow, moveCol, player)
{
    //ApplyMove assumes that the move is valid!
    //It returns the modified state of theBoard.
    
    var opponent = GetOpponent(player);
    var offset, applyOffset, checkSquare, i, j;
    
    theBoard[moveRow][moveCol] = player;

    for(i = -1; i <= 1; i++)
    for(j = -1; j <= 1; j++)
        if(i != 0 || j != 0)
        {
            if(theBoard[moveRow + i][moveCol + j] == opponent)
            {
                offset = 2;
                do {
                    checkSquare = theBoard[moveRow + i * offset][moveCol + j * offset];
                    if(checkSquare == player)
                    {
                        //Apply capture along vector [i, j]
                        for(applyOffset = 1; applyOffset < offset; applyOffset++)
                            theBoard[moveRow + i * applyOffset][moveCol + j * applyOffset] = player;
                        break;
                    }
                    offset++;
                } while(checkSquare == opponent);
            }
        }
    return theBoard;
}

//---------------------------------------------------------------------------------------

function GetValidMoveList(theBoard, player)
{
    var currRow, currCol, intNumValidMoves = 0;
    var arrValidMoves = new Array(2);
    arrValidMoves[0] = new Array(40);
    arrValidMoves[1] = new Array(40);
    
    for(currRow = 1; currRow <= BOARD_SIZE; currRow++)
        for(currCol = 1; currCol <= BOARD_SIZE; currCol++)
            if(theBoard[currRow][currCol] == EmptySquare)
                if(IsValidMove(theBoard, currRow, currCol, player))
                {
                    arrValidMoves[0][intNumValidMoves] = currRow;
                    arrValidMoves[1][intNumValidMoves] = currCol;
                    intNumValidMoves++;
                }
    
    var result = new Object();
    result.NumValidMoves = intNumValidMoves;
    result.ValidMoves = arrValidMoves;
    return result;
}

//---------------------------------------------------------------------------------------

function CloneBoard(theBoard)
{
    var boardCopy  = new Array(10);
    var i;
    for(i = 0; i < 10; i++)
        boardCopy[i] = [].concat(theBoard[i]);
    return boardCopy;
}
//---------------------------------------------------------------------------------------

function ChooseMove(theBoard, player)
{
    var boardCopy = CloneBoard(theBoard);
        
    var result = new Object();
    var intNumMoves, arrMoveList, intBestMove, intBestScore, i, intCurrScore, intNumEmptySquares
	var blnUseSimpleCount, intSearchDepth, dummy1, dummy2
	
	var squareCount = GetSquareCount(boardCopy);
	var blnUseSimpleCount = ( squareCount.NumEmpty < 8 );
	
	var validMoveList = GetValidMoveList(boardCopy, player);
	intNumMoves = validMoveList.NumValidMoves;
	if(intNumMoves == 0)
	{
	    //Forfeit move.
	    result.Row = -1;
	    result.Score = EvaluatePosition(boardCopy, player, blnUseSimpleCount);
	    return result;
	}
	
	intSearchDepth = (squareCount.NumEmpty > 8) ? 1 : 7;
	intBestScore = -9999;
	
	for(i = 0; i < intNumMoves; i++)
	{
	    intCurrScore = EvaluateMove(boardCopy, player, validMoveList.ValidMoves[0][i], validMoveList.ValidMoves[1][i],
	                                    intSearchDepth, blnUseSimpleCount);
        if(intCurrScore > intBestScore || (intCurrScore == intBestScore && Math.random() < 0.5))
        {
            intBestMove = i;
            intBestScore = intCurrScore;
        }            
	}
	result.Row = validMoveList.ValidMoves[0][intBestMove];
	result.Col = validMoveList.ValidMoves[1][intBestMove];
	result.Score = intBestScore;
	return result;	
}

//---------------------------------------------------------------------------------------

function EvaluateMove(theBoard, player, moveRow, moveCol, searchDepth, blnUseSimpleCount)
{
    var boardCopy = CloneBoard(theBoard);
        
    var opponent = GetOpponent(player);
    boardCopy = ApplyMove(boardCopy, moveRow, moveCol, player);
    
    if(searchDepth > 0)
    {
    	var validReplyList = GetValidMoveList(boardCopy, player);
        var intNumReplies = validReplyList.NumValidMoves;
        if(intNumReplies == 0)        
            //Opponent would have no reply.
            return ChooseMove(boardCopy, player).Score;
        else
        {
            var intBestOpponentScore = -9999;
            var i;
            for(i = 0; i < intNumReplies; i++)
            {
                var intOpponentScore = EvaluateMove(boardCopy, opponent, validReplyList.ValidMoves[0][i], validReplyList.ValidMoves[1][i],
                                                searchDepth - 1, blnUseSimpleCount);
                if(intOpponentScore > intBestOpponentScore)
                    intBestOpponentScore = intOpponentScore;
            }
            return (-1 * intBestOpponentScore);
        }           
    }
    else
        return EvaluatePosition(boardCopy, player, blnUseSimpleCount);
}

//---------------------------------------------------------------------------------------
function EvaluatePosition(theBoard, player, blnUseSimpleCount)
{
	//Returns a score for the position from player's point of view.  High score is better for player, low score is better for opponent.
	var opponent = GetOpponent(player);
    var intScore = 0;
    var intSquareWeight, currRow, currCol, numPlayerSquares = 0, numOpponentSquares = 0;
    if(blnUseSimpleCount)
        intSquareWeight = 1;
        
    for(currRow = 1; currRow <= BOARD_SIZE; currRow++)
        for(currCol = 1; currCol <= BOARD_SIZE; currCol++)
            if(theBoard[currRow][currCol] === player)
            {
                if(!blnUseSimpleCount)
                    intSquareWeight = evalWeight[currRow][currCol];
                intScore += intSquareWeight;
                numPlayerSquares++;
            }
            else if(theBoard[currRow][currCol] == opponent)
            {
                if(!blnUseSimpleCount)
                    intSquareWeight = evalWeight[currRow][currCol];
                intScore -= intSquareWeight;  
                numOpponentSquares++;                  
            }
    if(numOpponentSquares == 0)
       intScore = 9998; //victory 
    else if(numPlayerSquares == 0)
       intScore = -9998; //defeat            
    return intScore;            
}

//---------------------------------------------------------------------------------------

function GetSquareCount(theBoard)
{
    var result = new Object();
    var intNumEmpty = 0, intNumWhite = 0, intNumBlack = 0;
    var currRow, currCol;
    
    for(currRow = 1; currRow <= BOARD_SIZE; currRow++)
        for(currCol = 1; currCol <= BOARD_SIZE; currCol++)       
            switch(theBoard[currRow][currCol])
            {
                case EmptySquare:
                    intNumEmpty++;
                    break;                    
                case WhitePlayer:
                    intNumWhite++;
                    break;                    
                case BlackPlayer:
                    intNumBlack++;
                    break;                    
            }
    
    result.NumWhite = intNumWhite;   
    result.NumBlack = intNumBlack;   
    result.NumEmpty = intNumEmpty;   
    return result;
}