Minimax Decision Theory

Minimax – Decision Rule 

Minimax is referred to a decision rule which is used in decision theory, statistics, game theory and philosophy, in reducing the possible loss for a worst case scenario. It is a principle for decision making when presented with two various and conflicting strategies with the use of logic and determine using the strategy which will minimize the maximum loss that may occur.

Formulated earlier for two players zero sum game theory covers both cases wherein players make alternate moves. Those that make simultaneous moves have been extended to more complex games with general decision in the presence of uncertainty. In the case of theory of simultaneous games, a minimax strategy is considered to be a mixed strategy that is part of the solution to a zero sum and in zero sum games; the minimax solution is the similar to the Nash equilibrium.

There is a minimax algorithm for game solutions in combinatorial game theory. With games like tic-tac-toe, simple version of the minimax algorithm is used where individual player can win, lose or end up in a draw. Minimax algorithm is considered to be a recursive algorithm in choosing the next move in a game which usually has two players participating in a game.

Combinatorial Game Theory

It is associated with a value for each position or state of the game and the value is computed by a position evaluation function, indicating how good it would be for a player to reach a particular position. The player on his part tends to make the maximum moves thereby minimizing the value of the position from the opponent’s following moves.

 An allocation method comprises of assigning a certain win for one play as +1 and for the other player as -1 which leads to combinatorial game theory developed by John Horton Conway. Using a rule is an alternative if the result of a move is an immediate win for one player, it is considered positive infinity and if it is an immediate win for the other player, then it is a negative infinity. Value of the first player of any other move is the minimum values resulting from each of the second players possible moves. Due to this the first player is called the maximizing player while the second player is called the minimizing player; hence it is given the name minimax algorithm.

Heuristic Evaluation Function 

This algorithm assigns a value of positive as well as negative infinity to any position since the value of every position will be the value of some final winning or losing position. Generally this is often possible at the end of a complicated game like chess because it is not feasible to know about the result before the completion of the game which could lead to one of the player winning.

We could extend this if we supply a heuristic evaluation function which gives values to non final game status without taking into account all possible following complete sequences and then limit the minimax algorithm to note only a certain number of moves coming up. The number is known the `look-ahead’, which is measured in `plies’. For instance, the chess computer `Deep Blue’ looked forward to at least 12 plies and then applied a heuristic evaluation function.