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:
- Calculando a tabela WIN/LOSS.
- Descobrindo uma propriedade utilizando a backward induction.
- 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:
Postar um comentário