function map(a, f, t) { var na = new Array(a.length); for (var i = 0; i < a.length; i++) { na[i] = f.call(t, a[i]); } return na; } function showCoord(c) { return "[" + c[0] + ", " + c[1] + "]"; } function TicTacToe(size, container, ai, p1char, p2char) { this.size = size; this.container = container; this.p1char = p1char || 'X'; this.p2char = p2char || 'O'; this.ai = ai; this.winningCells = []; this.move = 0; this.board = new Array(this.size); if (this.ai) { this.ai.init(this); } // Set up the initial state this.iterateRows(function(i) { this.board[i] = new Array(this.size); this.iterateColumns(function(j) { this.board[i][j] = ''; }); }); } var p = TicTacToe.prototype; p.iterateRows = function(f) { for (var i = 0; i < this.size; i++) { var res = f.call(this, i); if (res !== undefined) { return res; } } } p.iterateColumns = p.iterateRows; p.iterate = function(f) { for (var i = 0; i < this.size; i++) { for (var j = 0; j < this.size; j++) { var res = f.call(this, i, j); if (res !== undefined) { return res; } } } }; p.render = function() { var html = ""; this.iterateRows(function(i) { html += ""; }); html += "

" + map(this.board[i], this.charFor, this).join("

") + "

"; this.container.empty().html(html); this.boardHTML = new Array(this.size); this.iterateRows(function(i) { this.boardHTML[i] = map(this.container.find("tr").slice(i,i+1).find("td"), jQuery); }); this.iterateRows(function(i) { this.boardHTML[i][0].addClass("first"); this.boardHTML[i][this.size - 1].addClass("last"); this.boardHTML[0][i].addClass("top"); this.boardHTML[this.size - 1][i].addClass("bottom"); }); this.addClickEvents(); }; p.addClickEvents = function() { var game = this; function makeClickEvent(row, col) { return function(event) { var player = game.move; if (game.playerMove(player, row, col)) { jQuery(this).unbind("click.move").removeClass("clickable"); if (!game.checkGameOver()) { if (game.ai) { game.aiMove(player == 1 ? 0 : 1); game.checkGameOver(); } } } } } this.iterate(function(i, j) { function returnFalse() { return false; } if (this.board[i][j] == "") { this.boardHTML[i][j].bind("click.move", makeClickEvent(i, j)) .addClass("clickable") .bind("selectstart.move", returnFalse) .bind("mousedown.move", returnFalse); } }); } p.removeClickEvents = function() { if (this.boardHTML) { this.iterate(function(i, j) { this.boardHTML[i][j].unbind("click.move").unbind("selectstart.move").unbind("mousedown.move").removeClass("clickable"); }); } } p.checkGameOver = function() { if (this.isGameOver()) { if (this.onGameOver) { this.onGameOver(); } this.removeClickEvents(); return true; } return false; } p.charFor = function(player) { switch(player) { case 0: case '': return ''; case 1: return this.p1char; case 2: default: return this.p2char; } } p.update = function() { if (!this.boardHTML) { this.render(); } this.iterate(function(i, j) { this.boardHTML[i][j].html(this.charFor(this.board[i][j])); }); }; p.tied = function() { var done = true; this.iterate(function(i, j) { if (this.board[i][j] == '') { done = false; return true; } }); return !this.p1wins() && !this.p2wins() && done; }; p.checkRow = function(i, pchar) { var same = true; this.iterate(function(j) { if (this.board[i][j] != pchar) { same = false; return true; } }); if (same) { this.winningCells = this.boardHTML[i]; } return same; }; p.checkColumn = function(i, pchar) { var same = true; this.iterate(function(j) { if (this.board[j][i] != pchar) { same = false; return true; } }); if (same) { this.winningCells = new Array(this.size); this.iterate(function(j) { this.winningCells[j] = this.boardHTML[j][i]; }) } return same; }; p.checkDiagonals = function(pchar) { var same = true; this.iterate(function(i) { if (this.board[i][i] != pchar) { same = false; return true; } }); // Not on primary diagonal; check secondary if (!same) { same = true; this.iterate(function(i) { var max = this.size - 1; if (this.board[max - i][i] != pchar) { same = false; return true; } }); if (same) { this.winningCells = new Array(this.size); this.iterate(function(i) { var max = this.size - 1; this.winningCells[i] = this.boardHTML[max - i][i]; }) } } else { this.winningCells = new Array(this.size); this.iterate(function(i) { this.winningCells[i] = this.boardHTML[i][i]; }) } return same; }; p.isWinner = function(pchar) { if (this.checkDiagonals(pchar)) { return true; } var winner = false; this.iterateRows(function(i) { if (this.checkRow(i, pchar) || this.checkColumn(i, pchar)) { winner = true; return true; } }); return winner; }; p.p1wins = function() { return this.isWinner(1); }; p.p2wins = function() { return this.isWinner(2); }; p.isGameOver = function() { this.winner == 0; if (this.p1wins()) { this.winner = 1; } else if (this.p2wins()) { this.winner = 2; } else if (this.tied()) { this.winner = 0; } else { return false; } return true; }; p.calculateAI = function(myChar, otherChar) { return this.ai.calculateMove(myChar, otherChar); }; p.aiMove = function(player) { if (this.winner) return false; var coord = this.calculateAI(player == 0 ? 1 : 2, player == 0 ? 2 : 1); return this.playerMove(player, coord[0], coord[1]); }; p.playerMove = function(player, row, col) { if (this.winner) { return false; } var res = this.set(row, col, player == 0 ? 1 : 2); if (res) { this.move = (player == 1) ? 0 : 1; this.update(); if (this.onTurn) { this.onTurn(); } } return res; }; p.set = function(row, col, value) { if ((row < 0 || col < 0) || (row >= this.size || col >= this.size) || (this.board[row][col] != "")) { return false; } this.board[row][col] = value; return true; }; // Artificial Intelligence Strategies function AI(game) { } AI.prototype.init = function(game) { this.game = game; this.boardStack = []; } AI.prototype.pushState = function() { function clone(aa) { var cloned = new Array(aa.length); for (var i = 0; i < aa.length; i++) { cloned[i] = new Array(aa[i].length); for (var j = 0; j < aa[i].length; j++) { cloned[i][j] = aa[i][j]; } } return cloned; } this.boardStack.push(clone(this.game.board)); } AI.prototype.popState = function() { return this.game.board = this.boardStack.pop(); } // Random AI function RandomAI() { this.calculateMove = function(myChar, otherChar) { this.pushState(); var row, col; do { row = Math.floor(Math.random() * this.game.size); col = Math.floor(Math.random() * this.game.size); } while (!this.game.set(row, col, myChar)); this.popState(); return [row, col]; } } RandomAI.prototype = AI.prototype; // First Available AI function FirstAvailableAI() { this.calculateMove = function(myChar, otherChar) { return this.game.iterate(function(i, j) { if (this.board[i][j] == "") { return [i, j]; } }); }; this.init = function(game) { this.game = game; }; } function countRow(a, row, value) { var count = 0; for (var i = 0; i < a[row].length; i++) { if (a[row][i] == value) count++; } return count; } function countColumn(a, col, value) { var count = 0; for (var i = 0; i < a.length; i++) { if (a[i][col] == value) count++; } return count; } function countDiagonal(a, value) { var count = 0; for (var i = 0; i < a.length; i++) { if (a[i][i] == value) count++; } return count; } function countSecondaryDiagonal(a, value) { var count = 0; var max = a.length - 1; for (var i = 0; i < a.length; i++) { if (a[i][max - i] == value) count++; } return count; } function findEmptyColumn(a, row) { for (var i = 0; i < a[row].length; i++) { if (a[row][i] == "") return i; } return -1; } function findEmptyRow(a, column) { for (var i = 0; i < a.length; i++) { if (a[i][column] == "") return i; } return -1; } function findEmptyDiagonal(a) { for (var i = 0; i < a.length; i++) { if (a[i][i] == "") return [i, i]; } return [-1, -1]; } function findEmptySecondaryDiagonal(a) { var max = a.length - 1; for (var i = 0; i < a.length; i++) { if (a[i][max - i] == "") return [i, max - i]; } return [-1, -1] } if (!Array.prototype.shuffle) { // Fisher-Yates/Knuth shuffle Array.prototype.shuffle = function fisherYates () { var i = this.length; if ( i == 0 ) return this; while ( --i ) { var j = Math.floor( Math.random() * ( i + 1 ) ); var tempi = this[i]; var tempj = this[j]; this[i] = tempj; this[j] = tempi; } return this; } } // Scored AI function ScoredAI() { this.calculateScore = function(row, col, me, other) { var board = this.game.board; var size = this.game.size; var otherInRow = countRow(board, row, other); var otherInCol = countColumn(board, col, other); var otherInMainDiag = (row == col ? (countDiagonal(board, other)) : 0); var otherInSecondDiag = (row == (size - col - 1) ? (countSecondaryDiagonal(board, other)) : 0); var selfInRow = countRow(board, row, me); var selfInCol = countColumn(board, col, me); var selfInMainDiag = (row == col ? countDiagonal(board, me) : 0); var selfInSecondDiag = (row == (size - col - 1) ? countSecondaryDiagonal(board, me) : 0); var score = 0; //var otherScale = 1; //var myScale = 1; //score = (myScale * (selfInRow + selfInCol + selfInMainDiag + selfInSecondDiag)) - (otherScale * (otherInRow + otherInCol + otherInMainDiag + otherInSecondDiag)); score = Math.max.apply(Math, [ selfInRow - otherInRow, selfInCol - otherInCol, selfInMainDiag - otherInMainDiag, selfInSecondDiag - otherInSecondDiag ]); /*if (selfInRow) { score += selfInRow; score -= otherInRow; } if (selfInCol) { score += selfInCol; score -= otherInCol; } if (selfInMainDiag) { score += selfInMainDiag; score -= otherInMainDiag; } if (selfInSecondDiag) { score += selfInSecondDiag; score -= otherInSecondDiag; }*/ //score += (selfInRow && !otherInRow); //score += (selfInCol && !otherInCol); //score += (selfInMainDiag && !otherInMainDiag); //score += (selfInSecondDiag && !otherInSecondDiag); return score; } this.calculateMove = function(me, other) { var ai = this; window.scores = []; this.game.iterate(function(i, j) { if (this.board[i][j] == "") { var score = ai.calculateScore(i, j, me, other); scores.push({ "score": score, "row": i, "col": j }); } }); if (scores.length == 0) return [-1, -1]; scores.shuffle().sort(function(a, b) { var as = a.score; var bs = b.score; if (as < bs) { return -1; } if (as > bs) { return +1; } else { return +0; } // Randomly decide whether to swap them //return (Math.random() < 0.5) ? -1 : +1; }); var topScore = scores[scores.length - 1]; return [topScore.row, topScore.col]; }; this.init = function(game) { this.game = game; }; } // Base AI // Wins if it can, protects itself from losing if it can, otherwise picks based on another AI's strategy function BaseAI(strategy) { this.init = function(game) { AI.prototype.init.call(this, game); this.randomAI = strategy || new RandomAI(); this.randomAI.init(game); } this.findWin = function(myChar) { var coords = this.game.iterate(function(i) { var row, col; if (countRow(this.board, i, myChar) == this.size - 1 && (col = findEmptyColumn(this.board, i)) != -1) { //alert("found " + myChar + " win by row"); return [i, col]; } else if (countColumn(this.board, i, myChar) == this.size - 1 && (row = findEmptyRow(this.board, i)) != -1) { //alert("found " + myChar + " win by col"); return [row, i]; } }); if (coords) { return coords; } // No luck with rows or columns - check diagonals if (countDiagonal(this.game.board, myChar) == this.game.size - 1) { coords = findEmptyDiagonal(this.game.board); if (coords[0] != -1 && coords[1] != -1) { //alert("found " + myChar + " win by main diagonal"); return coords; } } if (countSecondaryDiagonal(this.game.board, myChar) == this.game.size - 1) { coords = findEmptySecondaryDiagonal(this.game.board); if (coords[0] != -1 && coords[1] != -1) { //alert("found " + myChar + " win by secondary diagonal"); return coords; } } return false; } this.calculateMove = function(myChar, otherChar) { // If we can win, do it var pos = this.findWin(myChar); if (pos) { //alert(showCoord(pos)); return pos; } // Try to block the other player from winning pos = this.findWin(otherChar); if (pos) { //alert(showCoord(pos)); return pos; } // Pick randomly pos = this.randomAI.calculateMove(myChar, otherChar); //alert(showCoord(pos)); return pos; } } BaseAI.prototype = AI.prototype;