sexta-feira, 10 de fevereiro de 2012

Algoritmos para jogos

Neste post, vamos estudar jogos com dois jogadores com informação perfeita (tanto as posições dos jogadores quanto os movimentos que podem ser realizados pelos jogadores é público) imparcial (as regras do jogo não fazem distinção entre os jogadores). O jogo termina quando alcança uma posição que nenhum movimento pode ser realizado. Com a regra normal, o jogador que fez o último movimento ganha. Com a regra misere, o jogador que o fez o último movimento perde. O jogo sempre termina com um número finito de movimentos não importa como ele é jogado. Isso elimina a possibilidade de empates. Esta descrição elimina jogos como o poker (não temos informações perfeitas), jogo da velha e xadrez (não são jogos imparciais) e papel-pedra-tesoura (este jogo permite empate). Vamos chamar os jogos com as características acima de jogos imparciais
Os jogos imparciais podem ser resolvidos completamente através do Teorema Sprague-Grundy.
Jogo Nim com uma pilha
Considere o seguinte jogo:

  •  Inicialmente, temos n pedras na mesa.

  •  Cada jogador pode remover 1,2 ou 3 pedras.

  • Se um jogador não pode fazer nenhum movimento então ele perde.

Vamos denotar este jogo por (1,2,3)-NIM. Se o jogo começa com 21 pedras, quem é o jogador vencedor?

Nós podemos utilizar um método chamado backward-induction para resolver este problema. Com 0 pedras, o jogador I perde. Com 1,2,3 pedras o jogador I vence, ele pode fazer um movimento deixando 0 pedras para o próximo que perde o jogo. Com 4 pedras, qualquer movimento realizado pelo jogador I deixa um número de pedras que pode ser retirado totalmente pelo próximo jogador. Com 5,6,7 pedras, podemos deixar uma situação ruim para o próximo jogador retirando 1,2,3 pedras, respectivamente. Aplicando este raciocínio, com 21 pedras, o jogador I será o vencedor.
Podemos colocar as informações em tabela WIN/LOSS (Vitória/Derrota):

 
  
 
Podemos calcular os valores desta tabela com o seguinte algoritmo:
  
int table[MAX];
int moves[NMOVES]={1,2,3};
bool ehVencedor(int pos){
     //descobre as posições que podem ser alcançadas
//a partir da posição pos
int new_pos[NMOVES];
     int cnew=0;
     for(i=0;i<NMOVES;i++)
          if(pos - moves[i] >= 0)
                new_pos[cnew++] = pos - moves[i];
     //Se conseguimos fazer um movimento que deixa
//o próximo jogador em um estado não vencedor
//então retorne true
for(i=0;i<cnew;i++)
          if( !ehVencedor(new_pos[i]) ) { 
            table[pos]=true;
            return table[pos];
          }
     table[pos] = false;
     return table[pos];
}

Neste caso, para qualquer número múltiplo de 4 é uma posição de derrota e o padrão LWWW repete-se indefinidamente. Não precisamos calcular a tabela completamente para saber se uma dada posição é vencedor ou não.
Podemos resolver este problema de três maneiras:
  1. Calculando a tabela WIN/LOSS.
  2. Descobrindo uma propriedade utilizando a backward induction. 
  3. Encontrando um padrão que repete-se indefinidamente.
Versão generalizada do jogo NIM
Seja a1,a2,...,ak número naturais distintos então (a1,..,ak)-NIM é definido da seguinte maneira:
  • ·         Inicialmente, temos n pedras na mesa.
  • ·         Cada jogador pode remover a1 ou a2 ou ... ou ak pedras
  • ·         Se um jogador não pode fazer nenhum movimento então ele perde.
Vamos analisar o problema (1,4)-NIM. O jogo com 21 pedras é vencedor ou perdedor para o jogador I.
Tabela WIN/LOSS




Backward-Induction
Se n = 1,3,4 (mod 5) então o jogador I vence
Se n = 0,2   (mod 5) então o jogador I perde
Padrão
Podemos notar que o padrão WLWWL repete-se indefinidamente.
Encontrando o padrão
Se um padrão repete-se depois de algum segmento inicial, então o jogo é periódico. O tamanho do menor padrão que se repete é o período. O jogo (1,2,3)-NIM tem período 4 e o jogo (1,4)-NIM tem período 5.

Teorema: Para qualquer a1,..,ak, o jogo (a1,..,ak)-NIM é periódico.
Seja m o valor maior ak então temos 2m padrões de W/L diferentes de tamanho m. Tome as primeiras m(2m+1) entradas da tabela WIN/LOSS. Agrupe em 2m+1 grupos de m entradas.  Como existe apenas 2m possíveis padrões para cada grupo (Tem certeza disso?). Então pelo princípio das casas dos pombos, dois grupos devem ser o mesmo. O padrão, que ocorre entre esses dois grupos, se repete indefinidamente.

Corolário: O tamanho máximo do padrão de um o jogo (a1,..,ak)-NIM é k2k.
Aplicação: JOGO (1,2)-NIM
k=2
Calcule os 2(22+1) primeiros valores da tabela WIN/LOSS:
0
1
2
3
4
5
6
7
8
9
L
W
W
L
W
W
L
W
W
L

Agrupe em grupos de tamanho k=2
Grupo 1                  Grupo 2                    Grupo 3                   Grupo 4                     Grupo 5
0
1

2
3

4
5

6
7

8
9
L
W

W
L

W
W

L
W

W
L

O grupo 1 e 4 são repetidos então o padrão LWWLWW repete-se indefinidamente. Note que o padrão é formado pelo sub-padrão LWW. Note que o padrão encontrado não é o menor.

Versão Fácil Jogo NIM com duas pilhas
Considere a seguinte versão do jogo NIM:
  • ·         Inicialmente, temos duas pilhas de pedras que vamos denotar por (a,b).
  • ·         Um jogador pode remover quantas pedras ele quiser de uma pilha.
  • ·         Se um jogador não pode fazer nenhum movimento então ele perde.
Teorema: Se a=b sse o jogador I perde o jogo (a,b).
Basta o jogador II repetir todas as jogadas do jogador I na outra pilha.
Exemplo: Considere o jogo com duas pilhas com 5 pedras.
·         O jogador I remove 2 pedras da pilha 1. Nova posição (3,5)
·         O jogador II remove 2 pedras da pilha 1. Nova posição (3,3)
·         O jogador I remove 2 pedras da pilha 2. Nova posição (3,1)
·         O jogador II remove 2 pedras da pilha 1. Nova posição (1,1)
·         O jogador I remove 1 pedra da pilha 2. Nova posição (1,0)
·         O jogador II remove 1 pedra da pilha 1. Nova posição (0,0)
·         O jogador I perde.
Podemos definir uma estratégia vencedora para o jogador I se a != b. Sempre o jogador I deixando o número de pedras nas pilhas iguais.
Versão Generalizada Jogo NIM com múltiplas pilhas
Considere a seguinte versão do jogo NIM:
  • ·         Inicialmente, temos k pilhas de pedras que vamos denotar por (a1,..., ak).
  • ·         Um jogador pode remover quantas pedras ele quiser de uma pilha.
  • ·         Se um jogador não pode fazer nenhum movimento então ele perde.
A posição (a1,..., ak) é um posição perdedora para o jogador se a1 xor ...xor ak  = 0. A posição (a1,..., ak) tal que  a1 xor ...xor ak  = 0 será denominada de combinação segura. Os seguintes teoremas são válidos:

Teorema 1: Se o jogador I deixa uma combinação segura para o jogador II então o jogador II não conseguirá deixa uma combinação segura na sua vez de jogar.

Teorema 2: Se o jogador I deixa uma combinação segura e B retira pedras de uma certa pilha, então A poderá recompor uma combinação segura retirando algumas pedras de uma das pilhas restantes.
Considere o seguinte jogo NIM (6,9,3):
        6 = (110)2           1 1 0
       9 = (1001)2        1 0 0 1  
        3 = (11)2              1 1
                          --------
                           1 1 0 0

·         O jogador I deve retirar 4 pedras da pilha 2 para deixar uma combinação segura para o jogador 2.
6 = (110)2           1 1 0
5 = (0101)2        0 1 0 1  
3 = (11)2              1 1
                   --------
                   0 0 0 0
·         Se o jogador II retirar 4 pedras da pilha 1
2 = (010)2           0 1 0
5 = (1001)2        0 1 0 1  
3 = (11)2              1 1
                   --------
                   0 1 0 0
·         O jogador I deve retirar 4 pedras da pilha 2
2 = (010)2           0 1 0
1 = (001)2         0 0 0 1  
3 = (11)2              1 1
                   --------
                   0 0 0 0
·          O jogador II retira 3 pedras da pilha 3
2 = (010)2           0 1 0
1 = (001)2         0 0 0 1  
0 = (00)2              0 0
                   --------
                   0 0 1 1
·         O jogador retira 1 pedra da pilha 1
1 = (001)2           0 0 1
1 = (001)2         0 0 0 1  
0 = (00)2              0 0
                   --------
                   0 0 0 0


Nenhum comentário: