Teoría de juegos

Nim

Reglas

Nim es quizás uno de los ejemplos más conocidos de teoría de juegos. En este juego se consideran $n$ pilas de algún ítem. El problema usa palitos, mientras que otros usan piedras; usaremos palitos para ser consistentes con el problema de CSES. En cualquier caso, los jugadores se turnan para quitar una cantidad no nula de palitos de una pila determinada, y el jugador que toma el último palito gana.

Representemos el estado actual de las pilas con $[x_1, x_2, x_3, \ldots, x_n]$, donde $x_i$ es el número de palitos en la pila $i$. Pronto se verá que no importa si incluimos pilas vacías en nuestro arreglo.

Ahora proponemos algo que al principio puede parecer poco intuitivo:

El jugador que mueve primero siempre puede ganar si la xor-suma de los tamaños de las pilas es distinta de cero.

Demostración

Por nuestra propia sanidad, llamaremos “estado perdedor” a un estado con xor-suma $0$ y “estado ganador” a un estado con xor-suma distinta de cero.

Para demostrarlo, tenemos que mostrar que desde un estado perdedor, cualquier movimiento que hagamos resultará en un estado ganador, y desde un estado ganador, al menos un movimiento que podemos hacer resultará en un estado perdedor. Observar que cuando hacemos nuestro movimiento, el juego pasa a un “subjuego” en el que el segundo jugador se convierte en el primero. Así, moverse a un estado ganador para el siguiente turno significa que ellos ganan y nosotros perdemos.

Sin embargo, es bueno demostrar primero los casos base. $[0]$ es un estado perdedor, ya que el primer jugador no puede hacer ningún movimiento y por lo tanto pierde. Por otro lado, $[x]$ donde $x$ es cualquier entero positivo es un estado ganador, ya que podemos tomar $x$ palitos de la única pila. Como se ve, el primer estado tiene xor-suma $0$ mientras que el segundo tiene xor-suma $x$, que es distinta de cero.

Perdedor $\rightarrow$ Ganador

Demostremos primero que cualquier estado perdedor se moverá a un estado ganador para el otro jugador.

Como XOR es una operación conmutativa y asociativa, podemos asumir sin pérdida de generalidad que el movimiento que hacemos es sobre la pila $1$.

La xor-suma actual del estado es $x_1 \oplus x_2 \oplus \dots x_n=0$. Observar que esto se puede pensar como $x_1$ XOR la xor-suma del resto de los números. Llamemos $y$ a esa xor-suma de todo lo demás.

Como la xor-suma es $0$, $x_1=y$. Quitar cualquier número de palitos de $x_1$ romperá esta igualdad y hará $x_1 \oplus y$ distinto de cero, que es precisamente la definición de nuestro estado ganador.

Ganador $\rightarrow$ Perdedor

Ahora tenemos que demostrar que cualquier estado ganador puede moverse a un estado perdedor para el otro jugador. Observar el uso de puede en lugar de va a en nuestro enunciado, por cómo funcionan estos juegos.

Esta vez, definimos $y$ como la xor-suma de todas las pilas en lugar de todas excepto una. Entonces, digamos que tenemos un $x_i$ tal que $x_i > y \oplus x_i$. Observar que $y \oplus x_i$ es la xor-suma de todos los demás elementos, ya que XOR es su propia inversa.

Con esto, podemos tomar $x_i - (y \oplus x_i)$ palitos de $x_i$, lo que lo hace equivalente a $y \oplus x_i$ y la xor-suma de todo el tablero será $0$, formando así un estado perdedor para el segundo jugador.

Pero todo esto depende de la existencia de un $x_i$ tal que $x_i > y \oplus x_i$. ¿Existe siempre?

Supongamos que $p$ es la posición del bit más significativo de $y$. Entonces, sabemos que debe existir algún $x_i$ con un bit activado también en $p$. Ya sea que $p$ sea o no el bit más significativo de $x_i$, al hacer XOR de los dos se obtiene un resultado con un $0$ en el bit $p$. Esto garantiza que existe un $x_i > y \oplus x_i$.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int pile_num;
		std::cin >> pile_num;
		vector<int> piles(pile_num);
		for (int &p : piles) { std::cin >> p; }
 
		int xor_sum = 0;
		for (int p : piles) { xor_sum ^= p; }
 
		cout << (xor_sum != 0 ? "first" : "second") << '\n';
	}
}

import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			int pileNum = Integer.parseInt(read.readLine());
			StringTokenizer pileST = new StringTokenizer(read.readLine());
			int[] piles = new int[pileNum];
			for (int p = 0; p < pileNum; p++) {
				piles[p] = Integer.parseInt(pileST.nextToken());
			}
 
			int xorSum = 0;
			for (int p : piles) { xorSum ^= p; }
 
			System.out.println(xorSum != 0 ? "first" : "second");
		}
	}
}

for _ in range(int(input())):
	pile_num = int(input())
	sizes = [int(p) for p in input().split()]
	assert pile_num == len(sizes)
 
	xor_sum = 0
	for s in sizes:
		xor_sum ^= s
 
	print("first" if xor_sum != 0 else "second")

Teorema de Sprague-Grundy

Antes de entrar en este teorema, primero tenemos que definir qué son los “nimbers” (a veces llamados “valores de Grundy”). Cada nimber — por ejemplo 0, 3 o 4 — representa un juego de Nim de una sola pila con esa cantidad de piedras. Observar que para cualquier nimber positivo, el primer jugador siempre gana, ya que puede tomar todas las piedras de la pila y no dejar ninguna para el segundo. Por otro lado, el nimber 0 es un estado perdedor, ya que el primer jugador no puede tomar más piedras.

Lo que el teorema de Sprague-Grundy nos permite hacer es reducir el estado de ciertos tipos de juegos a un nimber.

La forma de hacerlo es con una definición recursiva. Si podemos calcular los nimbers de todos los estados $r_i$ alcanzables desde un cierto estado $s$, entonces $s$ mismo se puede reducir al nimber

Por conveniencia, hemos definido $n$ como la función que reduce estados de juego a nimbers.

La función $\text{mex}$ toma una lista de números y devuelve el menor entero no negativo que no está incluido en la lista. Observar que el nombre es un acrónimo de “min” y “excluded” (mínimo excluido).

Ejemplo de una pila

Veamos una versión alterada de Nim. Aquí hay solo una pila, pero cada jugador solo puede quitar 1, 2 o 3 piedras.

Según el teorema, el valor del nimber es el $\text{mex}$ de los valores de nimber alcanzables. En el caso de este juego, cada estado puede alcanzar los $3$ valores anteriores porque solo podemos quitar 1, 2 o 3 piedras en un movimiento.

Así se calculan los valores:

• $n(0) = 0$
• $n(1) = \text{mex}(0) = 1$
• $n(2) = \text{mex}(0, 1) = 2$
• $n(3) = \text{mex}(0, 1, 2) = 3$
• $n(4) = \text{mex}(1, 2, 3) = 0$
• $n(5) = \text{mex}(2, 3, 0) = 1$
• $n(6) = \text{mex}(3, 0, 1) = 2$
• $n(7) = \text{mex}(0, 1, 2) = 3$

Esto nos da la siguiente tabla de valores de nimber:

Aquí está la tabla de valores de nimber:

Todas las reducciones a nimber que son iguales a 0 son estados perdedores; ver $n(0)$ y $n(4)$.

Recordar que un estado ganador significa que se puede poner al otro jugador en un estado perdedor. Por otro lado, un estado perdedor significa que cada movimiento resulta en un estado ganador para el oponente. Por ejemplo, $n(4)=0$ porque $1$, $2$ y $3$ son ganadores. De forma similar, $n(8) = 0$, porque no podemos alcanzar $4$ en un solo movimiento.

Ejemplo de varias pilas

¿Qué tal si intentamos reducir juegos de Nim de varias pilas con este teorema?

Sabemos que un estado es perdedor si la xor-suma es 0. Esto encaja exactamente con cómo funcionan nuestros nimbers, ya que el nimber 0 representa un estado perdedor.

Así, para reducir un juego de Nim de varias pilas a un nimber, podemos tomar la xor-suma de los nimbers de las pilas individuales. Observar que el nimber de una sola pila es el tamaño de la pila.

Esto es equivalente a la fórmula usando mex , pero una demostración de eso está fuera del alcance de este módulo. Solo intentamos dar alguna intuición de por qué es cierto.

Esta reducción por xor-suma se puede extender a más cosas que solo Nim. Si podemos descomponer un juego en varias partes disjuntas donde un jugador elige un subjuego y luego hace un movimiento, entonces los nimbers de estos juegos se pueden combinar con la xor-suma.

Aplicaciones

S-Nim

Explicación

Podemos calcular los valores de nimber de cada pila con la definición de mex y luego combinarlos usando el operador XOR.

Implementación

Complejidad temporal: $\mathcal{O}(PK+ML)$, donde $P$ es el tamaño máximo de pila.

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
const int MAX_PILE = 1e4;
 
int main() {
	int move_num;
	std::cin >> move_num;
	vector<int> can_remove(move_num);
	for (int &n : can_remove) { std::cin >> n; }
 
	vector<int> nimbers(MAX_PILE + 1);
	for (int i = 1; i <= MAX_PILE; i++) {
		std::set<int> reachable;
		for (int n : can_remove) {
			if (i - n >= 0) { reachable.insert(nimbers[i - n]); }
		}
 
		for (int n = 0; n <= MAX_PILE; n++) {
			if (!reachable.count(n)) {
				nimbers[i] = n;
				break;
			}
		}
	}
 
	int game_num;
	std::cin >> game_num;
	vector<char> wins(game_num);
	for (int g = 0; g < game_num; g++) {
		int pile_num;
		std::cin >> pile_num;
 
		int xor_sum = 0;
		for (int p = 0; p < pile_num; p++) {
			int pile;
			std::cin >> pile;
			xor_sum ^= nimbers[pile];
		}
 
		wins[g] = xor_sum == 0 ? 'L' : 'W';
	}
 
	for (const char &w : wins) { cout << w; }
	cout << endl;
}

MAX_PILE = 10**4
 
can_remove = [int(i) for i in input().split()][1:]
 
nimbers = [0 for _ in range(MAX_PILE + 1)]
for i in range(1, MAX_PILE + 1):
	reachable = {nimbers[i - n] for n in can_remove if i - n >= 0}
	for n in range(MAX_PILE + 1):
		if n not in reachable:
			nimbers[i] = n
			break
 
wins = []
for _ in range(int(input())):
	piles = [int(i) for i in input().split()][1:]
 
	xor_sum = 0
	for p in piles:
		xor_sum ^= nimbers[p]
 
	wins.append("L" if xor_sum == 0 else "W")
 
print("".join(wins))

Chessboard Game, Again!

Explicación

Aquí vemos un caso de usar la xor-suma para combinar cosas que no son directamente juegos de Nim.

En este problema, podemos descomponer cada juego en un montón de subjuegos, donde cada subjuego es una sola moneda. Los jugadores eligen el subjuego (moneda) y luego hacen un movimiento.

Primero aplicamos la fórmula de mex para calcular nimbers de monedas individuales, y luego los combinamos al final con una xor-suma

Implementación

Complejidad temporal: $\mathcal{O}(TK)$, ya que el tablero es de tamaño constante.

#include <iostream>
#include <map>
#include <set>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
const int BOARD_LEN = 15;
 
/** @return The nimber value of a coin at a single position. */
int nimber(int r, int c) {
	static std::map<std::pair<int, int>, int> cache;
	if (cache.count({r, c})) { return cache[{r, c}]; }
 
	if (r < 0 || BOARD_LEN <= r || c < 0 || BOARD_LEN <= c) {
		return -1;  // return -1 to not interfere with the mex operations
	}
 
	std::set<int> reachable{nimber(r - 2, c + 1), nimber(r - 2, c - 1),
	                        nimber(r + 1, c - 2), nimber(r - 1, c - 2)};
 
	int ret = 0;
	while (reachable.count(ret)) { ret++; }
 
	return cache[{r, c}] = ret;
}
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int coin_xor = 0;
		int coin_num;
		std::cin >> coin_num;
		for (int i = 0; i < coin_num; i++) {
			int r, c;
			std::cin >> r >> c;
			coin_xor ^= nimber(r - 1, c - 1);
		}
 
		cout << (coin_xor == 0 ? "Second" : "First") << '\n';
	}
}

from functools import lru_cache
 
BOARD_LEN = 15
 
 
@lru_cache
def nimber(r: int, c: int) -> int:
	""":return: The nimber value of a coin at a single position"""
	if not (0 <= r < BOARD_LEN and 0 <= c < BOARD_LEN):
		return -1  # Return -1 to not interfere with the mex operation
 
	reachable = set()
	for dr, dc in [(-2, 1), (-2, -1), (1, -2), (-1, -2)]:
		reachable.add(nimber(r + dr, c + dc))
 
	ret = 0
	while ret in reachable:
		ret += 1
	return ret
 
 
for _ in range(int(input())):
	coin_xor = 0
	for _ in range(int(input())):
		r, c = [int(i) - 1 for i in input().split()]
		coin_xor ^= nimber(r, c)
 
	print("Second" if coin_xor == 0 else "First")

Problemas