![]()
Visiting guest. Why not sign in?
|
|
|
Minimax ExplainedIntroductionThere 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 AlgorithmThe 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. ![]() 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 Remember you can visit the Message Store to discuss this tutorial. There are already 4 replies in the thread, why not join in? Back to the Artificial Intelligence Depot.
|