Minimax is a backtracking algorithm used in decision-making and game theory to determine the best move for a player, provided that your opponent also plays optimally. It is commonly employed in two-player turn-based games like Tic-Tac-Toe, Backgammon, Mancala, and Chess.

Minimax is a decision rule used in AI, decision theory, game theory, statistics, and philosophy to minimise the potential loss in the worst-case (maximum loss) scenario. When dealing with gains, it is referred to as "maximin" – to maximise the lowest gain. Initially developed for several-player zero-sum game theory, it has been extended to more complicated games and general decision-making under uncertainty.

Game theory

The two participants in Minimax are referred to as the maximizer and minimizer. The maximizer strives to achieve the maximum score, whereas the minimizer seeks to achieve the lowest score. A value accompanies each board state. If the maximizer has the upper hand in a particular situation, the board score will typically be positive. In that board condition, if the minimizer has the advantage, it will typically be some negative number. 

Pseudo-code

function minimax( node, depth, maximizingPlayer ) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max( value, minimax( child, depth − 1, FALSE ) )
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min( value, minimax( child, depth − 1, TRUE ) )
        return value

Operation

We can explain the minimax algorithm's functioning with an example. An example of a game tree that illustrates a two-player game is shown below.

• In this example, there are two players named Maximizer and Minimizer.
• Maximizer will strive for the highest possible score, while Minimizer will aim for the lowest possible score.
• This algorithm employs DFS. Hence to reach the terminal nodes in this game tree, we must traverse all the leaves.
• At the terminal node, the terminal values are provided. Therefore we will compare these values and traverse the tree in reverse till we reach the original state.

Properties

• The Min-Max algorithm is complete. It will almost certainly find a solution (if one exists) in the finite search tree.
• If both opponents are playing optimally, the Min-Max algorithm is optimal.
• Time complexity- Because it performs DFS for the game tree, the time complexity of the Min-Max algorithm is O(bm), where b is the game-branching tree's factor and m is the tree's maximum depth.
• Space Complexity- The Mini-max algorithm has the same space complexity as DFS, which is O. (bm).

Conclusion

Minimax decision-making is non-probabilistic: unlike decisions based on expected value or utility, it makes no assumptions about the likelihood of alternative outcomes, instead relying on scenario analysis of the possible results. In contrast to these other choice approaches, it is hence resistant to changes in assumptions. Other adaptations to this non-probabilistic method include minimax regret and Info-gap decision theory.

Furthermore, the fundamental disadvantage of the minimax algorithm is that it becomes prolonged while playing complex games like chess, go, and so on. This game style features a high branching factor, giving the player numerous options. The minimax algorithm's drawback can be overcome by alpha-beta pruning.