Adversarial Search

Minimax

In Game Theory, minimax is a decision rule used to minimize the worst-case potential loss.

The value for a particular state is given by $v_i(s)={\max }_{a_i}{\min }_{a_{-i}}{v}_i(a_i,a_{-i})$

• $i$ is the index of the player of interest
• $-i$ denotes all other players except player $i$
• $a_i$ is the action taken by player $i$
• $a_{-i}$ denotes the actions taken by all other players
• $v_i$ is the value function of player $i$

This value function for player $i$ is calculated in a worst-case approach: player $i$ considers the best opponent responses to his strategies (who tries to minimize), and selects the strategy such that the opponent’s best strategy gives a payoff as large as possible (i.e. maximize).

Serendipity I also see this in F1TENTH. This is the most common framework in adversarial settings. ohh so CFR is the minimax version for Imperfect Information games!

A side note on “Expectiminimax”

Actually, you can have chance events and still be Perfect Information, such as Backgammon. You run the expectiminimax algorithm, which simply takes the expected value of the chance nodes, see walkthrough example here.

Representation + Implementation

Minimax represents winning conditions as (-1) for one side and (+1) for the other side. We implement a minimax algorithm by doing Depth-First Search.

To explain this to people, you sort of need to reason backwards with them.

Good article: https://philippmuens.com/minimax-and-mcts

Also, when we refer to minimax, we often refer to the Depth-Limited version of minimax, since most games are already too big to traverse the entire game tree.

Pseudocode

This is for the Depth-Limited Search version.

```py
def minimax(state, max_depth, is_player_minimizer):
    if max_depth == 0 or state.is_end_state():
        # We're at the end. Time to evaluate the state we're in
        return evaluation_function(state)
 
    # Is the current player the minimizer?
    if is_player_minimizer:
        value = -math.inf
        for move in state.possible_moves():
            evaluation = minimax(move, max_depth - 1, False)
            min = min(value, evaluation)
        return value
 
    # Or the maximizer?
    value = math.inf
    for move in state.possible_moves():
        evaluation = minimax(move, max_depth - 1, True)
        max = max(value, evaluation)
    return value

The minimax function returns a heuristic value for leaf nodes (terminal nodes and nodes at the maximum search depth).

Random

In two-player zero-sum games, the minimax solution is the same as the Nash Equilibrium.

Ahh this explains: “In perfect-information games, the value that is substituted at a leaf node of a depth-limited subgame is simply an estimate of the state’s value when all players play an equilibrium”.

Next

Depth-Limited Minimax is still not enough. We can optimize even more. See Alpha-Beta Pruning.