Desenvolvimento e Implementação de um Jogo de Damas em Prolog

O jogo de damas é uma alternativa de distração para muitas pessoas em todo o mundo. A sua implementação em inteligência artificial é uma tarefa que visa dar a um computador a habilidade de jogá-lo como se fosse um ser humano. Esta tarefa pode ser facilitada quando são utilizadas linguagens de programação em lógica. Baseado em pesquisas bibliográficas, este artigo apresenta as principais características de um jogo de damas e da linguagem PROLOG, além de mostrar os passos do desenvolvimento de um jogo de damas, seguindo tais características. O objetivo final trata da implementação de um protótipo do jogo de damas em PROLOG.

por Andréa Cerqueira

A linguagem de programação PROLOG (Programming in logic) é utilizada pela Inteligência Artificial desde a sua criação, visando a resolver problemas lógicos de simulação do raciocínio do homem através da programação em um computador. Dentre muitos problemas da vida real, que podem ser mapeados por meio de programação lógica, destacam-se os jogos, mais especificamente, para este trabalho, o jogo de damas.

As características do PROLOG associadas às características estratégicas de um jogo de damas proporcionam um ambiente adequado para a programação do jogo através desta linguagem. Assim, é possível mapear os passos da inteligência humana, utilizando-se das jogadas do computador, e ensiná-lo a realizar seus próprios movimentos, a partir do conhecimento das jogadas, das regras e da utilização de uma estratégia.

O artigo visa apresentar as experiências vivenciadas no desenvolvimento de um jogo de damas em PROLOG, realizado como trabalho da disciplina Tópicos em Inteligência Artificial, ministrada para alunos do curso de Ciência da Computação da Faculdade Ruy Barbosa, e justifica-se pela dinâmica dada na assimilação do conhecimento associado às técnicas de Inteligência Artificial, mais especificamente no paradigma do processamento simbólico, que busca resolver problemas de soluções algorítmicas inexistentes ou complexas.

Para o desenvolvimento deste projeto, estabeleceu-se um conjunto de ações que foram distribuídas pelos componentes da equipe. Estas ações foram a pesquisa bibliográfica, o entendimento e a prática do PROLOG, a análise de algoritmos minimax, o levantamento das regras do jogo de damas e a implementação do projeto.

O capítulo dois trata do jogo de damas, o capítulo três apresenta a linguagem PROLOG com suas características, o capítulo quatro descreve a implementação do jogo de damas e o capítulo cinco tece as considerações finais sobre o projeto.

JOGO DE DAMAS

O jogo de damas trabalha com a inteligência, através da manipulação de peças num tabuleiro. O objetivo do jogo é fazer com que um jogador consiga “capturar” as peças do adversário, de forma a deixá-lo sem peças no tabuleiro ou sem movimentações possíveis.

Segundo [1], um jogo de damas é realizado num tabuleiro de tamanho 8x8, com casas escuras e claras em formato xadrez. Nele, as casas são identificadas a partir da combinação coluna x linha, onde as colunas são assinaladas pelas letras de a a h, da esquerda para a direita. Similarmente, as linhas são assinaladas através dos números de 1 a 8, de baixo para cima. A partir dessa convenção, podem-se descrever os lances de uma partida, indicando a movimentação das peças pelas casas. As linhas 1 e 8 são conhecidas como travessas de coroação, uma vez que é em uma dessas travessas que ocorre a conversão de uma peça em dama.

As peças, num jogo de damas, são também conhecidas como peões. Elas possuem as cores branca ou preta, e cada jogo é composto de 24 peças – 12 brancas e 12 pretas.

As regras para o início de um jogo de damas são definidas da seguinte forma:

1. as peças brancas são dispostas no início do tabuleiro, nas casas escuras, das linhas 1 a 3;

2. as peças pretas são dispostas nas casas escuras, das linhas 6 a 8;

3. o tabuleiro deve ser posicionado de forma que a casa escura A1 fique à esquerda do jogador com peças brancas. Da mesma forma, a casa escura H8 deve ficar à esquerda do jogador com peças pretas;

4. o primeiro lance deve ser sempre do jogador com peças brancas.

Após a disposição inicial do tabuleiro e das peças, o jogo inicia. Para que uma partida seja corretamente disputada, as seguintes regras devem ser consideradas:

1. as peças só andam para frente, em diagonal, uma casa de cada vez;

2. quando uma peça consegue parar pela primeira vez numa casa da travessa de coroação da cor oposta, essa peça vira uma dama (uma peça é colocada em cima da outra);

3. se a peça somente passar pela travessa de coroação, nada acontece;

4. as damas deslocam-se para frente e para trás, na diagonal, quantas casas quiserem;

5. as tomadas são obrigatórias, seja para frente, seja para trás;

6. uma tomada pode apanhar uma (tomada simples) ou várias peças (tomada em cadeia);

7. numa tomada em cadeia, a peça pode passar mais de uma vez pela mesma casa vazia;

8. é proibida a tomada de uma mesma peça mais de uma vez, numa tomada em cadeia;

9. se, num mesmo lance, houver mais de uma possibilidade de tomada, é obrigatório que se tome a maior quantidade possível de peças adversárias;

10. a peça e a dama têm o mesmo valor para apanhar ou serem apanhados;

11. as peças tomadas só podem ser retiradas do tabuleiro após o término do lance.

Uma partida é dita encerrada quando um jogador apanhar todas as pedras do adversário ou deixá-lo sem jogadas possíveis. Um jogador pode exigir o empate quando forem jogados 20 lances sucessivos somente de damas ou quando a mesma posição apresentar-se por três vezes consecutivas para um mesmo jogador [1].

Existem estratégias possíveis para se dominar a partida de um jogo de damas. O domínio do centro é uma delas, já que propicia ao jogador mais mobilidade e poder de ação do que jogando pelas casas do canto,possibilitando o ataque ao adversário por quatro diferentes casas. Além desta, existem a do bloqueio, onde as pedras adversárias são imobilizadas, ficando sem movimento, e o algoritmo Minimax, que analisa as possíveis conseqüências das jogadas, pontuando cada escolha.

Essas estratégias, bem como o jogo, podem ser implementadas em diversas linguagens de programação diferentes. Entretanto, a linguagem de programação PROLOG foi a escolhida para o desenvolvimento desse jogo, pois ela dá suporte à tradução da linguagem natural em linguagem de máquina, conforme abaixo.

LINGUAGEM PROLOG

A linguagem PROLOG (Programming in Logic) foi desenvolvida na década de 70 com o intuito de possibilitar a programação das definições lógicas. O objetivo principal era que se pudesse traduzir em linguagem de máquina a linguagem natural, falada por humanos. Essa linguagem é baseada nas relações entre objetos, partindo do princípio de que este é o retrato do mundo real, daí a necessidade de se representar o mundo em um computador.

A tabela 1 mostra a comparação entre as características do PROLOG e das linguagens de programação convencionais, extraídas de [3].

Tabela 1 - Uma comparação entre programas convencionais e programas em lógica [3].

A linguagem trabalha basicamente com estruturas de predicados, fatos e cláusulas, conforme descrições seguintes: predicados: um predicado é uma expressão que retorna YES ou NO quando aplicado a um conjunto de termos. Pode ser considerado descritivo, quando possui um único termo: gosta (chocolate); ou relacional, quando é composto de mais de um termo: ama(mãe, filho); fatos: quando se quer caracterizar um objetivo, utiliza-se um fato, que serve para indicar alguma condição. O fato: canta (Vânia), serve para indicar que Vânia é cantora; cláusulas: servem para definir predicados a partir de outros. Por exemplo, para saber se uma pessoa x é filha de y, deve-se verificar se y é pai de x: filha(x, y) :- pai(y, x).

Para igualar duas expressões, utiliza-se a função de unificação. Pode-se dizer que duas expressões estão unificadas quando, dentre outras condições, são formadas pelo mesmo número de argumentos, a partir de um mesmo predicado.

Além da unificação, é utilizado o recurso de backtracking. Quando uma busca por soluções é realizada, a evolução desta assume o formato de uma árvore de pesquisa. Caso, durante a pesquisa, um objetivo falhe, o PROLOG aciona o backtracking, que retorna pelo mesmo caminho percorrido na árvore, procurando por resultados alternativos [2]. IMPLEMENTAÇÃO DO JOGO DE DAMAS

O desenvolvimento do jogo de damas proposto seguiu as características citadas anteriormente, no que diz respeito às regras das jogadas. Para ajudar e facilitar na implementação do jogo, desenhou-se uma rede semântica, descrita no Apêndice A. Esta rede facilitou o entendimento do negócio e deu suporte à escrita dos predicados, fatos e cláusulas implementados.

O projeto de desenvolvimento foi feito em duas etapas. Na primeira etapa, implementou-se a parte gráfica da ferramenta, com a criação do tabuleiro do jogo, bem como a validação dos movimentos das peças. A caracterização do “ponto de parada” de desenvolvimento desta etapa deu-se através da obtenção de um jogo de damas sem suporte a jogadas entre humano e computador. Para que esse tipo de jogada fosse possível, foi necessária a realização da segunda etapa da implementação, sendo desenvolvido um algoritmo de estratégia para que o computador pudesse responder às jogadas e competir com um ser humano. Alguns algoritmos para implementação das jogadas do computador foram pesquisados, dentre eles o Minimax. Entretanto, neste trabalho, utilizamos apenas a heurística na regras de movimentação e captura de peças.

a. Estrutura do Banco de Conhecimento

A estrutura da implementação do jogo de damas proposto baseou-se no conceito da inteligência artificial e das linguagens de programação naturais. Esse conceito tem como objetivo fornecer os conhecimentos necessários relativos a um determinado assunto. Sendo assim, após o entendimento de como funciona as regras do jogo de damas e o aprendizado da linguagem PROLOG, foi possível criar uma estrutura para que o jogo fosse implementado.

A linguagem PROLOG funciona basicamente com o acesso à memória, como já mencionado na introdução. Outra característica é a facilidade de ler um arquivo com extensão “.dba” de forma seqüencial e carregá-lo na memória do computador utilizando o comando Database, que representa a área de armazenamento de todo o conhecimento utilizado na lógica de programação, podendo essa área ser atualizada, excluída e consultada a qualquer momento da execução do software.

Dentro desse contexto, foram elaboradas algumas estruturas (ou predicados), com o objetivo de mapear as informações conhecidas do jogo de damas. Os principais predicados foram criados, cujos respectivos fatos foram armazenados em um arquivo denominado “BancoDeConhecimento.dba”, sendo esse arquivo carregado para a memória logo no início da execução do aplicativo do jogo de damas.

Dentre as estruturas criadas, destacamos o predicado “casa” – o primeiro a ser criado –, uma vez que faz parte da composição do tabuleiro, sendo necessário criar 64 fatos, um para cada casa. Essa estrutura tem a seguinte definição: “casa(A,B,C,D)”, na qual as letras A, B, C e D são os argumentos e indicam a localização na matriz, o status da casa no tabuleiro (casa com peça, com dama ou vazia), a indicação do jogador (casa com peça ou dama do jogador 1 ou 2, ou então casa vazia) e um argumento para indicar o número seqüencial da casa, respectivamente.

Outro predicado criado foi o “movepeca”, com o intuito de mapear todas as posições no tabuleiro possíveis de serem utilizadas pelos jogadores para mover uma determinada peça, ou seja, são os possíveis caminhos das peças. A estrutura desse predicado “movepeca(A,B,C)” possui três argumentos, sendo A o argumento para indicar a posição de origem da jogada, B a posição de destino da jogada e C a direção da jogada, uma vez que as peças não podem ser movidas para trás. Para esse predicado foram mapeados 98 fatos, sendo 49 para as jogadas das peças brancas e 49 para as jogadas das peças pretas.

Um terceiro predicado criado foi o “comepeca”, com o intuito de mapear todas as posições no tabuleiro que podem ser utilizadas pelos jogadores para capturar uma determinada peça. A estrutura desse predicado “comepeca(A,B,C)” possui também três argumentos, sendo A o argumento para indicar a posição de origem da jogada, B a posição da peça a ser capturada e C para indicar a posição de destino da jogada. Para esse predicado foram mapeados 72 fatos, que são utilizados pelos dois jogadores sem restrições de direção, já que as capturas podem ser efetuadas para trás.

A figura 1 mostra graficamente a estrutura da matriz utilizada para implementar o tabuleiro, contendo também as estruturas dos predicados citados acima:

Figura 1 - Estrutura de predicados do banco de conhecimento

A utilização desses predicados facilitou a implementação do jogo de damas, já que todas as validações das jogadas (movimentações e capturas) eram realizadas acessando essa base de conhecimento. No entanto, esse mapeamento, apenas, não é o suficiente para fazer funcionar o jogo, sendo também desenvolvidas diversas cláusulas contendo uma lógica de implementação capaz de analisar e processar todos os passos do jogo de damas.

Nessa implementação, foi de grande importância o uso da recursividade, uma vez que, praticamente, todas as cláusulas utilizadas foram estruturadas de forma recursiva, garantindo um código mais “enxuto” e de qualidade.

b. Implementação da Parte Gráfica do Jogo de Damas

Para que fosse possível o início do desenvolvimento da parte gráfica, foi necessária a criação de um escopo. Nele deveriam estar contidas as ações a serem tomadas na implementação. Assim, de acordo com as regras descritas no início deste artigo, ficou definido que a parte gráfica seria constituída de: tabuleiro com casas, peças brancas e peças pretas; possibilidade de movimentação das peças para casas válidas; possibilidade de “captura” de uma peça adversária; área para descrição das jogadas; área para informar que uma jogada errada não foi processada.

Para construir o tabuleiro, foi utilizado o artifício de desenhar uma janela, de cor branca, maior, devidamente calculada para conter mais 32 janelas de cor preta, sendo esta a forma encontrada para resolver o problema da limitação de janela que a linguagem PROLOG possui.

Utilizou-se também um banco de conhecimento para armazenar o estado inicial do tabuleiro. Este banco de conhecimento armazena todas as casas do tabuleiro, definindo quais as casas possuem peças (1 – brancas, 2 – pretas) e damas (4-brancas, 5-pretas). Casa que não tem peça, mas possui movimentação (3) e casa que não tem movimentação (0), ou seja, todo o conhecimento que se tem e que será adquirido durante a partida do jogo de damas. Este recurso da linguagem PROLOG contribuiu para tornar a codificação mais simples, legível e conseqüentemente mais fácil de ser compreendida.

A figura 2 apresenta uma matriz estática, com o mapeamento de linha e coluna para referenciar as 64 casas que compõem o tabuleiro. Cada casa é representada por um símbolo composto de um número e uma letra indicando a linha e a coluna, respectivamente. Ao iniciar o jogo, e em cada jogada efetuada, a matriz é percorrida pela cláusula “imprimeMatriz”, e para cada símbolo da matriz são analisadas as informações complementares para desenhar a casa.

Porém, cada uma dessas casas possui suas próprias características. Sendo assim, o predicado no banco de conhecimento denominado casa contém quatro argumentos: o primeiro representa o símbolo correspondente na matriz de referência, o segundo indica a presença da peça ou da dama e a respectiva cor da casa, o terceiro argumento informa a que jogador pertence a peça ou dama, caso exista na casa, e o quarto uma numeração seqüencial das casas.

Figura 2 - Matriz do tabuleiro As peças são movidas de acordo com comandos dados pelo usuário, no momento da sua jogada. No exemplo da figura 3, abaixo, pode-se verificar a estrutura do tabuleiro no seu estado inicial.

Figura 3 - Tabuleiro no estado inicial do jogo de damas

Caso seja solicitada a movimentação da peça branca na casa 3C para a casa 4B, é feita uma pesquisa no banco de conhecimento, para analisar se se trata ou não de uma movimentação válida. Além disso, observa-se se realmente é a vez do jogador e se existe a possibilidade de captura.

O resultado da movimentação, bem como o comando executado, pode ser visto na figura 5. Nela, a nova estrutura, após a movimentação, mostra que a casa 4B possui a peça, e a 3C se encontra vazia. Note que a figura 4 já contém a jogada do adversário, que é automática, seguindo essa mesma noção para as demais figuras.

Figura 4 – Tabuleiro após uma jogada inicial

Existe a possibilidade de o jogador realizar um movimento inválido. Neste caso (ver figura 5), será enviada para o jogador uma mensagem informando que a jogada foi realizada com erro.

Figura 5 – Tabuleiro com uma jogada inválida

Caso um jogador esteja numa posição em que seja possível realizar uma captura de uma peça adversária, ele é obrigado a fazê-la. Conforme a figura 5, a peça branca da casa 4F tem a possibilidade de realizar duas jogadas de captura de peça. Pela regra, a escolha deve ser a que proporcionar um maior número de captura. No exemplo, podemos capturar duas peças pretas com as jogadas 4Fx6D; 6Dx4B (capturar as peças da casa 5E e da 4D). Pode-se também realizar as jogadas 4Fx6D; 6Dx8B.

Figura 6 - Tabuleiro com Captura de Peça

Neste caso, a vez somente será dada ao adversário quando não existir mais nenhuma peça para captura. É importante ressaltar que não foi implementada uma das regras do jogo de damas, a retirada das peças capturadas do tabuleiro apenas ao término da jogada.

Conforme ilustração na figura 7, se a peça sai da casa 4F com destino à casa 8B, ela se torna dama, uma vez que realizou a movimentação e chegou a uma linha de coroação. O resultado desta movimentação e da peça sendo coroada é ilustrado na figura 7.

Figura 7 – Tabuleiro com peça sendo coroada

Embora o escopo do trabalho não comportasse a coroação da peça em dama, mesmo sendo uma regra do jogo, chegou-se a um ponto do trabalho onde tivemos a necessidade de implementar essa regra. Como as regras de movimentação da peça não permitem movimentos “para trás”, quando chegamos à linha de coroação (linha 8) a peça não movimentava mais, exceto para capturas obrigatórias. Para evitar esse “porco”1, implementamos a coroação da peça em dama e permitimos as movimentações “para trás”.

Utilizamos a regra de movimentação da peça, apenas uma casa na diagonal esquerda ou direita, conforme mostra a figura 8.

Figura 8 – Tabuleiro com a movimentação da dama

Existem diversas regras para se finalizar um jogo de damas, como, por exemplo, não existir mais a possibilidade de movimentação de nenhuma das peças brancas ou pretas que estejam no tabuleiro. A única regra implementada é a de não existir nenhuma peça branca ou preta no tabuleiro. A figura 10 ilustra um término de uma partida.

Figura 9 – Tabuleiro no final do jogo de damas

As maiores dificuldades em se implementar a parte gráfica do jogo de damas foi a falta de conhecimento na linguagem PROLOG. Além disso, o estouro de pilha era constante, o que possibilitava apenas oito jogadas e impedia, com isso, a continuação e a finalização do jogo. Uma solução paliativa foi adotada, a de salvar as jogadas no banco de conhecimento e restaurá-las, quando ocorria o estouro da pilha. Resolvemos o problema utilizando o comando de corte 1 (!) da linguagem PROLOG – responsável por desempilhar as instruções de memória, ao perceber-se que nem todas as cláusulas recursivas eram desempilhadas.

A parte gráfica provê uma partida de jogo de damas completa, entre dois adversários humanos. A próxima seção informa-nos como se deu o desenvolvimento da estratégia do jogo de damas, que permite ao computador responder as jogadas humanas.

c. Desenvolvimento da Estratégia do Jogo de Damas

Para que fosse possível a realização de partidas entre um jogador humano e o computador, era necessário que uma certa “inteligência” fosse implementada ao jogo. Essa “inteligência” deveria ser útil para que o computador pudesse responder a jogadas realizadas por humanos de forma correta e competitiva.

Existem diversas deduções diferentes para a implementação das estratégias num jogo de damas. A mais conhecida e difundida é a estratégia do algoritmo Minimax. d. Algoritmo Minimax

É um algoritmo de busca em árvore por profundidade, cujo objetivo principal é ajudar a escolher a melhor ação a ser tomada em uma situação ou em jogos em que os participantes desejem alcançar resultados mutuamente exclusivos[4].

O Minimax baseia-se no princípio de maximizar o ganho de um jogador “A” tentando minimizar as possibilidades de ganho de um jogador “B”. Para cada jogada, um jogador irá escolher o melhor movimento possível para ele e, ao mesmo tempo, o pior para o seu adversário [4,5].

O Minimax trabalha através da construção de uma árvore de jogo. Esta árvore deve possuir todas as jogadas possíveis. Para abstração do jogador em ação, deve-se atribuir todas as jogadas disponíveis para o próximo jogador, alcançando o nível que se deseja chegar, e ressaltar que o último nível deve ser sempre o do jogador da vez [4,5.6].

O Minimax irá fazer uma busca na árvore, até um determinado nível, avaliando e atribuindo um valor a cada movimento possível. Essa busca deve retornar ao valor mais alto e ao mais baixo, dentre as possíveis jogadas de um nível da árvore.

A figura 10 mostra uma árvore simulando a progressão em um jogo de damas, através das próximas quatro possíveis jogadas, considerando o jogador em ação como sendo o que possui peças pretas.

Figura 10 –Progressão para as próximas quatro jogadas [4]

Conforme a figura 10, acima, o jogador com peças pretas pode obter uma maior pontuação se escolher a jogada de maior valor, enquanto que, para o jogador de peças brancas, a melhor pontuação dar-se-ia escolhendo o caso no qual o jogador com peças pretas escolhe a jogada de menor valor.

Efetuando-se uma análise algorítmica no Minimax, pode-se observar que o trabalho dele cresce exponencialmente com o aumento da profundidade. Para tentar diminuir o tempo de busca e, ainda assim, tentar chegar a um melhor resultado, deve-se utilizar o corte alfa-beta.

O corte alfa-beta parte do princípio de que um jogador nunca conseguirá fazer uma boa jogada caso permita ao seu adversário realizar uma jogada melhor. Dessa forma, se uma jogada aparece com pontuação menor que o melhor valor até o momento, o algoritmo será interrompido, iniciando-se a busca neste ramo da árvore [4,5,6]. Um exemplo de corte alfa-beta pode ser visualizado na figura 11.

Figura 11 – Exemplo de utilização do corte alfa-beta [4]

Conforme observado na figura 11, o corte alfa-beta reduz o tamanho da árvore a ser pesquisada, visando diminuir o tempo de busca.

Apesar de ser uma boa estratégia para se implementar num jogo de damas, a complexidade de implementação deste algoritmo, associada ao curto espaço de tempo para desenvolvê-lo, restringiu o escopo final do trabalho.

e. Estratégia Implementada

Com a utilização da função minimax e heurísticas de peso, obteríamos uma melhor resposta do algoritmo. Devido a sua complexidade, não se utilizou o minimax, sendo adotada uma heurística para se implementar a estratégia do jogo de damas. A estratégia considera a melhor jogada aquela que dificulta a captura da peça pelo adversário.

A estratégia implementada no jogo de damas utilizou todas as informações fornecidas pelo banco de conhecimento, uma vez que nesse banco estavam mapeadas todas as casas do tabuleiro, todas as possíveis jogadas de uma peça, jogadas simples e captura. A partir de tais informações, observa-se que todo esse mapeamento não descaracteriza a implementação do jogo, já que ele pode ser feito em qualquer tabuleiro, bastando, para isso, seguir as regras do jogo de dama visto na figura 12.

Figura 12 – Mapeamento do tabuleiro das jogadas possíveis

Sendo assim, para iniciar a estratégia foi necessário analisar todo o tabuleiro, ou seja, localizar primeiramente as peças do jogador que irá jogar automaticamente. Para isso, foi criada uma cláusula listando todas as casas que contêm peças do jogador automático. No caso do jogador 2, fazendo uso do predicado “casa” do banco de conhecimento. A partir dessa lista, utilizando o recurso para salvar no banco de conhecimento, foram gravadas todas as jogadas possíveis do jogador no predicado definido como “jogadaspossiveis”. Uma vez carregadas todas as jogadas, aplica-se uma cláusula com o objetivo de verificar cada jogada possível. É nessa verificação que está embutida a heurística, observando-se que quanto maior o número de heurísticas e melhor a sua qualidade, mais inteligente será a jogada. A primeira heurística implementada foi simples e ineficiente. O seu funcionamento baseava-se na consulta da lista de possíveis jogadas, sendo selecionada a última jogada da lista. Essa estratégia foi denominada de “Suicida”, pelo fato de a última peça da lista ser sempre selecionada quando fosse capturada ou bloqueada.

Posteriormente, foi introduzida a segunda heurística ao jogo, utilizando uma análise mais detalhada das possíveis jogadas, atribuindo pesos para cada jogada e selecionando a jogada que possui o maior peso. Com esse recurso de atribuição de peso, as próximas heurísticas diferenciam-se umas das outras apenas no fator considerado para a análise.

A formação do fator da segunda estratégia foi escolher uma jogada que não tivesse risco de perda da peça, ou seja, a análise está relacionada com a proximidade da peça às peças do adversário. O fato de a peça se movimentar apenas nas diagonais limita a quantidade de movimentações; portanto, cada peça terá no máximo duas movimentações possíveis. A possibilidade de movimentação das peças é analisada atribuindo-se peso a cada movimentação. O maior peso é dado à movimentação da peça que fique com pelo menos uma casa vazia entre a nova posição e qualquer peça do adversário.

Esse procedimento é realizado em todas as peças. Após todo mapeamento, a jogada realizada é a de maior peso, conseqüentemente, a de menor risco. Como não utilizamos nenhuma outra heurística, quando temos pesos iguais é realizada a primeira jogada encontrada. A heurística analisa casas adjacentes à casa de destino da jogada em questão (a jogada é composta pela casa origem e casa destino). A figura 13 mostra como é realizada a análise e a contribuição do valor dos pesos atribuídos a cada jogada possível:

Figura 13 - Estrutura da estratégia implementada no jogo de damas

Para analisar a qualidade da jogada da peça situada na casa “7E”, conforme mostra a figura 13, a estratégia é verificar as possíveis jogadas da peça que está na referida casa. Sendo assim, os deslocamentos da peça preta serão para as casas “6D” ou “6F”. A partir dessa informação, são checadas as próximas casas adjacentes a esse deslocamento, ou seja, o algoritmo checa as casas “5C”, “5E” e “5G”, verificando os status de cada uma. As casas que estiverem vazias ou com peças do próprio jogador recebem pontuação 10; já as casas contendo peças do adversário não receberão pontuação, e terão valor zero.

Após essa análise, são totalizadas as pontuações de cada folha da árvore e atribuídos aos nós antecessores que correspondam às possíveis jogadas. Posteriormente, escolhe-se a jogada com maior pontuação. No exemplo ilustrado na figura 13, a melhor jogada será a movimentação da peça da casa “7E” para a casa “6F”.

Nessa estratégia, pode ocorrer a igualdade na pontuação para mais de uma jogada possível; nesse caso, é escolhida a primeira jogada analisada.

A dificuldade maior para a implementação dessa estratégia seria a análise para pontuação da dama movimentando-se pelas diagonais do tabuleiro. Como essa movimentação ainda não foi implementada, a implementação não está complexa, já que utiliza também o banco de conhecimentos.

CONCLUSÃO

Programar a inteligência humana em computadores é uma tarefa que requer conhecimento, tanto em relação ao negócio que se está implementando, quanto em relação à linguagem de programação utilizada. Para que fosse possível o desenvolvimento de um jogo de damas utilizando a linguagem de programação PROLOG, o primeiro passo dado foi a descoberta de regras básicas do jogo, como a posição das peças em um tabuleiro, as possíveis estratégias para se ganhar ou empatar uma partida, dentre outras.

As maiores dificuldades encontradas diziam respeito à utilização da linguagem PROLOG, pois sua estrutura, comandos e características não eram do conhecimento de nenhum componente da equipe. Apesar de toda dificuldade e do tempo despendido com o desenvolvimento deste trabalho, o retorno, em termos de conhecimento adquirido, foi positivo. Este retorno se deu, principalmente, por causa do esforço conjunto da equipe em aprender a utilizar a linguagem e, conseqüentemente, desenvolver o jogo de damas.

Apesar de ter sido desenvolvido a partir da estratégia descrita na seção de implementação da ferramenta, sugere-se a implementação da estratégia utilizando outros algoritmos, inclusive o Minimax. Somente assim será possível realizar a análise da melhor estratégia para o jogo de damas e, com isso, aprofundar os estudos com programação em lógica.

REFERÊNCIAS BIBLIOGRÁFICAS:

[1] FERRINHO, Carlos Alberto. ABC do Jogo de Damas. Manual de regras básicas regulamentadas para o jogo de damas. 1996. Disponível em: . Acesso em: 02 mar. 2004.

[2] BIANCHI, Reinaldo Augusto da Rocha; RILLO, Anna Helena Reali Costa. PROLOG. Apostila de aulas visando o aprendizado da linguagem de programação PROLOG. Versão 2.1, 1999.

[3] PUC. Rio. Site de iniciação científica dos alunos de graduação em Matemática. Disponível em: . Acesso em:03 mar. 2004.

[4] Instituto de Informática da UFRG. Um Jogo de damas com processamento distribuído de jogadas. Disponível em: . Acesso em: 03 mar. 2004.

[5] Centro de Inteligência Artificial – CENTRIA. Pesquisas em Jogos. Disponível em: . Acesso em: 03 mar. 2004.

[6] Faculdade de Engenharia da Universidade do Porto. Relatório da Implementação de um jogo de damas, utilizando interface Java e estratégias em YAP. Acesso disponível em: . Acesso em: 03 mar. 2004.