Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
TicTacToe with minimax
#!/usr/bin/env node
// board is single array
// [x, x, x,
// x, x, x,
// x, x, x]
// where x may be string 'X', 'O', or null
var readline = require('readline-sync');
const XMARK = 'X';
const OMARK = 'O';
function drawBoard(board) {
var template = '\
A B C \n\
+-----------+\n\
1 | ? | ? | ? |\n\
+-----------+\n\
2 | ? | ? | ? |\n\
+-----------+\n\
3 | ? | ? | ? |\n\
+-----------+\n';
var boardString = template;
// replace single '?' at time
board.forEach(function(field) {
boardString = boardString.replace('?', field || ' ');
});
console.log(boardString);
}
function getUserMove(mark) {
var userMove = null,
row,
col,
first = true;
do {
if (!first) {
console.log('error: invalid position');
console.log('example position format: 1B')
}
userMove = readline.question('[' + mark + '] Your move? ');
userMove = userMove.trim() || 'invalid';
first = false;
} while (!userMove.match(/^(1|2|3)(A|B|C)$/));
row = Number(userMove.charAt(0)) - 1;
col = userMove.charCodeAt(1) - 'A'.charCodeAt(0);
return ({ row:row, col:col });
}
function choice() {
if (!arguments.length)
return null;
var choosen = arguments[0];
for (var i = 1; i < arguments.length; i += 1) {
if ( Math.random() < (1/(i+1)) ) {
choosen = arguments[i];
}
}
return choosen;
}
function initGame() {
var game = { };
game.board = [null, null, null,
null, null, null,
null, null, null];
game.xCounters = makeCounters();
game.oCounters = makeCounters();
return game;
function makeCounters() {
return {
rows: [0,0,0],
cols: [0,0,0],
tbDiag: 0,
lrDiag: 0
};
}
}
function getWinner(game) {
if (has3Marks(game.xCounters))
return XMARK;
if (has3Marks(game.oCounters))
return OMARK;
return null;
function has3Marks(counters) {
if (counters.rows.some(equals3))
return true;
if (counters.cols.some(equals3))
return true;
if (equals3(counters.tbDiag) || equals3(counters.lrDiag))
return true;
return false;
function equals3(n) { return (n === 3); }
}
}
function putMark(game, mark, position) {
var index = position.row*3 + position.col;
var remove = (mark === null);
if (game.board[index] && !remove)
return false;
else if (!game.board[index] && remove)
return false;
if (remove) {
mark = game.board[index];
}
game.board[index] = remove ? null : mark;
var inc = remove ? (-1) : 1;
var counters = (mark === XMARK ? game.xCounters : game.oCounters);
counters.rows[position.row] += inc;
counters.cols[position.col] += inc;
if (isOnTbDiag(position))
counters.tbDiag += inc;
if (isOnLrDiag(position))
counters.lrDiag += inc;
return true;
function isOnTbDiag(position) {
return position.row === position.col;
}
function isOnLrDiag(position) {
return position.row === (2-position.col);
}
}
function deepCopy(obj) {
return JSON.parse(JSON.stringify(obj));
}
function minimax(game, compMark) {
var bestMove = null;
game = deepCopy(game);
_minimax(compMark, 0);
console.assert(bestMove);
return bestMove;
function _minimax(mark, level) {
var value = (mark === compMark) ? -1000 : 1000;
_emptyPositions(game.board).forEach(function(pos) {
var tmp;
console.assert( putMark(game, mark, pos) );
var winner = getWinner(game);
if (!winner && isBoardFull(game)) {
tmp = 0;
}
else if (winner) {
tmp = (winner == compMark ? 100-level : level-100);
}
else {
tmp = _minimax(mark === XMARK ? OMARK : XMARK, level+1);
}
if (mark === compMark) {
// maximizing player
if (value < tmp) {
value = tmp;
if (!level) bestMove = pos;
}
}
else {
// minimizing player
if (value > tmp) {
value = tmp;
if (!level) bestMove = pos;
}
}
console.assert( putMark(game, null, pos) );
});
return value;
}
function _emptyPositions(board) {
var positions = [];
for (var i = 0; i < board.length; i += 1) {
if (!board[i]) {
positions.push({ row: Math.floor(i/3), col: Math.floor(i%3) });
}
}
return positions;
}
}
function isBoardFull(game) {
var board = game.board;
for (var i = 0; i < board.length; i += 1) {
if (!board[i])
return false;
}
return true;
}
function run() {
var currMark = choice(XMARK, OMARK),
position;
var game = initGame();
drawBoard(game.board);
while (!getWinner(game) && !isBoardFull(game)) {
position = (currMark === XMARK) ?
getUserMove(currMark) :
minimax(game, OMARK);
if (!putMark(game, currMark, position)) {
console.log('error: invalid move');
continue;
}
currMark = (currMark === XMARK ? OMARK : XMARK);
drawBoard(game.board);
}
var winner = getWinner(game);
if (winner) {
console.log('!!! ' + winner + ' WON !!!');
}
else {
console.log('~~~ DRAW ~~~');
}
}
run();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment