O primeiro projeto de programação, a ser implementado em
LISP, terá como tema o jogo de gato e rato, explicado a seguir.
O progama deverá ser entregue até o dia 07/09/97
às 23:59, por e-mail para o endereco do professor (
meidanis@dcc.unicamp.br).
Abaixo encontram-se as explicações sobre o programa.
O jogo será jogado num tabuleiro 8x8, como o de xadrêz, mas serão utilizadas apenas as casas pretas, como no jogo de damas.
A numeração do tabuleiro deverá seguir o seguinte padrão:
_____ _____ _____ _____ _____ _____ _____ _____
| | | | | | | | |
8 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
7 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
6 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
5 | | | | A | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
4 | | | | | | | B | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
3 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
2 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
1 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
1 2 3 4 5 6 7 8
As casas serão representadas por listas de dois átomos
numéricos da forma (l c) , onde l
é a linha e c é a coluna. Por exemplo, as
posições marcadas no tabuleiro acima são A = (5
4) e B = (5 7).
As casas que os Gatos e o Rato podem ocupar são somente as pretas, isto é, casas (l c) com l+c par. A posição inicial do jogo contem um Rato em (8 4) e quatro Gatos nas posições (1 1) , (1 3) , (1 5) e (1 7) .
_____ _____ _____ _____ _____ _____ _____ _____
| | | | | | | | |
8 | | | | R | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
7 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
6 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
5 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
4 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
3 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
2 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
1 | G | | G | | G | | G | |
|_____|_____|_____|_____|_____|_____|_____|_____|
1 2 3 4 5 6 7 8
Joga um jogador de cada vez. Não é permitido "passar" a vez. Não é permitido "comer" outras pecas (ocupar uma casa já ocupada por outra peca). O Rato sempre começa.
Os movimentos são da seguinte forma. Gatos andam uma casa de cada vez, sempre para a frente. Um Gato na posição (l c) pode ir para (l+1 c+1) ou (l+1 c-1) , se estas casas existirem e estiverem desocupadas. O Rato anda para a frente e para trás. Da posição (l c) ele pode ir para (l+1 c+1) , (l+1 c-1) , (l-1 c+1) ou (l-1 c-1) , se existirem e estiverem desocupadas. Uma casa (x y) existe se 1 <= x , y <= 8.
O objetivo dos Gatos é encurralar o Rato de modo que ele não tenha mais movimentos. O Rato tem como objetivo atingir a linha numero 1.
A seguir exibimos ums partida para ilustrar melhor como é o jogo. Os lances são indicados por uma lista da forma ( (l1 c1) (l2 c2) ) , onde (l1 c1) é a posição da peca que está sendo jogada antes do lance, e (l2 c2) é a posição da peca que está sendo jogada depois do lance.
Rato Gatos
((8 4) (7 5)) ((1 1) (2 2))
((7 5) (6 4)) ((1 3) (2 4))
((6 4) (5 5)) ((1 5) (2 6))
((5 5) (4 4)) ((1 7) (2 8))
((4 4) (3 5)) ((2 8) (3 7))
((3 5) (4 6)) ((2 6) (3 5))
((4 6) (5 5)) ((2 4) (3 3))
((5 5) (4 4)) ((2 2) (3 1))
((4 4) (5 5)) ((3 1) (4 2))
((5 5) (4 6)) ((3 3) (4 4))
((4 6) (5 7)) ((3 5) (4 6))
((5 7) (4 8)) ((4 6) (5 7))
Ganham os Gatos , pois o Rato não pode se mover. Posição final:
_____ _____ _____ _____ _____ _____ _____ _____
| | | | | | | | |
8 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
7 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
6 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
5 | | | | | | | G | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
4 | | G | | G | | | | R |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
3 | | | | | | | G | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
2 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
| | | | | | | | |
1 | | | | | | | | |
|_____|_____|_____|_____|_____|_____|_____|_____|
1 2 3 4 5 6 7 8
Voce deverá escrever um programa em LISP que joga este jogo, tanto do lado dos Gatos como do lado do Rato . Seu programa deverá exportar apenas quatro funções:
(rato-inicia)
Esta função, sem argumentos, deve inicializar o que for
necessário e retornar o primeiro lance do Rato .
(rato-responde jogada)
Esta função recebe um argumento, que reflete a
última jogada dos Gatos , e deve retornar a próxima
jogada do Rato . Se o Rato não puder se mover, retorna NIL .
(gato-inicia jogada)
Esta função recebe um argumento, que foi a primeira
jogada do Rato . Ela deve inicializar o que for necessário e
retornar o primeiro lance dos Gatos .
(gato-responde jogada)
Esta função recebe um parâmetro, que reflete a
última jogada do Rato , e deve retornar a próxima jogada
dos Gatos . Se nenhum dos Gatos puder se mover, retorna NIL .
Mais tarde no curso serão vistos mais detalhes sobre como encaspular seu programa num pacote e como exportar funções. Isto será necessário pois os programas jogarão uns contra os outros, sob monitoração de um gerenciador escrito pelo professor, e o encaspulamento evitará conflitos de nomes de funções e/ou vari´veis usados nos programas individuais.
O funcionamento mínimo é importante pois todo aluno que não o cumprir vai para exame direto.
Neste projeto de Gatos e Rato , o funcionamento mínimo é o seguinte: nenhuma das funções poderá em momento algum retornar uma jogada inválida.