<?php
// $Id: gen9.php,v 1.17 2011/10/06 21:41:26 bediger Exp $
require("sajax.php");  // Sajax 0.13 - JavaScript files referenced in HTML

$DEPTH_LIMIT = 4;
$VERY_LARGE = 200000;

// Explanation of jargon used internally to this program:
// A "board" is 9 sub-boards:
//    0   1   2
//    3   4   5
//    6   7   8
//
// Each "subboard" is a standard, 9 slot tic-tac-toe board:
//    0   1   2
//    3   4   5
//    6   7   8
//
// The PHP code keeps the board of 9 subboards, each of 9 slots
// as a numerically-indexed array of size 88.  The index into
// the array $board of any given mark (-1 for human, 1 for
// computer, 0 for open) equals 10*subboard + slot. The array contains
// some unused slots, indexes 9, 19, 29, 39, 49, 59, 69, 79.

// The JavaScript also keeps an array of length 88 with values 1 for
// computer ('O' marks), -1 for human ('X' marks) and 0 for unmarked.
// This array gets passed to the PHP every time PHP needs to calculate
// a move.

// Array of arrays of 3 slot-indexes.  Each "triad" constitutes
// the slot-indexes in a subboard of a winning position.
$WINNING_TRIADS = array(
	array(0, 1, 2), // 0
	array(3, 4, 5), // 1
	array(6, 7, 8), // 2
	array(0, 3, 6), // 3
	array(1, 4, 7), // 4
	array(2, 5, 8), // 5
	array(0, 4, 8), // 6
	array(2, 4, 6)  // 7
);

// Array of potentially-winning-triads, indexed by slot
// that lies in one of the potentially-winning-triads.
// Pre-calculation and allocation of this keeps the static utility
// function from having to check all 8 winning triads every time.
$WINNING_TRIADS_BY_SLOT = array(
	array($WINNING_TRIADS[0], $WINNING_TRIADS[3], $WINNING_TRIADS[6]),
	array($WINNING_TRIADS[0], $WINNING_TRIADS[4]),
	array($WINNING_TRIADS[0], $WINNING_TRIADS[5], $WINNING_TRIADS[7]),
	array($WINNING_TRIADS[1], $WINNING_TRIADS[3]),
	array($WINNING_TRIADS[1], $WINNING_TRIADS[4], $WINNING_TRIADS[6], $WINNING_TRIADS[7]),
	array($WINNING_TRIADS[1], $WINNING_TRIADS[5]),
	array($WINNING_TRIADS[2], $WINNING_TRIADS[3], $WINNING_TRIADS[7]),
	array($WINNING_TRIADS[2], $WINNING_TRIADS[4]),
	array($WINNING_TRIADS[2], $WINNING_TRIADS[5], $WINNING_TRIADS[6])
);

// Indexes into a given 88-place board for corner-squares
// of the 9 sub-boards
$CORNER_INDEXES = array(
 	 0,  2,  6,  8,
	10, 12, 16, 18,
	20, 22, 26, 28,
	30, 32, 36, 38,
	40, 42, 46, 48,
	50, 52, 56, 58,
	60, 62, 66, 68,
	70, 72, 77, 78,
	80, 82, 88, 88
);

// Make an array, indexable by board-slot-index, value 1
// for a corner index, value 0 for non-corner index.
// Pre-calculation of this array allows easy utility value calcs.
$CORNERS = array_pad(array(), 89, 0);
foreach ($CORNER_INDEXES as $idx => $x) {
	$CORNERS[$x] = 1;
}

// Indexes into a given 88-place board for middle-squares
// of the 9 sub-boards.
// Pre-calculation of this array allows easy utility value calcs.
$MIDDLE_INDEXES = array(
	4, 14, 24, 34, 44, 54, 64, 74, 84
);
// Array, indexable by board-slot-index, value 1
// if the index is a middle square in a sub-board,
// 0 if it's not a middle square in a sub-board.
$MIDDLES = array_pad(array(), 89, 0);
foreach ($MIDDLE_INDEXES as $idx => $x) {
	$MIDDLES[$x] = 1;
}

// A single move's static value.  Sets $wn to 1 if it
// finds a win for anyone.  Gives smaller, possibly negative,
// values for 'X' (-1) player, gives larger, possibly positive,
// values for 'O' (1) player.
// The move has a (subboard, slot) representation.  Both have
// numeric values 0 thru 8 inclusive.
function utility($board, $subboard, $slot, $depth, &$wn) {

	global $DEPTH_LIMIT, $VERY_LARGE, $MIDDLES, $CORNERS;
	global $WINNING_TRIADS_BY_SLOT;

	$wn = 0;

	$score = 0;

	$winning_triads = $WINNING_TRIADS_BY_SLOT[$slot];

	foreach ($winning_triads as $mv => $triad) {

		$triad_sum = $board[$triad[0] + $subboard]
			+ $board[$triad[1] + $subboard] + $board[$triad[2] + $subboard];

		switch ($triad_sum) {
		case  3:
		case -3:
			$wn = 1;
			$score = $board[$triad[0]+$subboard] * ($VERY_LARGE - $depth);
			break;
		case  2:
			$score += 3000;  // Two in a triad, next move wins for maximizer
			break;
		case -2:
			$score -= 3000;  // Two in a triad, next move wins for minimizer
			break;
		// 1, -1: could be a single mark, or could be a block.
		// $triad_sum contains -1 if -1 got blocked, 1 if 1 got blocked.
		// Bitwise-and lets us distinguish between a single mark, and
		// a two-X, one-O type of position.
		case  1:
		case -1:
			if (($board[$triad[0] + $subboard]
				& $board[$triad[1] + $subboard]
				& $board[$triad[2] + $subboard]) != 0) {
				$score -=  $triad_sum * 1000;  // blocks a win
			}
			break;
		case  0:  // One of each mark, since player marked $slot 
			// Give a point just for monkeying with the other guy.
			$score += $board[$subboard + $slot];
			break;
		default:
			error_log("bad value calc in utility(): " . $triad_sum);
			break;
		}
		if ($wn) break;
	}

	if (!$wn) {
		// Give it a general preference for middles and 
		// slightly lesser preference for corners, but only
		// in non-winning positions.
		$move = $subboard + $slot;
		$bonus = 7*$MIDDLES[$move] +  2*$CORNERS[$move];
		$score += $board[$move]*$bonus;
	}

	return $score;
}


// Alpha-Beta minimaxing.
// Slightly non-standard, as it calculates the static utility incrementally.
// Beginning at the top ply in your_move(), utility() gets called on each
// preceding move, and added to the overall utility value ($score_so_far
// parameter. This practice speeds up the frequent calls to utility() in
// terminal nodes of the game tree, as it only has to calculate the delta
// utility for the move in question.
function alphabeta(
	$board, $last_slot, $player, $next_player,
	$alpha, $beta, $depth,
	$score_so_far,
	$last_move_won
) {
	global $DEPTH_LIMIT;

	// Static evaluation.  You could actually move this adjacent to the
	// actual calls to utility(), but that would mess up the readability.
	if ($last_move_won || $depth >= $DEPTH_LIMIT)
		return $score_so_far;

	// Find value of all the moves available to $player.
	// $subboard - "slot" of the last move becomes the
	// subboard in which this move must take place.
	$subboard = $last_slot * 10;

	if ($player == 1) {
		// Maximizing player, 'O', the computer
		for ($slot = 0; $slot < 9; ++$slot) {
			$move = $subboard + $slot;
			if ($board[$move] == 0) {
				$board[$move] = $player;
				$wn = 0;
				$move_score = utility($board, $subboard, $slot, $depth, $wn);
				$val = alphabeta($board, $slot, $next_player, $player,
					$alpha, $beta, $depth + 1, $score_so_far + $move_score, $wn);
				$board[$move] = 0;
				if ($val > $alpha) $alpha = $val;
				if ($beta <= $alpha) break;
			}
		}
		return $alpha;
	} else {
		// Minimizing player, 'X', the human
		for ($slot = 0; $slot < 9; ++$slot) {
			$move = $subboard + $slot;
			if ($board[$move] == 0) {
				$board[$move] = $player;
				$wn = 0;
				$move_score = utility($board, $subboard, $slot, $depth, $wn);
				$val = alphabeta($board, $slot, $next_player, $player,
					$alpha, $beta, $depth + 1, $score_so_far + $move_score, $wn);
				$board[$move] = 0;
				if ($val < $beta) $beta = $val;
				if ($beta <= $alpha) break;
			}
		}
		return $beta;
	}
}

// Called on server side by sajax. On client side, looks like a JavaScript
// function call to x_your_move()
function your_move($board, $jssubboard) {
	global $VERY_LARGE, $DEPTH_LIMIT;

	error_log("enter your_move([" . $board . "], " . $jssubboard . ")");

	// Find out if we're given an empty board. If so, make the first move.
	$empty_board = 1;
	for ($i = 0; $empty_board && $i < 9; ++$i) {
		$sb = 10 * $i;
		for ($slot = 0; $empty_board && $slot < 9; ++$slot) {
			$move = $sb + $slot;
			if ($board[$move])
				$empty_board = 0;
		}
	}

	if ($empty_board) {
		// JavaScript passed an empty board, indicating computer moves first.
		// Choice of first move doesn't seem to confer a huge advantage.
		// In lieu of a "book" just pick a random postition.
		while ((($r = rand(0, 88))%10) == 9)
			;
		error_log("Taking random first move $r");
		return $r;
	}

	// Not the first move.  Pick the best move remaining.  Again, a "book"
	// would have some value for maybe 2 moves into the game.
	$my_moves = null;
	$best_val = -$VERY_LARGE - $DEPTH_LIMIT;

	$subboard = $jssubboard * 10;

	for ($slot = 0; $slot < 9; ++$slot) {

		$move = $subboard + $slot;

		if ($board[$move] == 0) {
			error_log("Evaluating move " . $move . ". best value " . $best_val);
			$board[$move] = 1;
			$wn = 0;
			$mv_score = utility($board, $subboard, $slot, 0, $wn);
			$val = alphabeta($board, $slot, -1, 1, -2000000, 2000000, 1, $mv_score, $wn);
			error_log("Move " . $move . ". has value " . $val);
			$board[$move] = 0;
			if ($val > $best_val) {
				error_log("Best move so far: " . $move . ", value ". $val);
				$best_val = $val;
				$my_moves = array($move);
			} else if ($val == $best_val) {
				error_log("Equally good move: " . $move . ". value " . $val);
				array_push($my_moves, $move);
			}
		}
	}

	if (count($my_moves) == 0)
		error_log("Problem: found no acceptable moves.");
	
	// We've kept all the moves that end up with $best_val.  Pick one
	// of them to make the game seem less deterministic.
	$rv = $my_moves[array_rand($my_moves)];
	error_log("choosing " . $rv . ", value " . $best_val);

	return $rv;
}

$sajax_request_type = "GET";
sajax_export("your_move");
sajax_handle_client_request();
?>
<html>
<head>
<title>Nine-board Tic Tac Toe</title>

<!-- These script tags do includes for sajax-0.13, see http://sajax.info -->
<script language="JavaScript" type="text/javascript" src="json2.stringify.js"></script>
<script language="JavaScript" type="text/javascript" src="json_stringify.js"></script>
<script language="JavaScript" type="text/javascript" src="json_parse_state.js"></script>
<script language="JavaScript" type="text/javascript" src="sajax.js"></script>
<script language="JavaScript" type="text/javascript">
<?php sajax_show_javascript(); ?>

// Elapsed time: used by startTimer() and stopTimer()
var timerDiv = null;
var before = null;

// Used in removeGoFirstButton()
var goFirstButtonDiv = null;

// Used by humanClick() to decide if browser should allow
// a human's click to continue the game.
var gameOver = 0;

// Used to decide if the game is over.
var moveCount = 0;

// jsGameBoard: array of 88 slots, values -1 (human), 0, 1 (computer)
// This array keeps some elements that never get used, indexes 9, 19, ... 79.
var jsGameBoard = new Array();
for (var i = 0; i < 89; ++i)
	jsGameBoard[i] = 0;

// Set all 9 subboards to a given color.
function setSubboardColor(color) {
	for (var boardno = 0; boardno < 9; ++boardno)
		document.getElementById('bd' + boardno).style.backgroundColor = color;
}

function disableButtons(not_this_board) {
	for (var boardno = 0; boardno < 9; ++boardno) {
		// Can't just continue: have to enable possibly disabled buttons.
		var ability = (boardno == not_this_board)? false: true;
		for (var slotno = 0; slotno < 9; ++slotno) {
			var elem_id = 'btn'+boardno+slotno;
			var elem = document.getElementById(elem_id);
			// Buttons keep turning into 'X' or 'O', so
			// not every "btnXY" id tag exists.
			if (elem) elem.disabled = ability;
		}
	}
}

// Array of Arrays of 3 numbers.  Each triad consitutes a 3-in-a-row
// position, indexed by 3 numbers, each 0-88, into the jsGameBoard array.
// Different method of checking for winning positions than PHP part of
// the game uses, so that some redundancy exists.
var jsWinningTriads = new Array(
new Array(0, 1, 2),
new Array(3, 4, 5),
new Array(6, 7, 8),
new Array(0, 3, 6),
new Array(1, 4, 7),
new Array(2, 5, 8),
new Array(0, 4, 8),
new Array(2, 4, 6),
new Array(10, 11, 12),
new Array(13, 14, 15),
new Array(16, 17, 18),
new Array(10, 13, 16),
new Array(11, 14, 17),
new Array(12, 15, 18),
new Array(10, 14, 18),
new Array(12, 14, 16),
new Array(20, 21, 22),
new Array(23, 24, 25),
new Array(26, 27, 28),
new Array(20, 23, 26),
new Array(21, 24, 27),
new Array(22, 25, 28),
new Array(20, 24, 28),
new Array(22, 24, 26),
new Array(30, 31, 32),
new Array(33, 34, 35),
new Array(36, 37, 38),
new Array(30, 33, 36),
new Array(31, 34, 37),
new Array(32, 35, 38),
new Array(30, 34, 38),
new Array(32, 34, 36),
new Array(40, 41, 42),
new Array(43, 44, 45),
new Array(46, 47, 48),
new Array(40, 43, 46),
new Array(41, 44, 47),
new Array(42, 45, 48),
new Array(40, 44, 48),
new Array(42, 44, 46),
new Array(50, 51, 52),
new Array(53, 54, 55),
new Array(56, 57, 58),
new Array(50, 53, 56),
new Array(51, 54, 57),
new Array(52, 55, 58),
new Array(50, 54, 58),
new Array(52, 54, 56),
new Array(60, 61, 62),
new Array(63, 64, 65),
new Array(66, 67, 68),
new Array(60, 63, 66),
new Array(61, 64, 67),
new Array(62, 65, 68),
new Array(60, 64, 68),
new Array(62, 64, 66),
new Array(70, 71, 72),
new Array(73, 74, 75),
new Array(76, 77, 78),
new Array(70, 73, 76),
new Array(71, 74, 77),
new Array(72, 75, 78),
new Array(70, 74, 78),
new Array(72, 74, 76),
new Array(80, 81, 82),
new Array(83, 84, 85),
new Array(86, 87, 88),
new Array(80, 83, 86),
new Array(81, 84, 87),
new Array(82, 85, 88),
new Array(80, 84, 88),
new Array(82, 84, 86)
);

// Show a pop-up when someone wins.
function winnerNotice(phrase) {
	gameOver = 1;  // Global variable.
	var el = document.getElementById('notification');
	el.innerHTML = "<h3>"+phrase+"</h3>";
	var btn = document.getElementById('resetBtn');
	btn.value = 'New Game';
	alert(phrase);
}

// Color winning triad green, so human can see it easily.
function colorWinningTriad(triad) {
	var prefix = 'sq';
	if (triad[0] < 10) prefix = 'sq0';
	for (var j = 0; j < 3; ++j)
		document.getElementById(prefix + triad[j]).style.backgroundColor = "#00FF00";
}

// Figure out if somebody won.  Color the winning triad. Raise a pop-up.
function jsDetermineWinner() {
	var who_won = 0;
	for (var idx in jsWinningTriads) {
		var triad = jsWinningTriads[idx];
		var triadSum = jsGameBoard[triad[0]] + jsGameBoard[triad[1]]
			+ jsGameBoard[triad[2]];
		if (triadSum == 3 || triadSum == -3) {
			colorWinningTriad(triad);
			who_won = jsGameBoard[triad[0]];
			break;
		}
	}
	if (who_won == -1) winnerNotice('human wins');
	else if (who_won == 1) winnerNotice('computer won');
	else if (noLegalMoves()) winnerNotice('cat got another game');
	else who_won = 2;  // Magic value meaning "computer makes next move".  See humanClick().
	return who_won;
}

// Remove the "computer goes first" button from view.
// Called either from gofirst() or from humanClick()
function removeGoFirstButton() {
	goFirstButtonDiv.innerHTML = "";
}

// Event handler for clicks on 'computer goes first' button.
function gofirst() {
	if (!moveCount) removeGoFirstButton();
	startTimer();
	x_your_move(jsGameBoard, -1, computerClicked);
}

// Check if any legal move exists.  Mainly used to
// decide if cat wins.  Which it never does.
function noLegalMoves() {
	if (moveCount >= 81)
		return 1;
	return 0;
}

function startTimer() {
	before = (new Date()).getTime();
	timerDiv.innerHTML = '<p><strong>Working...</strong></p>';
}

function stopTimer() {
	var after = (new Date()).getTime();
	var et = (after - before)/1000.;
	timerDiv.innerHTML = '<p>Move took ' + et + 'sec</p>';
	before = null;
}

// Called asynch by PHP/Sajax, with computer's move.
function computerClicked(pos) {
	stopTimer();
	
	var pos = parseInt(pos);

	var sq = pos%10;
	var sb = (pos - sq)/10;
	clicked(sb, sq, 1);

	jsDetermineWinner();
}

// Human clicks fire this method:
function humanClick(subboard, slot) {
	if (!gameOver) {
		if (!moveCount) removeGoFirstButton();
		clicked(subboard, slot, -1);
		if (jsDetermineWinner() == 2) {
			startTimer();
			x_your_move(jsGameBoard, slot, computerClicked);
		}
	}
}

// Common things that happen no matter who made the move.
function clicked(subboard, square, player) {

	++moveCount;

	// Grey-out all subboards.
	setSubboardColor("#999999");

	// Highlight the legal board for the next move.
	document.getElementById('bd' + square).style.backgroundColor = "#FFFFFF";

	// Disable all buttons while remote server computes its answer,
	// keep human from jacking up the game, or just disable the buttons
	// in the non-legal subboards.
	disableButtons(player == -1? -1: square);

	// This doesn't cover the case of no legal moves in the subboard,
	// which I have not ever gotten to.

	// Set square to 'X' or 'O', set jsGameBoard[] appropriately.
	document.getElementById('sq' + subboard + square).innerHTML
		= '&nbsp;<strong>' +((player == 1)? 'O': 'X')+ '</strong>&nbsp;';

	// Keep track of game state in arrary jsGameBoard, passed to
	// PHP back on the server via x_your_move() call.
	var idx = parseInt(subboard)*10 + parseInt(square);
	jsGameBoard[idx] = player;
}

// Called by "reset" or "New game" button.  Should just totally reload
// the HTML, which is lazy, but effective: don't have to clean up JavaScript
// globals.
function totalReset() {
	document.location = "gen9.php";
}

// Print out HTML for a single, 3x3 TTT board, a "subboard"
// of the giant 3x3 board of TTT boards. tbody tags exist
// because FF complains about "unbalanced" tree creation bu
// document.write() without them.
function gen_board(subboard) {
	document.write('<table border="1"><tbody>');
	var counter = 0;  // ranges from 0 - 8 inclusive.
	for (var i = 0; i < 3; ++i) {
		document.writeln('<tr>');
		for (var j = 0; j < 3; ++j) {
			var numstr = ''+subboard+counter;

			// td-tag ID used to set background color of a winning triad,
			// and to change a button to an 'X' or an 'O' mark.
			// See JS functions colorWinningTriad() and clicked().
			var td_id = 'sq'+numstr;

			// input-tag-button ID used to disable or re-enable buttons so that
			//  only "legal" moves get made, or so that human doesn't click a button
			//  while PHP calculates. See JS function disableButtons()
			var btn_id = 'btn'+numstr;

			document.write("<td id='"+ td_id +"'>");
			document.write("<input type='button' name='"+ btn_id +"' "
				+ "value='&nbsp;' id='"+ btn_id +"' "
				+ "onclick='humanClick("+ subboard +", "+ counter +");' />");
			document.write('</td>');

			++counter;
		}
		document.write("</tr>");
	}
	document.write("</tbody></table>");
}
</script>
</head>
<body>
<h1>Nine-board Tic Tac Toe</h1>
<p><strong>Strength <?php echo $DEPTH_LIMIT; ?></strong></p>
<form name="f" method="get">
<table border="0">
<tbody><tr><td>
<table border="1">   <!-- put a border around all 9 sub-boards -->
<tr>
<td>
<table border='0' cellpadding='10'>
<tbody>
<script language="JavaScript" type="text/javascript">
// Fill in 9 subboards, each with a 3x3 TTT board
var subboard = 0;
for (var i = 0; i < 3; ++i) {
	document.write("<tr>");
	for (var j = 0; j < 3; ++j) {
		// The td-tag-ID value gets used by setSubboardColor()
		// and in clicked() to let human see which subboard can
		// contain the next move and which can't.
		document.write("<td id='bd"+subboard+"' align='center'>");
		gen_board(subboard);
		document.write('</td>');
		++subboard;
	}
	document.write("</tr>");
}
</script>
</tbody>
</table>
</td>
</tr>
</table>
<div id="timerDiv"><p>&nbsp;</p></div><br/>
<div id="notification"></div><br/> <!-- At end-of-game, JavaScript puts a phrase in this div -->
<input type="button" name="resetbtn" value="Reset" id="resetBtn" onclick="totalReset();" />
<div id="gofirstbutton"><input type="button" name="go1st" value="Computer moves first" onclick="gofirst();" /></div>
</td><td>
&nbsp;
</td>
<td>
<h3>Rules</h3>
<p>Nine-board tic-tac-toe is a <a
href="http://en.wikipedia.org/wiki/Tic-tac-toe#Variations">tic tac toe
variant</a> where nine ordinary, 3-by-3 tic-tac-toe boards make up a 3-by-3
array.  Players take turns making marks (human 'X', computer 'O') in the
ordinary tic-tac-toe boards. The first mark can appear anywhere. Each
subsequent mark gets made in any un-marked spot in the ordinary board that
corresponds to the spot where the previous mark got made.
The usual 3-in-a-row arrangement of marks in any of the 9 ordinary boards
wins.
</p>
<h3>Design</h3>
<p>
Nine-board tic-tac-toe is a distributed system: the user interface,
written in JavaScript, runs entirely in your browser.  Move calculation,
written in PHP, runs in the web server.
</p>
<p>
This program uses a stock alpha-beta minimax algorithm. 
It does calculate the utility function incrementally, rather than
doing the entire calculation at each terminal node in the game tree.
</p>
<h3>Download and Install</h3>
<p>
This version uses <a href="http://sajax.info/">Sajax</a> version 0.13 for
communication between the user interface
and the move calculation.
Download <a href="http://sajax.info/sajax-0.13.zip">sajax-0.13.zip</a>,
unzip it, and put files <kbd>sajax.php</kbd>, 
<kbd>json2.parse.js</kbd>,
<kbd>json2.stringify.js</kbd>,
<kbd>json_parse.js</kbd>,
<kbd>json_parse_state.js</kbd>,
<kbd>json_stringify.js</kbd>,
and
<kbd>sajax.js</kbd>
in a directory under the web server's <kbd>DocumentRoot</kbd>.
Download <a href="gen9.php.txt">the PHP file</a>, rename it to
<kbd>gen9.php</kbd>, and move it to the same directory used for the Sajax
files above.
</p>
<h3>Configuration</h3>
<p>
As currently configured, the program does a 4-level deep search
of the game tree for the best move. Changing the value of <kbd>$DEPTH_LIMIT</kbd>
in the PHP code to a greater value will make it search deeper, and take
longer to decide. A value of 4 will handily defeat humans who have never
played Nine-board before, and most who have.
</p>
</td>
</tr>
</tbody>
</table>
</form>
<script language="JavaScript" type="text/javascript">
// Declared way back at the top, used by JavaScript functions.  Initialize
// them here so that we don't have to muck up the JS code with "singleton
// initialization" type stuff.
goFirstButtonDiv = document.getElementById("gofirstbutton");
timerDiv = document.getElementById('timerDiv');
</script>
</body>
</html>