Damas Clássicas

Mestrado de Inteligência Artificial e Computação

Trabalho no âmbito da disciplina de Metodologias de Inteligência Artificial

António Manuel Correia Pereira


[Introdução] [Implementação das Regras] [O algoritmo Minimax] [Trabalhos futuros] [Referências] [Jogo]

Introdução

Embora seja um jogo com regras muito simples, o jogo de damas é um jogo bastante difícil de dominar completamente. Basta consultar, além dos livros da especialidade, o site do projecto Chinook para verificar o volume de informação necessário para ter o conhecimento perfeito do desenrolar do jogo. Por isso o melhor é colocar as regras do jogo no programa, implementar uma pesquisa usando minimax com cortes alfa-beta, com vários níveis de profundidade, conseguir uma função heurística que saiba avaliar minimanente a posição das peças no tabuleiro de jogo e esperar que o computador saiba o que faz.
O conhecimento de algumas jogadas típicas pode ajudar o computador a evitar cair em ratoeiras ou a fazer jogadas excepcionais.

Cito algumas opiniões de intelectuais e damistas:

"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.

"Para estimular a memória e aguçar a inteligência nada há melhor que um bom problema de damas. E por esse motivo obrigo os alunos do curso secundário a resolver diariamente problemas do jogo de damas" - Dr. Richard Schmidt (director da Dublin-School, em 1932).

" A primeira qualidade de um bom damista traduz-se no desejo de aprender SEMPRE. Por muito vastos que sejam os nossos conhecimentos temos sempre que aprender. Em Damas, vivemos um aprendimento permanente e morremos sabendo muito pouco. O geral de todo o sábio é o desejo de mais aprender. Como diz um velho provérbio oriental: " Os sábios são como as espigas cheias: curvam-se humildemente para a terra. Os néscios, como as espigas vazias: erguem-se altaneiras para os céus". - Lukhov Stanislawsky, mestre russo.

Implementação das Regras

As regras do jogo de damas são conhecidas da maioria das pessoas e apenas vou descrever as mais elementares - a totalidade das regras pode ser consultada no livro [1]:

Para se aproximar mais da realidade o tabuleiro é apresentado sempre com as peças escolhidas pelo jogador em baixo, simulando a proximidade física do jogador com o tabuleiro.

Existe a possibilidade de o jogador escolher um de três níveis de análise do computador (Iniciado, Médio e Especialista). A cada um deste níveis está associada uma profundidade de procura no algoritmo minimax.

As jogadas efectuadas são registadas de acordo com a numeração do tabuleiro adoptada para o jogo de damas:

O algoritmo Minimax

O jogo de damas é um jogo de soma zero e com conhecimento perfeito das regras - 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). Contudo este espaço de estados é demasiado grande para a capacidade de processamento do computador e o algoritmo minimax, com cortes alfa-beta, permite reduzir a árvore de procura de possíveis soluções até níveis desejados pelo utilizador.

Como este jogo é simétrico, atribuí o valor 1 ao jogador branco e -1 ao jogador preto. Com esta definição é simples quantificar o resultado da função heurística e da função de avaliação, para cada jogador.

Função heurística

Entre as jogadas típicas que se podem analisar no jogo de damas temos as aberturas. Segundo os especialistas [1] o lance mais forte de saída das brancas é sempre 10-14. Se o computador jogar com as peças brancas sairá sempre com esta jogada pois é a que cria mais dificuldades ao adversário. Se o computador jogar com as peças pretas e o adversário sair com 10-14, as respostas mais fortes são 23-19 ou 22-18.

A abertura do rio 10-14, 23-19 é assim chamada porque a saída e a resposta são jogadas no rio. A abertura clássica 10-14, 22-18 é assim chamada por ser a mais estudada (além da do rio) pelos autores clássicos de damas.

Na prática a primeira jogada do computador será sempre 10-14, se jogar com as peças brancas, ou 23-19, se jogar com as peças pretas.

Na função de avaliação de um nó terminal uma dama tem um valor três vezes superior a um peão, e é valorizado o facto de um peão estar na sua base, pertencer ao triângulo defensivo ou estar localizado nas bordas laterais do tabuleiro. Também é valorizada a presença da dama no rio (mais importante na fase final do jogo).

Trabalhos Futuros

O conhecimento introduzido neste jogo ainda é um pouco incipiente, face à quantidade de informação existente relativamente ao jogo de damas. A introdução de mais posições típicas (flechas, bateria, judia, luneta, gambito, etc.) e de alguns finais práticos (dama contra dois peões, dama contra três peões, a forçada, etc.) podem melhorar muito o desempenho do computador.

No aspecto gráfico pode traçar-se a linha da jogada quando acontecem tomadas múltiplas.

Pode ainda ser realizado um programa de estudo que ensine a jogar ou, pelo menos, que possa indicar ao jogador a sua melhor jogada e os dois ou três lances consequentes.

Referências e Bibliografia

Iniciação ao Jogo de Damas, Sena Carneiro, Ed. Presença, 4ª edição, Lisboa, 1994

JAVA in a Nutshell, David Flanagan, O'Reilly, 2nd edition, USA, 1997

Artificial Intelligence, Elaine Rich & kevin Knight, McGraw-Hill, Inc., 2nd edition, 1991, pp.307-327

Chinook:"http://www.web.cs.ualberta.ca/~chinook"

DAMAS CLÁSSICAS


[Introdução] [Implementação das Regras] [O algoritmo minimax] [Trabalhos futuros] [Referências] [Jogo]