Apresentacao
607 palavras
3 páginas
Trabalho deInteligência Artificial
Grupo:
Dino Leonetti
Fabio Marzullo
Tema: Jogo Reversi
O Problema:
Consiste em um tabuleiro dividido em nxn casas.
Comumente encontrado no tamanho
8x8.
Jogadores se revezam tentando transformar peças do adversário em suas. 2
Regras do Jogo
Tabuleiro inicia com
4 peças no centro.
As peças iniciais são dispostas na diagonal.
O jogador deve tentar encobrir peças do adversário em qualquer direção
Não há limite de peça a encobrir
Peças encobertas serão substituídas
Se não houver jogada válida o jogador passa a vez.
Ganha quem tiver o maior número de peças da sua cor.
3
Implementação
Desenvolvido em Java.
Utilização de técnicas de IA.
Algoritmos utilizados:
Mini-Max e Alfa-Beta.
4
Dificuldades Encontradas
Performance.
Linguagem de programação orientada à objetos. Tempo excessivo gasto com criação de objetos. Uma jogada demorava em média 30 segundos. Heurística
Dificuldade em encontrar uma heurística que atendesse o tamanho variável do tabuleiro.
5
Heurísticas
Solução 1: Heurísticas Existentes
Diversas heurísticas disponíveis na internet.
Todas para tabuleiro tamanho 8x8.
Solução 2 (utilizada): Criação de
Heurística Própria
Foi criada uma heurística que satisfizesse nossas necessidades.
6
Heurística Utilizada
Características da Busca:
A árvore de busca não é expandida até o final.
Limite da altura da árvore por questões de performance. Conforme a altura da árvore aumenta, maior é o nível de dificuldade (melhor é a jogada do computador).
Avaliação de um nó:
O nó não é necessariamente um nó folha.
Para cada peça do jogador da vez soma-se o peso correspondente à sua posição no tabuleiro.
7
Pesos das Casas do
Tabuleiro
20
0
10
10
10
10
10
10
0
20
0
0
10
10
10
10
10
10
0
0
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
5
5
10
10
10
10
10
10
10
10
5
5
10
10