MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3091 6140

E-MAIL cef@ime.usp.br

MONITOR Paulo E. Silveira

E-MAIL peas@ime.usp.br

MAC 122 - Princípios de Desenvolvimento de Algoritmos
http://panda.ime.usp.br

EP 1: Jogo da Velha 3D - entrega 18 de setembro de 2003

O objetivo deste exercício-programa é fazer um programa que jogue o jogo da velha tridimensional que apareceu na Maratona de Programação 2003. Abaixo o jogo é descrito.

O jogo é feito de $n \times n$ pinos, dispostos em forma de uma matriz quadrada. Cada pino tem espaço para receber $n$ bolinhas das duas cores (azuis e brancas). Como no jogo da velha tradicional o objetivo é conseguir uma seqüência completa (em qualquer direção) de $n$ bolinhas da mesma cor. Note que ao colocar uma bolinha num dos pinos ela necessariamente cai até chegar ao primeiro nível vazio por causa da gravidade. As brancas sempre começam. Na figura abaixo mostramos uma situação do jogo em que as azuis ganharam.

A estratégia do seu programa será baseada na tentativa de todas as possibilidades. Seu programa deverá testar todas as possíveis jogadas, e para cada uma delas, todas as possíveis respostas do oponente, e para cada uma, todas as suas possíveis opções, e assim por diante. O usuário poderá definir no início do jogo um nível em que seu programa jogará, que é o número de jogadas do oponente que ele preverá. Assim, no nível 0 o seu programa apenas testa as suas possibilidades; no nível 1, testa suas possibilidades, para cada uma as possíveis respostas e para cada uma suas opções; e assim por diante. A implementação da estratégia deverá usar uma pilha, como visto em sala de aula.

Como a estratégia é fixa, os programas vão se diferenciar pela análise que fizerem do tabuleiro para escolher sua jogada. Caprichem, pois, é claro, o melhor programa receberá um grande prêmio!!

Para determinar o melhor jogador vamos organizar um campeonato. Seu programa deverá estar preparado para jogar com as brancas ou as azuis (dado através da chamada do programa, juntamente com o nível e o tamanho do tabuleiro), e a seqüência de jogadas do seu adversário será dada através da entrada padrão, uma jogada por linha (coordenadas x e y). Da mesma forma, seu programa deverá dar como saída a coordenada que está jogando na saída padrão. Maiores detalhes serão dados no fórum da disciplina.

$$\epsffile{ep1fig1.eps}$$