Skip to Content
CTRL K

Juegos sobre grafos arbitrarios

Sea un juego jugado por dos jugadores sobre un grafo arbitrario GG. Es decir, el estado actual del juego es un cierto vértice. Los jugadores realizan movimientos por turnos, y se mueven del vértice actual a un vértice adyacente usando una arista de conexión. Según el juego, la persona que no puede moverse o bien perderá o bien ganará el juego.

Consideramos el caso más general, el caso de un grafo dirigido arbitrario con ciclos. Nuestra tarea es determinar, dado un estado inicial, quién ganará el juego si ambos jugadores juegan con estrategias óptimas, o determinar que el resultado del juego será un empate.

Resolveremos este problema de forma muy eficiente. Hallaremos la solución para todos los vértices de partida posibles del grafo en tiempo lineal respecto al número de aristas: O(m)O(m).

Descripción del algoritmo

Llamaremos a un vértice un vértice ganador si el jugador que empieza en este estado ganará el juego, si juega de forma óptima (independientemente de los turnos que haga el otro jugador). De manera similar, llamaremos a un vértice un vértice perdedor si el jugador que empieza en este vértice perderá el juego, si el oponente juega de forma óptima.

Para algunos de los vértices del grafo, ya sabemos de antemano que son vértices ganadores o perdedores: a saber, todos los vértices que no tienen aristas salientes.

También tenemos las siguientes reglas:

  • si un vértice tiene una arista saliente que lleva a un vértice perdedor, entonces el vértice mismo es un vértice ganador.
  • si todas las aristas salientes de un cierto vértice llevan a vértices ganadores, entonces el vértice mismo es un vértice perdedor.
  • si en algún momento todavía hay vértices indefinidos, y ninguno encaja en la primera ni en la segunda regla, entonces cada uno de estos vértices, cuando se usa como vértice de partida, llevará a un empate si ambos jugadores juegan de forma óptima.

Así, podemos definir de inmediato un algoritmo que corre en tiempo O(nm)O(n m). Recorremos todos los vértices e intentamos aplicar la primera o la segunda regla, y repetimos.

Sin embargo, podemos acelerar este procedimiento y bajar la complejidad a O(m)O(m).

Recorreremos todos los vértices para los que inicialmente sabemos si son estados ganadores o perdedores. Para cada uno de ellos, iniciamos una búsqueda en profundidad (DFS). Este DFS se moverá hacia atrás sobre las aristas invertidas. Ante todo, no entrará en vértices que ya están definidos como vértices ganadores o perdedores. Y además, si la búsqueda va de un vértice perdedor a un vértice indefinido, entonces marcamos este como un vértice ganador, y continuamos el DFS usando este nuevo vértice. Si vamos de un vértice ganador a un vértice indefinido, entonces debemos comprobar si todas las aristas desde este llevan a vértices ganadores. Podemos realizar esta prueba en O(1)O(1) guardando el número de aristas que llevan a un vértice ganador para cada vértice. Así, si vamos de un vértice ganador a uno indefinido, entonces aumentamos el contador, y comprobamos si este número es igual al número de aristas salientes. Si es el caso, podemos marcar este vértice como un vértice perdedor, y continuar el DFS desde este vértice. En caso contrario todavía no sabemos si este vértice es ganador o perdedor, y por lo tanto no tiene sentido seguir el DFS usándolo.

En total visitamos cada vértice ganador y cada vértice perdedor exactamente una vez (los vértices indefinidos no se visitan), y recorremos cada arista también a lo sumo una vez. De ahí que la complejidad sea O(m)O(m).

Implementación

Aquí está la implementación de tal DFS. Asumimos que la variable adj_rev guarda la lista de adyacencia del grafo en forma invertida, es decir, en lugar de guardar la arista (i,j)(i, j) del grafo, guardamos (j,i)(j, i). También para cada vértice asumimos que el grado saliente ya está calculado.

vector<vector<int>> adj_rev;
 
vector<bool> winning;
vector<bool> losing;
vector<bool> visited;
vector<int> degree;
 
void dfs(int v) {
    visited[v] = true;
    for (int u : adj_rev[v]) {
        if (!visited[u]) {
            if (losing[v])
                winning[u] = true;
            else if (--degree[u] == 0)
                losing[u] = true;
            else
                continue;
            dfs(u);
        }
    }
}

Ejemplo: “Policía y ladrón”

Aquí hay un ejemplo concreto de tal juego.

Hay un tablero m×nm \times n. Algunas de las celdas no se pueden entrar. Se conocen las coordenadas iniciales del policía y del ladrón. Una de las celdas es la salida. Si el policía y el ladrón están ubicados en la misma celda en cualquier momento, gana el policía. Si el ladrón está en la celda de salida (sin que el policía también esté en la celda), entonces gana el ladrón. El policía puede caminar en las 8 direcciones, el ladrón solo en 4 (a lo largo de los ejes de coordenadas). Tanto el policía como el ladrón se moverán por turnos. Sin embargo también pueden saltar un turno si quieren. El primer movimiento lo hace el policía.

Ahora construiremos el grafo. Para ello debemos formalizar las reglas del juego. El estado actual del juego está determinado por las coordenadas del policía PP, las coordenadas del ladrón TT, y también por de quién es el turno, llamemos a esta variable PturnP_{\text{turn}} (que es verdadera cuando es el turno del policía). Por lo tanto un vértice del grafo está determinado por la terna (P,T,Pturn)(P, T, P_{\text{turn}}) El grafo entonces se puede construir fácilmente, simplemente siguiendo las reglas del juego.

Luego necesitamos determinar qué vértices son ganadores y cuáles son perdedores inicialmente. Hay un punto sutil aquí. Los vértices ganadores / perdedores dependen, además de las coordenadas, también de PturnP_{\text{turn}}: de quién es el turno. Si es el turno del policía, entonces el vértice es un vértice ganador si las coordenadas del policía y del ladrón coinciden, y el vértice es perdedor si no es ganador y el ladrón está en el vértice de salida. Si es el turno del ladrón, entonces un vértice es un vértice perdedor si las coordenadas de los dos jugadores coinciden, y es un vértice ganador si no es perdedor y el ladrón está en el vértice de salida.

El único punto pendiente antes de implementar es decidir si se quiere construir el grafo explícitamente o solo construirlo sobre la marcha. Por un lado, construir el grafo explícitamente será mucho más fácil y hay menos chance de cometer errores. Por otro lado, aumentará la cantidad de código y el tiempo de ejecución será más lento que si se construye el grafo sobre la marcha.

La siguiente implementación construirá el grafo explícitamente:

struct State {
    int P, T;
    bool Pstep;
};
 
vector<State> adj_rev[100][100][2]; // [P][T][Pstep]
bool winning[100][100][2];
bool losing[100][100][2];
bool visited[100][100][2];
int degree[100][100][2];
 
void dfs(State v) {
    visited[v.P][v.T][v.Pstep] = true;
    for (State u : adj_rev[v.P][v.T][v.Pstep]) {
        if (!visited[u.P][u.T][u.Pstep]) {
            if (losing[v.P][v.T][v.Pstep])
                winning[u.P][u.T][u.Pstep] = true;
            else if (--degree[u.P][u.T][u.Pstep] == 0)
                losing[u.P][u.T][u.Pstep] = true;
            else
                continue;
            dfs(u);
        }
    }
}
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
 
    for (int P = 0; P < n*m; P++) {
        for (int T = 0; T < n*m; T++) {
            for (int Pstep = 0; Pstep <= 1; Pstep++) {
                int Px = P/m, Py = P%m, Tx = T/m, Ty = T%m;
                if (a[Px][Py]=='*' || a[Tx][Ty]=='*')
                    continue;
                
                bool& win = winning[P][T][Pstep];
                bool& lose = losing[P][T][Pstep];
                if (Pstep) {
                    win = Px==Tx && Py==Ty;
                    lose = !win && a[Tx][Ty] == 'E';
                } else {
                    lose = Px==Tx && Py==Ty;
                    win = !lose && a[Tx][Ty] == 'E';
                }
                if (win || lose)
                    continue;
 
                State st = {P,T,!Pstep};
                adj_rev[P][T][Pstep].push_back(st);
                st.Pstep = Pstep;
                degree[P][T][Pstep]++;
                
                const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
                const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
                for (int d = 0; d < (Pstep ? 8 : 4); d++) {
                    int PPx = Px, PPy = Py, TTx = Tx, TTy = Ty;
                    if (Pstep) {
                        PPx += dx[d];
                        PPy += dy[d];
                    } else {
                        TTx += dx[d];
                        TTy += dy[d];
                    }
 
                    if (PPx >= 0 && PPx < n && PPy >= 0 && PPy < m && a[PPx][PPy] != '*' &&
                        TTx >= 0 && TTx < n && TTy >= 0 && TTy < m && a[TTx][TTy] != '*')
                    {
                        adj_rev[PPx*m+PPy][TTx*m+TTy][!Pstep].push_back(st);
                        ++degree[P][T][Pstep];
                    }
                }
            }
        }
    }
 
    for (int P = 0; P < n*m; P++) {
        for (int T = 0; T < n*m; T++) {
            for (int Pstep = 0; Pstep <= 1; Pstep++) {
                if ((winning[P][T][Pstep] || losing[P][T][Pstep]) && !visited[P][T][Pstep])
                    dfs({P, T, (bool)Pstep});
            }
        }
    }
 
    int P_st, T_st;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'P')
                P_st = i*m+j;
            else if (a[i][j] == 'T')
                T_st = i*m+j;
        }
    }
 
    if (winning[P_st][T_st][true]) {
        cout << "Police catches the thief"  << endl;
    } else if (losing[P_st][T_st][true]) {
        cout << "The thief escapes" << endl;
    } else {
        cout << "Draw" << endl;
    }
}
Teorema de Sprague-Grundy. NimJuego del 15: existencia de la solución