Unbeatable Tic-Tac-Toe AI

tictactoebot.js

"use strict";

const OPPONENT = 1;
const RANDOM_OPPONENT = false;

module.exports = {
  onTurn: function onTurn(turn) {
    try {
      const { gameState: state } = turn;
      const { x, y, index, message } = makeMove(state);
      console.log(
        state.player ? 'O' : 'x', index, message
      );
      // console.table(move);
      return [y, x];
    } catch(e) {
      console.error(e.lineNumber - 3, e);
    }
  }
};

const ROWS = [
  [0, 4, 8], [2, 4, 6],
  [0, 1, 2], [3, 4, 5], [6, 7, 8],
  [0, 3, 6], [1, 4, 7], [2, 5, 8]
];
const OPPOSITE_CORNERS = {
  0: 8, 2: 6, 6: 2, 8: 0
};

const formatBoard = state => state.board.flat().map(
  formatCell(state.player.toString())
);

const formatCell = player => (mark, index) => ({
  mark, index,
  x: index % 3,
  y: index / 3 | 0,
  empty: mark === null,
  own: player === mark,
  opponent: mark !== null && player !== mark,
  side: index % 2 == 1,
  center: index == 4,
  corner: index % 2 == 0 && index !== 4
});

const formatRows = board => ROWS.map(
  row => row.map(boardIndex => board[boardIndex])
);


function makeMove(state) {
  const board = formatBoard(state);
  const rows = formatRows(board);

  if(RANDOM_OPPONENT && state.player === OPPONENT) {
    return { ...findCell(board, 'empty'), message: '?' };
  }

  // win: place third in a row, if the other 2 are mine
  const winRows = findRowsWithTwo(rows, 'own');
  if(winRows.length) {
    const empty = findCell(winRows.flat(), 'empty');
    if(empty) return { ...empty, message: '!' };
  }

  // block: place third in a row, if opponent has the other 2
  const blockRows = findRowsWithTwo(rows, 'opponent');
  if(blockRows) {
    const empty = findCell(blockRows.flat(), 'empty');
    if(empty) return { ...empty, message: 'X' };
  }

  // fork: force a win on next turn (minimax?)
  const fork = false;
  if(fork) return fork;

  // block fork: prevent lose on next turn (minimax?)
  const blockFork = false;
  if(blockFork) return blockFork;

  // center
  const center = findCell(board, ['center', 'empty']);
  if(center) return { ...center, message: '+' };

  // opposite corner
  const cornerWithOpponent = findCell(board, ['corner', 'opponent']);
  if(cornerWithOpponent) {
    const opposite = board[
      OPPOSITE_CORNERS[cornerWithOpponent.index]
    ];
    if(opposite.empty) return { ...opposite, message: '/' };
  }

  // corner
  const corner = findCell(board, ['corner', 'empty']);
  if(corner) return { ...corner, message: 'L' };

  // side
  return { ...findCell(board, ['side', 'empty']), message: '_' };
};

const findRowsWithTwo = (rows, test) => rows.filter(
  row => (
    row.filter(cell => cell[test]).length === 2 &&
    row.some(cell => cell.empty)
  )
);

const findCell = (cells, tests) => sample(
  cells.filter(
    cell => (
      Array.isArray(tests) ? tests : [tests]
    ).every(
      key => cell[key]
    )
  )
);

const sample = ar => ar[
  Math.floor(ar.length * Math.random())
];