Teoría de juegos (posiciones ganadoras)

Tema: Matemática y Combinatoria · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Decide quién gana un juego por turnos —dos jugadores, información completa, sin azar ni empates— clasificando cada posición en ganadora o perdedora para quien tiene el turno. La definición se muerde la cola de forma útil: una posición es perdedora si todos sus movimientos dejan al rival en una ganadora, y ganadora si existe al menos uno que deja al rival en una perdedora.

Complejidad: O(estados × movimientos por estado). En un juego de sustracción con n fichas y |S| movimientos posibles, O(n·|S|).

Cuándo usarlo

El enunciado dice “ambos juegan de forma óptima” y pregunta quién gana, o cuál es el primer movimiento ganador. Señal clara: dos jugadores que alternan, sin azar, sin información oculta y con la partida garantizada finita.

Implementación recomendada (C++)

// Juego de sustracción: quedan i fichas y puedes sacar cualquier cantidad de S.
// gana[i] = ¿gana quien tiene el turno con i fichas, si ambos juegan perfecto?
vector<char> ganadoras(int n, const vector<int>& S, bool misere = false) {
    vector<char> gana(n + 1, 0);
    for (int i = 0; i <= n; i++) {
        bool hay_jugada = false, deja_perdiendo = false;
        for (int s : S)
            if (s <= i) {                                  // jugada legal
                hay_jugada = true;
                if (!gana[i - s]) { deja_perdiendo = true; break; }
            }
        // ⚠️ el caso base NO es solo i = 0: es TODA posición sin jugada legal
        // (con S = {2,3}, i = 1 tampoco tiene). Normal: quien no puede, pierde.
        // Misère: quien no puede, gana.
        gana[i] = hay_jugada ? deja_perdiendo : misere;
    }
    return gana;                 // basta UNA jugada que deje al rival perdiendo
}
 
// Si cada jugador tiene sus propios movimientos, el turno entra al estado.
vector<array<char,2>> ganadoras_asim(int n, const vector<int>& S0,
                                     const vector<int>& S1, bool misere = false) {
    vector<array<char,2>> gana(n + 1, {0, 0});
    for (int i = 0; i <= n; i++)
        for (int t = 0; t < 2; t++) {                      // t = de quién es el turno
            bool hay_jugada = false, deja_perdiendo = false;
            for (int s : (t == 0 ? S0 : S1))
                if (s <= i) {
                    hay_jugada = true;
                    if (!gana[i - s][1 - t]) { deja_perdiendo = true; break; }
                }
            gana[i][t] = hay_jugada ? deja_perdiendo : misere;
        }
    return gana;
}

⚠️ Notas

El caso base no es una casilla, es una condición. El cuerpo del ciclo es idéntico en las dos modalidades; lo único que cambia es qué vale una posición sin jugada legal. En juego normal pierde quien no puede mover; en misère —“quien toma la última pierde”— gana. Es tentador escribir eso como y seguir, pero es un error: con S = {2, 3} la posición i = 1 tampoco tiene jugada, y si la das por perdedora el error se propaga hacia arriba y da vuelta respuestas. Solo cuando 1 ∈ S coinciden las dos versiones. Confundir normal con misère sigue siendo el error número uno del tema.

Busca el patrón antes de programar de más. Estos juegos casi siempre son periódicos. Imprime las primeras 30 posiciones y mira: con S = {1, …, k} las perdedoras del juego normal son exactamente los múltiplos de k+1 (déjale al rival un múltiplo de k+1 y, saque lo que saque, tú puedes completar k+1). En misère la misma familia se corre en uno: las perdedoras son las de la forma i ≡ 1 (mod k+1). Si n llega a 10^18, la tabla no cabe y el patrón es la solución.

Cuando los jugadores no son simétricos, el turno deja de ser irrelevante y pasa a ser parte del estado, como en ganadoras_asim. Ese es exactamente el caso de Galletas (OCI 2025 Nacional): Alicia puede sacar hasta a y Boberto hasta b, con la regla misère.

Frontera del syllabus: entran las posiciones ganadoras/perdedoras y el minimax básico, que es lo de esta página. Sprague-Grundy y el NIM general están explícitamente excluidos — no los estudies para competir (ver Syllabus IOI).

🔗 Relacionados