Minimise the loss,
Maximise the gain, then start,
All over again

Minimax is a basic adversarial search algorithm, therefore, in its base form it requires two or more players [2]. This algorithm searches through all possible game states assuming both players play optimally. One player looks to minimise the maximum score of the opponent, while the opponent looks to maximise its own score. This is where the name Minimax comes from.

With more complicated games it becomes infeasible to search all possible games states, for example, tic-tac-toe has a game tree size of 9! = 362,880 states which is feasible to traverse through; however, the Chess game tree has approximately 10¹⁵⁴ nodes which are infeasible to search through with modern computers [2]. When used for more complicated games Minimax is required to cut off its search at a given depth and evaluate the current game state returning the desirability of that state, the state with the best desirability for the Min player is then chosen.

A very similar algorithm to Minimax is coined Maximin, it is the exact same premise but instead of looking to minimise the opponents maximum it tries to maximise its own score while the opponent is trying to minimise the first player's score. This requires the same rules for the search it just changes what states are picked for the players.

Minimax has seen great success in use with perfect information two-player games such as tic-tac-toe and chess. In a zero-sum game minimax solution is the same as the Nash equilibrium.

Every board state in the tree has a value associated with it, these values are gathered by performing a static evaluation on the leaf nodes [6]. If the maximum player has the upper hand in a state the value will be positive and if the minimum player has the upper hand a negative value will be given to the state [3]. For example, in a chess game, a state where white has more pieces left on the board will have a high value if the maximum player is white.

The algorithm moves down the tree checking the value of the deepest nodes it is allowed to reach, recording that value and then applying it to the previous node depending on if the value is best for the player whose turn it is. Once all options have been explored in the tree the optimal plays for each player on their turn will be known.

Animated Example for the Minimax search algorithm in action, working through a two-player game with two moves for each player. From: https://upload.wikimedia.org/wikipedia/commons/e/e1/Plminmax.gif.

• One of the best search types for two person perfect information games [4]
• Can be enhanced with additions such as Alpha–Beta Pruning
• Robust at modelling uncertainties [5]

• Depth of search must be restricted for more complex games [2]
• Base form is restricted to adversarial games
• Assumes all players play optimally [3]

 def minimax(state):
    max_trans = None
    max_u = None
    transitions = possible_transitions(state, 'x')
    # Find the transition (move) that provides the maximum
    # utility, assuming the opponent also makes a best move
    for trans, nextstate in transitions.iteritems():
        # after making our move, find the best move the
        # opponent can make (best for opponent = worse for us;
        # if we consider the opponent winning as negative
        # utility, we want to find the minimum utility move
        # of the opponent's possible moves)
        u = min_utility(nextstate, 'o')
        if max_u is None or u > max_u:
            max_trans = trans
            max_u = u
    return max_trans

def min_utility(state, player):
    # if the current state is a win/loss/tie, stop searching
    if is_winning(state, player) or \
            is_winning(state, switch_player(player)) or \
            is_tie(state):
        return utility(state, 'x')
    else:
        transitions = possible_transitions(state, player)
        min_u = None
        for nextstate in transitions.values():
            # after making a move (current player is in the
            # "player" variable), find the minimum next
            # move and return its utility
            u = max_utility(nextstate, switch_player(player))
            if min_u is None or u < min_u:
                min_u = u
        return min_u

def max_utility(state, player):
    # if the current state is a win/loss/tie, stop searching
    if is_winning(state, player) or \
            is_winning(state, switch_player(player)) or \
            is_tie(state):
        return utility(state, 'x')
    else:
        transitions = possible_transitions(state, player)
        max_u = None
        for nextstate in transitions.values():
            # after making a move (current player is in the
            # "player" variable), find the maximum next
            # move and return its utility
            u = min_utility(nextstate, switch_player(player))
            if max_u is None or u > max_u:
                max_u = u
        return max_u 

Shows a base example of the Minimax structure. Code is from http://cse3521.artifice.cc [1]

Negamax is a variant of Minimax that works only for zero-sum two-player games. It uses the fact that the value of a position to player A in these games is the negation of the value to player B. For example player A having a value of 10 in a state, will mean that to player B that state is a value of -10. Because of this, it is possible to use a single procedure to value the state for both positions.

https://github.com/TMGilchrist/connect4/blob/master/MiniMaxScript.cs

[1] "Adversarial search", Cse3521.artifice.cc, 2019. [Online]. Available: http://cse3521.artifice.cc/adversarial-search.html. [Accessed: 14- Feb- 2019].
[2] G. Yannakakis and J. Togelius, "Artificial intelligence and games.", Springer International Publishing, 2018.
[3] "Minimax Algorithm in Game Theory | Set 1 (Introduction) - GeeksforGeeks", GeeksforGeeks, 2019. [Online]. Available: https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/. [Accessed: 14- Feb- 2019].
[4] A. Scheucher, "The Reason for the Benefits of Minimax Search.", Citeseer.
[5] S. Verdu and H. Poor, "On minimax robustness: A general approach and applications", IEEE Transactions on Information Theory, vol. 30, no. 2, pp. 328-340, 1984. Available: 10.1109/tit.1984.1056876.
[6] S. Lague, Algorithms Explained – minimax and alpha-beta pruning. 2018.