Jogo da Velha

O projeto de programação a ser implementado terá como tema o Jogo da Velha, explicado a seguir. O progama deverá ser entregue até o dia 17/05/2004 às 23:59. A forma de entrega será pela Internet.

Abaixo encontram-se as explicações sobre o programa.

Tabuleiro

O jogo será jogado num tabuleiro 3x3. As casas serão denotadas por pares de coordenadas como segue:

    _____ _____ _____
   |     |     |     |
   |(0 2)|(1 2)|(2 2)|
   |_____|_____|_____|
   |     |     |     |
   |(0 1)|(1 1)|(2 1)|
   |_____|_____|_____|
   |     |     |     |
   |(0 0)|(1 0)|(2 0)|
   |_____|_____|_____|

As casas serão representadas por uma lista de números como acima.

Regras do Jogo

Quem joga primeiro será chamado de PRETO, e o outro jogador é BRANCO. O objetivo de cada jogador é posicionar suas três pedras em linha reta (vertical, horizontal ou diagonal). O tabuleiro começa vazio, e alternadamente os jogadores fazem suas jogadas, comçando pelo jogador PRETO. Uma jogada consiste em colocar uma pedra em uma casa vazia. Não é permitido "passar" a vez. Caso o tabuleiro esteja cheio e nenhum dos jogadores tenha formado três pedras em linha, o jogo acaba em empate.

Exemplo de partida

A seguir exibimos umapartida para ilustrar o jogo.

PRETO	BRANCO
(0 2)	(1 1)
(2 1)	(2 2)
(0 0)	(0 1)
(2 0)	(1 0)
(1 2)

A partida acabou empatada. Posição final:

    _____ _____ _____
   |     |     |     |
   |  P  |  P  |  B  |
   |_____|_____|_____|
   |     |     |     |
   |  B  |  B  |  P  |
   |_____|_____|_____|
   |     |     |     |
   |  P  |  B  |  P  |
   |_____|_____|_____|

O que voce deve implementar

Voce deverá escrever um programa em LISP que joga este jogo, tanto do lado do PRETO como do lado do BRANCO. Seu programa deverá ser uma pacote e exportar quatro funções:

preto-inicia

Esta função será chamada sem argumentos deverá retornar a casa onde seu programa jogará o primeiro lance como PRETO. Além disso, pode executar as inicializações necessárias em suas estruturas internas.

preto-responde jogada-do-branco

Esta função será chamada com a última jogada do BRANCO como argumento, e deve retornar a jogada-resposta. Além disso, pode executar as atualizações necessárias em suas estruturas internas.

branco-inicia jogada-do-preto

Esta função será chamada com a última jogada do PRETO como argumento e retorna a casa onde seu programa jogará o primeiro lance como BRANCO. Além disso, pode executar as inicializações necessárias em suas estruturas internas.

branco-responde jogada-do-preto

Esta função será chamada com a última jogada do PRETO como argumento, e deve retornar a jogada-resposta. Além disso, pode executar as atualizações necessárias em suas estruturas internas.

Para evitar conflitos com outros programas, usaremos pacotes. Cada pacote definirá um espaço de nomes diferente, evitando conflitos. Para usar pacotes em Common LISP, e para exportar as funções necessárias para este projeto, basta que seu arquivo comece com as seguintes linhas:

(make-package 'raNNNNNN)
(in-package raNNNNNN)
(use-package 'common-lisp)
(export '(preto-inicia preto-responde branco-inicia branco-responde))

onde NNNNNN é o seu RA. Exemplo: se seu RA é 973451, use ra973451 como nome do pacote. Seu programa pode deve ser submetido num único arquivo chamado raNNNNNN.lsp, onde novamente NNNNNN é o seu RA.

Funcionamento mínimo

O funcionamento mínimo é importante pois ele tem implicação direta na nota do aluno. Programas cumprindo o funcionamento mínimo terão nota maior ou igual a 5.0, enquanto que os que não cumprirem o funcionamento mínimo terão nota menor que 5.0.

Neste projeto, o funcionamento mínimo é o seguinte: seu programa não poderá perder mais do que 10% das partidas disputadas por desclassificação. Perder uma partida por desclassificação significa fazer uma jogada inválida ou não retornar em tempo hábil.

Avaliação

Os programas de todos os alunos que entregarem no prazo, ou até dez dias após o prazo, serão colocados num campeonato. Este campeonato consiste em jogar uns contra os outros e ver quem acumula mais pontos. Os pontos são contados da seguinte forma: 2 para vitória, 1 para empate, 0 para derrota (desclassificação conta como derrota).

Os jogadores serão ordenados pelo total de pontos. Os que não fizeram o funcionamento mínimo serão removidos da lista. O primeiro colocado tira 10 (dez). O último colocado fica com 5 (cinco). Os outros terão sua nota calculada por interpolação de seu total de pontos em relação ao interalo [5,10]. Por exemplo, se houver quatro jogadores A, B, C e D que obtiveram 7, 4, 7 e 6 pontos respectivamente no campeonato, então as notas serão assim: A=10, B=5, C=10, D=8,33.

Após tudo isso, será descontada nota devido aos dias de atraso, se houver. Como punição por atraso, o aluno perde nota à razão de 10% ao dia. Por exemplo, um aluno que tiraria 7 e tenha 5 horas de atraso ficaria após o desconto com 7 - 7*5/24*10% = 6,85.

A nota dos que não cumprirem o funcionamento mínimo será 5 multiplicado pela fração de partidas onde o programa não perdeu por desclassificação. Por exemplo, se em 110 partidas o programa se desclassificou em 20 delas, a nota é 5*(90/110) = 4,09.

Como sempre, programas iguais ou suficientemente parecidos serão punidos com nota zero para todos os envolvidos e informação à Coordenadoria de Graduação para as devidas providências.

Joao Meidanis

Last modified: Sat Apr 24 08:03:45 BRT 2004 by JM