Quarto Exercício-Programa

Jogo da Velha 3D

Entrega: 5 de dezembro

O objetivo deste exercício-programa é implementar um algoritmo para um jogo que baseia-se em explorar todas as possibilidades de jogadas dentro de um limite, e implementar boas heurísticas de avaliação de melhor jogada, dentre as várias examinadas.

O jogo escolhido é o jogo da velha 3D, que é uma variante do nosso bem conhecido jogo da velha. Esta variante consiste de n x n pinos dispostos em forma de uma matriz quadrada. Cada pino tem espaço para receber n bolinhas. Cada bolinha é branca e preta. Veja uma figura (tirada do endereço http://www.naturwaren-online.de/catalog/images/4462_TicTacToe.jpg) da versão 4 x 4 do jogo.

Cada jogador fica com uma das cores. O jogador que tem as bolinhas brancas sempre começa. O objetivo de cada jogador, como no original, é conseguir uma sequência completa, com n bolinhas da dua cor, em uma das direções.

Note que, nesta variante 3D, ao colocarmos uma bolinha em um dos pinos, esta cai até chegar ao primeiro nível vazio, por conta da gravidade. Na figura acima, as brancas ganharam, já que completaram a segunda fileira de baixo para cima, do plano mais externo à frente.

Estratégia do programa

O seu programa, para decidir pela jogada, tentará todas as possíveis jogadas e, para cada uma delas, todas as possíveis jogadas do adversário, e de novo, todas as suas possíveis jogadas, etc, até um certo ponto. O usuário escolherá no início do jogo a profundidade desta busca exaustiva pela melhor jogada. Se a profundidade escolhida for 0, o seu programa apenas escolhe a melhor jogada dentre todas as possíveis neste ponto. Se a profundidade escolhida for 1, o seu programa gera, para cada possível jogada, cada possível jogada do adversário e cada possível resposta sua a esta jogada, e escolhe a jogada que o leva a melhor situação em dois passos (levando em conta que o adversário provavelmente escolherá a melhor resposta à sua jogada). Se a profundidade for 2, de forma semelhante seu programa escolhe a jogada que o levará à melhor situação levando em conta as próximas duas jogadas do adversário, e assim por diante.

Para decidir qual é a melhor jogada entre as várias possíveis, você vai ter que pensar em uma função que avalie a situação do tabuleiro, para ajudá-lo a decidir qual das situações parecem melhor. Evidentemente uma jogada que o leve a ganhar é a melhor possível. Algumas vezes porém não chegaremos a vitória na nossa busca exaustiva. Assim mesmo, seu programa terá que decidir por uma jogada.

Entrada e saída do programa

O seu programa vai jogar contra o usuário. Ele deve estar preparado para jogar com as brancas e com as pretas. Primeiramente o programa lerá o inteiro n, a cor com que o usuário quer jogar e a profundidade máxima da busca exaustiva a ser usada. Depois disso, o jogo começa e, a cada passo, a jogada do usuário é lida, no formato (x,y), indicando em que pino o usuário quer colocar a sua próxima bolinha.

Depois de cada jogada, seu programa deve imprimir o pino em que jogou, no mesmo formato (x,y), e deve mostrar a situação do tabuleiro, para que o usuário possa escolher sua próxima jogada.

Avaliação da sua estratégia

Cada programa terá a sua própria estratégia de escolha da próxima jogada, que dependerá da sua função de avaliação do tabuleiro.

Capriche para implementar a melhor estratégia, pois, para avaliarmos as diversas estratégias de vocês, organizaremos um campeonato! Neste campeonato, o seu programa jogará contra o programa de outros alunos. O melhor programa receberá um grande prêmio!!

Divirta-se com o EP!

Entrega, prazos e observações

Last modified: Wed Dec 1 12:53:47 BRST 2010