Teorema de Sprague-Grundy, Nim

Introdução

Este teorema descreve o chamado jogo imparcial para dois jogadores, ou seja, aquele em que os movimentos disponíveis e a vitória / derrota dependem apenas do estado do jogo. Em outras palavras, a única diferença entre os dois jogadores é que um deles se move primeiro.

Além disso, assumimos que o jogo possui informações perfeitas, ou seja, nenhuma informação está oculta dos jogadores (eles conhecem as regras e os possíveis movimentos).

Supõe-se que o jogo seja finito, ou seja, após um certo número de jogadas, um dos jogadores terminará em uma posição perdedora - da qual não poderá se mover para outra posição. Por outro lado, o jogador que configurou esta posição para o oponente vence. Compreensivelmente, não há empates neste jogo.

Esses jogos podem ser completamente descritos por um grafo direcionado acíclico: os vértices são estados do jogo e as arestas são transições (movimentos). Um vértice sem arestas de saída é um vértice perdedor (um jogador que deve fazer um movimento a partir desse vértice perde).

Como não há empates, podemos classificar todos os estados do jogo como vencedor ou perdedor. Os estados vencedores são aqueles dos quais existe uma jogada que causa a inevitável derrota do outro jogador, mesmo com sua melhor resposta. Estados perdedores são aqueles dos quais todos os movimentos levam a estados vencedores para o outro jogador. Resumindo, um estado está vencendo se houver pelo menos uma transição para um estado perdedor e está perdendo se não houver pelo menos uma transição para um estado perdedor.

Nossa tarefa é classificar os estados de um determinado jogo.

A teoria desses jogos foi desenvolvida independentemente por Roland Sprague em 1935 e Patrick Michael Grundy em 1939.

Nim

Este jogo obedece às restrições descritas acima. Além disso, qualquer jogo imparcial para dois jogadores com informações perfeitas pode ser reduzido ao jogo de Nim. O estudo deste jogo nos permitirá resolver todos os outros jogos semelhantes, mais sobre isso mais tarde.

Historicamente, este jogo era popular nos tempos antigos. Sua origem provavelmente está na China - ou pelo menos o jogo Jianshizi é muito parecido. Na Europa, as primeiras referências a ele são do século XVI. O nome foi dado por Charles Bouton, que em 1901 publicou uma análise completa deste jogo.

Descrição do jogo

Existem várias pilhas, cada uma com várias pedras. Em um movimento, um jogador pode pegar qualquer número positivo de pedras de qualquer pilha e jogá-las fora. Um jogador perde se não puder fazer um movimento, o que acontece quando todas as pilhas estão vazias.

O estado do jogo é descrito por um multiset de números inteiros positivos. Um movimento consiste em diminuir estritamente um número inteiro escolhido (se ele se torna zero, é removido do conjunto).

Solução

A solução de Charles L. Bouton é semelhante da seguinte forma:

Teorema: O jogador atual tem uma estratégia vencedora se, e somente se, o xor-sum dos tamanhos das pilhas for diferente de zero. O xor-sum de uma sequência $a$ será: $a_1 \oplus a_2 \oplus \ldots \oplus a_n$, em que $\oplus$ é o bitwise exclusive or.

Prova. A "chave" da prova é a presença de uma estratégia simétrica para o oponente. Mostramos que, uma vez em uma posição com a xor-sum igual a zero, o jogador não poderá torná-lo diferente de zero a longo prazo - se fizer a transição para uma posição com uma soma-xor diferente de zero, o oponente sempre terá um movimento retornando o xor-sum de volta a zero.

Vamos provar o teorema por indução matemática.

Para um Nim vazio (onde todas as pilhas estão vazias, ou seja, o multiset está vazio), a xor-sum é zero e o teorema é verdadeiro.

Agora, suponha que estejamos em um estado não vazio. Usando a suposição de indução (e a aciclicidade do jogo), assumimos que o teorema é comprovado para todos os estados alcançáveis ​​a partir do atual.

Então a prova se divide em duas partes: se para a posição atual a xor-sum $s = 0$, temos que provar que esse estado está perdendo, ou seja, todos os estados alcançáveis ​​possuem xor-sum $t \neq 0$. Se $s \neq 0$, temos que provar que há uma mudança que leva a um estado com $t = 0$.

$$t = s \oplus x \oplus y = 0 \oplus x \oplus y = x \oplus y$$

Como $y < x$, $y \oplus x$ não pode ser zero, então $t \neq 0$. Isso significa que qualquer estado alcançável é vencedor (pelo pressuposto da indução), então estamos em uma posição perdedora.

$$ t = s \oplus x \oplus y = s \oplus x \oplus (s \oplus x) = 0$$

Isso significa que encontramos um estado alcançável e perdedor (pelo pressuposto da indução) e o estado atual está vencendo.

Corolário. Qualquer estado de Nim pode ser substituído por um estado equivalente, desde que o xor-sum não seja alterado. Além disso, ao analisar um Nim com várias pilhas, podemos substituí-lo por uma única pilha de tamanho $s$.

A equivalência de jogos imparciais e Nim (teorema de Sprague-Grundy)

Agora veremos como encontrar, para qualquer estado de jogo imparcial, um estado correspondente de Nim.

Lema sobre Nim

Consideramos a seguinte modificação no Nim: também permitimos adicionar pedras a uma pilha escolhida. As regras exatas sobre como e quando o aumento é permitido não nos interessam, no entanto, as regras devem manter nosso jogo acíclico. Nas seções posteriores, exemplos de jogos são considerados.

Lema. As adições em Nim não muda a maneira como os estados vencedores e perdedores são determinados. Em outras palavras, os aumentos são inúteis e não precisamos usá-los em uma estratégia vencedora.

Prova. Suponha que um jogador tenha adicionado pedras a uma pilha. Então seu oponente pode simplesmente desfazer sua jogada - diminuir o número de volta ao valor anterior. Como o jogo é acíclico, mais cedo ou mais tarde o jogador atual não poderá usar um movimento de aumento e precisará executar o movimento do Nim usual.

Teorema de Sprague-Grundy

Vamos considerar um estado $v$ de um jogo imparcial para dois jogadores e deixar que $v_i$ sejam os estados acessíveis (em que $i \in { 1, 2, \dots, k } , k \ge 0$). Para esse estado, podemos atribuir um jogo totalmente equivalente ao de Nim com uma pilha de tamanho $x$. O número $x$ é chamado de "valor Grundy" ou "valor nim" do estado $v$.

Além disso, esse número pode ser encontrado da seguinte maneira recursiva:

$$ x = \text{mex} { x_1, \ldots, x_k }, $$

em que $x_i$ é o valor Grundy para o estado $v_i$ e a função $\text{mex}$ (minimum excludant) é o menor número inteiro não negativo não encontrado no conjunto fornecido.

Vendo o jogo como um grafo, podemos calcular gradualmente os valores Grundy a partir de vértices sem arestas de saída. O valor de Grundy igual a zero significa que um estado é perdedor.

Prova. Usaremos uma prova por indução.

Para vértices sem movimento, o valor $x$ é o $\text{mex}$ de um conjunto vazio, o que é zero. Isso está correto, pois um Nim vazio está perdendo.

Agora considere qualquer outro vértice $v$. Por indução, assumimos que os valores $x_i$ correspondentes aos seus vértices alcançáveis ​​já estão calculados.

Seja $p = \text{mex} { x_1, \ldots, x_k }$. Então sabemos que para qualquer número inteiro $i \in [0, p)$ existe um vértice alcançável com o valor Grundy $i$. Isso significa que $v$ é equivalente a um estado do jogo de Nim com adições e com uma pilha de tamanho $p$. Nesse jogo, temos transições para pilhas de todos os tamanhos menores que $p$ e, possivelmente, transições para pilhas com tamanhos maiores que $p$. Portanto, $p$ é realmente o valor Grundy desejado para o estado atualmente considerado.

Aplicação do teorema

Por fim, descrevemos um algoritmo para determinar o resultado de vitória / perda de um jogo, aplicável a qualquer jogo imparcial para dois jogadores.

Para calcular o valor Grundy de um determinado estado, você precisa:

Em comparação com a seção anterior, levamos em conta o fato de que pode haver transições para jogos combinados. Nós os consideramos um Nim com tamanhos de pilha iguais aos valores Grundy dos jogos independentes. Nós podemos fazer a xor-sum para eles assim como em um Nim usual, de acordo com o teorema de Bouton.

Padrões em valores Grundy

Muitas vezes, ao resolver tarefas específicas usando valores Grundy, pode ser benéfico estudar a tabela de valores em busca de padrões.

Em muitos jogos, o que pode parecer bastante difícil para a análise teórica, os valores de Grundy acabam sendo periódicos ou de uma forma facilmente compreensível. Na esmagadora maioria dos casos, o padrão observado acaba sendo verdadeiro e pode ser provado por indução, se desejado.

No entanto, os valores de Grundy estão longe de sempre conter tais regularidades e, mesmo para alguns jogos muito simples, o problema de perguntar se essas regularidades ainda existem estão em aberto (por exemplo: "Grundy's game").

Exemplos de jogos

Crosses-crosses

Regras. Considere uma faixa quadriculada de tamanho $1 \times n$. Em um movimento, o jogador deve colocar uma cruz, mas é proibido colocar duas cruzes próximas umas das outras (nas células adjacentes). Como sempre, o jogador sem uma jogada válida perde.

Solução. Quando um jogador coloca uma cruz em qualquer célula, podemos pensar na faixa sendo dividida em duas partes independentes: à esquerda da cruz e à direita dela. Nesse caso, a célula com uma cruz, assim como seus vizinhos esquerdo e direito, são destruídos - nada mais pode ser colocado neles. Portanto, se numerarmos as células de $1$ a $n$ e então colocar a cruz na posição $1 < i < n$ quebra a tira em duas tiras de comprimento $i-2$ e $n-i-1$ ou seja, vamos para o soma dos jogos $i-2$ e $n-i-1$. Para o caso da aresta da cruz sendo marcado na posição $1$ ou $n$, vamos para o jogo $n-2$.

Assim, o valor de Grundy $g(n)$ tem a forma:

$$g(n) = \text{mex} \Bigl( { g(n-2) } \cup {g(i-2) \oplus g(n-i-1) \mid 2 \leq i \leq n-1} \Bigr) .$$

Portanto, temos uma solução em $O(n^2)$.

De fato, $g(n)$ tem um período de comprimento 34 começando com $n=52$.

Referências