Minimax Algorithm

Minimax is a game tree search algorithm is used in decision making to find the optimal move for a player. It assumes that your opponent also plays optimally. It is widely used in two player turn-based games such as Tic-Tac-Toe, Checkers, Chess, etc.

In general, the two players are called maximizer and minimizer. The maximizer tries to get the highest score possible while the minimizer tries to do the opposite and get the lowest score possible.

Minimax is generally implemented as a recursive algorithm. Each level in the stack alternates turns, and thus alternates searching for a min node and a max node. Sometimes the min and max operations are broken into separate functions, min() and max(). While this makes the code more readable, it probably slows execution.

As will always be the case on CouraJS we're not going to explain the theory of Minimax. There are a ton of resources online which explain how it works. We instead present a practical implementation of Minimax in a game, Tic Tac Toe.

Key Notes

  • Minimax is for 2 player games
  • Generally applies to zero-sum games
  • The algorithm is typically shown as recursive
  • Plain Minimax is a depth first search of the game tree
  • Minimax is the base for many, many better search algorithms
  • Optimizations are required for use in complex games
  • The search likely won't complete in a reasonable amount of time as most game trees expands exponentially, so most implementations are depth limited
  • A variation known as Negamax is more typically used
  • An overwhelming set of pseudo-code variations exist and they're all technically correct but typically aren't practical

CouraJS Implementation

  • Algorithm: Basic depth limited Minimax
  • Language: TypeScript
  • Example Game: Tic Tac Toe
  • Two Minimax AIs, X and O, are both using the same AI
  • The game always results in a Draw because both AIs are playing perfectly
  • We evaluate all moves at the root level and return a sorted array of results, allowing the game to make a decision on which move to make based on difficulty / randomness of moves
  • Our evaluation / utility function always evaluates relative to the searcher be it X or O, thus the searcher is always the Max player
  • We make use of Generic Classes

Project

  • Click a file name tab to view the code
  • Press Run to run the game
  • Expand the workspace by pressing the green expand button in the top right
  • Feel free to copy and use as you please!