domingo, 4 de março de 2012

Jogo Nim

Suponha que duas pessoas participem de um jogo, e que cada um na sua vez toma uma, duas ou três pedras de uma pilha  que contém 15 pedras. A pessoa que remove a última pedra ganha o jogo. Mostre que o primeiro jogador pode ganhar, não importando o que o segundo faça.

Estrategia 1: Pensando de trás para frente


Para comprovar que o primeiro jogador pode sempre ganhar o jogo, podemos pensar de trás para frente.
No último passo, o primeiro jogador pode ganhar se sobrar  uma pilha com 1,2 ou 3 pedras. O segundo jogador será forçado a deixar 1,2 ou 3 pilhas se ele tiver com um pilha com contém 4 pedras. O primeiro jogador pode deixar uma pilha com 4 pedras se ele tiver uma pilha com 5, 6 ou 7 pilhas. Assim por diante, dessa maneira se o primeiro jogador receber uma pilha com 4n+1,4n+2 ou 4n+3 pedras, ele pode deixar uma pilha com 4n pedras para o segundo jogador. Essa é a estratégia vencedora do primeiro jogador.

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
#define NMOVES 3

int table[MAX];
int moves[NMOVES]={1,2,3};

bool ehVencedor(int pos){
  int new_pos[NMOVES];

  int cnew=0;
  //anota os possiveis movimentos
  for(int i=0;i<NMOVES;i++)
      if(pos - moves[i] >= 0)
          new_pos[cnew++] = pos - moves[i];

  //testa se cada movimento eh possivel   
  for(int i=0;i<cnew;i++)

  if( !ehVencedor(new_pos[i]) ) { 
          table[pos]=true;
          return table[pos];
  }
  //a pessoa perde quando nao pode fazer nenhum movimento
  //ou se nenhum movimento vencedor
  table[pos] = false;
  return table[pos];
}

int main(){

  int n;
  
  printf("informe o numero de pedras:");
  scanf("%d",&n);
  if(ehVencedor(n))
    printf("O primeiro jogador tem uma estrategia vencedora\n");
  else
    printf("O primeiro jogador nao tem uma estrategia vencedora\n");
  system("PAUSE");

}


Estratégia 2
O primeiro jogador deve anular cada movimento feito pelo segundo jogador. Vamos separar as pedras em grupos com 4 pedras.

**** | **** | **** | **** | ***

Primeiramente, o primeiro jogador retira as pedras do grupo que não está completo. Depois, se o segundo jogador retirar x pedra, o primeiro jogador deve retirar 4-x pedras. O primeiro jogador deve sempre fazer um movimento visando  completar um grupo. Essa é a estratégia vencedora do primeiro jogador.


#include <stdio.h>
#include <stdlib.h>


int main(){
  int n;
  char c,enter;
  do{
    printf("Voce quer comecar o jogo?(S/N))");
    c = getchar();
    enter = getchar();
  }while(c!='S'&&c!='s'&&c!='N'&&c!='n');

  if(c=='S'||c=='s'){
    n = 16;
    printf("numero de pedras escolhidos %d\n",n);
  }else{
    n = 17;
    printf("numero de pedras escolhidos %d\n",n);
    printf("Eu retiro 1 pedra\n");
    n--;
  }
  
  while(n>0){
    int m;
    do{
      printf("Quantas pedras vc vai retirar?(1,2,3)");
      scanf("%d",&m);
    }while(m < 1 ||  m > 3);
    n = n -m;
    printf("Sobraram %d pedras\n",n);
    printf("Eu retiro %d pedras\n",4-m);
    n = n - (4-m);
    printf("Sobraram %d pedras\n",n);
    if(n==0) printf("Eu venci\n");
  }
  system("PAUSE");
}

Links relacionados:
Post do Blog Algoritmos para Jogos
Problema do br-spoj Last Year at Marienbad
 
 

3 comentários:

David Sena disse...

Caramba, muito massa. Vou começar a jogar esse jogo aí. Claro que a regra número um será eu sempre começar primeiro.

Wladimir Araújo Tavares disse...

Valeu David Sena!!!

Thiago Nepomuceno disse...

Um professor apostou comigo uma vez, se eu ganhasse dele num jogo parecido com esse (mas segue a mesma ideia) eu teria 10 na média, eu joguei mas obviamente perdi ¬¬.