Minimax Algorithm Tutorial

There are plenty of application in AI but games are the most important thing in today's world and nowadays every OS comes with two player games like chess, checkers etc. So there are algorithm that help to design these games. These algorithm not only just help in making games but they also help in making the life of the player(i.e. user) tough in the game-play. So Minimax Algorithm is one such kind of algorithm. 

The Min-Max algorithm is applied in two player games, such as tic-tac-toe, checkers, chess, go, and so on as it helps us to find the accurate values of the board position. 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, so we assume that the player will always try to play his/her best move.

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

below :

Algorithm :

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;
}

The values here represents how good a 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.