Trabalho de Graduação

Universidade São Judas Tadeu

Faculdade de Tecnologia e Ciências Exatas

Trabalho de Graduação

Ciência da Computação

“The Best of Brazilian Draugths”

UNIVERSIDADE SÃO JUDAS TADEU

FACULDADE DE Tecnologia e CIÊNCIAS exatas

Ciencia da Computação

TRABALHO DE GRADUAÇÃO

“The Best of Brazilian Draugths”

Relatório Final do Trabalho de Graduação apresentado à banca examinadora do Curso de Ciência da Computação da Faculdade de Tecnologia e Ciências Exatas da Universidade São Judas Tadeu, como exigência parcial para obtenção do grau de bacharel em Ciência da Computação sob orientação do professor Carlos Eduardo Dantas de Menezes.

Avaliação do trabalho de graduação

Banca examinadora

A - Qualidade e clareza da apresentação 2,0 pontos

B - Nível de conhecimento do assunto 1,5 pontos

C - Cumprimento dos objetivos finais 2,0 pontos

D - Qualidade técnica do projeto 1,0 ponto

E - Implementação e testes 2,0 pontos

F - Documentação o apresentada 1,5 pontos

Agradecimentos

Agradeço a J.R.R. Tolkien quem escreveu “O Silmarilion” uma obra prima e inspiração de todos os dias.

Resumo

Este trabalho visou o desenvolvimento de um sistema utilizando técnicas de inteligência artificial, e decidiu-se pelo famoso jogo de damas, não seria possível prever o tamanho ou os limites do universo vasto e de capital intelectual tão imenso relacionado ao tema deste trabalho acadêmico.

Em pouco tempo de pesquisa é surpreendente encontrar trabalhos excepcionais como o de Arthur Samuel da IBM, que desenvolveu em 1959 um programa que usava técnicas de aprendizado nunca antes estudadas e fazia uso de algoritmo Min-Max também, ou como também o de Jonathan Schaeffer que desenvolveu Chinook, tornando-o o mais conhecido e em 1994 o campeão do mundo, usando poda alfa-beta e uma base de dados para todas possibilidades de finais de jogos para seis peças.

O objetivo dessa monografia não foi o de repetir tal façanha, mas o de ter conhecimento de tais técnicas e desenvolver um jogo que utilizasse as regras Brasileiras para tal. Uma vez que, em sua grande maioria, os jogos são desenvolvidos nas regras Norte-Americanas.

Para isso, os métodos de Busca Heurística, Algoritmo Min-Max e Poda Alfa-Beta, demonstrados abaixo, foram utilizados no desenvolvimento desse trabalho. Continuar o seu desenvolvimento para melhor estudar e aprimorar as técnicas, é de grande importância. A utilização de técnicas de aprendizagem, base de dados para possibilidades de finais, além do aprimoramento da parte gráfica estão previstas para trabalhos futuros.

Palavras-Chave: Inteligência Artificial; Jogo de Damas; Checkers; Regras Internacionais 8x8; Brazilian Draugths; Algoritmo Min-Max; Chinook; Poda Alfa-Beta; Busca Heurística; Aprendizado; SAL; Base de Dados de Finais; Base de Dados de Aberturas; Winbraz; Heuristical Search; Min-Max Algorithm; Alfa-Beta Pruning;

Abstract

This work intended to develop a system using artificial intelligence techniques, and we choose the famous “game of checkers”. It would not be possible to imagine the size or the limits of the vast universe and so immense intellectual capital related to the subject for this academic work.

In little time of research it is surprising to find out exceptional works, like the one of Arthur Samuel from IBM who developed in 1959 a program that used techniques of learning never studied before and also made use of Min -Max algorithm We can also mention Jonathan Schaeffer who developed Chinook, becoming the most famous and the World Champion in 1994, using Alpha Beta Pruning and a database for all possibilities of games ends for six pieces.

The objective of this monograph was not to repeat such exploit, but to have knowledge of those techniques and develop a game using Brazilian rules, because the most of games are developed using North American rules.

The methods of Heuristical Search, Min-Max Algorithm and Alfa-Beta Pruning demonstrated below, were used in this work development. To continue its development for better studying and improving the techniques, is very important. The use of learning techniques, database for possibilities of ends and also the graphics improvement are foreseen for future works.

Sumário

Introdução

Da História do Jogo de Damas

Regras do Jogo

Comparação entre as Regras

Regras Internacionais 8x8 do Jogo de Damas

Solução de Problemas de Jogos envolvendo Inteligência Artificial

Objetivo

O Problema da Busca

Busca Heurística

Algoritmo Min Max

Algoritmo Min Max com Poda Alfa-Beta

Implementação

Modelagem

Conclusão

Anexos

Trabalhos Futuros

Aprendizado

Síntese da tese “A Game-Learning Machine” de Michael Guerrity ( SAL)

Interface Gráfica

Base de Dados de Finais

Bibliografia

Lista de Tabelas e Ilustrações

Tabela 1. Número de Possibilidades 20

Figura 1. Comparação entre Regras 13

Figura 2. Tabuleiro 13

Figura 3. Diagrama 1 A casa escura do canto do tabuleiro à esquerda do jogador 14

Figura 4. Diagrama 2 A pedra é obrigada a tomar para g5 15

Figura 5. Diagrama 3 A pedra c1, na tomada em cadeia, pode passar duas vezes pela casa vazia e3 15

Figura 6. Diagrama 4 A dama é obrigada a tomar 4 pedras e parar na casa e5 porque não pode tomar a pedra f4 duas vezes 16

Figura 7. Diagrama 5 As quatro tomadas são opcionais 16

Figura 8. Diagrama 6 Como “ler”e “escrever” 18

Figura 9. Arvore de Possibilidades 20

Figura 10. Os valores das casas do tabuleiro 23

Figura 11. Poda Alfa-Beta 28

Figura 12. Diagrama de Classes 31

Figura 13. Interface Gráfica 39

Figura 14. Interface Gráfica – Menu Inicial 40

Introdução

História do Jogo de Damas

"As combinações inumeráveis e brilhantes do jogo de damas, deviam ser admiradas, em todas as idades, como uma obra prima da imaginação dos homens" - Poirson, "Encyclopédie du jeu de Dames", 1855.

A origem do Jogo de Damas perde-se na bruma dos tempos.

Sabe-se que é conhecido, desde os tempos imemoriais, no Extremo Oriente.

Nas escavações feitas no Vale do Rio Nilo, foram encontradas incrustações com desenhos do tabuleiro e algumas pedras soltas, pelo que se pode afirmar que ele era jogado no antigo Egito.

Assegura-se que o Jogo de Damas era conhecido no Egito desde a época de Osortasen I, pois que nas paredes do palácio de Ramsés Meiamoun, Medineth-Habou, existe um desenho que representa este Faraó jogando as Damas com uma de suas mulheres.

Também, nos mausoléus de Saggarah, no Egito, se vêem tabuleiros de Damas. Dois destes, que são da época dos Faraós, existem no Museu do Louvre, em Paris.

No British Museum, de Londres, conserva-se uma antiga caricatura, que representa um leão e uma cabra, jogando as Damas.

Os gregos referindo-se aos tempos fabulosos, e apoiados em alguns dados de Platão, ou talvez em sua exagerada fantasia, afirmavam que Mercúrio, foi o inventor do Jogo de Damas.

Homero, na Odisséia, apresenta dos pretendentes de Penélope jogando à porta do palácio de Ulisses, o Pessoi (vocábulo grego que significa: jogo de cálculo). Parecido com o Jogo de Damas.

Posteriormente, jogou-se na Grécia o DIAGRISMA.

Mais tarde aparece em Roma o LUDUS – LATRUNCULORUM, modificação do DIAGRISMA dos gregos, pois no jogo romano já se moviam as pedras, e, quando uma delas chegava a 1ª fila do adversário, convertia-se em rainha ou pedra coroada (como no jogo moderno), podendo se mover em todas as direções.

Supõe-se, portanto, que o Jogo de Damas clássicas é o mais antigo de todos que atualmente se praticam no mundo. Descendo do LUDUS – LATRUNCULORUM, dos romanos.

Durante a Idade Média, o Jogo de Damas gozou de uma popularidade imensa em quase toda a Europa.

Quanto ao nome porque é conhecido atualmente, supõe-se que foi por muitos séculos o passatempo predileto das Damas da nobreza, que o tinham por seu jogo favorito, chegando este se familiarizar tanto com o belo sexo, que adquiriu o título de Jogo de Damas.

A história bibliográfica do Jogo de Damas principia na Espanha, com o livro de Antom Torquemana, intitulado: EL INGÉNIO Ó JUEGO DE MARRO DE PUNTA Ó DAMAS – Valência, 1547.

A mais alta antiguidade do Jogo de Damas clássicas, não tem contestação. Por esta razão os historiógrafos consideram este jogo como auxiliar indispensável para a reconstrução e interpretação do jogo romano LUDUS – LATRUNCULORUM.

O primeiro campeão mundial, homologado pela Federação Mundial de Jogo de Damas, foi o austríaco Isidore Weiss, em 1895. A Federação Mundial foi fundada em 1948, em Paris, França. O Jogo de Damas se popularizou no mundo em dois tabuleiros: 64 casas, que se joga com 12 pedras de cada lado e 100 casas, que se joga com 20 pedras de cada lado.

Tem-se como certo, considerando a sua grande popularidade na Europa antes da época do descobrimento, que o Jogo de Damas tenha sido introduzido no Brasil pelos primeiros colonizadores.

O Jogo de Damas, como esporte, teve seu início no Brasil nos anos de 1935 a 1940, pelas mãos de Geraldino Izidoro. Grande parte das provas realizadas naquela época estão registradas no livro "Ciência e Técnica do Jogo de Damas" de autoria de G. Izidoro e J. Cardoso. Maiores detalhes a respeito deste surto damístico podem ser encontrados naquela publicação. O primeiro livro editado no Brasil foi "40 Golpes Clássicos", de autor ignorado, publicado no Rio de Janeiro, em 1940.

A partir de 1940, a prática do Jogo de Damas de uma forma organizada, entrou em recesso. Não há registros de movimento damístico até 1954, quando, com o advento do mestre russo W. Bakumenko, um novo surto começou a surgir, no tabuleiro de 64 casas.

Alguns trechos foram extraídos Da coluna Damas e Damistas de Cleuber Landim

1. Regras do Jogo

2. Comparação entre as Regras

Devido ao Jogo de Damas ter se desenvolvido em vários países e de forma paralela, afinal naquela época não havia internet, cada País ou, às vezes, mesmo dentro do mesmo país existem variações significativas nas Regras do Jogo.

Considerando alguns critérios básicos conseguimos diferenciar e classificar alguns Modelos de Regras.

A mais óbvio diferença é com relação ao tamanho do Tabuleiro: no Canadá e Sri Lanka são jogados em Tabuleiros 12x12, nas Regras Internacionais e na Holanda em 10x10, no resto dos Países, inclusive no Brasil, o mais comum é Tabuleiro de 8x8 (Algumas vezes com a casa escura do canto do tabuleiro ficando à esquerda do jogador e às vezes à direita).

Outra importante diferença é sobre a movimentação da Dama: Em parte dos EUA e na Itália, a dama se movimenta somente nas casas adjacentes a que ela se encontra, em outros casos ela é livre para andar nas 2 diagonais que cruzam o seu lugar, podendo haver uma Captura no caminho e continuar com a captura em cadeia.

A Terceira diferença é nas leis de captura: Nas regras Internacionais 10x10, no Brasil, Canadá, Leste dos EUA, Rússia e Holanda, as Pedras podem capturar tanto para frente quanto para trás, nos outros casos somente é permitido capturas para frente. Nas Regras Internacionais (10x10, Brasil, Canadá), na Espanha, Holanda e Itália, existe a obrigatoriedade de capturas o número maior de peças possíveis. Mas na Itália, tem um agravante, existem outras prioridades, para as peças que irão capturar e as capturadas.

Um resumo ilustrativo se encontra abaixo:

1. Regras Internacionais 8x8 do Jogo de Damas

Ou Brazilian Draughts como é conhecida internacionalmente foram as regras utilizadas nesta monografia e são detalhadas neste item conforme abaixo:

O tabuleiro coloca-se de forma que a casa escura do canto do tabuleiro fique à esquerda do jogador (diagrama abaixo).

Do início

1. As pedras brancas são colocadas, no início da partida, nas casas escuras, nas travessas 1, 2 e 3 e as pedras pretas nas travessas 6, 7 e 8 (Diagrama 1).

Diagrama 1

A casa escura do canto do tabuleiro

fica à esquerda do jogador

2. O tabuleiro coloca-se de forma que a casa escura do canto do tabuleiro fique à esquerda do jogador.

3. O primeiro lance é sempre das brancas.

Do movimento

4. A pedra anda só para frente, em diagonal, uma casa de cada vez.

5. A dama desloca-se para frente e para trás, nas diagonais onde estiver colocada, quantas casas quiser.

Da coroação

6. A pedra branca que chegar à travessa 8 ou pedra preta que chegar à travessa 1 será promovida a dama. A coroação é assinalada colocando-se sobre a pedra coroada outra pedra da mesma cor.

7. Não será coroada a pedra que, numa tomada, apenas passe pela travessa de coroação.

Da tomada

8. A tomada é obrigatória.

9. A pedra tanto toma para frente como para trás.

10. A tomada denomina-se simples se toma apenas uma peça e em cadeia se captura mais de uma peça no mesmo lance.

11. Se no mesmo lance existir mais de uma forma de tomar, é obrigatório obedecer à "Lei da Maioria", ou seja, fazer o lance que tome o maior número de peças (Diagrama 2).

Diagrama 2

A pedra é obrigada a tomar para g5

12. Numa tomada em cadeia, a peça pode passar mais de uma vez pela mesma casa vazia (Diagrama 3).

Diagrama 3

A pedra c1, na tomada em cadeia,

pode passar duas vezes pela

casa vazia e3

13. Numa tomada em cadeia, é proibido tomar a mesma peça mais que uma vez (Diagrama 4).

Diagrama 4

A dama é obrigada a tomar 4 pedras

e parar na casa e5 porque não

pode tomar a pedra f4

duas vezes

14. A pedra e dama têm o mesmo valor para tomar ou ser tomada (Diagrama 5).

Diagrama 5

As quatro tomadas são opcionais

15. As peças tomadas só serão retiradas do tabuleiro após terminado o lance de tomada.

Da vitória

16. Ganha a partida o jogador que capturar todas as peças adversárias ou as deixar sem movimento possível.

17. A partida é considerada ganha quando o adversário se recusa a cumprir o regulamento.

Do empate

18. O jogador interessado pode exigir o empate se tiverem sido jogados 20 lances sucessivos só de damas.

19. Quando a mesma posição se apresente pela terceira vez com o mesmo jogador com o lance, o jogador interessado pode exigir o empate.

Da Notação

Para que se possam "escrever" e "ler" os lances e assim poder registrar o desenrolar de uma partida, o desenlace ou análise de uma posição, enfim "escrever" e "ler" os movimentos das peças, torna-se necessário conhecer a NOTAÇÃO.

Convencionou-se que as COLUNAS são assinaladas, a partir do lado esquerdo das brancas, pelas letras de a a h.

As TRAVESSAS, a partir do lado das brancas, são numeradas de 1 a 8.

Desta forma, todas as casas do tabuleiro têm "nome": ele é determinado pelo cruzamento da coluna com a travessa nessa casa (Diagrama 6); a letra primeiro seguida do algarismo.

O lance é "escrito" indicando a casa de saída e a casa de chegada, separadas por um hífen, assim: c3-d4. No caso de tomada o hífen é substituído por um "x": c3xe5.

Vamos dar um exemplo da anotação dos primeiros lances de uma partida.

1. c3-d4 b6-c5

2. d4xb6 a7xc5

3. b2-c3 f6-g5

4. c3-d4 c5-b4

Quando se deseja comentar que o lance é bom, coloca-se uma exclamação "!" depois do lance e se o lance é mal se assinala com uma interrogação "?", desta forma: c3-d4! ou f6-e5?.

As Regras oficiais completas estão disponíveis no site da Confederação Brasileira de Dama do autor Carlos Alberto Ferrinho para maiores informações.

1. Solução de Problemas de Jogos envolvendo Inteligência Artificial

2. Objetivo

O Objetivo desse trabalho é realizar um sistema com conhecimento de fundamentos teóricos do jogo de Damas por exemplo:

1. • a combinação

   • o valor do centro

   • a oposição

   • o bloqueio

   • a força da dama

   • o bloqueio da dama

   • a prisão da dama

   • a Forçada

Para sua implementação utilizaremos os métodos de Busca Heurística, Algoritmo Min Max com Poda Alfa Beta para que possamos processar uma Arvore de Possibilidades de Jogadas com Inteligência Artificial.

Inteligência essa suficiente para poder realizar jogos contra seres humanos.

1. O Problema da Busca

O jogo de damas é um jogo de soma zero e com conhecimento perfeito das regras, ou seja, a partir do estado inicial pode gerar-se todo o espaço de estados possíveis até um estado terminal (vitória de um dos jogadores ou empate).

Sendo assim podemos pensar em montar uma Árvore que contenha todas as possibilidades de jogadas e levar o computador a partir do estado inicial até o final por um caminho totalmente conhecido.

Arvore de Possibilidades

Repare que podemos começar o jogo de 7 formas diferentes, considerando somente o primeiro movimento, e logo poderíamos imaginar mais 7 formas diferentes de resposta para cada 1 das 7 primeiras jogadas.

Deduzindo como sendo 7 o número de jogadas que podem ser feitos ( o que sabemos que não é verdade, pois em muitos momentos esse número pode ser bem maior ou menor) temos o seguinte calculo:

N = Número de jogadas ocorridas

Em apenas 16 jogadas, ou seja, 8 de cada jogador temos 33 Trilhões de possibilidades a ser considerado, considerando a tecnologia existente hoje isso seria impossível de ser processado em um tempo razoável de espera, sem levar em consideração que um jogo de Damas dificilmente tem menos que 12 jogadas de cada lado.

1. Busca Heurística

A busca Heurística é uma técnica sem um embasamento matemático muito sólido, porém com base em funções de análise podemos optar em dizer qual o caminho mais curto ou melhor até um estado final.

As funções heurísticas buscam retornar uma estimativa que, dada uma posição do jogo, retorne o melhor caminho ou o mais promissor para se chegar ao fim do jogo.

Essa técnica não é recente e é utilizada há séculos pelos jogadores de xadrez.

As funções que conseguem retornar valores analisando somente o estado atual do jogo, com base em valores das peças independente de fatores externos, são chamadas de funções lineares.

Existem funções não-lineares que levam em consideração elementos externos, como por exemplo o lançamento de um dado, que influenciem diretamente a posição atual do jogo. Não é o caso do jogo de damas, mas podemos citar o jogo de gamão, como exemplo.

Para isso, é necessário então Quantificar em um número o estado atual em um determinado momento do Jogo de Damas.

Dividimos o jogo em 4 fases onde em cada fase será usada 1 função diferente para uma melhor analise heurística, são elas:

Fase 1 – Abertura: 18 ou mais peças.

Fase 2 – Meio Jogo: de 14 a 18 peças.

Fase 3 – Meio Final: de 10 a 14 peças.

Fase 4 – Final: 10 ou menos peças.

Os parâmetros que estamos considerando para tal função são:

• Quantidade de Peças no Tabuleiro

• Peso de diferença entre Pedra e Dama

• Peso de cada casa do Tabuleiro (Considerando o conceito do Valor do Centro e Casas privilegiadas de Defesa)

• Peso da tomada

• Avanço das Peças atrasadas

• Não manutenção de peças sucessíveis

- Quantidade de Peças no Tabuleiro

Uma contagem simples de quantas pedras existem no tabuleiro, a intuição é saber quem tem mais peças no tabuleiro. Variável Q.

- Peso de diferença entre Pedra e Dama

Com base nas regras do jogo, precisamos diferenciar as Pedras das Damas para ter uma melhor quantificação sobre uma possível vantagem para um dos lados. Para isso atribui-se um valor de peso como segue: Pedras tem peso 1 e Damas tem peso 3. Variável Pe.

- Peso de cada casa do Tabuleiro

Cada casa do Tabuleiro em cada fase do jogo tem um “valor” associado estratégico para cada jogador, que somados teremos um fator de analise.

Os Valores das Casas do Tabuleiro em cada fase são:

Os valores acima foram definidos com base em conversa com um grande jogador de damas brasileiro e idealizador do programa Winbraz.

O Valor do Centro terá um bônus a ser somado ou subtraído de 10 pontos para cada casa F4 e C5, pois trata-se de um dos pontos mais estratégicos do tabuleiro para se ter o domínio.

A Peça Privilegiada de defesa E1 terá um bônus de 10 pontos. Essa atribuição tem por finalidade evitar jogadas que possam abrir possibilidades para o adversário obter a dama. Variável PeCa

- Peso da Tomada

Caso tenha a possibilidade de Tomada será somado o valor 100 ao Peso por peça Tomada. No caso de Tomadas de damas o valor não será de 100 x 3 e sim de 10000, o motivo é quando houver damas no tabuleiro devemos considerar as jogadas que envolvam as damas as mais importantes do jogo. Variável T.

- Avanço das Peças atrasadas

A1 e H2 são as casas que chamamos de atrasadas e ira valer 5 pontos a mais cada na saída rápida. Informação essa obtida com João Guimarães em uma conversa informal. Variável AvAt.

- Não manutenção de peças sucessíveis

Manter uma peça sucessível significa facilitar o trabalho de tomada do adversário, cada pedra mantida dessa forma significa uma perda de 5 pontos. Variável Su.

A Dama será mantida sempre na Diagonal Principal. No caso de mais de uma Dama ela será mantida na Bidiagonal. Pelo simples fato de que nenhuma peça poderá atravessar o tabuleiro sem que tenha a anuência da dama.

A escolha dessa função, bem como os valores utilizados, tem por objetivo no nosso trabalho dar uma maior ênfase nas tomadas no estado atual, nos estados que estão por vir ou no caminho que leva ao estado mais promissor.

A Função de cada fase então será:

Fase 1 – F(x) = Q * Pe + Som(PeCa) + MAX(T) - Su

Fase 2 – F(x) = Q * Pe + Som(PeCa) + MAX(T) + AvAt

Fase 3 – F(x) = Q * Pe + Som(PeCa) + MAX(T) + AvAt- Su

Fase 4 – F(x) = Q * Pe + Som(PeCa) + MAX(T) + AvAt- Su

F(x) = Q * Pe + Som(PeCa) + MAX(T) + AvAt- Su

Em segundo plano, ela trata do Domínio do Centro e das Casas privilegiadas de defesa do jogo de damas, dando valores diferenciados para essas situações, inclusive para cada fase do jogo em separado, conforme o jogador for revelando suas movimentações.

Esses conceitos são fundamentais para uma eficiência mínima da evolução do jogo conforme vão se desenvolvendo as jogadas, em um estágio mais avançado consideramos a não manutenção de peças sucessíveis e .o avanço das pedras atrasadas como fatores de ponderação.

Como proposta o conhecimento de algumas aberturas estudadas em livros especializados no assunto, bem como quais as melhores jogadas para “responder” essas jogadas se encontram abaixo descritas:

Da Abertura:

Brancas

1-)C3-D4 B6-A5

D4-C5

2-)C3-D4 B6-C5

D4XB6

3-)C3-D4 D6-C5

G3-F4

4-)C3-D4 D6-E5

B2-C3

5-)C3-D4 F6-E5

D4-F6

6-)C3-D4 F6-G5

B2-C3

7-)C3-D4 H6-G5

G3-H4

Pretas

1-)A3-B4 F6-E5

2-)C3-B4 H6-G5

3-)C3-D4 B6-C5

D4xB6 A7xC5

4-)E3-D4 F6-E5

D4xF6 G7xE5

5-)E3-F4 F6-G5

6-)G3-F4 F6-E5

7-)G3-H4 B6-C5

A intuição da função é identificar jogadas que, a partir desta, deixe o jogador adversário (humano) com apenas 1 jogada possível e após essa jogada obrigatória realizar uma, duas ou mais tomadas para o computador.

Algoritmo Min Max

O Algoritmo Min Max interpreta e simula Problemas que envolvem dois Jogadores, foi largamente utilizado em jogos como Dama, Xadrez, Jogo da Velha, Lig-4 e muitos outros.

O algoritmo Min Max é responsável por determinar a estratégia que será seguida e qual o melhor primeiro passo para se chegar ao resultado necessário.

Os passos do algoritmo Min Max são:

Gerar a árvore de todas as possibilidades de jogadas;

Aplicar a função heurística para cada nó da árvore de possibilidades e obter o respectivo valor daquele estado do jogo;

Decidir qual jogada será realizada.

Para decidir qual jogada será realizada, o Algoritmo trata um jogador como sendo o Maximizador e um o Minimizador, com base no resultado obtido pela heurística, ele faz com que o Maximizador quando de posse da jogada escolha o resultado que tem o maior número (daí o nome Maximizador); enquanto o Minimizador, que é o oponente, irá escolher os caminhos que tem como resposta os menores valores.

A decisão sempre deve ser baseada “olhando” o valor do Minimizador (oponente), não basta decidir somente verificando o maior valor para o Maximizador pois esse pode também levar a uma possibilidade de ótimo para o Minimizador.

É claro que no jogo de Damas, se você “olhar” somente o próximo estado, muito provavelmente, esse pode não ser o Estado de ótimo, porém não podemos olhar todas as possibilidades conforme já verificado anteriormente.

Uma solução para esse problema seria limitar a quantidade máxima de níveis que o algoritmo irá descer na arvore de possibilidades até tomar uma decisão.

Sendo assim, temos que incluir mais um parâmetro a ser considerado que é o nível máximo de profundidade da árvore de procura em que iremos processar, e desta forma definimos três níveis de dificuldade:

Principiante – nível de profundidade 2 ;

Intermediário – nível de profundidade 4;

Especialista – nível de profundidade 6.

Quanto maior o nível de profundidade, mais possibilidades de jogadas serão analisadas e maior será a visibilidade do jogo pelo computador, que terá mais opções para sua decisão. Logicamente, o nível de dificuldade para o jogador oponente cresce proporcionalmente.

No caso de jogos para dois jogadores, como é o caso do jogo de damas, onde não há nenhuma dependência de fatores externos aos jogadores, trata-se de jogos Simétricos.

Em jogos simétricos precisamos diferenciar o Maximizador do Minimizador para que o valor retornado pela função heurística seja interpretado de forma correta.

Para isso atribuímos o valor 1 ao jogador Maximizador e -1 ao jogador Minimizador. Com esta definição é simples quantificar e diferenciar o resultado da função heurística para cada jogador.

Algoritmo Min Max com Poda Alfa-Beta

O conceito de Poda Alfa-Beta (Pruning) é baseado no fato de que o ser humano não irá continuar pensando nas jogadas que o levem a uma situação desfavorável com relação a atual posição, nesse caso essa situação deve ser descartada do pensamento.

Computacionalmente falando a Poda Alfa-Beta é baseada na árvore de estados e nos valores dos estados obtido com o algoritmo Min Max, quando oponente estiver a jogar, ele irá escolher a melhor condição para ele e a pior condição para o seu oponente.

É desnecessário para o computador analisar as outras possíveis jogadas, uma vez que a probabilidade do oponente escolher a melhor jogada é alta. Isso somente tomaria tempo de processamento desnecessário do computador e atrasaria relativamente sua resposta.

Em outras palavras seria descartar a parte menos promissora da árvore do algoritmo Min Max.

Segue uma ilustração para melhor visualizar o conceito:

Os critérios a serem utilizados para o corte alfa-beta devem ser bem analisados e não simplesmente desconsiderar o menor valor obtido.

O motivo é simples, devido a grande dinâmica do jogo, em um momento a função heurística pode retornar o pior valor e, em apenas uma jogada, a mesma função heurística pode retornar agora os melhores valores possíveis.

Nesse caso um corte mal sucedido na arvore de possibilidades poderia significar um descarte do ramo da árvore mais promissor. A conseqüência seria drástica para o computador pela não obtenção do valor de ótimo e sim um valor sub-ótimo como sendo o de ótimo.

O algoritmo Min Max, com cortes alfa-beta, permite reduzir a árvore de procura de possíveis soluções até níveis que, segundo estatísticas, deixam o algoritmo mais rápido em, aproximadamente, 30%.

Para que o algoritmo Min Max com Poda alfa-beta se torne eficiente é preciso que ele somente faça o corte na árvore de possibilidades quando aquele ramo for irrelevante para se levar até um estado final com vitória para o computador.

Implementação

O programa foi desenvolvido em linguagem Java, o que possibilita a sua execução em vários sistemas operacionais através da sua inclusão em páginas HTML.

Poderá ser executado em browsers que suportem Java (versão 1.3.1), nomeadamente o Netscape 4.6 e o Internet Explorer 5.5, e ainda usando o appletviewer distribuido com o JDK; assim facilitando a sua disponibilização na grande rede mundial de computadores, a Internet.

Todo o programa foi escrito usando o ambiente de desenvolvimento do pcGrasp versão 6.2.17 com o JDK 1.3.1.

Devido a existência de muitos códigos disponíveis na internet, analisou-se e identificou-se quais as melhores maneiras de adaptação poderiam ser feitas para o objetivo dessa monografia.

A parte de controle da interface, em especial, tomamos como base o trabalho desenvolvido na Universidade de Alberta pelos autores Victor Huang e Sung Ha Huh, nossa contribuição nesse item foi significativa nas cores de acordo com padrão para o jogo, a visão de uma dama com 2 pedras e tradução para o Português utilizado no Brasil.

A parte das movimentações foi em sua totalidade reformulada para que sua função fosse realizada de maneira satisfatória, ou seja, para que permitisse a implementação das regras brasileiras.

Logicamente as funções heurísticas e a inteligência envolvida por trás de cada modelo, na maioria dos casos, não são reveladas devido a ser esse o fato de maior capital intelectual envolvido. Nesse caso nosso programa conta com a contribuição de damistas e programadores de grande expressão em especial João Guimarães, Carlos Alberto Ferrinho, Thiago Meneghello entre outros e muito estudos em sites e livros especializados no assunto.

Modelagem

Diagrama de Classes

Conclusão

Implementamos um sistema que joga de modo competitivo com seres humanos, desenvolver um programa que joga igual a nós mesmos é algo que deixa a sensação de trabalho realizado.

Estudamos e implementamos todas as regras brasileiras, com exceção de algumas peculiaridades, como por exemplo o empate entre jogadores, que por motivos práticos deixaram de ser implementados. As regras brasileiras são bastante complexas pois elas possuem peculiaridades como nenhuma outra, cuja implementação viria dificultar demasiadamente o projeto e demandaria muito tempo de processamento.

Boas surpresas podem surgir para jogadores menos atentos, principalmente em algumas jogadas no nível de dificuldade máximo desenvolvido (Especialista), pois o jogo consegue "olhar" 6 jogadas adiante.

A implantação de uma base de finais traria um grande avanço na inteligência do computador e para sua implementação teríamos que, além do exposto no item base de dados de finais, estudar uma boa função de pesquisas em banco de dados de grande porte.

Com base no conhecimento adquirido, recomendamos a utilização de funções do tipo Hash que seriam a melhor escolha, para realizar a pesquisa numa base de dados de finais, devido a sua rapidez de acesso a banco de dados de grande porte e, isso seria necessário para não inviabilizar a execução do programa devido as necessidades com relação a tempo de resposta e tempo de processamento.

Nossas peripécias poderão ser acompanhadas pelo mundo todo para o resto dos anos em www.checkers.hpg.com.br ou, caso o hpg venha a se extinguir, em www.jogodedamas.kit.net

Anexos

Trabalhos Futuros

O conhecimento introduzido neste jogo ainda é um pouco comparado à quantidade de informação existente ao jogo de damas, porém os pontos a seguir implementados um grande avanço de desempenho para o computador.

Aprendizado

Uma das habilidades dos seres humanos que tem sido alvo de indagações e de pesquisas ao longo dos séculos é a capacidade de aprender. Esta capacidade recebe o nome técnico de protopeiria. Os homens e alguns animais superiores possuem a protopeiria muito desenvolvida. Eles aprendem com a experiência, aprendem ouvindo o que lhes é dito e aprendem ampliando o alcance do conhecimento que já possuem, através de reordenações sucessivas.

É muito comum em jogos e em outros tipos de aplicativos que utilizam a Inteligência Artificial, existir uma base de conhecimento, que é onde são armazenadas por exemplos regras de jogo, como será processada uma regra a partir de determinados dados de entrada, como será executada uma jogada em um jogo de damas ou de xadrez a partir da jogada do oponente e até como um robô irá reagir a determinados estímulos ou ações. Para se ter um sistema deste tipo, que funcione perfeitamente, ou seja, que o computador reaja adequadamente a toda e qualquer ação do operador do computador ou programa, precisaríamos ter uma imensa base de conhecimento, possivelmente tornando o programa muito lento devido as buscas na sua base de conhecimento, até mesmo inviabilizando o uso do referido programa.

Para se evitar isto, podemos utilizar o aprendizado no programa. Em um programa que utiliza aprendizado, não há a necessidade de se criar previamente uma base de conhecimento. Nesse tipo de programa, a base de conhecimento será alimentada gradativamente, conforme as ações e tarefas executadas no programa. Por exemplo, em um jogo de damas, o programa poderá começar em um nível, em que ele só saberá as regras do jogo, essa seria sua única base de conhecimento. Conforme o jogo é utilizado, ele armazena as jogadas que vão sendo executadas pelo oponente, aumentando assim sua base de conhecimento. Nos jogos posteriores, esse programa poderá utilizar essas jogadas anteriormente "aprendidas". Dessa maneira não há a necessidade de se imaginar as milhões de ações que um programa poder enfrentar no momento da sua programação, um processo que, dependendo do programa, poderia durar meses e té anos.

A única adversidade deste tipo de programa, é de sua base de conhecimento demorar muito até que seja efetivamente utilizável. No exemplo do jogo de damas, demoraria milhares de jogadas até que o computador vencesse.

A seguir veremos alguns conceitos para tornar uma máquina apta a ter uma protopeiria mais desenvolvida.

Indução é o processo de usar observações para descobrir regras e procedimentos para compreender melhor determinado fenômeno. Uma ferramenta muito comum para auxiliar na construção de regras por indução é a chamada arvore de decisões, que utiliza a divisão das observações de acordo com os valores de um dos indicadores observados.

Porém o tamanho e a complexidade de uma arvore de decisões depende muito da ordem em que os indicadores são escolhidos para efetuar a ramificação da arvore.

Arvores pouco ramificadas são boas porque produzem um número pequeno de regras. E cada regra, originada de arvores pouco ramificadas, tem poucas condições e, por isso, é mais eficiente.

Sendo assim, conclui-se que precisamos descobrir qual é o indicador que deve ser utilizado para ramificar um dado nódulo da arvore de decisão, o método mais simples para descobrir-se o melhor indicador foi proposto por Ross Quillan e é baseado na entropia da informação. Entropia é uma grandeza que mede desordem de informação. Quanto maior a entropia, maior a desordem.

Quando examinamos um conjunto de objetos e descobriu entre eles uma classe cujos membros possuem características em comum. Essa classe é denominada conceito, do ponto de vista computacional o problema da generalização e quando queremos aprender conceitos novos e precisamos classificar ocorrências que irão fazer parte do conceito. A resolução desse problema é bem complexa e não será explicada nesse momento, porém Tom Mitchell mostra que é possível usar praticamente todo o tipo de busca para aprender conceitos.

Em inteligência artificial é muitas vezes necessário utilizar-se de linguagens especiais a fim de atacar certos problemas. Quando isto acontece, precisamos fornecer à maquina um programa determinado intérprete, que fornece diretivas de como interpretar as sentenças da linguagem especial. O problema disso é que talvez não teremos possibilidade de processar todas as informações em um tempo razoável. Foi por isso que os pesquisadores de IA inventaram a Avaliação Parcial que traduz a linguagem especial em uma linguagem comum.

Desta forma o computador não precisa do intérprete e executa o programa em um tempo hábil de processamento.

Uma tese reconhecida mundialmente foi a escrita por Michael Guerrity e foi chamada de SAL. A seguir um breve resumo sobre uma das mas apreciadas teses sobre aprendizado já escritas.

Síntese da tese “A Game-Learning Machine” de Michael Guerrity ( SAL)

Introdução

A relação entre máquinas, jogos e pensamentos é um tópico de muitas discussões. Em 1948, Norbert Wiener considerou que a habilidade de jogar xadrez "representa uma essencial diferença entre as potencialidades de uma máquina e da mente". Em 1950, Alan Turing sugeriu que o "jogo da imitação" seria um teste de como a máquina poderia pensar. Ele sugeriu que usar problemas do jogo de xadrez como uma parte deste teste. Também em 1950, Claude Shannon propôs que usando a habilidade de jogar xadrez das máquina seria uma forma de responder a pergunta: "Uma máquina pode ser desenvolvida de forma que seja capaz de pensar?".

Depois que o primeiro computador digital se tornou operacional em 1951, discussões em torno de máquinas, jogos e pensamento passaram a não ser somente acadêmicas. Programas para computador para jogos eletrônicos passaram a ter um maior foco em pesquisas na área da Inteligência Artificial. Os primeiros programas para jogar xadrez, jogavam em nível iniciante. Alguns jogos de hoje, jogam extremamente bem. O atual programa campeão de xadrez, o DEEP THOUGHT, possui a pontuação de 2600 da Federação de Xadrez dos EUA, sendo que o atual campeão mundial tem 2900 pontos neste ranking. Isto pode provar de acordo com Shannon, que as máquina são capazes de pensar. Mas, muitas pessoas ainda não estão convencidas.

Mas mesmo depois de mais de 40 anos de pesquisa, um bom jogo de xadrez, não é um bom teste para dizer o quanto uma máquina pode pensar, há ainda muitos teste que podem ser executados para responder a questão de Shannon.

Nesta dissertação isto é sugerido, não somente baseado em um único jogo de tabuleiro para dois jogadores (como o xadrez), mas em qualquer jogo deste tipo. Especificamente, a máquina precisa estar habilitada a aprender como jogar qualquer jogo de tabuleiro para dois jogadores simplesmente jogando este jogo.

Procura Seletiva e Procura por Força Bruta

Jogos típicos de xadrez selecionam um movimento procurando através de milhares de possíveis movimentos, formando uma vasta árvore de jogo de possíveis posições no tabuleiro.

Para se ter certeza de que movimentos chaves não serão perdidos, todos os movimentos legais de cada posição na árvore precisam ser considerados. O número de movimentos de cada seqüência de movimentos da posição atual do tabuleiro (posição corrente é chamada de rool) é tratado como o departamento da árvore de jogo. O procura procede uniformemente e incrementalmente no departamento, onde todas as posições no tabuleiro que resultam de dois movimentos são examinadas, em seguida, as posições que resultam de três movimentos e assim sucessivamente. Cada movimento adicionado ao departamento da árvore de procura é chamado do ply.

Muitos esforços tem sido feitos para criar uma forma de procura mais seletiva na árvore de procura. Uma procura seletiva pode determinar quais seqüências de movimentos podem ser consideradas baseadas nas características das posições do tabuleiro examinadas na árvore do jogo. Um procedimento de procura seletiva efetivo pode ser aplicado a problemas mais complicados que o jogo de xadrez. De cada posição de um jogo de xadrez, geralmente existem 35 possíveis movimentos. Isto é chamado de fator de ramificação. Um procedimento de procura seletiva pode ser aplicado a problemas com um fator de ramificação muito maior.

Ao contrário do procedimento de procura seletiva, os procedimentos de procura dos jogos de xadrez de maior sucesso podem ser caracterizados por um uniforme, aumento na departamento da árvore de procura. A procura é feita virtualmente independente das características das posições de tabuleiro examinadas, e inclui um grande número de posições de tabuleiro. Esses métodos de procura são referidos como força bruta.

Quando os jogos de xadrez começaram a ser desenvolvidos, a velocidade dos computadores podia alcançar departamentos de menos de 4-ply usando força bruta sob condições de campeonato. Uma procura de apenas 4-ply para um jogo de xadrez resulta num jogo ruim. Os pesquisadores da época chegaram a conclusão de que teria que ser desenvolvido um método de procura seletiva que fosse hábil a jogar bem xadrez. O jogo de xadrez se tornou o campo de testes para os novos algoritmos para procura seletiva.

Nos dias de hoje, onde a velocidade dos computadores é muito maior que a velocidade dos computadores daquela época, o procedimento de força bruta pode atingir departamentos maiores que os daquela época, mas para problemas mais complicados que o xadrez, onde o fator de ramificação é maior do que 50, a procura por força bruta pode não Ter efeito. Pesquisas na área da busca seletiva mostram ser mais frutíferas do que tentativas de apenas aumentar a velocidade dos computadores. A área de aprendizado de jogos, onde os fatores de ramificação são muitos grandes, pode ser uma boa área na qual podem ser feitos testes de novos algoritmos para a procura seletiva.

Aprendizado de jogos

Uma crítica comum as máquinas que jogam xadrez é de que elas podem apenas jogar xadrez e possuem habilidades limitadas para mudar seu estilo de jogo. É discutido que máquinas que pensam não podem ser limitadas.

Uma máquina para aprendizado deve poder trabalhar com muitos tipos de jogos.

Aprendizado de Regras X Aprendizado de Estratégia

Alguma consideração foi dada a como as regras de um jogo podem ser aprendidas em adição a boa estratégia. Desde que o programa permita somente jogando o jogo, as regras podem ser aprendidas jogando e dizendo quando um movimento é ilegal. Informação sobre movimentos legais também podem ser obtidas observando os movimentos do oponente (assumindo as mesmas regras aplicadas aos dois jogadores).

Um jogo que utilizava aprendizado foi desenvolvido de forma que aprendeu as regras o jogo usando simples funções lineares discriminantes. O Teorema da Convergência Perceptron (R. O. Duda e P. E. Hart) pode ser usado para discutir que dadas informações suficientes sobre a posição no tabuleiro e movimento, as regras de qualquer jogo podem ser aprendidas depois de um número finito de movimentos ilegais. Informação sobre a posição no tabuleiro e movimento é suficiente se movimentos legais podem ser separados linearmente de movimentos ilegais.

As regras de maioria dos jogos são simples. Desde que um procedimento para aprendizado que requer um número finito de movimentos ilegais possa ser colocado em prática. Por outro lado, uma boa estratégia pode ser um pouco complexa, mesmo para jogos com regras simples. Por exemplo, o jogo Go possuía regras muito simples e um simples critério para vitória. Por outro lado, este jogo pode ser mais difícil que xadrez, desde que boas estratégias para os jogos tendem a ser mais complexas que as regras do jogo. Como no teorema de Perceptron, pode se obter um bom jogo depois de um certo número de partidas jogadas.

Procurando na árvore do jogo pode-se determinar o quanto um movimento pode ser benéfico. Um programa que somente pode aprender jogando pode fazer um movimento que antes não havia sido observado ainda em outros jogos como sendo um movimento legal, ou pode fazer um movimento ilegal. Por outro lado, uma boa estratégia pode ser aprendida procurando na árvore de jogo antes de fazer qualquer movimento.

Alternativamente, um programa pode ser bom fazendo somente movimentos que já haviam sido observados em partidas anteriores, só que desta forma, alguns movimentos legais podem não ser considerados.

Para evitar estas dificuldades, nesta dissertação não é considerado o aprendizado das regras do jogo.

Interface Gráfica

Como um valor agregado ao programa e ao trabalho, um estudo foi desenvolvido para a disciplina de Computação Gráfica, e tem por objetivo desenvolver de forma mais ampla e intuitiva a Interface Homem-Máquina.

Tela que demonstra um momento do Jogo ( Lado Esquerdo Central), Pedra Preta selecionada, Placar do jogo (Direita Superior).

Comentários e indicador se tiver alguém em vantagem ( Lado Direito Central ), Tabuleiro informando a jogada anterior e painel de anotações das jogadas ( Lado Direito Inferior).

Menu de Abertura do Programa, com a tela do jogo ao fundo.

Base de Dados de Finais

Alguns algoritmos, quando o jogo está perto de seu final ou existem poucas peças no tabuleiro, começam a trabalhar com uma Base de Dados que contém todas as alternativas possíveis de jogadas, porém isso demanda muito consumo de máquina e muito tempo de processamento.

O Chinook, por exemplo, conhece todas as possibilidades até 6 peças, o Winbraz conhece todas as possibilidades até 4 peças, não consideramos está técnica em nosso programa por demandar uma máquina especial ou muito tempo de processamento.

Para se ter uma idéia, para construirmos uma Base de Dados para finais de 2 Peças (PedraxPedra, PedraXDama, DamaxPedra e DamaxDama) levaríamos aproximadamente 6 horas de processamento utilizando uma máquina com a tecnologia existente atualmente e não traria grandes habilidades ao computador pois com 1 peça de cada lado o jogo muito provavelmente não terá um vencedor.

No caso do Chinook eles, além de utilizarem super computadores em seu desenvolvimento, em suas páginas tem uma citação sobre o desenvolvimento de uma Base de Dados de Finais para 8 peças, e que ela ficou com as seguintes “medidas”:

Total de 443.748.401.247 posições possíveis.

Tamanho aproximadamente de 2.7 GB com compressão e;

5.6 GB sem compressão de dados.

O Winbraz, que possui uma Base de Dados para 4 peças, foram necessários 5 computadores e 1 dia e meio de processamento para ter esse base pronta.

Bibliografia

Site sobre Aberturas

Rui Manuel Santos Rodrigues Leite Mestrado “Jogo das "Damas" clássicas” . 1999

António Manuel Correia Pereira Mestrado “Damas Clássicas” . 1998

Luciane Maria de Souza Monografia "Aplicações em Teoria dos Jogos: Jogo da Velha e Jogo de Damas" .

ARARIBÓIA, G Inteligência Artificial. LTC. Livros Técnicos e Científicos. 1988

Stuart J. Russell, Peter Norvig Artificial Intelligence: Modern Approach. Prentice Hall. 1995

Ciências da Computação 2002 – 4ACPN

Página 43 de 43