AIOJ

Prerequisite knowledge: Introduction to Game Theory

This article discusses the two-player zero-sum game.

In a zero-sum game, the sum of the two players' payoffs is always zero, so one player's gain necessarily means a loss for the other. A zero-sum game can be viewed as a special case of a constant-sum game. Conversely, any constant-sum game can be converted equivalently into a zero-sum game by adding or subtracting a constant from one player's payoff, so it suffices to discuss zero-sum games.

In algorithm competitions, common zero-sum games can roughly be divided into sequential zero-sum games and simultaneous zero-sum games.

Sequential Zero-Sum Games

In a sequential zero-sum game, the two players take turns acting until the game ends.

The payoff function of a sequential zero-sum game has a recursive structure. A game state $S$ can be divided into three types: terminal states $S_0$ , states $S_1$ where player $1$ acts, and states $S_2$ where player $2$ acts. Suppose that at a terminal state $s\in S_0$ , player $1$ receives $v(s)$ and player $2$ receives $-v(s)$ . Therefore, when it is player $2$ 's turn, maximizing that player's payoff is equivalent to minimizing player $1$ 's payoff. If both players use optimal strategies, the maximum payoff player $1$ can obtain at state $s\in S$ , denoted by $V(s)$ , satisfies the following recurrence:

V(s) = \begin{cases} v(s), & s \in S_0,\\ \max_{t\in s} V(t), & s\in S_1,\\ \min_{t\in s} V(t), & s\in S_2. \end{cases}

Here, $t\in s$ means that $t$ is a successor state of $s$ . This is the minimax principle.

When applying this algorithm to an actual problem, the following approaches are common:

If the game has only a small number of states, implement the algorithm by brute force.
If the game has many states and no special structure, consider Alpha–Beta pruning together with other search-pruning methods.
If a single game state is often the successor of multiple states, use memoized search or another dynamic-programming algorithm to avoid repeated searches.
If a player's final payoff is the sum of the payoffs of all actions before the game ends, the model can be optimized. Specifically, suppose that at terminal state $s\in S_0$ , player $i=1,2$ takes the action sequence $\{a^{(i)}_j\}_{j=1}^{k_i}$ , action $a$ has payoff $w(a)$ , and player $1$ 's payoff function is
$v(s) = \sum_{j=1}^{k_1}w(a_j^{(1)}) - \sum_{j=1}^{k_2}w(a_j^{(2)}).$
Let $\tilde V(s)$ be the maximum score the player to move can obtain in the game after state $s\in S$ . For the initial state $s_0$ , $V(s_0)=\tilde V(s_0)$ , so finding $\tilde V(\cdot)$ is enough to solve the original problem. For $\tilde V(\cdot)$ , the recurrence is:
$\tilde V(s) = \begin{cases} 0, & s \in S_0, \\ \max_{t\in s} w(a_{s\to t}) - \tilde V(t), & s\in S_1\cup S_2. \end{cases}$
Here, $a_{s\to t}$ is an action that moves the state from $s$ to $t$ . If several such actions exist, choose the one with the largest payoff $w(a)$ .
Every impartial combinatorial game is a sequential zero-sum game; assign payoffs $+1$ and $-1$ to the winning and losing sides. The recurrence for $V(\cdot)$ is then exactly the lemma for deciding winning and losing states.

A common variant asks for the minimum number of turns needed by the winner and the maximum number of turns for which the loser can survive. When BFS is started from terminal states and the lemma is used to classify states, record the BFS round in which each winning or losing state is classified; these are the required turn counts. A winning state needs only one losing successor, so it is reached from the losing successor with the smallest round number. A losing state requires all successors to be winning, so it is reached from the winning successor with the largest round number.

The same method extends to general directed-graph games.

Example

Codeforces 794 E. Choosing Carrot

Given a sequence ${a_i}$ of length $n$ , two players $1$ and $2$ alternately remove a number from one of its ends until only one number remains. Player $1$ wants to maximize the remaining number, while player $2$ wants to minimize it. Before the game officially starts, player $1$ may make $k$ moves first. Assuming both players use optimal strategies throughout, find the final remaining number for every $k = 0,1,2,\cdots,n-1$ . Here, $1 \le n \le 3\times 10^5$ .

Solution

Regardless of how the players remove numbers, the remaining sequence is always a contiguous interval. Thus a game state is fully described by this interval $[l,r]$ and the player $i=1,2$ whose turn it is, so dynamic programming applies. Let $f(l,r,i)$ be the final remaining number for the state $(l,r,i)$ . As discussed above, when $l < r$ it satisfies:

\begin{aligned} f(l,r,1) &= \max\{f(l+1,r,2),f(l,r-1,2)\},\\ f(l,r,2) &= \min\{f(l+1,r,1),f(l,r-1,1)\}. \end{aligned}

The terminal condition is $f(l,l,1)=f(l,l,2) = a_l$ . Therefore all possible states can be evaluated in $\Theta(n^2)$ time. For each $k$ , the answer is

g(k) = \max f(l,r,1) \text{ subject to } r - l + 1 = k.

This algorithm is too slow for the constraints of the original problem, so we need to optimize the transitions. There are several ways to do this; we present only one.

View the transitions as operations on the whole sequence. The two recurrences replace each pair of adjacent numbers by its maximum or minimum; call them the maximization operation and the minimization operation, respectively. Each operation decreases the sequence length by one. There are $(n-d+1)$ intervals of length $d$ , corresponding to the sequence obtained after $(d-1)$ operations. To obtain $f(l,r,1)$ , the last operation must be a maximization operation, so every relevant operation sequence ends with maximization.

Consider the effect of two consecutive operations. Suppose the minimization operation is performed first, followed by maximization. The three numbers $a_1,a_2,a_3$ become

\max\{\min\{a_1,a_2\},\min\{a_2,a_3\}\}.

Examining all possible relative orders of $a_1,a_2,a_3$ shows that this expression equals $a_2$ except when $a_1 < a_2$ and $a_2 > a_3$ , that is, when $a_2$ is a strict local maximum. In other words, if a sequence has no strict local maximum, two consecutive operations only remove one element from each end. This greatly simplifies the transitions. The remaining question is how to ensure that the sequence has no strict local maximum. A single maximization operation is enough to guarantee this. Therefore, this results after an even number of operations can be obtained by applying two operations to the initial sequence and then repeatedly removing one element from each end; results after an odd number of operations are obtained by applying one operation and then repeatedly removing one element from each end.

The complete sequence needs at most $3$ operations, and the subsequent answer collection takes only $2$ passes, so the total time complexity is $\Theta(n)$ .

this concept

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int& x : a) std::cin >> x;
  std::vector<int> ans(n), tmp;
  tmp = a;
  for (int i = 0; i < n - 1; ++i) {
    tmp[i] = std::max(tmp[i], tmp[i + 1]);
  }
  for (int l = n / 2 - 1, r = (n - 1) / 2, ma = 0; l >= 0; --l, ++r) {
    ma = std::max({ma, tmp[l], tmp[r]});
    ans[r - l] = ma;
  }
  tmp = a;
  for (int i = 0; i < n - 1; ++i) {
    tmp[i] = std::min(tmp[i], tmp[i + 1]);
  }
  for (int i = 0; i < n - 2; ++i) {
    tmp[i] = std::max(tmp[i], tmp[i + 1]);
  }
  for (int l = (n - 3) / 2, r = n / 2 - 1, ma = 0; l >= 0; --l, ++r) {
    ma = std::max({ma, tmp[l], tmp[r]});
    ans[r - l] = ma;
  }
  ans[n - 1] = *std::max_element(a.begin(), a.end());
  for (auto x : ans) std::cout << x << ' ';
  std::cout << std::endl;
  return 0;
}

Exercises

Simultaneous Zero-Sum Games

In a simultaneous zero-sum game, the two players act at the same time.

A simultaneous zero-sum game is usually represented by a payoff matrix. Let player $i=1,2$ have action set $A_i$ . If players $i=1,2$ choose $a_i\in A_i$ , their payoffs are $v(a_1,a_2)$ and $-v(a_1,a_2)$ , respectively.

Example

Consider rock–paper–scissors. Suppose a win is worth $1$ , a loss is worth $-1$ , and a draw is worth $0$ . The two players' payoffs can then be written as

\begin{pmatrix} 0,0 & 1,-1 & -1,1 \\ -1,1 & 0,0 & 1,-1 \\ 1,-1 & -1,1 & 0,0 \end{pmatrix}.

A general two-player simultaneous game can be represented in the same form and is therefore also called a bimatrix game. In a zero-sum game, player $1$ 's payoff matrix is the negative of player $2$ 's, so it is enough to consider player $1$ 's payoff matrix:

V = (v(a_1,a_2))_{(a_1,a_2)\in A_1\times A_2} = \begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}.

The problem is: given the payoff matrix $V = (v(a_1,a_2))_{(a_1,a_2)\in A_1\times A_2}$ , how can we find the optimal strategies and maximum payoffs of the two players?

Mixed Strategies

In contrast to sequential zero-sum games, the roles of the two players in a simultaneous game are symmetric. Since we have already solved the sequential version, suppose first that player $1$ acts before player $2$ . Then, by the preceding discussion, player $1$ 's payoff at the end of the game is

w_-=\max_{a_1\in A_1}\min_{a_2\in A_2} v(a_1,a_2)

This is the worst payoff player $1$ can obtain because player $2$ can observe player $1$ 's action. Conversely, if player $2$ acts first, player $1$ 's payoff is

w_+ = \min_{a_2\in A_2}\max_{a_1\in A_1} v(a_1,a_2)

This is the best payoff player $1$ can obtain because player $2$ 's action is visible to player $1$ . Thus player $1$ should expect a payoff $w\in[w_-,w_+]$ in the actual simultaneous game. Although $w_-\le w_+$ always holds (see the proof of the weak duality theorem), equality need not hold, so the sequential-game analysis generally cannot determine a unique outcome.

Continuing the example

In rock–paper–scissors, if the two moves are made in sequence, the first player always loses and the second player always wins. In mathematical terms, this is

w_- = -1 \le +1 = w_+.

Here, $w_-\neq w_+$ , so the two bounds are not equal.

The preceding analysis missed a key feature of simultaneous games: a player cannot accurately predict the opponent's action. Formally, this means that both players may use randomized strategies. This idea does not help in a sequential game, because the second player can always observe the first player's action and respond accordingly. In a simultaneous game, however, the strategic uncertainty introduced by randomization prevents the opponent from targeting a specific action effectively.

Continuing the example

In rock–paper–scissors, suppose player $0$ chooses rock, paper, or scissors uniformly at random. Depending on player $2$ 's action, player $1$ 's possible expected payoffs are

\dfrac{1}{3}(0,1,-1)^T + \dfrac{1}{3}(-1,0,1)^T + \dfrac{1}{3}(1,-1,0)^T = (0,0,0)^T.

Thus player $1$ 's expected payoff is always $1$ , regardless of player $2$ 's action. This is clearly better than committing to a single deterministic action.

This motivates the definition of a mixed strategy.

Mixed Strategy

In a simultaneous game, a mixed strategy for player $\Delta(A_i)$ is a function $s_i:A_i\to[0,1]$ satisfying $\sum_{a_i\in A_i}s_i(a_i)=1$ . In other words, $s_i$ is a probability distribution on the action set $A_i$ . The set of all mixed strategies for player $i$ is denoted by $i$ ; here, $S_i=\Delta(A_i)$ denotes the set of all probability distributions on $A_i$ . For player $i$ , if $s_i$ is a degenerate distribution, meaning that some $a\in A_i$ satisfies $s_i(a)=1$ , then $s_i$ is called a pure strategy.

The payoff of mixed strategies is the expected payoff of a single pair of actions:

v(s_1,s_2) = \sum_{a_1\in A_1}\sum_{a_2\in A_2}s_1(a_1)s_2(a_2)v(a_1,a_2).

If each individual action is viewed as the corresponding pure strategy, the action set $A_i$ can be embedded in the (mixed) strategy set $S_i$ . The expression $v(s_1,s_2)$ above can then be viewed as extending $v(a_1,a_2)$ from $A_1\times A_2$ to $S_1\times S_2$ .

von Neumann's Theorem

After mixed strategies are introduced, the maximin and minimax values agree, so the outcome of a simultaneous zero-sum game is uniquely determined.

Theorem (von Neumann)

In a simultaneous zero-sum game with mixed strategies, if both players use optimal strategies, player $1$ 's maximum payoff is

w = \max_{s_1\in S_1}\min_{s_2\in S_2} v(s_1,s_2) = \min_{s_2\in S_2}\max_{s_1\in S_1} v(s_1,s_2),

and player $2$ 's maximum payoff is $-w$ .

Proof

Let $w = \max_{s_1\in S_1}\min_{s_2\in S_2} v(s_1,s_2)$ . For the inner minimization, $v(s_1,s_2)=\sum_{a_2\in A_2}s_2(a_2)v(s_1,a_2)$ , so $\max_{s_2\in S_2}v(s_1,s_2)=\max_{a_2\in A_2}v(s_1,a_2)$ ; an optimal solution is the corresponding pure strategy. Therefore $w = \max_{s_1\in S_1}\min_{a_2\in A_2} v(s_1,a_2)$ . Introducing an auxiliary variable $u$ , rewrite this as

w = \max_{s_1\in S_1} u \text{ subject to }u \le \min_{a_2\in A_2} v(s_1,a_2).

The constraint is equivalent to $u\le v(s_1,a_2)$ for every $a_2\in A_2$ . Substituting the definition of the mixed strategy $s_1$ and the payoff function $v(s_1,a_2)$ , the problem is equivalent to the linear program

(P) \qquad \begin{aligned} w = \max_{u,s_1}\; & u\\ \text{subject to }& \sum_{a_1\in A_1}s_1(a_1)v(a_1,a_2) \ge u,~\forall a_2\in A_2,\\ & \sum_{a_1\in A_1}s_1(a_1) = 1,\\ & s_1(a_1) \ge 0,~\forall a_1\in A_1. \end{aligned}

This problem is feasible and has an optimum. By the duality principle, its optimum equals that of the dual problem:

(D) \qquad \begin{aligned} w = \min_{t,s_2}\; & t\\ \text{subject to }&\sum_{a_2\in A_2}s_2(a_2)v(a_1,a_2) \le t,~\forall a_1\in A_1,\\ &\sum_{a_2\in A_2}s_2(a_2) = 1,\\ &s_2(a_2)\ge 0,~\forall a_2\in A_2. \end{aligned}

Repeating the preceding steps, this problem is equivalent to $\min_{s_2\in A_2}\min_{s_1\in S_1}v(s_1,s_2)$ . The theorem follows.

This result is precisely the Nash equilibrium of the game. If both players choose optimal strategies in the equilibrium, neither player can gain strictly by deviating from the equilibrium strategy.

Reduction to Linear Programming

The proof of von Neumann's theorem also gives a way to solve simultaneous zero-sum games. Let $n$ and $m$ be the numbers of actions available to players $1$ and $2$ , respectively. Given player $1$ 's payoff matrix $V\in\mathbf R^{n\times m}$ , solve the following linear program:

\begin{aligned} w = \max_{(u,s)\in\mathbf R\times\mathbf R^n}\; & u\\ \text{subject to }& V^Ts \ge u\mathbf 1,\\ & \mathbf 1^Ts = 1,\\ & s \ge 0. \end{aligned}

This is a linear program of size $\Theta(n+m)$ and can be solved efficiently with the simplex method. The optimal solution $s$ returned by the algorithm is player $1$ 's optimal mixed strategy. To obtain player $2$ 's optimal strategy, read the dual variables (the shadow prices) of the optimal solution from the simplex tableau.

Exercises

Luogu P4232 Hide and Seek Outside Consciousness

Zero-Sum Game

Sequential Zero-Sum Games

Example

Exercises

Simultaneous Zero-Sum Games

Mixed Strategies

von Neumann's Theorem

Reduction to Linear Programming

Exercises

References and Notes