// JavaScript Othello Game
// Copyright (c) 2000, 2001 Kelly Yancey <kbyanc@posi.net>
// All rights reserved.
//
// Redistribution and use in source form, with or without modification, is
// permitted provided that the following conditions are met:
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer,
//    without modification, immediately at the beginning of the file.
// 2. All advertising materials mentioning features or use of this software
//    must display the following acknowledgement:
//      This product includes software developed by Kelly Yancey     
//    and a reference to the URL http://www.posi.net/software/othello/
// 3. The name of the author may not be used to endorse or promote products
//    derived from this software without specific prior written permission.
//    
// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  
// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT  
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// picture numbers
var	EMPTY = 0;		// empty square
var	WHITE = 1;		// white piece
var	BLACK = 2;		// black piece
var	WHITETRANS = 3;		// white transparent cursor piece
var	BLACKTRANS = 4;		// black transparent cursor piece
var	NUMBASE = 5;		// beginning of numeric pictures

// size of the pictures used to represent pieces (all pictures must be the same size)
var	piecewidth = 42;
var	pieceheight = 42;

// size of the board
var	width = 8;
var	height = 8;

// player settings
var	human = BLACK;
var	showcursor = true;	// display cursor showing user where they can go
var	showflips = false;	// display counts showing how many pieces they can flip by putting a piece in a given square

// AI settings
var	weightsquares = 1;	// whether AI prefers squares that yield higher flip counts
var	edgesensitive = 1;	// whether AI is sensitive to the importance of edge squares

// user-supplied expression to evaluate at the end of each round.
var	roundhook = "";

// some internal global variables
var	picture = new Array();
var	board = new Array(width);
var	score = new Array();
var	turn = BLACK;
var	AI_timerID;


var     lastlookup = 0;
function lookup(name) {
// routine to get image number by name
// optimized for the case where we lookup successive images
    for(i = lastlookup; i < document.images.length; i++)
        if(document.images[i].name == name) { lastlookup = i; return(i); }
    for(i = 0; i < lastlookup; i++)
        if(document.images[i].name == name) { lastlookup = i; return(i); }
    return(-1);
}

function piece(imagename) {
// object definition for 'piece' type
    this.imagenum = lookup(imagename);
    this.player = EMPTY;
    // how many pieces each player could flip by taking this square
    this.flips = new Array();
    this.flips[WHITE] = 0;
    this.flips[BLACK] = 0;
    // how valuable this location is to each player
    this.value = new Array();
    this.value[WHITE] = 0;
    this.value[BLACK] = 0;
}

function LoadPieceImage(picnum, pictureURL) {
// routine to associated the given picture with a picture number.
    picture[picnum] = new Image();
    picture[picnum].src = pictureURL;
}

function SetPieceImage(x, y, src) {
// routine to set the image associated with the given piece
    if(document.images[board[x][y].imagenum].src != src) {
	// we explicitely check to see if we are changing the image source to prevent
	// unnecessary redrawing of images which do not change
	document.images[board[x][y].imagenum].src = src;
    }
}

function InitializeBoard(color) {
// routine to initialize the state of the game and draw the board
    // build the board array
    for(x = 0; x < width; x++)
	board[x] = new Array (height);

    document.write('<TABLE CELLPADDING="0" CELLSPACING="0" BORDER="1" COLS="' + width + '" ROWS="' + height + '">');
    for(y = 0; y < height; y++) {
	document.write('<TR>');
	for(x = 0; x < width; x++) {
	    // place initial pieces
	    if((x == 3 && y == 3) || (x == 4 && y == 4)) player = WHITE;
	    else if((x == 3 && y == 4) || (x == 4 && y == 3)) player = BLACK;
	    else player = EMPTY;

	    document.write('<TD BGCOLOR="' + color + '" WIDTH="' + piecewidth + '" HEIGHT="' + pieceheight + '"><A HREF="javascript:void(0);" onClick="PutPiece(' + x + ', ' + y + ')" onMouseOver="CheckPutPiece(' + x + ', ' + y + ')" onMouseOut="RestorePiece(' + x + ', ' + y + ')"><IMG NAME="c[' + x + ',' + y + ']" SRC="' + picture[player].src + '" BORDER="0" HEIGHT="' + pieceheight + '" WIDTH="' + piecewidth + '"></A></TD>');
	    board[x][y] = new piece('c[' + x + ',' + y + ']');
	    board[x][y].player = player;
	}

	document.writeln('</TR>');
    }
    document.write('</TABLE>');

    // initialize scores
    score[WHITE] = 2;
    score[BLACK] = 2;
}

function ResetBoard() {
// routine to reset all of the pieces on the board

    // cancel any pending AI task
    if(AI_timerID != undefined) {
	clearTimeout(AI_timerID);
	AI_timerID = undefined;
    }

    // reset the board
    for(y = 0; y < height; y++) {
	for(x = 0; x < width; x++) {
	    board[x][y].player = EMPTY;
	    SetPieceImage(x, y, picture[EMPTY].src);
	}
    }

    // reset scores
    score[WHITE] = 0;
    score[BLACK] = 0;

    // put initial pieces back on the board
    RawPutPiece(3, 3, WHITE);
    RawPutPiece(4, 4, WHITE);
    RawPutPiece(3, 4, BLACK);
    RawPutPiece(4, 3, BLACK);

    turn = BLACK;
    if(turnhook != "") eval(turnhook);
}

function NumFlips(x, y, player) {
    var deltax, deltay, distance;
    var posx, posy;
    var count = 0;

    for(deltay = -1; deltay <= 1; deltay++) {
	for(deltax = -1; deltax <= 1; deltax++) {
	    for(distance = 1;; distance++) {
		posx = x + (distance * deltax);
		posy = y + (distance * deltay);
		// stop if we go off the board
		if(posx < 0 || posx >= width || posy < 0 || posy >= height)
		    break;
		// stop when we reach an empty square
		if(board[posx][posy].player == EMPTY)
		    break;
		// only update the flip count when we reach another of the
		// player's pieces
		if(board[posx][posy].player == player) {
		    count += distance - 1;
		    break;
		}
	    }
	}
    }
    return(count);
}

function CalcFlipCounts() {
    var x, y;

    for(y = 0; y < height; y++) {
	for(x = 0; x < width; x++) {
	    board[x][y].flips[WHITE] = 0;
	    board[x][y].flips[BLACK] = 0;

	    if(board[x][y].player != EMPTY) continue;

	    board[x][y].flips[WHITE] = NumFlips(x, y, WHITE);
	    board[x][y].flips[BLACK] = NumFlips(x, y, BLACK);
	}
    }
}

function RawPutPiece(x, y, player) {
    var other = OtherPlayer(player);
    if(board[x][y].player == other) score[other]--;
	
    board[x][y].player = player;
    SetPieceImage(x, y, picture[player].src);
    score[player]++;
}

function FlipPieces(x, y, player) {
    var deltax, deltay, distance;
    var posx, posy;
    var count = 0;

    // put a piece down at the desired location
    RawPutPiece(x, y, player);

    for(deltay = -1; deltay <= 1; deltay++) {
	for(deltax = -1; deltax <= 1; deltax++) {
	    for(distance = 1;; distance++) {
		posx = x + (distance * deltax);
		posy = y + (distance * deltay);
		// stop if we go off the board
		if(posx < 0 || posx >= width || posy < 0 || posy >= height)
		    break;
		// stop when we reach an empty square
		if(board[posx][posy].player == EMPTY)
		    break;
		if(board[posx][posy].player == player) {
		    // backtrack, flipping pieces
		    for(distance--; distance > 0; distance--) {
			posx = x + (distance * deltax);
			posy = y + (distance * deltay);
			RawPutPiece(posx, posy, player);
		    }
		    break;
		}
	    }
	}
    }
    return(count);
}

function AnyMoves(player) {
    var x, y;

    for(y = 0; y < height; y++) {
	for(x = 0; x < width; x++) {
	    if(board[x][y].player != EMPTY) continue;
	    if(NumFlips(x, y, player) > 0) return(true);
	}
    }
    return(false);
}

function CanPutPiece(x, y, player) {
// determine whether the player can put a piece at the given position
    if(turn != player)
	return(false);
    if(board[x][y].player != EMPTY)
	return(false);
    return(NumFlips(x, y, player) > 0);
}

function CheckPutPiece(x, y) {
    var over;

    if(overhook != "") eval(overhook);

    if(! showcursor) return;
    if(! CanPutPiece(x, y, human)) return;

    if(human == WHITE) over = WHITETRANS;
    else over = BLACKTRANS;

    SetPieceImage(x, y, picture[over].src);
}

function RestorePiece(x, y) {
    if(showflips && RawShowFlipCount(x, y, human)) return;
    SetPieceImage(x, y, picture[board[x][y].player].src);
}

function PutPiece(x, y) {
    if(! CanPutPiece(x, y, human)) return;

    FlipPieces(x, y, human);
    DoneTurn();
}

function RawShowFlipCount(x, y, player) {
    var flips;
    if(board[x][y].player != EMPTY) return(false);
    if((flips = board[x][y].flips[player]) == 0) return(false);
    SetPieceImage(x, y, picture[NUMBASE + flips].src);
    return(true);
}

function ShowFlipCounts(player) {
    var x, y;

    CalcFlipCounts();
    for(y = 0; y < height; y++) {
	for(x = 0; x < width; x++) {
	    RawShowFlipCount(x, y, player);
	}
    }
}

function HideFlipCounts() {
    var x, y;

    for(y = 0; y < height; y++) {
	for(x = 0; x < width; x++) {
	    if(board[x][y].player == EMPTY) 
		SetPieceImage(x, y, picture[EMPTY].src);
	}
    }
}

function OtherPlayer(player) {
    return((player == WHITE)? BLACK: WHITE);
}

function DoneTurn() {
    var moves = AnyMoves(turn);

    if(turnhook != "") eval(turnhook);

    turn = OtherPlayer(turn);

    // check whether the new player has any moves
    if(! AnyMoves(turn)) {
	if(! moves) return(GameOver());

	// XXX inform user the player has no move

	// and switch players again
	turn = OtherPlayer(turn);
    }

    // add a slight delay before the computer takes it's turn so game feels
    // "warmer"; when computer is playing itself, add larger delay so user
    // can watch
    if(turn != human) {
	HideFlipCounts();
	AI_timerID = setTimeout("OthelloAI(" + turn + ")", human == EMPTY? 1000: 150);
    }
    else if(showflips)
	ShowFlipCounts(human);
}

function Rate(x, y, player) {
    var rating;

    if(board[x][y].player != EMPTY) return(0);
    if(x < 0 || x >= width || y < 0 || y >= height) return(0);

    rating = board[x][y].flips[player];

    if(! weightsquares)
	rating = (rating > 0)? 1: 0;

    if(edgesensitive && rating > 0) {
	// increase all non-zero weightings by 3 so we have room
	// to wait 'less ideal' squares below the baseline
	rating += 10;

	// raise edge ratings 4 points, corners are raised 8
	if(x == 0 || x == width - 1) rating += 4;
	if(y == 0 || y == height - 1) rating += 4;
	// lower next-to-edge ratings by 5 points, next-to-corner by 10
	if(x == 1 || x == width - 2) rating -= 5;
	if(y == 1 || y == height - 2) rating -= 5;

	// we cannot rule out a move because of bad location; we must
	// always go somewhere
	if(rating < 1) rating = 1;
    }
    return(rating);
}

function OthelloAI(player) {
    var x, y;
    var best = 0, numbest = 0;
    var rating;
    var pick, count;

    // rank each position on the board by the potential flip count
    CalcFlipCounts();

    // apply AI rating algorithm
    for(y = 0; y < height; y++) {
	for(x = 0; x < width; x++) {
	    rating = Rate(x, y, player);

	    // store the rating back into the board
	    board[x][y].value[player] = rating;

	    if(rating == best)
		numbest++;
	    else if(rating > best) {
		best = rating;
		numbest = 1;
	    }
	}
    }

    while(numbest > 0) {
	// pick a square to put our piece
	pick = Math.floor(Math.random() * numbest);
	count = 0;
	for(y = 0; y < height; y++) {
	    for(x = 0; x < width; x++) {
		rating = board[x][y].value[player];
		if(rating == best) {
		    if(count == pick) {
			FlipPieces(x, y, player);
			DoneTurn();
			return;
		    }
		    else count++;
		}
	    }
	}
    }

    // if we make it here, then there was nowhere to go
    DoneTurn();
}

function Play() {
    // black always goes first
    if(human != BLACK)
	OthelloAI(BLACK);
    else if(showflips)
	ShowFlipCounts(human);
}

function GameOver() {
    alert("Game Over; White: " + score[WHITE] + ", Black: " + score[BLACK]);
    turn = EMPTY;
}


// THE FOLLOWING INITIALIZATION SHOULD APPEAR IN THE MAIN HTML SOURCE
//
// // define a mouse-over and per-turn handler...
// overhook = 'window.status = "White: " + score[WHITE] + ", Black: " + score[BLACK]';
// turnhook = 'window.defaultStatus = "White: " + score[WHITE] + ", Black: " + score[BLACK]';
//
// // load player piece images
// LoadPieceImage(EMPTY, "images/blank.gif");
// LoadPieceImage(WHITE, "images/white.gif");
// LoadPieceImage(BLACK, "images/black.gif");
// LoadPieceImage(WHITETRANS, "images/white-trans.gif");
// LoadPieceImage(BLACKTRANS, "images/black-trans.gif");
//
// // load number images (must have at least 0-21)
// for(i = 0; i <= 21; i++)
//    LoadPieceImage(NUMBASE + i, "images/trans-" + i + ".gif");
//
// // set defaults
// human = BLACK;
// showcursor = true;
// showflips = false;
// weightsquares = true;
// edgesensitive = true;
//
// // initialize the state of the board
// InitializeBoard("#006600");
//
// // start the game!
// Play();
//