# 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.

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.