Minimax

Template: Look at the example. Click this link, fork, and invite mrcodeswildride: new project

Technique

Use a backtracking technique called minimax. For two-player games, minimax is an algorithm that attempts to choose the best possible move for any given game state. It does this by assigning a score to every possible move, and choosing the move with the highest score.

If the move results in an endgame, the score can be computed directly. This is the base case.

If the move doesn't result in an endgame, the score must be computed by looking ahead. This is the recursive case. Minimax assumes that each player will choose the best possible move, so if the opponent is choosing a move, they will choose a move that minimizes the computer's score. If the computer is choosing a move, it will choose a move that maximizes its score.

Illustration

Pseudocode

function move():
  highestScore = -Infinity

  for each possible next move:
    score = getScore(nextMove, true)

    if score > highestScore:
      bestMove = nextMove

function getScore(move, computerTurn):
  if game is over:
    return score of game state
  else:
    if computerTurn:
      strongestScore = Infinity

      for each possible next move:
        score = getScore(nextMove, false)
        strongestScore = min(score, strongestScore)

      return strongestScore
    else:
      strongestScore = -Infinity

      for each possible next move:
        score = getScore(nextMove, true)
        strongestScore = max(score, strongestScore)

      return strongestScore

Last section Next section