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