Minimax is a kind of backtracking algorithm that is used in decision making and game theory to find the optimal move for a player, assuming that your opponent also plays optimally.

• In Minimax 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.

Every board state has a value associated with it.

• In a given state if the maximizer has upper hand then, the score of the board will tend to be some positive value.
• If the minimizer has the upper hand in that board state then it will tend to be some negative value.
• The values of the board are calculated by some heuristics which are unique for every type of game.

Since this is a backtracking based algorithm, it tries all possible moves, then backtracks and makes a decision.

A program to illustrate the Minimax Algorithm

A program to illustrate the Minimax Algorithm2

A Tic-Tac-Toe example program to illustrate the Minimax Algorithm

function minimax(board, depth, isMaximizingPlayer):
 
  if current board state is a terminal state :
    return value of the board
 
  if isMaximizingPlayer :
    bestVal = -INFINITY 
    for each move in board :
      value = minimax(board, depth+1, false)
      bestVal = max( bestVal, value) 
    return bestVal
 
  else :
    bestVal = +INFINITY 
    for each move in board :
      value = minimax(board, depth+1, true)
      bestVal = min( bestVal, value) 
    return bestVal