///////////////////////////////////////////////////////////////////////////////
//
//  GarboChess.js
//
// 
// © 2007 Microsoft Corporation. All Rights Reserved.
//
// This file is licensed as part of the Silverlight 1.1 SDK, for details look here: http://go.microsoft.com/fwlink/?LinkID=89145&clcid=0x409
//
///////////////////////////////////////////////////////////////////////////////


var g_debug = true;

function FinishMove(bestMove, value, timeTaken)
{
	var bestMove = bestMove;
	
	if (bestMove != null)
	{
    	MakeMove(bestMove);
    	
    	var encodedMove;
    	
        encodedMove = ((bestMove.start & 0x7) | (bestMove.start & 0x70) >> 1);
        encodedMove |= (((bestMove.end & 0x7) | (bestMove.end & 0x70) >> 1)) << 6;
        
        var flags = bestMove.flags;
        
        if (flags == moveflagEP) flags = 2 << 12;
        else if (flags == moveflagEPC) flags = 2 << 12;
        else if (flags == moveflagCastleQueen) flags = 5 << 12;
        else if (flags == moveflagCastleKing) flags = 4 << 12;
        else if (flags == (moveflagPromotion | moveflagPromoteKnight)) flags = 7 << 12;
        else if (flags == (moveflagPromotion | moveflagPromoteQueen)) flags = 10 << 12;
        else if (flags == (moveflagPromotion | moveflagPromoteBishop)) flags = 8 << 12;
        else if (flags == moveflagPromotion) flags = 9 << 12; // Rook is implicit
        
        encodedMove |= flags;

        g_playerProxy.MoveComplete(encodedMove, g_nodeCount + g_qNodeCount, timeTaken);
	}
	else
	{
//		alert("Checkmate!");
	}
}

function HandleMove(csharpMove)
{
    var from = (csharpMove & 0x7) | ((csharpMove << 1) & 0x70);
    var to = ((csharpMove >> 6) & 0x7) | ((csharpMove >> 5) & 0x70);
    var flags = (csharpMove & 0xF000) >> 12;  
    
    if (flags == 2) flags = moveflagEP;
    else if (flags == 4) flags = moveflagCastleKing;
    else if (flags == 5) flags = moveflagCastleQueen;
    else if (flags == 7) flags = moveflagPromotion | moveflagPromoteKnight;
    else if (flags == 8) flags = moveflagPromotion | moveflagPromoteBishop;
    else if (flags == 9) flags = moveflagPromotion; // rook is implicit
    else if (flags == 10) flags = moveflagPromotion | moveflagPromoteQueen;
        
    var piece = g_board[from];
    var captured = g_board[to];

    if ((piece & 0x7) == piecePawn && to == g_enPassentSquare)
    {
            flags = moveflagEPC;
    }
    
    var move = new Move(from, to, piece, captured, flags);
    
    MakeMove(move);
}

function GetFen()
{
		var result = "";
		for (row = 0; row < 8; row++)
		{
			if (row != 0) result += '/';
			var empty = 0;
			for (col = 0; col < 8; col++)
			{
				var piece = g_board[(row << 4) + col];
				if (piece == 0)
				{
					empty++;
				}
				else
				{
					if (empty != 0) result += empty;
					empty = 0;			
					
                    result += ((piece & colorWhite) == colorWhite) ? "w" : "b";
                    result += (piece >> 4).toString(16).toUpperCase();
                    result += (piece & 0xF).toString(16).toUpperCase();
                }
			}
			if (empty != 0)
			{
				result += empty;
			}
		}

		result += g_toMove == colorBlack ? " b" : " w";
		result += " ";
		if (g_castleRights == 0)
		{
			result += "-";
		}
		else
		{
			if ((g_castleRights & 1) != 0) result += "K";
			if ((g_castleRights & 2) != 0) result += "Q";
			if ((g_castleRights & 4) != 0) result += "k";
			if ((g_castleRights & 8) != 0) result += "q";
		}

        result += " ";

        if (g_enPassentSquare == -1)
        {
            result += '-';
        }
        else
        {
            result += (g_enPassentSquare >> 4);
            result += (g_enPassentSquare & 0xF);
        }

		return result;
}

function FormatMove(move)
{
    var letters = [ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' ];
    var string = letters[move.start & 0xF] + ((7 - (move.start >> 4)) + 1);
    string += letters[move.end & 0xF] + ((7 - (move.end >> 4)) + 1);
    return string;
}

function PVFromHash(move, ply)
{
    if (ply == 0) return "";
    
    var pvString = " " + FormatMove(move);
    MakeMove(move);

    var hashNode = g_hashTable[g_hashKey & g_hashMask];
    if (hashNode != null && hashNode.lock == g_hashKey && hashNode.bestMove != null)
    {
        pvString += PVFromHash(hashNode.bestMove, ply - 1);
    }
       
    UnmakeMove(move);
    
    return pvString;
}

//
// Searching code
//

var g_startTime;
var g_timeout = 166;

var g_nodeCount;
var g_qNodeCount;
var g_searchValid;
var g_validMoveFound;
var g_collisions;

function Search()
{
    var ply = 50;
    var lastEval;
    var alpha = minEval;
    var beta = maxEval;

    g_nodeCount = 0;
    g_qNodeCount = 0;
    g_collisions = 0;
    g_searchValid = true;
    g_validMoveFound = false;
    
    var bestMove;
    var value;

    g_startTime = (new Date()).getTime();

    for (var i = 1; i <= ply && g_searchValid; i++)
    {
        var state = new State();
        var tmp = AlphaBeta(i, alpha, beta);
        if (g_searchValid)
        {
            value = tmp;

            if (value > alpha && value < beta)
            {
                alpha = value - 200;
                beta = value + 200;
            }
            else
            {
                if (alpha != minEval)
                {
                    alpha = minEval;
                    beta = maxEval;
                    i--;
                    continue;
                }
                // else it's a checkmate or mate score
            }

            if (g_hashTable[g_hashKey & g_hashMask] != null)
            {
                bestMove = g_hashTable[g_hashKey & g_hashMask].bestMove;
            }
            else
            {
                break;
            }
            if (bestMove != null) g_validMoveFound = true;
        }
        var state2 = new State(); if (state.CompareTo(state2)) alert("State comparison error: " + state.CompareTo(state2));
    }

    if (bestMove == null)
    {
        // We ran out of time during our search, so go through the valid moves and find the best one
        var moves = GenerateAllMoves();
        var best = minEval;
        for (var i = 0; i < moves.length; i++)
        {
            if (!MakeMove(moves[i]))
            {
                continue;
            }
            if (-g_baseEval >= best)
            {
                best = -g_baseEval;
                bestMove = moves[i];
            }
            UnmakeMove(moves[i]);
        }
    }
    
    g_moveFinishedCallback(bestMove, value, (new Date()).getTime() - g_startTime);
}

var minEval = -2000000;
var maxEval = +2000000;

var materialTable = [ 0, 1000, 3250, 3250, 5000, 9750, 600000 ];
var castledBonus = 300;

var pawnAdj =
    [   0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
      100, 300, 400, 600, 600, 400, 300, 100, /**/  0,0,0,0,0,0,0,0,
       40, 150, 200, 300, 300, 200, 150,  40, /**/  0,0,0,0,0,0,0,0,
       15,  75, 100, 150, 150, 100,  75,  15, /**/  0,0,0,0,0,0,0,0,
       10,  40,  60, 100, 100,  60,  40,  10, /**/  0,0,0,0,0,0,0,0,
        5,  10,  15, -10, -10,  15,  10,   5, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0, -80, -80,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0
     ];

var knightAdj =
    [ -50, -50, -50, -50, -50, -50, -50, -50, /**/  0,0,0,0,0,0,0,0,
      -50,   0,   0,   0,   0,   0,   0, -50, /**/  0,0,0,0,0,0,0,0,
      -50,   0, 120, 120, 120, 120,   0, -50, /**/  0,0,0,0,0,0,0,0,
      -50,   0,  60, 120, 120,  60,   0, -50, /**/  0,0,0,0,0,0,0,0,
      -50,   0,  60, 120, 120,  60,   0, -50, /**/  0,0,0,0,0,0,0,0,
      -50,   0,  60,  60,  60,  60,   0, -50, /**/  0,0,0,0,0,0,0,0,
      -50,   0,   0,   0,   0,   0,   0, -50, /**/  0,0,0,0,0,0,0,0,
      -50, -60, -50, -50, -50, -50, -60, -50, /**/  0,0,0,0,0,0,0,0
     ];

var bishopAdj =
    [   0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,  40,  40,  40,  40,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,  40,  80,  80,  40,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,  40,  80,  80,  40,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,  60,  40,  40,  60,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,  40,   0,   0,   0,   0,  40,   0, /**/  0,0,0,0,0,0,0,0,
       20,   0, -20,   0,   0, -20,   0,  20, /**/  0,0,0,0,0,0,0,0
     ];

var rookAdj =
    [   0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
      100, 100, 100, 100, 100, 100, 100, 100, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
      -10,   0,   0,   0,   0,   0,   0, -10, /**/  0,0,0,0,0,0,0,0
     ];

var kingAdj =
    [   0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
     -800,-800,-800,-800,-800,-800,-800,-800, /**/  0,0,0,0,0,0,0,0,
     -1500,-1500,-1500,-1500,-1500,-1500,-1500,-1500, /**/  0,0,0,0,0,0,0,0,
     -1200,-1200,-1200,-1200,-1200,-1200,-1200,-1200, /**/  0,0,0,0,0,0,0,0,
     -900,-900,-900,-900,-900,-900,-900,-900, /**/  0,0,0,0,0,0,0,0,
     -600,-600,-600,-600,-600,-600,-600,-600, /**/  0,0,0,0,0,0,0,0,
     -300,-300,-300,-300,-300,-300,-300,-300, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0
     ];

var emptyAdj =
    [   0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0,
        0,   0,   0,   0,   0,   0,   0,   0, /**/  0,0,0,0,0,0,0,0
     ];

var pieceSquareAdj = [ [], pawnAdj, knightAdj, bishopAdj, rookAdj, emptyAdj, kingAdj, [] ];

var flipTable =
    [ 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, /**/  0,0,0,0,0,0,0,0,
      0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, /**/  0,0,0,0,0,0,0,0,
      0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, /**/  0,0,0,0,0,0,0,0,
      0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, /**/  0,0,0,0,0,0,0,0,
      0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, /**/  0,0,0,0,0,0,0,0,
      0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, /**/  0,0,0,0,0,0,0,0,
      0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, /**/  0,0,0,0,0,0,0,0,
      0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, /**/  0,0,0,0,0,0,0,0
    ];

function Evaluate()
{
    var curEval = g_baseEval;

	var kingPosTerm = 0;
	// Black queen gone, then cancel white's penalty for king movement
	if (g_pieceList[0x1C] == -1) kingPosTerm -= kingAdj[g_pieceList[0x1F]];
	// White queen gone, then cancel black's penalty for king movement
	if (g_pieceList[0x1D] == -1) kingPosTerm += kingAdj[flipTable[g_pieceList[0x1E]]];

	var bishopPairTerm = 0;
	// Black bishop pair
	if (g_pieceList[0x14] != -1 && g_pieceList[0x16] != -1) bishopPairTerm -= 500;
	// White bishop pair
	if (g_pieceList[0x15] != -1 && g_pieceList[0x17] != -1) bishopPairTerm += 500;

	if (g_toMove == 0)
	{
		curEval -= kingPosTerm;
		curEval -= bishopPairTerm;
	}
	else
	{
		curEval += kingPosTerm;
		curEval += bishopPairTerm;
	}
    
    return curEval;
}

var historyTable = new Array(32);
for (var i = 0; i < 32; i++)
{
    historyTable[i] = new Array(128);
    for (var j = 0; j < 128; j++)
        historyTable[i][j] = 0;
}

var killerMoves = new Array(200);
for (var i = 0; i < 200; i++) killerMoves[i] = new Array(2);

function ScoreMove(move)
{
    var score = 0;
    if (move.captured != pieceEmpty)
    {
        var victim = materialTable[move.captured & 0x7];
        var attacker = materialTable[move.piece & 0x7];
        if (victim > attacker) score += 5000;
        score += victim - attacker / 10;
    }
    score += historyTable[move.piece >> 3][move.end];
    return score;
}

function Comp(a, b)
{
    return b.score - a.score;
}

function QSearch(alpha, beta)
{
    if ((g_qNodeCount & 15) == 15)
    {
        if ((new Date()).getTime() - g_startTime > g_timeout)
        {
            // Time cutoff
            g_searchValid = false;
            return alpha;
        }
    }

    var realEval = g_baseEval;

    if (realEval >= beta)
        return g_baseEval;

    if (realEval > alpha)
        alpha = g_baseEval;

    g_qNodeCount++;

    var moves = GenerateAllMoves();
    var ourKingPiece = 0x1E | (g_toMove >> 3);

    for (var i = moves.length - 1; i >= 0; i--)
    {
        if (moves[i].captured != pieceEmpty)
        {
            moves[i].score = materialTable[moves[i].captured & 0x7] - (materialTable[moves[i].piece & 0x7] / 10);
        }
        else
        {
            moves[i].score = -5000000;
        }
    }
    moves.sort(Comp);

    for (var i = 0; i < moves.length; i++)
    {
        if (moves[i].captured == pieceEmpty)
            break;

        if (!MakeMove(moves[i]))
        {
            continue;
        }

        var value;

/*        // Super simple SEE implementation
        if (IsSquareAttackable(moves[i].end, g_toMove))
        {
            value = -g_baseEval - materialTable[moves[i].piece & 0x7];
        }
        else
        {*/
            value = -QSearch(-beta, -alpha);
        // }
        
        UnmakeMove(moves[i]);

        if (value > realEval)
        {
            if (value >= beta)
                return value;
        
            if (value > alpha)
                alpha = value;
                
            realEval = value;
        }
    }

    return realEval;
}

function StoreHash(value, flags, ply, move)
{
//    var hashNode = g_hashTable[g_hashKey & g_hashMask];
//    if (hashNode != null && hashNode.ply > ply) return;
    g_hashTable[g_hashKey & g_hashMask] = new HashEntry(g_hashKey, value, flags, ply, move);
}

function AlphaBeta(ply, alpha, beta)
{ 
    if ((g_nodeCount & 3) == 3)
    {
        if ((new Date()).getTime() - g_startTime > g_timeout)
        {
            // Time cutoff
            g_searchValid = false;
            return alpha;
        }
    }

    g_nodeCount++;

    var hashMove = null;
    var hashFlag = hashflagAlpha;
    var hashNode = g_hashTable[g_hashKey & g_hashMask];
    if (hashNode != null && hashNode.lock == g_hashKey)
    {
        hashMove = hashNode.bestMove;
        if (hashNode.depth >= ply)
        {
            if (hashNode.flags == hashflagExact)
                return hashNode.value;
            if (hashNode.flags == hashflagAlpha && hashNode.value <= alpha)
                return alpha;
            if (hashNode.flags == hashflagBeta && hashNode.value >= beta)
                return beta;
        }
    }

    var ourKingPiece = 0x1E | (g_toMove >> 3);
    var inCheck = IsSquareAttackable(g_pieceList[ourKingPiece], 8 - g_toMove);

    if (ply <= 0 && !inCheck)
    {
        var value = QSearch(alpha, beta);
        if (!g_searchValid)
        {
            return alpha;
        }
        
        StoreHash(value, value <= alpha ? hashflagAlpha : (value >= beta ? hashflagBeta : hashflagExact), ply, null);
        return value;
    }

    if (!inCheck && ply >= 3)
    {
        // Try null move
        g_toMove = 8 - g_toMove;
        g_baseEval = -g_baseEval;
        SetHash();
        var value = -AlphaBeta(ply - 3, -beta, -beta + 1);
        g_toMove = 8 - g_toMove;
        g_baseEval = -g_baseEval;
        SetHash();
        if (value >= beta)
            return beta;
    }

    var moves = GenerateAllMoves();
    var moveMade = false;

    // Move ordering
    for (var i = moves.length - 1; i >= 0; i--)
    {
        moves[i].score = ScoreMove(moves[i]);
        if (hashMove != null && moves[i].start == hashMove.start && moves[i].end == hashMove.end && moves[i].flags == hashMove.flags)
        {
            moves[i].score += 10000000;
        }
    }
    moves.sort(Comp);

    var realEval = minEval;
    for (var i = 0; i < moves.length; i++)
    {
        var plyToSearch = ply - 1;

//        var state = new State();
        if (!MakeMove(moves[i]))
        {
//            var state2 = new State(); if (state.CompareTo(state2)) alert(FormatMove(moves[i]) + "," + moves[i].piece + "," + moves[i].captured + "," + moves[i].flags + "," + state.CompareTo(state2));
            continue;
        }


        if (inCheck)
        {
            // Check extensions
            plyToSearch++;
        }
/*        else
        {
            // Futility pruning
            if (moves[i].captured == pieceEmpty)
            {
                if ((plyToSearch == 0 && g_baseEval + 2000 < alpha) ||
                    (plyToSearch == 1 && g_baseEval + 4000 < alpha))
                {
                    UnmakeMove(moves[i]);
                    continue;
                }
            }
        }*/

        var value;
        // PVS disabled for now
/*        if (!moveMade)
        {*/
            value = -AlphaBeta(plyToSearch, -beta, -alpha);
/*        }
        else
        {
            value = -AlphaBeta(plyToSearch, -alpha - 1, -alpha);
            if (alpha < eval && eval < beta)
            {
                value = -AlphaBeta(plyToSearch, -beta, -alpha);
            }
        }*/

        moveMade = true;

        UnmakeMove(moves[i]);

        if (!g_searchValid)
        {
            return alpha;
        }

//        var state2 = new State(); if (state.CompareTo(state2)) alert(FormatMove(moves[i]) + "," + moves[i].piece + "," + moves[i].captured + "," + moves[i].flags + "," + state.CompareTo(state2));

        if (value > realEval)
        {
            if (value >= beta)
            {
                historyTable[moves[i].piece >> 3][moves[i].end] += ply * 3 + 3;
                StoreHash(value, hashflagBeta, ply, moves[i]);
                return value;
            }

            if (value > alpha)
            {
                historyTable[moves[i].piece >> 3][moves[i].end] += ply;
                hashFlag = hashflagExact;
                alpha = value;
            }
            
            realEval = value;
            hashMove = moves[i];
        }
    }

    if (!moveMade)
    {
        // If we have no valid moves it's either stalemate or checkmate
        if (inCheck)
            // Checkmate.
            return minEval;
        else
            // Stalemate
            return 0;
    }

    StoreHash(realEval, hashFlag, ply, hashMove);

    return realEval;
}

// 
// Board code
//

var colorBlack  = 0x00;
var colorWhite  = 0x08;

var pieceEmpty  = 0x00;
var piecePawn   = 0x01;
var pieceKnight = 0x02;
var pieceBishop = 0x03;
var pieceRook   = 0x04;
var pieceQueen  = 0x05;
var pieceKing   = 0x06;

var g_vectorDelta = new Array(256);

var g_bishopDeltas = [ -15, -17, 15, 17 ];
var g_knightDeltas = [ 31, 33, 14, -14, -31, -33, 18, -18 ];
var g_rookDeltas = [ -1, +1, -16, +16];
var g_queenDeltas = [ -1, +1, -15, +15, -17, +17, -16, +16 ];

var g_castleRightsMask =
    [   7,  15,  15,  15,   3,  15,  15,  11, /**/  0,0,0,0,0,0,0,0,
       15,  15,  15,  15,  15,  15,  15,  15, /**/  0,0,0,0,0,0,0,0,
       15,  15,  15,  15,  15,  15,  15,  15, /**/  0,0,0,0,0,0,0,0,
       15,  15,  15,  15,  15,  15,  15,  15, /**/  0,0,0,0,0,0,0,0,
       15,  15,  15,  15,  15,  15,  15,  15, /**/  0,0,0,0,0,0,0,0,
       15,  15,  15,  15,  15,  15,  15,  15, /**/  0,0,0,0,0,0,0,0,
       15,  15,  15,  15,  15,  15,  15,  15, /**/  0,0,0,0,0,0,0,0,
       13,  15,  15,  15,  12,  15,  15,  14, /**/  0,0,0,0,0,0,0,0
     ];

var moveflagEP = 0x1;
var moveflagEPC = 0x2;
var moveflagCastleKing = 0x4;
var moveflagCastleQueen = 0x8;
var moveflagPromotion = 0x10;
var moveflagPromoteKnight = 0x20;
var moveflagPromoteQueen = 0x40;
var moveflagPromoteBishop = 0x80;

function getRandomInt() {
  return Math.floor(Math.random() * 0xFFFFFFFF) + Math.floor(Math.random() + 0.5);
}
function getRandomLong() {
    return Math.floor(getRandomInt() * getRandomInt() / 10000 + getRandomInt());
}

// Position variables
var g_board = new Array(128);
var g_pieceList = new Array(32);
var g_toMove; // side to move, 0 or 8
var g_castleRights; // bitmask representing castling rights, 1 = wk, 2 = wq, 4 = bk, 8 = bq
var g_enPassentSquare;
var g_baseEval;
var g_hashKey;
var g_inCheck;

// Utility variables
var g_moveCount = 0;
var g_moveUndoStack = new Array();

var g_hashSize = 1 << 18;
var g_hashMask = g_hashSize - 1;
var g_hashTable;

var g_zobrist;
var g_zobristBlack;

function State()
{
    this.board = new Array(128);
    for (var i = 0; i < 128; i++) this.board[i] = g_board[i];
    this.pieceList = new Array(32);
    for (var i = 0; i < 32; i++) this.pieceList[i] = g_pieceList[i];
    this.toMove = g_toMove;
    this.castleRights = g_castleRights;
    this.enPassentSquare = g_enPassentSquare;
    this.baseEval = g_baseEval;
    this.hashKey = g_hashKey;
}

State.prototype.CompareTo = function(other)
{
    for (var i = 0; i < 128; i++)
        if (this.board[i] != other.board[i]) return 1;
    for (var i = 0; i < 32; i++)
        if (this.pieceList[i] != other.pieceList[i]) return 2;
    if (this.toMove != other.toMove) return 3;
    if (this.castleRights != other.castleRights) return 4;
    if (this.enPassentSquare != other.enPassentSquare) return 5;
    if (this.baseEval != other.baseEval) return 6;
    if (this.hashKey != other.hashKey) return 7;
    return 0;
}

var hashflagAlpha = 1;
var hashflagBeta = 2;
var hashflagExact = 3;

function HashEntry(lock, value, flags, depth, bestMove)
{
    this.lock = lock;
    this.value = value;
    this.flags = flags;
    this.depth = depth;
    this.bestMove = bestMove;
}

function ResetGame()
{
    g_hashTable = new Array(g_hashSize);

    g_zobrist = new Array(128);
    for (var i = 0; i < 128; i++)
    {
        g_zobrist[i] = new Array(16);
        for (var j = 0; j < 16; j++)
        {
            g_zobrist[i][j] = getRandomLong();
        }
    }
    g_zobristBlack = getRandomLong();

    var pieceDeltas = [ [], [], g_knightDeltas, g_bishopDeltas, g_rookDeltas, g_queenDeltas, g_queenDeltas ];
    
    for (var i = 0; i < 256; i++)
    {
        g_vectorDelta[i] = new Object();
        g_vectorDelta[i].delta = 0;
        g_vectorDelta[i].pieceMask = new Array(2);
        g_vectorDelta[i].pieceMask[colorBlack >> 3] = 0;
        g_vectorDelta[i].pieceMask[colorWhite >> 3] = 0;
    }
    
    // Initialize the vector delta table    
    for (var row = 0; row < 0x80; row += 0x10)
        for (var col = 0; col < 0x8; col++)
        {
            var square = row | col;
            
            // Pawn moves
            var index = square - (square - 17) + 128;
            g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << piecePawn);
            index = square - (square - 15) + 128;
            g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << piecePawn);

            index = square - (square + 17) + 128;
            g_vectorDelta[index].pieceMask[colorBlack >> 3] |= (1 << piecePawn);
            index = square - (square + 15) + 128;
            g_vectorDelta[index].pieceMask[colorBlack >> 3] |= (1 << piecePawn);

            for (var i = pieceKnight; i <= pieceKing; i++)
            {
                for (var dir = 0; dir < pieceDeltas[i].length; dir++)
                {
                    var target = square + pieceDeltas[i][dir];
                    while (!(target & 0x88))
                    {
                        index = square - target + 128;
                        
                        g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << i);
                        g_vectorDelta[index].pieceMask[colorBlack >> 3] |= (1 << i);
                        
                        var flip = -1;
                        if (square < target) flip = 1;

                        if ((square & 0xF0) == (target & 0xF0))
                        {
                            // On the same row
                            g_vectorDelta[index].delta = flip * 1;
                        }
                        else if ((square & 0x0F) == (target & 0x0F))
                        {
                            // On the same column
                            g_vectorDelta[index].delta = flip * 16;
                        }
                        else if ((square % 15) == (target % 15))
                        {
                            g_vectorDelta[index].delta = flip * 15;
                        }
                        else if ((square % 17) == (target % 17))
                        {
                            g_vectorDelta[index].delta = flip * 17;
                        }
                        
                        if ((i == pieceKnight) || (i == pieceKing)) break;
                        target += pieceDeltas[i][dir];
                    }
                }
            }
        }

    ResetBoard();
}

function ResetBoard()
{
    g_toMove = colorWhite;
    g_baseEval = 0;

    g_enPassentSquare = -1;

    g_castleRights = 0xF;
    
    g_moveCount = 0;
    g_inCheck = false;
    
    for (var i = 0; i < 128; i++) g_board[i] = pieceEmpty;
 
    for (var i = 0; i < 5000; i++)
    {
        g_moveUndoStack[i] = new Object();
    }

    for (var i = 0; i < 8; i++)
    {
        g_board[0x10 | i] = colorBlack | piecePawn | (i << 4);
        g_board[0x60 | i] = colorWhite | piecePawn | (i << 4);
    }

    g_board[0x00] = colorBlack | pieceRook | 0xC0;
    g_board[0x07] = colorBlack | pieceRook | 0xD0;
    g_board[0x01] = colorBlack | pieceKnight | 0x80;
    g_board[0x06] = colorBlack | pieceKnight | 0x90;
    g_board[0x02] = colorBlack | pieceBishop | 0xA0;
    g_board[0x05] = colorBlack | pieceBishop | 0xB0;
    g_board[0x03] = colorBlack | pieceQueen | 0xE0;
    g_board[0x04] = colorBlack | pieceKing | 0xF0;

    g_board[0x70] = colorWhite | pieceRook | 0xC0;
    g_board[0x77] = colorWhite | pieceRook | 0xD0;
    g_board[0x71] = colorWhite | pieceKnight | 0x80;
    g_board[0x76] = colorWhite | pieceKnight | 0x90;
    g_board[0x72] = colorWhite | pieceBishop | 0xA0;
    g_board[0x75] = colorWhite | pieceBishop | 0xB0;
    g_board[0x73] = colorWhite | pieceQueen | 0xE0;
    g_board[0x74] = colorWhite | pieceKing | 0xF0;
    
    for (var i = 0; i < 32; i++) g_pieceList[i] = -1;
    
    for (var i = 0; i < 128; i++)
    {
        if (g_board[i] != pieceEmpty)
        {
            g_pieceList[g_board[i] >> 3] = i;
        }
    }

    SetHash();
}

function SetHash()
{
    g_hashKey = 0;

    for (var i = 31; i >= 0; i--)
    {
        var square = g_pieceList[i];
        if (square != -1)
        {
            g_hashKey += g_zobrist[square][g_board[square] & 0xF];
        }
    }

    if (!g_toMove) g_hashKey += g_zobristBlack;
}

function InitializeFromFen(fen)
{
	var chunks = fen.split(' ');

    for (var i = 0; i < 128; i++) g_board[i] = pieceEmpty;

    for (var i = 0; i < 5000; i++)
    {
        g_moveUndoStack[i] = new Object();
    }

	var row = 0;
	var col = 0;

    var pieces = chunks[0];
    for (var i = 0; i < pieces.length; i++)
	{
        var c = pieces.charAt(i);

		if (c == '/')
		{
			row++;
			col = 0;
		}
		else
		{
			if (c >= '0' && c <= '9')
			{
				col += c - '0';
			}
			else
			{
				var piece = 0;

                if (c == 'w') piece |= colorWhite;

                i++; // Skip letter
                pieceString = pieces.substr(i,2);
                i++
/*                c = pieces.charAt(++i);
                var pieceType = parseInt(c, 16);
                var pieceCode = [ 0x1, 0x11, 0x21, 0x31, 0x41, 0x51, 0x61, 0x71, 0x82, 0x92, 0xA3, 0xB3, 0xC4, 0xD4, 0xE5, 0xF6 ];

                piece |= pieceCode[pieceType];                      */
                piece = parseInt(pieceString, 16);
                
				g_board[(row * 0x10) + col] = piece;

				col++;
			}
		}
	}

    for (var i = 0; i < 32; i++) g_pieceList[i] = -1;

    for (var i = 0; i < 128; i++)
    {
        if (g_board[i] != pieceEmpty)
        {
            g_pieceList[g_board[i] >> 3] = i;
        }
    }

    g_toMove = chunks[1].charAt(0) == 'w' ? colorWhite : colorBlack;
   
	g_castleRights = 0;
	if (chunks[2].indexOf('K') != -1) g_castleRights |= 1;
	if (chunks[2].indexOf('Q') != -1) g_castleRights |= 2;
	if (chunks[2].indexOf('k') != -1) g_castleRights |= 4;
	if (chunks[2].indexOf('q') != -1) g_castleRights |= 8;

	g_enPassentSquare = -1;
	if (chunks[3].indexOf('-') == -1)
	{
		g_enPassentSquare = parseInt(chunks[3],16);
	}

    SetHash();
}

function MakeMove(move)
{
    var otherColor = 8 - g_toMove;
    var me = g_toMove >> 3;
    var them = otherColor >> 3;

    g_moveUndoStack[g_moveCount].ep = g_enPassentSquare;
    g_moveUndoStack[g_moveCount].castleRights = g_castleRights;
    g_moveUndoStack[g_moveCount].inCheck = g_inCheck;
    g_moveUndoStack[g_moveCount].baseEval = g_baseEval;
    g_moveUndoStack[g_moveCount].hashKey = g_hashKey;
    g_moveCount++;

    g_enPassentSquare = -1;
    
    var epcEnd = move.end;

    if (move.flags)
    {
        if (move.flags & moveflagEP)
        {
            if (g_toMove == colorWhite)
                g_enPassentSquare = move.end + 0x10;
            else
                g_enPassentSquare = move.end - 0x10;
        }
        else if (move.flags & moveflagEPC)
        {
            epcEnd = move.end - 0x10;
            if (g_toMove == colorWhite) epcEnd = move.end + 0x10;
            g_board[epcEnd] = pieceEmpty;
        }
        else if (move.flags & moveflagCastleKing)
        {
			if (IsSquareAttackable(move.start + 1, otherColor) ||
				IsSquareAttackable(move.start + 2, otherColor))
			{
				g_moveCount--;
				return false;
			}

            g_board[move.end - 1] = g_board[move.end + 1];
            g_board[move.end + 1] = pieceEmpty;

            var piece = g_board[move.end - 1];

            g_baseEval -= pieceSquareAdj[piece & 0x7][me == 0 ? flipTable[move.end + 1] : (move.end + 1)];
            g_baseEval += pieceSquareAdj[piece & 0x7][me == 0 ? flipTable[move.end - 1] : (move.end - 1)];
            
            g_baseEval += castledBonus;
            
            g_pieceList[piece >> 3] = move.end - 1;
        }
        else if (move.flags & moveflagCastleQueen)
        {
			if (IsSquareAttackable(move.start - 1, otherColor) ||
				IsSquareAttackable(move.start - 2, otherColor))
			{
				g_moveCount--;
				return false;
			}

            g_board[move.end + 1] = g_board[move.end - 2];
            g_board[move.end - 2] = pieceEmpty;
            
            var piece = g_board[move.end + 1];

            g_baseEval -= pieceSquareAdj[piece & 0x7][me == 0 ? flipTable[move.end - 2] : (move.end - 2)];
            g_baseEval += pieceSquareAdj[piece & 0x7][me == 0 ? flipTable[move.end + 1] : (move.end + 1)];
            
            g_baseEval += castledBonus;

            g_pieceList[piece >> 3] = move.end + 1;
        }
    }

//    this.boardHash ^= this.zobrist[move.start][this.board[move.start]];
    //this.boardHash ^= this.zobrist[move.end][this.board[move.end]];

	g_castleRights &= g_castleRightsMask[move.start] & g_castleRightsMask[move.end];

    g_baseEval -= pieceSquareAdj[move.piece & 0x7][me == 0 ? flipTable[move.start] : move.start];

    if (move.flags & moveflagPromotion)
    {
        var newPiece = move.piece & (~0x7);
        if (move.flags & moveflagPromoteKnight) newPiece |= pieceKnight;
        else if (move.flags & moveflagPromoteQueen) newPiece |= pieceQueen;
        else if (move.flags & moveflagPromoteBishop) newPiece |= pieceBishop;
        else newPiece |= pieceRook;
        
        g_board[move.end] = newPiece;

        g_baseEval += pieceSquareAdj[newPiece & 0x7][me == 0 ? flipTable[move.end] : move.end];
        g_baseEval -= materialTable[piecePawn];
        g_baseEval += materialTable[newPiece & 0x7];
    }
    else
    {
        g_board[move.end] = g_board[move.start];

        g_baseEval += pieceSquareAdj[move.piece & 0x7][me == 0 ? flipTable[move.end] : move.end];
    }
    g_board[move.start] = pieceEmpty;
    
    g_pieceList[move.piece >> 3] = move.end;
    
    if (move.captured)
    {
        g_pieceList[move.captured >> 3] = -1;

        g_baseEval += materialTable[move.captured & 0x7];
        g_baseEval += pieceSquareAdj[move.captured & 0x7][them == 0 ? flipTable[epcEnd] : epcEnd];
    }

    g_toMove = otherColor;
    g_baseEval = -g_baseEval;
    
    if ((move.piece & 0x7) == pieceKing || g_inCheck)
    {
		if (IsSquareAttackable(g_pieceList[0x1E | me], otherColor))
		{
			UnmakeMove(move);
			return false;
		}
    }
    else
    {
		var kingPos = g_pieceList[0x1E | me];

		if (ExposesCheck(move.start, kingPos))
		{
			UnmakeMove(move);
			return false;
		}

		if (epcEnd != move.end)
		{
			if (ExposesCheck(epcEnd, kingPos))
			{
				UnmakeMove(move);
				return false;
			}
		}
    }

    g_inCheck = false;

    if (move.flags == 0 || move.flags == moveflagEP || move.flags == moveflagEPC)
    {
        var theirKingPos = g_pieceList[0x1E | them];

		// First check if the piece we moved can attack the enemy king
		g_inCheck = IsSquareAttackableFrom(theirKingPos, move.end);

		if (!g_inCheck)
		{
			// Now check if the square we moved from exposes check on the enemy king
			g_inCheck = ExposesCheck(move.start, theirKingPos);

			if (!g_inCheck)
			{
				// Finally, ep. capture can cause another square to be exposed
				if (epcEnd != move.end)
				{
					g_inCheck = ExposesCheck(epcEnd, theirKingPos);
				}
			}
		}
    }
    else
    {
        // Castle or promotion, slow check
        var ourKingPiece = 0x1E | (g_toMove >> 3);
        g_inCheck = IsSquareAttackable(g_pieceList[ourKingPiece], 8 - g_toMove);
    }
    
    SetHash();
    return true;
}

function UnmakeMove(move)
{
    g_toMove = 8 - g_toMove;
    g_baseEval = -g_baseEval;

//    this.boardHash ^= this.zobrist[move.end][this.board[move.end]];

    g_moveCount--;
    g_enPassentSquare = g_moveUndoStack[g_moveCount].ep;
    g_castleRights = g_moveUndoStack[g_moveCount].castleRights;
    g_inCheck = g_moveUndoStack[g_moveCount].inCheck;
    g_baseEval = g_moveUndoStack[g_moveCount].baseEval;
    g_hashKey = g_moveUndoStack[g_moveCount].hashKey;

    var otherColor = 8 - g_toMove;
    var me = g_toMove >> 3;
    var them = otherColor >> 3;

    if (move.flags)
    {
        if (move.flags & moveflagCastleKing)
        {
            g_board[move.end + 1] = g_board[move.end - 1];
            g_board[move.end - 1] = pieceEmpty;
            
            var piece = g_board[move.end + 1];
            
            g_pieceList[piece >> 3] = move.end + 1;
        }
        else if (move.flags & moveflagCastleQueen)
        {
            g_board[move.end - 2] = g_board[move.end + 1];
            g_board[move.end + 1] = pieceEmpty;
            
            var piece = g_board[move.end - 2];
            
            g_pieceList[piece >> 3] = move.end - 2;
        }
    }

    if (move.flags & moveflagPromotion)
    {
        g_board[move.start] = (g_board[move.end] & (~0x7)) | piecePawn;
    }
    else
    {
        g_board[move.start] = g_board[move.end];
    }

    var epcEnd = move.end;
    if (move.flags & moveflagEPC)
    {
        epcEnd = move.end - 0x10;
        if (g_toMove == colorWhite) epcEnd = move.end + 0x10;
        g_board[move.end] = pieceEmpty;
    }

    g_board[epcEnd] = move.captured;

    g_pieceList[move.piece >> 3] = move.start;

    if (move.captured)
    {
        g_pieceList[move.captured >> 3] = epcEnd;
    }
}

function ExposesCheck(from, kingPos)
{
	var index = kingPos - from + 128;
	// If a queen can't reach it, nobody can!
	if ((g_vectorDelta[index].pieceMask[0] & (1 << (pieceQueen))) != 0)
	{
		var king = g_board[kingPos];
		var delta = g_vectorDelta[index].delta;
		for (var pos = kingPos + delta;
			 ((pos & 0x88) == 0);
			 pos += delta)
		{
			if (pos == from)
			{
				continue;
			}

			var piece = g_board[pos];
			if (piece != 0)
			{
				if (((piece ^ king) & 0x8) != 0)
				{
					// Now see if the piece can actually attack the king
					var backwardIndex = pos - kingPos + 128;
					return (g_vectorDelta[backwardIndex].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) != 0;
				}
				else
				{
					return false;
				}
			}
		}
	}
    return false;
}

function IsSquareAttackableFrom(target, from)
{
    var index = from - target + 128;
    var piece = g_board[from];
    if (g_vectorDelta[index].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7)))
    {
        // Yes, this square is attackable
        if ((piece & 0x7) == pieceKnight)
            return true;
        
        from += g_vectorDelta[index].delta;
        while (from != target)
        {
            if (g_board[from] != pieceEmpty) break;
            from += g_vectorDelta[index].delta;
        }
        
        if (from == target)
        {
            return true;
        }
    }
    
    return false;
}

function IsSquareAttackable(target, color)
{
    color >>= 3;
    for (var i = 30 | color; i >= 0; i -= 2)
    {
        var square = g_pieceList[i];
        if (square != -1 &&
            IsSquareAttackableFrom(target, square))
        {
            return true;
        }
    }
    return false;
}

function FindPiece(piece)
{
    for (var row = 0; row < 0x80; row += 0x10)
        for (var col = 0; col < 0x8; col++)
        {
            var square = row | col;
            if (g_board[square] == piece)
                return square;
        }    
}

function GenerateValidMoves()
{
    var moveList = new Array();
    var allMoves = GenerateAllMoves();

    // Find our king
    var toMove = g_toMove;
    var ourKingPiece = 0x1E | (g_toMove >> 3);

    for (var i = allMoves.length - 1; i >= 0; i--)
    {
        if (MakeMove(allMoves[i]))
        {
            moveList[moveList.length] = allMoves[i];
            UnmakeMove(allMoves[i]);
        }
    }
    
    return moveList;
}

function GenerateAllMoves()
{
    var moveStack = new Array();
    for (var i = 30 | (g_toMove >> 3); i >= 0; i -= 2)
    {
        var square = g_pieceList[i];
        if (square != -1)
        {
            var piece = g_board[square];
			switch (piece & 0x7)
			{
			case piecePawn: GeneratePawnMoves(moveStack, square); break;
			case pieceKnight: GenerateDirectionalMoves(moveStack, square, true, g_knightDeltas); break;
			case pieceBishop: GenerateDirectionalMoves(moveStack, square, false, g_bishopDeltas); break;
			case pieceRook: GenerateDirectionalMoves(moveStack, square, false, g_rookDeltas); break;
			case pieceQueen: GenerateDirectionalMoves(moveStack, square, false, g_queenDeltas); break;
			case pieceKing:
			    if (!g_inCheck)
			    {
    			    var castleRights = g_castleRights;
	    		    if (!g_toMove) castleRights >>= 2;
		    	    if (castleRights & 1)
    			    {
	    		        // Kingside castle
		    	        if (g_board[square + 1] == pieceEmpty && g_board[square + 2] == pieceEmpty)
    			        {
       			            moveStack[moveStack.length] = new Move(square, square + 0x02, piece, pieceEmpty, moveflagCastleKing);
			            }
			        }
    			    if (castleRights & 2)
	    		    {
		    	        // Queenside castle
			            if (g_board[square - 1] == pieceEmpty && g_board[square - 2] == pieceEmpty && g_board[square - 3] == pieceEmpty)
			            {
       		    	        moveStack[moveStack.length] = new Move(square, square - 0x02, piece, pieceEmpty, moveflagCastleQueen);
        			    }
        			}
        	    }
				GenerateDirectionalMoves(moveStack, square, true, g_queenDeltas);
				break;
			}
	    }
	}
           
    return moveStack;
}

function GenerateDirectionalMoves(moveStack, start, onlyCheckFirst, deltas)
{
    var startPiece = g_board[start];
    for (var i = deltas.length - 1; i >= 0; i--)
    {
        var pos = start + deltas[i];
        while (!(pos & 0x88))
        {
            var piece = g_board[pos];
            if (piece == pieceEmpty)
            {
                moveStack[moveStack.length] = new Move(start, pos, startPiece, pieceEmpty, 0);
            }
            else
            {
                // Opposite colors
                if ((piece ^ startPiece) & 0x8)
                {
                    moveStack[moveStack.length] = new Move(start, pos, startPiece, piece, 0);
                }
                break;
            }
            
            if (onlyCheckFirst) break;
            pos += deltas[i];
        }
    }
}

function MovePawnTo(moveStack, start, square, piece, captured)
{
    if (((square & 0x70) == 0x70) || ((square & 0x70) == 0x00))
    {
        moveStack[moveStack.length] = new Move(start, square, piece, captured, moveflagPromotion | moveflagPromoteQueen);
        moveStack[moveStack.length] = new Move(start, square, piece, captured, moveflagPromotion | moveflagPromoteKnight);
        moveStack[moveStack.length] = new Move(start, square, piece, captured, moveflagPromotion | moveflagPromoteBishop);
        moveStack[moveStack.length] = new Move(start, square, piece, captured, moveflagPromotion);
    }
    else
    {
        moveStack[moveStack.length] = new Move(start, square, piece, captured, 0);
    }
}

function GeneratePawnMoves(moveStack, start)
{
    var piece = g_board[start];
    var color = piece & colorWhite;
    var inc = 16;
    if (color == colorWhite) inc = -16;
    
    var end = start + inc;

    // If a pawn is on the home rank, then it can jump two squares
    if ((((start & 0x70) == 0x10) && (color == colorBlack)) ||
        (((start & 0x70) == 0x60) && (color == colorWhite)))
    {
        // 2 square jump
        if (g_board[end] == pieceEmpty &&
            g_board[end + inc] == pieceEmpty)
        {
            moveStack[moveStack.length] = new Move(start, end + inc, piece, pieceEmpty, moveflagEP);
        }
    }
    
    // Can the pawn capture?
    for (var cInc = -1; cInc <= 1; cInc += 2)
    {
        var square = end + cInc;
        if (!(square & 0x88))
        {
            var targetPiece = g_board[square];
            if (targetPiece != pieceEmpty)
            {
                // Colors different?
                if ((targetPiece ^ color) & 0x8)
                {
                    MovePawnTo(moveStack, start, square, piece, targetPiece);
                }
            }
            else if (square == g_enPassentSquare)
            {
                moveStack[moveStack.length] = new Move(start, square, piece, g_board[start + cInc], moveflagEPC);
            }
        }
    }

    // Normal forward move
    if (g_board[end] == pieceEmpty)
    {
        MovePawnTo(moveStack, start, end, piece, pieceEmpty);
    }
}

function Move(start, end, piece, captured, flags)
{
    this.start = start;
    this.end = end;
    this.piece = piece;
    this.captured = captured;
    
    this.flags = flags;
}

/******************************************************************************
 * WPF/E UTILITY CODE
 *****************************************************************************/

/******************************************************************************
 * Helper method for creating per-object callbacks
 * @param target object to invoke the callback on
 * @param callback method to be called on the object
 *****************************************************************************/
function delegate(target, callback) {
	var func = function() {
		callback.apply(target, arguments);
	}
	return func;
}

/******************************************************************************
 * Hook up the specified event to the specified delegate.
 * Allows javascript delegates to be used and dynamically
 * creates the global method.
 * @param target WPF/e element to set the event on
 * @param eventName name of the event to set, ie "MouseEnter"
 * @param delegate function to call when the event occurs.
 *****************************************************************************/
function setCallback(target, eventName, delegate) {
	if (!window.methodID)
		window.methodID = 0;
	
	var callbackName = "uniqueCallback" + (window.methodID++);
	eval(callbackName + " = delegate;");
	
	target.AddEventListener(eventName, "javascript:" + callbackName);
}