Números de Grundy

[ghastlyX]

A raíz del tema que se habló sobre algoritmia, he escrito este pequeño artículo sobre un tema que considero bastante interesante. Espero que se entienda bien y a ver si sirve para interesar a gente en temas algorítmicos.

En este artículo voy a presentar lo que se conoce como nimbers o números de Grundy. El nombre nimber viene del juego del Nim, que será el primero que analizaremos. No incluiré demostraciones de los resultados que vaya poniendo, dado que no creo que muchos lectores estén familiarizados con demostraciones matemáticas y éste no pretende ser un texto técnico, sino más bien divulgativo.

Presentemos ahora el juego clásico del Nim de una pila. Se trata de un juego para dos jugadores muy tonto. Consideremos una pila con n piedras en que los jugadores van por turnos alternos. Cada turno, el jugador puede retirar una cantidad arbitraria de piedras (como mínimo una y como máximo las que queden). Cuando un jugador no puede hacer nada (no quedan piedras) pierde y el otro gana. El objetivo es dictaminar quién ganará si ambos juegan de forma óptima. En este caso es evidente: gana siempre el primer jugador excepto si hay 0 piedras inicialmente. Si hay alguna piedra, la jugada óptima consiste en retirar todas las piedras, dejando 0 al segundo, que perderá.

Si bien ese caso es muy tonto, presentemos el juego del Nim estándar. Consideremos ahora n pilas diferentes, donde la i-ésima tiene a_i piedras. El juego sigue siendo por turnos para dos jugadores. En cada turno, un jugador tiene que escoger una pila que aún tenga piedras y retirar una cantidad de piedras de ella (entre 1 y la cantidad total de la pila). Si no quedan piedras, el jugador pierde. Otra vez el objetivo será estudiar quién gana en caso de que ambos jueguen óptimamente.

Teorema: Consideremos un juego del Nim con n pilas diferentes, donde la i-ésima tiene a_i piedras. Jugando óptimamente ambos jugadores, el segundo jugador ganará si y sólo si a₁^a₂^...^a_n = 0, donde ^ denota la XOR bit a bit.

Corolario: Para el caso n = 2, el segundo jugador ganará si y sólo si ambas pilas tienen la misma cantidad de piedras. La estrategia óptima consiste en imitar lo que haga el jugador en el turno anterior en la pila contraria, para mantener siempre la misma cantidad en ambas pilas.

Si bien este resultado es interesante, esto puede generalizarse a otros juegos. Consideremos un juego finito por turnos donde cada jugador puede hacer los mismos movimientos y el jugador que no puede mover pierde. Por ejemplo, el ajedrez no entra en esta categoría dado que ambos jugadores no pueden hacer los mismos movimientos (cada uno mueve sólo sus fichas). Para analizar este tipo de juegos definiremos el nimber o número de Grundy de un cierto estado del juego. Para empezar, asignamos al estado en que no se puede tirar (el jugador pierde) el nimber 0.

Definición: Sea J un juego que cumple las condiciones anteriores y w un estado de ese juego. Sea W el conjunto de estados a los que se puede llegar desde w usando un sólo movimiento (es decir, un solo turno). Consideremos el nimber de cada estado de W. Se define el nimber de w como el menor número entero no negativo que no está entre esos nimbers.

Teorema: Sea J un juego que cumple las condiciones anteriores y w un estado de ese juego. Suponiendo que ambos jugadores juegan óptimamente jugando desde w, el primer jugador ganará si y sólo si el nimber de w es diferente de 0.

Considerémos ahora el siguiente juego de ejemplo. Consideremos un juego con una pila con n piedras (como en el Nim), pero en este caso cada turno se pueden retirar 1 ó 2 piedras como mucho (si las hay). Calculemos el nimber para cada n:

- Si n = 0, por definición el nimber es 0.
- Si n = 1, con un turno sólo podemos llegar a n = 0, con nimber 0. El menor entero no negativo al que no se puede llegar es 1, luego 1 es el nimber de n = 1.
- Si n = 2, con un turno se puede llegar a n = 0 y n = 1, con nimbers 0 y 1 respectivamente, luego el nimber de n = 2 es 2.
- Si n = 3, con un turno se puede llegar n = 1 y n = 2, con nimbers 1 y 2 respectivamente. En este caso el menor nimber al que no se llega es el 0, luego el nimber de n = 3 es 0 y es un estado perdedor.

Si se sigue calculando, se ve que la secuencia de nimbers es 0, 1, 2, 0, 1, 2, 0, 1, 2... en la que el patrón es evidente, dado que el juego es muy simple.

Sin embargo, ¿qué pasa si en vez de un juego tenemos dos o más? Pues que el nimber también se puede calcular igual. Supongamos que tenemos un juego J formado por varios juegos J₁, J₂, ..., J_n en que cada turno el jugador elige uno de los juegos y hace un movimiento. En este caso un estado w está formado por los subestados w₁, w₂, ..., w_n de cada uno de los juegos.

Teorema: En el caso anterior, si N(w_i) denota el nimber del i-ésimo subestado, el nimber de w es N(w₁)^N(w₂)^...^N(w_n).

Por ejemplo, consideremos un juego en el que se tiene una circumferencia y sobre ella n puntos distintos. En cada turno, el jugador debe unir dos puntos distintos por un segmento, de forma que no se cruce con ninguno que se haya hecho anteriormente y sin usar un punto más de una vez. En este juego, es fácil ver con un pequeño dibujo que si se unen dos puntos consecutivos, se obtiene el mismo juego con n - 2 puntos. En caso contrario, se obtienen dos juegos diferentes (porque los segmentos no pueden cruzarse): uno tendrá k puntos y el otro n - k - 2. Sin embargo, podemos calcular el nimber de un estado usando el teorema anterior. Pongo un pequeño código en C++ que dada una k calcula el nimber de los juegos para todo n <= k, si no he cometido ningún error:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int grundy(int n, vector<int>& nimber) {
    if (n == 0 or n == 1) return 0; //No hay movimientos posibles
    if (nimber[n] == -1) {
        set<int> A; //Guardare aqui los nimbers a los que se puede llegar
       
        //Itero sobre la cantidad de puntos que dejo en el primer subjuego
        for (int i = 0; i <= n - 2; ++i) A.insert(grundy(i, nimber)^grundy(n - i - 2, nimber));
       
        //Busco el primero que no este, empezando por 0
        nimber[n] = 0;
        while (A.count(nimber[n])) ++nimber[n];
    }
    return nimber[n];
}

int main() {
    int k;
    cin >> k;
    vector<int> nimber(k + 1, -1);
    for (int i = 0; i <= k; ++i) cout << "N[" << i << "] = " << grundy(i, nimber) << endl;
}

Como ejercicio para practicar, probad de hacer este problema de la UVa (podéis enviarlo para su corrección automática, es un juez online):
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2529

[ghastlyX]

Como veo que no hay dudas ni preguntas, pongo mi solución del problema planteado para dejar el tema acabado.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <set>
#include <string.h>
using namespace std;

int nimber[105][3][3];

int grundy(int n, int a, int b) {
    if (n == 0) return 0;
    if (n == 1) {
        if (not (a + b == 3)) return 1;
        return 0;
    }
    if (nimber[n][a][b] == -1) {
        set<int> A;
        for (int i = 1; i < n - 1; ++i) {
            A.insert(grundy(i, a, 1)^grundy(n - i - 1, 1, b));
            A.insert(grundy(i, a, 2)^grundy(n - i - 1, 2, b));
        }
        if (a != 1) A.insert(grundy(n - 1, 1, b));
        if (a != 2) A.insert(grundy(n - 1, 2, b));
        if (b != 1) A.insert(grundy(n - 1, a, 1));
        if (b != 2) A.insert(grundy(n - 1, a, 2));
        nimber[n][a][b] = 0;
        while (A.count(nimber[n][a][b])) ++nimber[n][a][b];
    }
    return nimber[n][a][b];
}

int main() {
    memset(nimber, -1, sizeof(nimber));
    int q;
    cin >> q;
    while (q--) {
        string s;
        cin >> s;
        int ant = 0, res = 0, qtt = 0, turno = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == 'X') {
                res ^= grundy(qtt, ant, 1);
                ant = 1;
                qtt = 0;
                ++turno;
            }
            else if (s[i] == 'O') {
                res ^= grundy(qtt, ant, 2);
                ant = 2;
                qtt = 0;
                ++turno;
            }
            else ++qtt;
        }
        res ^= grundy(qtt, ant, 0);
        if (turno&1) cout << ((res == 0)?"Possible.":"Impossible.") << endl;
        else cout << ((res != 0)?"Possible.":"Impossible.") << endl;
    }
}