TicTacToe with minimax

minimax.js

#!/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();