Minimax Explained

By ai-depot | July 28, 2002

Discusses how search can be applied to logic games with full information. Game trees are described, as well as an algorithm that can search them. Pseudo code is given and optimisations like alpha-beta are explained.

Written by Paulo Pinto.

The Algorithm

Introduction

There are plenty of applications for AI, but games are the most interesting to the public. Nowadays every major OS comes with some games. So it is no surprise that there are some algorithms that were devised with games in mind.

The Min-Max Algorithm

The Min-Max algorithm is applied in two player games, such as tic-tac-toe, checkers, chess, go, and so on. All these games have at least one thing in common, they are logic games. This means that they can be described by a set of rules and premisses. With them, it is possible to know from a given point in the game, what are the next available moves. So they also share other characteristic, they are ‘full information games’. Each player knows everything about the possible moves of the adversary.

Search Tree

Figure 1: A representation of a search tree for a logic game.

Before explaining the algorithm, a brief introduction to search trees is required. Search trees are a way to represent searches. The squares are known as nodes and they represent points of the decision in the search. The nodes are connected with branches. The search starts at the root node, the one at the top of the figure. At each decision point, nodes for the available search paths are generated, until no more decisions are possible. The nodes that represent the end of the search are known as leaf nodes.

There are two players involved, MAX and MIN. A search tree is generated, depth-first, starting with the current game position upto the end game position. Then, the final game position is evaluated from MAX’s point of view, as shown in Figure 1. Afterwards, the inner node values of the tree are filled bottom-up with the evaluated values. The nodes that belong to the MAX player receive the maximun value of it’s children. The nodes for the MIN player will select the minimun value of it’s children. The algorithm is described in Listing 1.

MinMax (GamePosition game) {
  return MaxMove (game);
}
 
MaxMove (GamePosition game) {
  if (GameEnded(game)) {
    return EvalGameState(game);
  }
  else {
    best_move < - {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MinMove(ApplyMove(game));
       if (Value(move) > Value(best_move)) {
          best_move < - move;
       }
    }
    return best_move;
  }
}
 
MinMove (GamePosition game) {
  best_move <- {};
  moves <- GenerateMoves(game);
  ForEach moves {
     move <- MaxMove(ApplyMove(game));
     if (Value(move) > Value(best_move)) {
        best_move < - move;
     }
  }
 
  return best_move;
}

So what is happening here? The values represent how good a game move is. So the MAX player will try to select the move with highest value in the end. But the MIN player also has something to say about it and he will try to select the moves that are better to him, thus minimizing MAX’s outcome.

Pages: 1 2 3

Tags: none
Category: tutorial |

13 Responses to “Minimax Explained”

  1. Jim Igor Says:
    August 18th, 2007 at 6:33 pm

    I just want to say thank you for writing this article and that it has helped me alot in my studies at time of writing.

  2. dobau Says:
    September 16th, 2007 at 7:53 am

    For me too, thanks Paulo.

  3. Sri Says:
    October 25th, 2007 at 11:20 pm

    Thank you for such simple yet elegant explanation.

  4. mohamamed Says:
    January 9th, 2008 at 4:27 pm

    neeeeeeeed your help

  5. Armin Says:
    January 29th, 2008 at 12:04 pm

    I want a chess source code using minimax alghoritm. you explaind checkers game.please help me.thank you

  6. Fming Says:
    February 13th, 2008 at 9:13 am

    Thank you
    it is very useful

  7. Does This Mistake Make Your AI Look Smarter? — AiGameDev.com Says:
    March 25th, 2008 at 5:08 pm

    […] game theory and, in a broader sense, decision theory. Most AI programmers who are familiar with his minimax model also know that one of the requisite premises of applying it is perfect knowledge of the game […]

  8. rupali Says:
    April 19th, 2008 at 5:51 am

    is it possible for 4 players

  9. Julio Granados Says:
    May 9th, 2008 at 4:04 am

    Thanks a lot. You really helped me out. I’ve had spent hours reading an incorrect translation of Russell and Norvig’s AI book without success. Your site helped me.

  10. Azade Says:
    June 11th, 2008 at 3:31 pm

    I want to impelement Othello with c#,but I can’t
    write c# code for minimax and alpha-beta.
    please help me.
    thanks

  11. toer Says:
    July 2nd, 2008 at 10:04 am

    Thanks for the good explaination

  12. toer Says:
    July 2nd, 2008 at 10:11 am

    sorry for two messages. One thing which would have been good to add, is the scoring on your tic tac toe game. showing which decision would have been made given the search depth of 2.

    Otherwise, a really great explanation

  13. thx Says:
    July 2nd, 2008 at 2:01 pm

    Very informative. Aside from the not-so-uncommon typo or grammatical error, a good read. This helped me with my AI project :)

Comments