Credit: BecomingHuman

**Minimax**, as the name suggest, is a method in decision theory for minimizing the maximum loss. Alternatively, it can be thought of as maximizing the minimum gain, which is also know as** Maximin**.

It all started from a *two player zero-sum *game theory, covering both the cases where players take alternate moves and those where they made simultaneous moves. It has also been extended to more complex games and to general decision making in the presence of uncertainty.

#### Top 4 Most Popular Ai Articles:

1. Deep learning for sensor-based human activity recognition

2. How to build a deep learning server based on Docker

3. Transfer Learning: retraining Inception V3 for custom image classification

4. How ethical is Artificial Intelligence?

### Zero-sum

In the above explanation, it has been mentioned that the *minimax* algorithms started off with the concept of zero-sum. Well then, what is zero-sum?

Zero sum games are a special case of constant sum of games, in which choices by players can neither increase nor decrease the available resources. In zero-sum games the total benefit to all players in the game, for every combination of strategies, always adds to zero(more informally, a player benefits only at the expense of the other).

Poker exemplifies a zero-sum, because one wins exactly the same amount one’s opponents lose.

### Non-Zero-Sum

Many games studied by game theorists are non-zero-sum games, because of some outcomes have net results greater or less than zero.

Informally, in non-zero-sum games, a gain by one player does not necessarily correspond with a loss by another.

“*Maximin*” is a term commonly used for non-zero-sum games to describe the strategy which maximizes one’s own minimum payoff.

Now, getting back to the minimax algorithm

The minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game.

- A value is associated with each position or state of the game.
- This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position.
- The player then makes the move that maximizes the minimum value of the position results from the opponent’s possible following moves.
- If it is A’s turn to move, A gives a value to each of his legal moves.

Pseudo-code of Minimax is as follows:

function minimax(node,depth)

if node is a terminal node or depth = 0

return the heuristic value of node

if the adversary is to play at node

let beta := +∞

for each child of node

beta:=min(beta,minimax(child,depth+1))

return beta

else {we are to play at node}

let alpha := -∞

for each child of node

alpha:=max(alpha,minimax(child,depth+1))

return alpha

Suppose the game being played only has a maximum of two possible moves per player each turn. The algorithm generates the tree below, where the circles represent the moves of the player running the algorithm(maximizing player), and squares represent the moves of the opponent(minimizing player). Because of the limitation of computation resources, the tree is limited to a look-ahead of 4 moves

### Alpha-Beta Pruning

The minimax algorithm is a way of finding an optimal move in a two player game. Alpha-beta pruning is a way of *finding the optimal minimax solution while avoiding searching subtrees of moves which won’t be selected*. In the search tree for a two-player game, there are two kinds of nodes, nodes representing your moves and nodes representing your opponent’s moves. Nodes representing your moves are generally drawn as squares (or possibly upward pointing triangles):

These are also called **MAX nodes**. The goal at a MAX node is to maximize the value of the subtree rooted at that node. To do this, a MAX node chooses the child with the greatest value, and that becomes the value of the MAX node.

Nodes representing your opponent’s moves are generally drawn as circles (or possibly as downward pointing triangles):

These are also called **MIN nodes**. The goal at a MIN node is to minimize the value of the subtree rooted at that node. To do this, a MIN node chooses the child with the least (smallest) value, and that becomes the value of the MIN node.

Alpha-beta pruning gets its name from two bounds that are passed along during the calculation, which restrict the set of possible solutions based on the portion of the search tree that has already been seen. Specifically,

### Beta is the minimum upper bound of possible solutions

### Alpha is the maximum lower bound of possible solutions

Thus, when any new node is being considered as a possible path to the solution, it can only work if:

where N is the current estimate of the value of the node.

To visualize this, we can use a number line. At any point in time, alpha and beta are lower and upper bounds on the set of possible solution values, like so:

As the problem progresses, we can assume restrictions about the range of possible solutions based on min nodes (which may place an upper bound) and max nodes (which may place a lower bound). As we move through the search tree, these bounds typically get closer and closer together:

This convergence is not a problem as long as there is some overlap in the ranges of alpha and beta. At some point in evaluating a node, we may find that it has moved one of the bounds such that there is no longer any overlap between the ranges of alpha and beta:

At this point, we know that this node could never result in a solution path that we will consider, so we may stop processing this node. In other words, we stop generating its children and move back to its parent node. For the value of this node, we should pass to the parent the value we changed which exceeded the other bound.

To demonstrate minimax with alpha-beta pruning, we use the following minimax tree as an example:

Credit: BecomingHuman By: Hemant Rakesh