Self-built Tic-tac-toe AIs vs Human - The ultimate showdown in five rounds

 X |   | X---+---+---   | O | X ---+---+--- O | O | X

const countSymbolsInBoard = (board, symbol) => board  .reduce((previousRowCount, currentRow) => {    return previousRowCount + currentRow      .filter(v => v === symbol).length  }, 0)

const copyBoard = board => [  [board[0][0], board[0][1], board[0][2]],  [board[1][0], board[1][1], board[1][2]],  [board[2][0], board[2][1], board[2][2]],]

// game.jsconst symbolX = 'X'const symbolO = 'O'export const isDraw = (board) => board.flat().every(v => v === symbolO || v === symbolX)

// game.jsexport const winningCoordinates = [  [    [0, 0], [0, 1], [0, 2],  ],  [    [1, 0], [1, 1], [1, 2],  ],  [    [2, 0], [2, 1], [2, 2],  ],  [    [0, 0], [1, 0], [2, 0],  ],  [    [0, 1], [1, 1], [2, 1],  ],  [    [0, 2], [1, 2], [2, 2],  ],  [    [0, 0], [1, 1], [2, 2],  ],  [    [2, 0], [1, 1], [0, 2],  ]]export const hasWon = (currentBoard, isX) => {  const checkingSymbol = isX ? symbolX : symbolO  for (let coordTriple of winningCoordinates) {    const symbolTriple = coordTriple.map(coords => currentBoard[coords[0]][coords[1]])    if (symbolTriple.every(v => v === checkingSymbol)) {      return true    }  }  return false}

// game.jsexport const doTurn = (currentBoard, isX, x, y) => {  if (isDraw(currentBoard)) {    throw new Error('Cannot move on board that is a draw')  }  if (hasWon(currentBoard, true) || hasWon(currentBoard, false)) {    throw new Error('Cannot move on board that was already won by someone')  }  if (x > 2 || y > 2) {    throw new Error(`Coordinates out of bounds: ${x}/${y}`)  }  if (currentBoard[y][x] === symbolX || currentBoard[y][x] === symbolO) {    throw new Error(`Illegal move: ${x}/${y} is already occupied`)  }  const numberOFXs = countSymbolsInBoard(currentBoard, symbolX)  const numberOFOs = countSymbolsInBoard(currentBoard, symbolO)  if ((isX && numberOFXs > numberOFOs) || (!isX && numberOFOs > numberOFXs)) {    throw new Error(`Illegal move, it would be ${(isX ? 'O' : 'X')}s turn`)  }  const newBoard = copyBoard(currentBoard)  newBoard[y][x] = isX ? symbolX : symbolO  return newBoard}

// playCli.jsimport { doTurn, hasWon, isDraw } from './game.js'import { createInterface } from 'readline'const playGame = async () => {  let isX = true  let board = [    ['', '', ''],    ['', '', ''],    ['', '', ''],  ]  const rl = createInterface({    input: process.stdin,    output: process.stdout  })  const getInput = question => new Promise(resolve => {    rl.question(question, resolve)  })  while (!hasWon(board, true) && !hasWon(board, false) && !isDraw(board)) {    console.table(board)    console.log(`${isX ? 'X' : 'O'}s turn!
`)    const x = Number(await getInput('X coordinate: '))    const y = Number(await getInput('Y coordinate: '))    try {      board = doTurn(board, isX, x, y)      isX = !isX    } catch (e) {      console.warn(e.message)    }  }  console.table(board)  console.log('----------')  console.log(isDraw(board) ? 'Draw!' : hasWon(board, true) ? 'X has won!' : 'Y has won!')  process.exit(0)}playGame()

// machineRandom.jsexport const getRandomNumber = (min, max) => Math.floor(  Math.random() * (max - min + 1)) + min

// playCli.js// ...    let x = 0    let y = 0    if (isX) {      x = Number(await getInput('X coordinate: '))      y = Number(await getInput('Y coordinate: '))    } else {      x = getRandomNumber(0, 2)      y = getRandomNumber(0, 2)    }// ...

// randomDefensePlay.jsimport { winningCoordinates } from './game.js'const symbolX = 'X'const symbolO = 'O'const getRandomNumber = (min, max) => Math.floor(Math.random() * (max - min + 1)) + minexport const getCoords = (board, isX) => {  for (let coordTriple of winningCoordinates) {    const boardTriple = coordTriple.map(coords => board[coords[1]][coords[0]])    const numberOfOpponentSymbols = boardTriple.filter(s => isX ? s === symbolO : s === symbolX).length    const numberOfEmpty = boardTriple.filter(s => s === '').length    // Found a triple the machine can still fill in    if (numberOfOpponentSymbols === 2 && numberOfEmpty === 1) {      for (let coords of coordTriple) { // Find the empty cell        if (board[coords[1]][coords[0]] === '') {          // Fill it in          return coords        }      }    }  }  return [    getRandomNumber(0, 2),    getRandomNumber(0, 2),  ]}

import { winningCoordinates } from './game.js'const symbolX = 'X'const symbolO = 'O'const getRandomNumber = (min, max) => Math.floor(Math.random() * (max - min + 1)) + minconst getFillingCoordinatesForSymbol = (symbol, board) => {  for (let coordTriple of winningCoordinates) {    const boardTriple = coordTriple.map(coords => board[coords[1]][coords[0]])    const numberOfMatchingSymbols = boardTriple.filter(s => s === symbol).length    const numberOfEmpty = boardTriple.filter(s => s === '').length    if (numberOfMatchingSymbols === 2 && numberOfEmpty === 1) {      for (let coords of coordTriple) { // Find the empty cell        if (board[coords[1]][coords[0]] === '') {          // Fill it in          return coords        }      }    }  }  return null}export const getCoords = (board, isX) => {  const ownWinCoords = getFillingCoordinatesForSymbol(isX ? symbolX : symbolO, board)  if (ownWinCoords !== null) {    return ownWinCoords  }  const opponentWinCoordinates = getFillingCoordinatesForSymbol(isX ? symbolO : symbolX, board)  if (opponentWinCoordinates !== null) {    return opponentWinCoordinates  }  return [    getRandomNumber(0, 2),    getRandomNumber(0, 2),  ]}

// bruteForcePlay.jsimport { doTurn, hasWon, isDraw } from './game.js'let createdCount = 0// You cannot compare arrays of arrays directly, so we create a// string representation of the board to compare thatconst areBoardsSame = (a, b) => {  const flatA = a.flat().map(c => c === '' ? '_' : c).join('')  const flatB = b.flat().map(c => c === '' ? '_' : c).join('')  return flatA === flatB}// Represents a single board and all it's possible child boards.class Node {  constructor(isXsTurn, board, xCoord, yCoord, depth) {    createdCount++    // Some logging to see progress    if (createdCount % 10000 === 0) {      console.log('Created ', createdCount)    }    this.board = board    this.isXsTurn = isXsTurn    // Score by depth. The further down a win is, the less likely it is to happen.    // Therefore: Try to take paths where a win is less deep.    this.score = null    if (hasWon(board, true)) {      this.score = -10 / depth    } else if (hasWon(board, false)) {      // Focus on winning      this.score = 50 / depth    } else if (isDraw(board)) {      this.score = 10 / depth    }    this.xCoord = xCoord    this.yCoord = yCoord    this.children = this.score === null ? this.createChildren(depth + 1) : []  }  createChildren(depth) {    let children = []    // Loop through the entire board and create children where allowed.    for (let x = 0; x < 3; x++) {      for (let y = 0; y < 3; y++) {        try {          const newBoard = doTurn(this.board, this.isXsTurn, x, y)          children.push(new Node(!this.isXsTurn, newBoard, x, y, depth))        } catch (_) {          // Move would be illegal, hence the error.          // We consider this as "skip this board"        }      }    }    return children  }  getChildNodeByBoard(board) {    // Since we've created _all_ the possible boards, if    // the subtree selection works once, it always works.    // So no need for checking.    return this.children.filter(node => areBoardsSame(node.board, board))[0]  }  // Just sum up all the subtrees  getScoreSum() {    if (this.score !== null) {      return this.score    }    return this.children.map(c => c.getScoreSum()).reduce((previous, current) => previous + current, 0)  }}

 X |   | ---+---+---   | O |  ---+---+---   |   | X

// The actual AI. This thing judges what move// should be done next based on the current board and its sub tree.export class AI {  constructor() {    // Turn here is false, so on the _next_ turn (the first) X would start    this.startNodeX = new Node(false,[      ['', '', ''],      ['', '', ''],      ['', '', ''],    ], null, null, 1)    this.startNodeO = new Node(true, [      ['', '', ''],      ['', '', ''],      ['', '', ''],    ], null, null, 1)    this.currentSubTree = null  }  // When a game is over  startOver() {    this.currentSubTree = null  }  getCoords(board) {    if (this.currentSubTree === null) {      if (board.flat().join('').length === 0) { // Empty board        this.currentSubTree = this.startNodeX      } else {        this.currentSubTree = this.startNodeO        this.currentSubTree = this.currentSubTree.getChildNodeByBoard(board)      }    } else {      this.currentSubTree = this.currentSubTree.getChildNodeByBoard(board)    }    // We nest this so we can sort better    const scoredCoords = this.currentSubTree.children.map(c => ({      score: c.getScoreSum(),      coords: [c.xCoord, c.yCoord],      subTree: c,    }))    scoredCoords.sort((a, b) => b.score - a.score)    // Debugging    // console.log(scoredCoords)    // Re-assign the sub tree for the next move    this.currentSubTree = scoredCoords[0].subTree    return scoredCoords[0].coords  }}

const symbolX = 'X'const symbolO = 'O'const hasTwoInARow = (board, coordTriple) => {  const symbols = coordTriple.map(    triple => board[triple[1]][triple[1]]  )  return symbols.filter(s => s === symbolX).length === 2    && symbols.filter(s => s === symbolO).length === 2    && symbols.filter(s => s === '').length === 1}

const calculateUtility = (board) => {  // Guaranteed win, go this lane.  if (hasWon(board, false)) {    return 1  }  // Every move is useless until  // proven otherwise  let utility = 0  winningCoordinates.forEach(coordTriple => {    // The more "two-in-a-row" configurations we get,    // the more likely a win further down the line.    // This checks if the computer has either    // gained or maintained such a configuration.    if (hasTwoInARow(board, coordTriple, false)) {      utility += 0.2    }    // Opponent still has a "two-in-a-row" configuration.    if (hasTwoInARow(board, coordTriple, true)) {      utility -= 0.2    }  })  return utility}

const getPossibleMoves = (board, isX) => {  const possibleMoves = []  for (let x = 0; x < 3; x++) {    for (let y = 0; y < 3; y++) {      try {        const resultingBoard = doTurn(board, isX, x, y)        possibleMoves.push({          move: [x, y],          resultingBoard: resultingBoard,          utility: null,        })      } catch (_) {        // Not a valid board, we therefore skip      }    }  }  return possibleMoves}

const minimax = (board, currentDepth, depthLimit, isMaximizing) => {  // If we reached a leave node or went as deep as we could,  // we calculate the utility of the result.  if (    currentDepth === depthLimit    || hasWon(board, true) || hasWon(board, false)    || isDraw(board)  ) {    return {      move: null,      utility: calculateUtility(board),      resultingBoard: board    }  }  const possibleMoves = getPossibleMoves(board, !isMaximizing)  possibleMoves.forEach(possibleMove => {    // Recursive call. For each possible move, we get all the    // subsequent moves the other player could do.    const bestMove = minimax(      possibleMove.resultingBoard,      currentDepth + 1,      depthLimit,      !isMaximizing    )    // This is where we set the current node's utility.    // It's the minimax'ed utility of all the moves    // before it.    possibleMove.utility = bestMove.utility  })  // The sorting, so the actual "min" and "max" part  // of the algorithm.  possibleMoves.sort((a, b) => {    if (isMaximizing) {      return a.utility - b.utility    }    return b.utility - a.utility  })  return possibleMoves[0]}export const getCoords = (board) => {  return minimax(board, 0, 5, true).move}