UNIVERSIDADE FEDERAL DE MINAS GERAIS

INSTITUTO DE CIÊNCIAS EXATAS

DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO

ALGORITMOS E ESTRUTURAS DE DADOS II

Prof. Raquel O. Prates 23 de março de 2006

Trabalho Prático I – Otelo

Data de entrega: 11 de abril de 2006

Penalidade por atraso: 10% por dia de atraso

Objetivo do trabalho: O objetivo deste trabalho é permitir aos alunos aprender a linguagem PASCAL, refletir e aprender sobre boas técnicas de programação e praticar técnicas de análise de algortimos

Descrição do jogo Otelo:

Otelo, também conhecido por Reversi, é um jogo que usa um tabuleiro, com dois jogadores. Um jogador (vamos chamá-lo de Branco) joga com pedras brancas (denotadas aqui por “o”) e outro (vamos chamá-lo de Preto) joga com pedras pretas (denotadas por “x”). (Normalmente o jogo possui peças coloridos contendo um lado branco e outro preto, que vão sendo viradas durante o jogo).

O tabuleiro é composto por 8 linhas e 8 colunas, totalizando 64 casas:

 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 

O jogo inicia-se com a seguinte disposição, com duas pedras de cada cor no centro:

 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . o x . . .
 . . . x o . . .
 . . . . . . . .
 . . . . . . . .
  . . . . . . . .

Preto começa primeiro e depois os dois adversários alternam suas jogadas, até que nenhum lado tenha uma jogada válida, ou até o tabuleiro estar totalmente preenchido. Então o jogador com mais pedras de sua cor ganha o jogo, podendo haver empate.

O que é uma jogada válida?

É colocar uma pedra no tabuleiro numa posição

1. que deve estar vazia antes da jogada,
2. ao colocar a pedra deve cercar uma ou mais pedras consecutivas do adversário, em linha horizontal, vertical ou diagonal.

Cercar significa ter no meio de duas pedras de mesma cor uma ou mais pedras consecutivas de outra cor. Note-se que uma das duas pedras cercantes deve ser a recentemente colocada através da jogada.

O resultado da jogada é mudar a cor das pedras cercadas para a sua cor.

Por exemplo, Preto pode jogar na posição abaixo, pois cerca uma pedra branca entre duas pedras pretas.

 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . o x . . .
 . . . x o . . .
 . . . . x . . .
 . . . . . . . .
 . . . . . . . .

resultando no seguinte:

 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . o x . . .
  . . . x x . . .
 . . . . x . . .
 . . . . . . . .
 . . . . . . . .

Branco pode jogar agora por exemplo assim:

 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . o x . . .
 . . . x x . . .
 . . . o x . . .
 . . . . . . . .
 . . . . . . . .

e com isso resulta em:

 . . . . . . . .
 . . . . . . . .
  . . . . . . . .
 . . . o x . . .
 . . . o x . . .
 . . . o x . . .
 . . . . . . . .
 . . . . . . . .

Sendo a vez do Preto ele pode então jogar por exemplo assim:

 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . o x . . .
 . . . o x . . .
 . . x o x . . .
 . . . . . . . .
 . . . . . . . .

e com isso resulta em:

 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . o x . . .
 . . . x x . . .
 . . x x x . . .
 . . . . . . . .
 . . . . . . . .
 
 

Observe nesta última jogada que a peça colocada por Preto, mudou a cor das pedras em duas direções (horizontal e diagonal), pois cercou peças do Branco nas duas direções de uma vez.

Quando um jogador não consegue fazer uma jogada válida, então perde a vez e passa ao adversário.

Você pode visitar o site http://www.intergate.com.br/lazer/otelo/otelo.html e jogar contra o computador para entender melhor o jogo.

Descrição do Trabalho:

O trabalho deve ser feito em duplas utilizando para isto a linguagem PASCAL. A dupla deverá implementar o jogo, para ser jogado por 2 jogadores, onde cada jogador alterna, entrando a posição (em coordenadas) em que deseja colocar sua pedra. O jogo não pode aceitar peças em posições que violam as regras. Caso algum jogador tente fazer uma jogada inválida, o jogo pede-lhe para repetir, exceto quando não haja nenhuma jogada válida possível para este jogador, quando então deve ser passada a jogada para o outro. A interface do jogo pode ser simples (e.g.: como a mostrada aqui), no entanto a cada jogada deve ser mostrado o tabuleiro aos jogadores, com o resultado da jogada. Ao final do jogo, deve-se apresentar aos jogadores, o número de peças que cada jogador tem no tabuleiro, dizendo então quem é o vencedor.

Recomendações técnicas:

· A cada momento cada posição do tabuleiro pode conter uma peça branca, uma preta ou estar vazia. A estrutura de dados deve explicitamente representar estas possibilidades.

· O programa deve estar dividido em subrotinas (funções e/ou procedimentos). A divisão deve ser guiada pela semântica do conjunto de comandos. Ou seja, se, por exemplo, existe um conjunto de comandos que verificam se a posição da peça é válida, isto poderia ser uma subrotina.

· Recomenda-se que subrotinas na média tenham no máximo 15 linhas.

O que deve ser entregue:

Cada dupla deverá entregar o código do programa PASCAL, o programa executável e a documentação. A documentação do programa deve apresentar:

· Explicação sobre a estrutura de dados utilizada

· Para cada subrotina apresentar:

o uma breve descrição do que ela faz (+- 2 linhas)

o a análise de sua complexidade (O), justificando a sua conclusão

· A análise da complexidade do programa

· Outras decisões específicas relevantes que tenham sido tomadas durante a implmentação do trabalho

Será marcada uma entrevista da dupla com um dos monitores para apresentar o trabalho. Os 2 membros do grupo devem saber responder a todas as perguntas dos monitores.

---