Disciplina Inteligência Artificial
Defesa de Projeto
Período 2008.2
Alan de Farias, Anderson Pablo, Rafael Dantas
Jogo de Damas usando Algoritmo Min-Max e poda
Alfa-Beta
Projeto Autotest – Linha geração de código mock
Agenda
 Introdução
 Escolha de projeto
 Algoritmo Min-Max
 Poda Alfa-Beta
 Implementação
 Considerações finais
Introdução
 Trabalho focado na prática de conceitos vistos durante
a disciplina
 Diferente de alguns jogos básicos com interface, a
implementação estará justamente na inteligência
artificial que será usada como adversário.
Escolha de projeto
 Projeto
 Jogo de damas
 Inteligência artificial
 Poucas regras
 Interface simples
 Os conceitos
 Algoritmo Min-Max e poda Alfa-Beta
Algoritmo Min-Max
 O algoritmo minimax ajuda a encontrar a melhor
jogada ao caminhar pelas opções válidas a partir do fim
do jogo.
 A cada passo assume-se que o jogador A está tentando
maximizar as chances de A ganhar, enquanto na
próxima rodada o jogador B está tentando minimizar
as chances de isso acontecer (ao maximizar as chances
de que ele próprio ganhe).
Pseudo-código
FUNÇÃO minimax(nó, profundidade)
SE nó é um nó folha OU profundidade = 0
RETORNE a heurística do valor do nó
SE o adversário jogará no nó
ASSUMA α := +∞
PARA_CADA filho DE n
α := min(α, minimax(filho, profundidade-1))
SENÃO
ASSUMA α := -∞
PARA_CADA filho DE nó
α := max(α, minimax(filho, profundidade-1))
RETORNE α
Poda Alfa-Beta
 Poda Alfa-Beta é uma variação do algoritmo Min-Max
que visa reduzir o número de nós que são avaliados na
árvore de busca
 Poda - :
 calcular a decisão correta sem examinar todos os nós da
árvore;
 retorna o mesmo que minimax, porém sem percorrer
todos os estados.
Implementação
 Para representar o tabuleiro usamos uma matriz com
todas as posições
 Cada posição ocupada por uma peça contém o peso
desta peça.
 Um jogador Max que maximiza as chances dele vencer
 Um jogador Min, que minimiza as chances do jogar
max ganhar
Considerações finais
 Esse projeto demonstrou que é possível com o uso da
inteligência artificial criar um adversário consciente
das jogadas que realiza.
 Apesar de algumas limitações o algoritmo Min-Max
produz bons resultados em jogos de raciocínio lógico.
 Caracterizando uma forma de raciocínio baseado em
lógica,