Trabalho Final

O Jogo das Damas

Sumário

1  Objectivos

O objectivo do trabalho final é o desenvolvimento de um programa para jogar o Jogo das Damas.  O trabalho deverá ser realizado em Linux, fazendo uso das bibliotecas Slang++, IPC++ e Utilitarios, distribuídas num pacote único de nome... Pacotes.  O manual das bibliotecas está disponível em HTML ou em PDF.  O pacote está disponível para instalação e chama-se Pacotes-1.0.tar.gz.

O programa a desenvolver funcionará em modo texto.  I.e., não fará uso das capacidades gráficas do ambiente XWindows (KDE) disponível no Linux.  No modo texto das consolas Linux, o ecrã correspondente à consola divide-se numa matriz de células, cada uma das quais pode conter um caractere qualquer com diferentes atributos (i.e., cor do fundo e cor do texto ou símbolo).  Com algum esforço é possível desenhar um tabuleiro de damas neste ambiente.

A matriz de células do ecrã tem um número de linhas e colunas que pode variar no tempo, i.e.: o utilizador pode redimensionar a janela da consola.  No entanto, o programa que deverá desenvolver não precisa de estar preparado para lidar com esta possibilidade.

O trabalho divide-se em duas fases, correspondendo a duas entregas de resoluções por parte dos alunos.  A primeira fase é naturalmente menos ambiciosa nos seus objectivos que a segunda fase, servindo sobretudo como incentivo à dedicação dos alunos ao trabalho o mais cedo possível.  Os objectivos de cada uma das fases serão descritos mais abaixo. 

1.1  O jogo

O Jogo das Damas é bem conhecido.  No entanto, as suas regras podem apresentar variantes.  Apresentam-se aqui as regras da variante que servirá de base a este trabalho, as regras das chamadas Damas Clássicas.

1.1.1  O tabuleiro e as peças

O jogo desenrola-se entre 2 jogadores, sobre um tabuleiro de 8×8 (64) casas.  Essas casas são coloridas em brancas e pretas alternadamente (ou mais genericamente, claras e escuras - tabuleiro clássico), com o quadrado (casa) inferior direito de cor clara, ou seja a grande diagonal (escura) deve ficar sempre à esquerda de cada jogador.

Cada jogador dispõe de 12 peças idênticas, 12 peças brancas de um lado e 12 peças pretas do outro, colocadas nas três primeiras filas horizontais consecutivas de cada lado do tabuleiro e sobre as casas de cor escura.  Os jogadores jogam alternadamente.  A jogada inicial cabe sempre a quem estiver com as peças brancas. 

1.1.2  Jogadas

Os jogadores efectuam jogadas em alternância, uma só de cada vez. 

Cada peça existente no início do jogo (Peão) só se move para a frente em relação ao respectivo jogador, em diagonal e em direcção ao campo adversário, sobre as casas de cor escura, uma casa de cada vez.

Se uma peça encontra uma peça contrária na posição imediatamente contígua e o quadrado a seguir na mesma direcção estiver vazio, pode "saltá-la" (captura), retirando-se imediatamente a peça capturada do tabuleiro.  Este procedimento pode repetir-se após cada salto (captura), caso logo a seguir a peça se volte a encontrar numa situação semelhante.  Assim, torna-se possível capturar várias peças numa única jogada.

Se uma peça consegue atingir a primeira fila de casas do campo contrário então é transformada em peça do tipo Dama, o que em geral se realiza empilhando uma outra peça já capturada sobre a primeira.  Esta nova peça resultante (a Dama) tem movimentos mais amplos e pode saltar e capturar sobre uma diagonal sem limitação de espaços para o salto.  A Dama pode andar para a frente e para trás mas não pode saltar uma peça da mesma cor.

A captura é obrigatória.  Duas peças juntas (contíguas), sobre a mesma diagonal, não podem ser capturadas.  O Peão pode capturar uma Dama e uma Dama pode capturar Peões, tendo assim as duas peças o mesmo valor para fins de captura.  Se na mesma jogada se apresentar mais de um modo de exercer captura, é obrigatório executar a jogada que capture o maior número de peças.  Além disso, se houver mais de uma situação com o mesmo número de capturas possíveis, deve-se preferir a que contiver peças mais poderosas (preferindo Dama a Peão) e em maior quantidade, caso isso seja aplicável.

Numa jogada de captura é permitido passar várias vezes por uma mesma casa vazia não sendo permitido capturar a mesma peça mais de uma vez nem as peças capturadas podem ser retiradas do tabuleiro antes do fim da jogada de captura.

1.1.3  Actualização de resultados

Depois de uma jogada, a imagem do tabuleiro no ecrã deve reflectir em todo o tempo o resultado do efeito acumulado de todas as jogadas já realizadas. 

Ganha o jogador que captura todas as peças contrárias ou as deixa numa situação de não terem qualquer movimento possível. 

Uma situação de empate ocorre após 20 jogadas sucessivas de damas sem que haja captura de peça.  Outras situações de empate ocorrem ao fim de cinco jogadas quando existem: (a) duas Damas de cada lado; (b) duas Damas contra uma; (c) duas Damas contra uma Dama e um Peão; (d) uma Dama contra uma Dama e (e) uma Dama contra Dama e Peão.

Ambos os jogadores devem ter perfeito conhecimento da disposição e natureza de todas as peças presentes sobre o tabuleiro, ou seja todas essas peças devem estar visíveis e reconhecíveis. 

1.2  O jogo a implementar

Pretende-se neste trabalho desenvolver um Jogo das Damas com regras mais simples.

1.2.1  Regras simplificadas

Em relação às regras descritas atrás devem ser consideradas as seguintes simplificações:

  1. Não há obrigatoriedade de capturar peças adversárias, tendo o jogador apenas que respeitar os tipos de movimentos permitidos pela peça que vai jogar. 
  2. As Damas movimentam-se como os Peões, podendo, no entanto, deslocar-se para trás, quer em movimento simples, quer saltando peças de cor diferente.
  3. Se num movimento for alcançada a linha de transformação de Peão em Dama e ainda forem possíveis outros movimentos de captura, estes devem ser permitidos, embora já depois de realizada a sua transformação em Dama.
  4. Não se consideram situações de empate.  Ou seja, em casos extremos um dos jogadores poderá ter de desistir, deixando as suas peças serem capturadas.

1.2.2  Interface com o utilizador

  1. Quando numa jogada for possível capturar mais que uma peça, tendo o jogador escolhido as casas de origem e de destino, o programa deve avisar o jogador que a jogada só é realizável usando mais do que um movimento.  Após este aviso, deve permitir ao jogador realizar os movimentos necessários para capturar as várias peças (um de cada vez).
  2. Do ponto de vista do computador uma jogada de uma jogador só termina quando:
    1. O movimento realizado consiste num movimento simples, sem captura.
    2. O movimento realizado consistiu num movimento de captura, mas a partir da localização final da peça não são possíveis outras capturas.
    3. O movimento realizado consistiu num movimento de captura, é possível realizar outras capturas a partir da posição final da peça, mas o jogador opta, por razões eventualmente tácticas, não a efectuar.
    4. Quando o jogador com a iniciativa do movimento decide desistir do jogo.

A interface do programa com o utilizador deverá ser fácil de usar, recorrendo-se para tal à biblioteca Slang++.

Atempadamente serão disponibilizados ficheiros executáveis oficiais, cuja interface com o utilizador deverá ser emulada pelos programas desenvolvidos pelos alunos.  Sempre que surgirem dúvidas acerca do comportamento pretendido para o programa a desenvolver, os alunos deverão reproduzir o comportamento exibido pelos programas oficiais.

Os ficheiros executáveis oficiais estão disponíveis através dos comandos

damas_solitárias_oficiais

damas_oficiais

disponíveis na máquina mercurio, no directório /usr/local/bin/.  Em breve serão disponibilizados também a partir de esta página.

O primeiro ficheiro executável corresponde a um jogo das damas em que alternadamente o jogador, solitário, efectua jogadas das peças brancas e pretas.  O segundo ficheiro executável corresponde a um jogo das damas em que o jogador joga contra outro jogador usando um programa equivalente, e exige comunicação entre processos.

1.2.3  Protocolo de comunicação

1.2.3.1  Quem começa?

A negociação é simples.  Cada um dos processos (um processo é a execução de um programa) gera um número aleatório recorrendo à função rand().  Depois comparam os resultados.  Se forem iguais, cada um gera novo número aleatório e o tenta-se de novo.  Se forem diferentes, aquele que tiver gerado o número maior joga com as peças brancas e é o primeiro a jogar.  A função rand() gera números pseudo-aleatórios, e portanto sempre a mesma sequência, o que pode levar a negociação a um impasse se ambos os processos começarem na mesma localização nessa sequência.  Para o evitar, deve-se começar por executar a instrução:

srand(getpid());

que levará, em princípio*, o gerador em cada processo a começar num ponto diferente da sequência de números pseudo-aleatórios.

A comunicação durante a inicialização consiste, assim,  no envio e recepção de inteiros com o objectivo de determinar qual dos dois processos (e respectivo utilizador) terá o privilégio de ficar com as peças brancas.  Ver exercício 2 da Aula Prática 11.

* Ou seja, continua a haver a possibilidade (remota), de os processos ficarem num impasse. Nesse caso a solução é matá-los... 

1.2.3.2  Jogadas

Durante uma jogada, um jogador tem um papel activo e o outro tem um papel passivo.  O jogador que realiza uma jogada deve movimentar uma das suas peças de acordo com as regras apresentadas atrás e o outro tem apenas de observar a jogada realizada.  No final da jogada o jogador activo deve enviar ao outro os movimentos que realizou.  O tabuleiro do jogador passivo deve, então, ser actualizado de acordo com os movimentos realizados pelo outro jogador.

No final de uma jogada, o jogador activo deve transmitir a seguinte informação:

  1. Número de posições ocupadas pela peça movimentada (o número de posições depende do número de movimentos da peça durante a jogada, incluindo a posição inicial e a posição final).
  2. A posição (linha e coluna separadamente) de cada uma das posições ocupadas.

O jogador passivo recebe esta mesma informação, pela mesma ordem, e utiliza-a para alterar o estado do tabuleiro, de modo a reflectir a jogada do outro jogador.

1.2.4  Exemplo de interacção com o utilizador

A interface é muito simples.  Em vez de se descrever aqui, optou-se por disponibilizar uma versão oficial do ficheiro executável.  Os alunos devem testá-lo e emular a sua interface.  

Abaixo apresentam-se três exemplos de interacção do programa com o utilizador.

Figura 1: Início do jogo.

 

Figura 2: Captura de Peão preto.

 

Figura 3: Jogada realizável em mais do que um movimento (há um Peão branco sob a caixa de aviso).

 

Figura 4: Captura de um Peão por uma Dama (andando para trás).

2  Fases do trabalho

O trabalho divide-se em duas fases, correspondendo a final da primeira à entrega intermédia prevista no método de avaliação da disciplina.  A segunda fase corresponde à entrega definitiva.

2.1  Entrega intermédia

Corresponde a um programa que serve para testar o funcionamento de algumas rotinas.  As rotinas a desenvolver nesta fase do trabalho são as seguintes:

  1. Rotina responsável pelo desenho do tabuleiro de jogo (sem peças).
  2. Rotina responsável pela colocação inicial das peças no tabuleiro de jogo.  Nesta fase considera-se que o tabuleiro tem apenas peões de cor branca, pelo que as quadrículas do tabuleiro estão apenas livres ou ocupadas.  Os peões são colocados a sul do tabuleiro.  Deverá adaptar a rotina de desenho do tabuleiro de modo a mostrar as posições ocupadas com peões (para já apenas brancos).
  3. Rotina responsável pela selecção interactiva de uma posição ocupada (por um Peão, nesta fase) do tabuleiro.  
  4. Rotina responsável pela selecção interactiva de uma posição livre (mas possível, i.e., escura) do tabuleiro.  
  5. Rotina que dada uma posição ocupada e outra desocupada, devolve verdadeiro se for possível, a partir da posição ocupada, atingir a desocupada, usando as regras simplificadas de movimentação de peões.  Admite-se que a posição ocupada inicial contém uma peça preta (embora não o seja na realidade).  Para testar esta rotina pode-lhe ser útil criar uma rotina que faça uma colocação aleatória dos peões no tabuleiro.

2.2  Entrega definitiva

Corresponde à implementação completa do jogo com as regras simplificadas.   É possível implementar quer a versão das damas solitárias, quer a versão "normal", com parceiro remoto.  No primeiro caso a nota do trabalho nunca será superior a 18 valores.  É possível ainda simplificar o jogo de modo a permitir apenas um movimento por jogada, independentemente de esse movimento originar ou não uma captura.  Esta simplificação implicará que o trabalho não poderá ter uma nota superior a 18 valores.  Com as duas simplificações em simultâneo a nota jamais ultrapassará 17 valores.

3  Dicas

Esta secção irá crescendo com outras dicas.  Mantenha-se atento.

4  Requisitos de implementação

  1. A resolução deste problema deverá recorrer a classes C++ sempre que apropriado. (2ª fase)
  2. Deverão existir as classes Jogo, Tabuleiro, Celula e Peca. (2ª fase)
  3. O jogo deverá ser resistente a todo o tipo de erros.  Em circunstância alguma deve simplesmente abortar ou bloquear! (2ª fase)
  4. Todas as rotinas e operações devem ser claramente documentados, nomeadamente quanto ao seu contrato (pré-condição e condição objectivo).  As condições invariantes das classes devem ser identificadas. (1ª e 2ª fases)
  5. As pré-condições, condições objectivo e condições invariantes devem constar na documentação do código, mas também na forma de instruções de asserção, excepto onde tal for impossível. (1ª e 2ª fases)

5  Condições de entrega e avaliação

5.1  Condições de entrega

O Trabalho Final será resolvido em grupo.  Confirme o registo do seu grupo em http://br.groups.yahoo.com/group/ip-iscte/database?method=reportRows&tbl=16.

5.1.1  Entrega intermédia

5.1.2  Entrega definitiva

  1. Este trabalho será resolvido em grupo (ver página da disciplina).  
  2. A resolução deste trabalho deve ser entregue até as 17:30h de sexta-feira, 24 de Janeiro de 2003 (até as 17:30h de sexta-feira, 31 de Janeiro de 2003, com penalizações).
  3. A resolução só se considera entregue depois de:
    1. ser entregue pessoalmente a um dos docentes da disciplina uma disquete, devidamente identificada, contendo apenas o ficheiro fonte onde se encontra o código C++ (extensão .C);
    2. ser entregue pessoalmente a um dos docentes da disciplina um relatório em papel, usando o modelo publicado para os problemas (Word, ou RTF), contendo um pequeno texto de no máximo uma página A4 explicando as opções tomadas para a resolução e contendo a listagem completa do código; e
    3. ser enviado o ficheiro fonte (também colocado na disquete) via correio electrónico para  Ricardo.Ribeiro@iscte.pt.
  4. Imprima o código em C++ integrado no relatório e sempre de uma forma bem legível: use sempre um tipo não proporcional (e.g., Courier) e, caso seja possível fazê-lo, imprima em papel reciclado, frente-e-verso.  A parte restante do relatório deverá manter os tipos de letra (proporcionais) usados no modelo de relatório.
  5. A entrega do problema fora do prazo implica a penalização de dois (2) valores por cada dia útil de atraso (i.e., 27 de Janeiro -2 valor, 28 de Janeiro -4 valores, 29 de Janeiro -6 valores, 30 de Janeiro -8 valores e 31 de Janeiro -10 valores) não se aceitando trabalhos após as 17:30h de sexta-feira, 31 de Janeiro de 2003.
  6. A não observação dos modos de entrega descritos acima poderá ser penalizada.
  7. Exija ao docente a entrega de um recibo comprovativo da entrega do trabalho.  Este recibo é a única prova que tem da entrega do seu trabalho.

As datas das orais e das inscrições nas orais serão anunciadas logo que possível.

5.2  Avaliação

A avaliação do Trabalho Final terá em conta não só a correcta execução do programa, mas também, e principalmente, a correcta estruturação das classes e métodos  e das rotinas que compõem o programa e ainda a sua legibilidade.  Valorizar-se-á mais a simplicidade que a eficiência.  Valorizar-se-á também código C++ correctamente comentado (mas não excessivamente, não vale a pena comentar o óbvio).

A nota deste trabalho será dada apenas após uma discussão, individual, com cada um dos elementos do grupo. Nesta discussão qualquer elemento do grupo terá de demonstrar um total conhecimento do programa e ser capaz de operar as alterações que forem pedidas.  Nessa oral poderão também ser feitas perguntas sobre a matéria em geral.  A nota final poderá depender não só da qualidade do trabalho, mas também, e principalmente, da avaliação que os docentes façam da participação relativa dos alunos na feitura do trabalho.

Quaisquer funcionalidades extra que não tenham sido pedidas no enunciado, tais como menus mais sofisticados etc., não serão avaliadas.

A  Depuração com o Slang++

A depuração de programas usando o Slang++ apresenta algumas complicações.  Acontece que estas aplicações não podem ser executadas dentro do depurador, pois fazem uso de capacidades do terminal que este não disponibiliza.  Assim, é necessário executar o programa a depurar numa janela xterm normal, fora do gdb, e depois convencer o gdb a "agarrar-se" ao programa já em execução.  Para isso:
  1. Coloque logo no início do programa a depurar uma instrução de leitura do teclado, de modo a que este não avance antes de o desejar.
  2. Lance o gdb dentro do Emacs, como habitualmente, especificando o ficheiro a depurar.  Não dê o comando r[un]!
  3. Execute o programa dentro de uma janela xterm.
  4. Cada instância de um programa em execução é um processo.  Cada processo, em Linux, tem um número de processo (PID, de Process IDentification).  É necessário identificar o número do processo em execução.  Para isso dê (numa consola) o comando:
      ps -auxww | grep nome_do_programa | grep annnnn
    onde nnnnn é o seu número de aluno e nome_do_programa é o nome do programa a depurar.  Surgir-lhe-á uma lista dos processos que são instâncias do seu programa e que lhe pertencem.  É conveniente que tenha apenas um programa em execução de modo a identificar claramente qual o PID que lhe interessa.
  5. No gdb coloque um ponto de paragem onde for conveniente.  Em seguida dê o comando:
      attach pid
    onde pid é o PID do processo identificado na alínea anterior.  Este comando faz com que o gdb passe a controlar o processo.  Dê o comando:
      c[ontinue]
  6. A partir deste momento a depuração prossegue como habitualmente.