Trabalho apresentado na II SACC

Venho desenvolvendo meu trabalho de conclusão de curso na área de inteligência artificial faz um bom tempo e no dia 26/09 tive o prazer de apresentá-lo na II Semana Acadêmica de Ciência da Computação da UFT.
Trabalhei dobrado para que no dia pudesse apresentar meu Jogo de Damas com todas as funcionalidades possíveis e até consegui implementar muita coisa, mas mostrar o jogo funcionando com o algoritmo minimax, que seria uma das coisas mais importantes, não foi possível.
Segue abaixo, explicações mais detalhadas sobre meu trabalho.

» Post Completo....:: Trabalho de conclusão de curso ::.
Estou concluindo o curso de Ciência da Computação da UFT e como monografia resolvi desenvolver algo de meu total interesse e que trouxesse um grau de dificuldade. Não posso reclamar do grau de dificuldade de desenvolver um Jogo de Damas e nem da possibilidade de aplicar os conhecimentos adquiridos em outros problemas similares como o xadrez, go e num futuro não tão distante o futebol de robôs.
O trabalho, com o título SOLUÇÕES HEURÍSTICAS PARA O JOGO DE DAMAS, está sendo desenvolvido juntamente com meu professor orientador Alexandre Tadeu Rossini da Silva. E de uma maneira geral, conta com duas soluções desenvolvidas para o problema do Jogo de Damas, sendo elas, algoritmo genético e minimax com corte alfa beta.
O trabalho encontra-se em desenvolvimento e apesar dos estudos nas duas soluções, ainda não foi implementado a solução por minimax e corte alfa beta.

.:: Implementação por algoritmo genético ::.
Como alternativa para solucionar o problema do Jogo de Damas, foi proposto utilizar algoritmo genético.
O resultado foi um tanto frustrado, pois desenvolver esta solução custou muito tempo no desenvolvimento e implementação, e não teve o retorno esperado.
Esperava-se mais pelo esforço aplicado, mesmo assim, estrou satisfeito de ter obtido resultados ciente das falhas no desenvolvimento.

.:: Implementação por minimax e corte alfa beta ::.
Esta sim é uma solução de eficácia comprovada para o problema do Jogo de Damas. Onde pode-se fazer a melhor jogada, num dado nível de busca, sem temer as conseqüências.
Esta teria sido a primeira opção, caso o objetivo do trabalho não fosse buscar novos horizontes.
Eu tinha esperanças de implementar o minimax ainda este mês, mas andei trabalhando em outras coisas como a nova interface gráfica e os slides para a apresentação na Semana Acadêmica.

.:: Implementação da Lógica ::.
Quando digo lógica estou me referindo às regras do jogo.
Para trabalhar os estados do tabuleiro eu numerei as 32 casas ocupáveis do tabuleiro, assim como atribuí id's para cada tipo de peça:
- ⇒ Espaço não ocupado
p ⇒ Peça do jogador branco
d ⇒ Dama do jogador branco
P ⇒ Peça do jogador preto
D ⇒ Dama do jogador preto
# ⇒ Peça capturada (função de impedir a recaptura da mesma peça)
Vetor de casas ocupáveis: PPPPPPPPPPPP--------pppppppppppp

Para referenciar um movimento basta indicar as casas numeradas:
» 22-18 Para abrir o jogo com as brancas.
» 9-13 Poderia ser a próxima jogada das pretas.
» 13-22-15 Poderia uma tomada em seqüência das pretas caso o movimento 21-17 fosse feito.
O jogo ficaria: 1.22-18 9-13 2.21-17 13-22-15

Através da função execMov(Peca peca) é possível validar e executar um movimento de cada vez:
» execMov(22) Seleção da peça na casa 22 válida.
» execMov(18) Movimento da peça da casa 22 para a casa 18 válida.

Outra coisa seria trabalhar o tabuleiro como uma máquina de estados:
» JOGO - Ativo para jogar.
» EM_JOGO - Deve continuar jogando.
» COMPLETO - O movimento foi válido e é a vez do oponente.
» VITORIA - O Jogador atual venceu a partida.
» EMPATE - Os jogadores empataram.
» DERROTA - O Jogador atual perdeu a partida.

Com controle de jogador, estados e tudo mais:

» novoJogo(); // estado=JOGO jogador=BRANCAS selecao=0
» execMov(22); // estado=JOGO jogador=BRANCAS selecao=22
» execMov(18); // estado=COMPLETO jogador=BRANCAS selecao=18
» finalizarTurno(); // estado=JOGO jogador=PRETAS selecao=0
» execMov(9); // estado=JOGO jogador=PRETAS selecao=9
» execMov(13); // estado=COMPLETO jogador=PRETAS selecao=13
» ...
» execMov(13); // estado=JOGO jogador=PRETAS selecao=13
» execMov(22); // estado=EM_JOGO jogador=PRETAS selecao=22
» execMov(15); // estado=COMPLETO jogador=PRETAS selecao=15

.:: Interface gráfica ::.
A interface gráfica também tem grande destaque neste trabalho.
Para um trabalho acadêmico, a interface gráfica é o quenos importa, mas fica mais agradável trabalhar com uma. Um jogo bonito e inteligente tem que valer créditos extras !!!
Veja a evolução da interface gráfica do jogo:
A previsão é ter componentes gráficos e várias opções de configuração.

A interface foi feita utilizando os programas Inkscape e GIMP. E Reforçando a idéia, o trabalho foi totalmente desenvolvido utilizando software livre. Ubuntu, Inkscape, GIMP, Geany, Makefile, GCC e SDL.

.:: Link's ::.
Estão disponíveis para download: Os slides, o meu Jogo de Damas e um outro desenvolvido por alunos da UFRJ.

Download: » Heurística Damas (946 kB)
Download: » Damas 0.3 alpha4 (747 kB)
Download: » Damas UFRJ (1 MB)

» Solução ideal para o jogo de damas
» Sobre futebol e robôs

» Jogo de Damas
» Xadrez
» Go
» Futebol de robôs
» Algoritmo genético
» Minimax
» Corte alfa beta