Introduction

Previous in part 1, we created a basic Tic tac toe interface and game. In part 2, we want to add A.I. feature to the game. We are going to develop 3 Level of A.I, from Easy -> Medium -> Unbeatable .

Final Product in Part 2

Easy Mode

Intuition

The easy mode random pick. We will start from finding empty cells from the game board. Just use a random to palce a mark in any empty cell.

Approach:

We will iterate through all the cell from the gameboard to find out all null cell. Then, we can random pick a cell and place the Mark to the gameboard.

import _ from "lodash"
 
function pickRandomEmptySpace(board: Cell[]) {
  const emptyIndices = _.compact(
    board.map((cell, index) => (cell === null ? index : null))
  )
 
  return _.sample(emptyIndices)
}

function pickRandomEmptySpace will filter all empty cell, we can use sample to pick a random index from the list.

Medium & Unbeatable Mode

The core of the Medium and Impossible game modes is the Minimax algorithm. This is a recursive algorithm used in decision-making and game theory to determine the optimal move for a player, assuming the opponent also plays optimally.

Minimax Algorithm

• Functionality: At each step, the algorithm simulates all possible moves, evaluates the resulting board state, and selects the move that maximizes the AI's chances of winning.
• Optimizations: To enhance performance, the algorithm implements several optimizations, especially in the Impossible mode.
• Space Complexity in Impossible Mode: O(n!), which translates to 9! (362880) computations if the AI plays as "X". To address potential performance concerns:
  • The AI's first move is pre-determined to the corner square, reducing complexity to 8! (40320) and improving response time.

function minimax(
  board: Cell[],
  depth: number,
  isMaximizingPlayer: boolean,
  aiPlayerMark: Marks,
  limit: number | null
) {
  const result = checkForWinner(board)
 
  if (result !== null) {
    return result === "TIE" ? 0 : result.winner === aiPlayerMark ? 10 : -10
  }
 
  // Depth limit condition
  if (limit !== null && depth == limit) return 0
 
  if (isMaximizingPlayer) {
    let bestScore = -Infinity
    for (let i = 0; i < board.length; i++) {
      if (board[i] === null) {
        board[i] = aiPlayerMark // AI's move
        const score = minimax(board, depth + 1, false, aiPlayerMark, limit)
        board[i] = null
        bestScore = Math.max(score, bestScore)
      }
    }
    return bestScore
  } else {
    let bestScore = Infinity
    for (let i = 0; i < board.length; i++) {
      if (board[i] === null) {
        board[i] = aiPlayerMark === "X" ? "O" : "X" // Human's move
        const score = minimax(board, depth + 1, true, aiPlayerMark, limit)
        board[i] = null
        bestScore = Math.min(score, bestScore)
      }
    }
    return bestScore
  }
}
 
function calcAIMove(board: Cell[], aiPlayerMark: Marks, limit: null | number) {
  let bestScore = -Infinity
  let move
  for (let i = 0; i < board.length; i++) {
    if (board[i] === null) {
      board[i] = aiPlayerMark // AI's move
      const score = minimax(board, 0, false, aiPlayerMark, limit)
      board[i] = null // Reset it
      if (score > bestScore) {
        bestScore = score
        move = i
      }
    }
  }
  return move
}

Final Product

Project Files

For more information about how to use the plugin and the features it includes, GitHub Repository for Part 2.

Ready to Lesson 3

In Lesson 3, we are going to create a Tic tac toe A.I. from easy -> medium -> Unbeatable. And we also will talk about the algorithm behine it. Tic-Tac-Toe-Lesson 2