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.
- Sáo sempre as BRANCAS a iniciarem o jogo sendo os lances alternados, sem que nenhum dos jogadores possa fazer dois lances seguidos.
- Peça tocada, peça jogada
- Nenhum jogador se pode recusar a eliminar qualquer peça do adversário que se encontre em posição eliminatória
- Nas eliminações simultâneas é obrigatório capturar sempre o MAIOR NÚMERO DE PEÇAS POSSÍVEL
- Se a quantidade for igual para todos os lados é obrigatório capturar A MELHOR QUALIDADE (esta regra só existe em Portugal)
- Se a quantidade e a qualidade forem iguais, o jogador pode optar por qualquer dos lados
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:
- As casas pretas (casas onde se joga) são numeradas de 1 até 32, iniciando-se a contagem na casa angular inferior direita e terminando na casa angular superior esquerda, contando-se sempre horizontalmente da direita para a esquerda e de baixo para cima.
- A numeração começa sempre do lado em que são colocados os peões brancos.
- A grande diagonal (negra) designada "rio" (casa 1, 5, 10, 14, 19, 23, 28 e 32) deve começar à direita de cada jogador.
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, 1994JAVA 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]