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.

Play at the leading casino on the web with Online Casino! Learn, practice and playyour favorite casino games online for real money or practice money play!

ReplyDeletecasino en ligne

hi!,I really like your writing very much! percentage we communicate extra about your post on AOL? I require an expert in this area to unravel my problem. May be that is you! Taking a look forward to peer you.

ReplyDeleteTy

ReplyDeleteHi,

ReplyDeleteshouldn't the line:

if (Value(move) > Value(best_move))

on the MinMove function be actually:

if (Value(move) < Value(best_move))

since we want the smaller value?

Very informative and impressive post you have written, this is quite interesting and i have went through it completely, an upgraded information is shared, keep sharing such valuable information. http://www.aceelo.com

ReplyDelete