Trabalho de Implementação – Jogo Reversi 1 Introdução

Trabalho de Implementação – Jogo Reversi
Paulo Afonso Parreira Júnior {[email protected]}
Rilson Machado de Olivera {[email protected]}
Universidade Federal de Lavras – UFLA
Departamento de Ciência da Computação - DCC
Resumo: este trabalho apresenta os artefatos gerados durante o desenvolvimento do jogo Reversi,
tais como: a descrição do trabalho, o diagrama de caso de uso e o diagrama de classes. O trabalho
apresenta ainda, detalhes sobre as técnicas de busca competitiva utilizadas pelo jogo. Ao final, será
indicado o link para execução do jogo através da Internet.
1 Introdução
Nos primeiros anos da pesquisa em Inteligência Artificial - IA, desenvolver bons métodos de busca
era o principal objetivo. Os pesquisadores acreditavam que a busca é a base da resolução de
problemas [1]. Antes de adentrar mais no assunto, faz-se necessário explicitar alguns termos
inerentes aos métodos de buscas. Esta terminologia é representada na Tabela 1.
Termos
Descrição
Estado
Situação relevante para o problema.
Estado inicial
Estado onde o agente se encontra no início.
Operadores ou ações
Conjunto de ações disponíveis ao agente que permite ir de um estado
para outro.
Espaço de estados
Conjunto de todos os estados alcançáveis a partir do estado inicial por
meios da aplicação de uma sequência de ações.
Caminho
Uma sequência de ações levando de um estado a outro.
Teste de objetivo
Teste aplicado pelo agente para verificar se chegou a um estado
objetivo.
Custo do caminho
A soma total dos custos das ações individuais ao longo de uma
caminho, denotada pela função “g”.
Solução
Um caminho que parte do estado inicial e leva a uma estado objetivo.
Completude
A estratégia garante encontrar uma solução se esta existir?
Complexidade de tempo
Quanto demorou a achar a solução?
Complexidade no espaço Quanta memória foi necessária para achar a solução?
Optimalidade
A solução encontrada foi a melhor?
Tabela 1Terminologia: Métodos de Busca. Fonte: [1]
A Figura 1, a Figura 2 e a Figura 3 representam exemplos de problemas e a definição de métodos de
busca que possam resolvê-los.
Figura 1: Exemplo: Quebra-Cabeça. Fonte: [1]
Figura 2: Exemplo: Oito Rainhas. Fonte: [1]
Figura 3: Exemplo: Missionário e Canibais. Fonte: [1]
O funcionamento de um método de busca pode ser visto como um processo de expansão de uma
árvore [1]. Assim sendo, podem-se utiliza estratégias para expansão deste nós. Algumas estratégias
conhecidas são: (i) busca de amplitude, (ii) bsuca de custo uniforme, (iii) bsuca em profundidade,
(iv) minimax, (v) poda alpha-beta, entre outras.
Neste trabalho, serão implementados o algoritmo mini-max e a estratégia de poda alpha-beta.
1.1 Minimax
O algorítimo MINIMAX é uma técnica de busca utilizada em jogos de soma zero (se alguém
ganha, alguém tem que perder). Considere o jogo de xadrez, por exemplo, temos dois lados: as
brancas e as pretas. Se um ganha, o outro perde, assim, se a pontuação de um jogador é X, a do
oponente é -X, garantindo a soma 0 [1].
Baseado no algoritmo descrito no livro “Prolog Programming For Artificial Intelligence”. É
através deste algoritmo que o computador “procura” a melhor jogada a efectuar. O algoritmo
minimax, consiste na construção de uma árvore com as jogadas possíveis para cada jogador e todas
as subsequentes destas. É atribuído então aos nós terminais (jogadas que não têm “descendentes”)
um valor conforme as condições do tabuleiro favoreçam um jogador ou outro. Desse modo, um dos
jogadores deverá tentar obter o valor máximo (jogador MAX) e outro o valor mínimo (jogador
MIN). Logo, a todo nó ascendente de um nó terminal, será atribuído o valor do filho com menor ou
maior valor, conforme seja uma jogada do MIN ou MAX respectivamente. O mesmo é repetido para
todos os nós da árvore, até chegar ao valor da raiz. Na prática, a árvore não é visitada até às folhas,
mas sim até uma determinada profundidade imposta por limites de tempo para efectuação da jogada
e capacidade de processamento [2].
Neste trabalho, o usuário poderá selecionar até que nível da árvore o algoritmo deverá
pesquisar. Através da opção Nível de Dificuldade na tela principal do jogo, o usuário poderá
escolher entre os valores:
•
Fácil
•
Intermediário
•
Difícil
Estes estes valores representam até que nível da árvore de busca o algoritmo deverá executar. Sendo
assim, o valor Fácil permitirá que o algoritmo vasculhe até o 3º nível, o nível intermediário até o
5º nível e o nível Difícil até o 7º nível.
Segundo [1], conforme a altura da árvore aumenta, melhor é a jogada do computador.
1.2 Cortes Alpha-Beta
Os cortes alpha-beta procuram aumentar a eficiência do algoritmo minimax permitindo a
omissão de alguns “ramos” da árvore de jogadas possíveis na procura da melhor jogada. A ideia é
encontrar uma jogada que seja suficientemente boa (não necessariamente a melhor) para conduzir à
decisão correcta. É com esse intuito que são introduzidos os limites Alpha e Beta, sendo Alpha o
valor mínimo que se garante que o MAX obtenha, e o Beta o valor máximo que o MAX pode
esperar obter (logo, o valor final obtido encontrar-se-á entre este dois limites). Se se concluir que
uma jogada têm valores exteriores ao intervalo, trata-se de uma jogada que não deverá ser
efectuada, não sendo necessário calcular o seu valor exacto, este só tem de ser calculado caso o
valor se encontre dentro do intervalo Alpha-Beta [2].
No pior caso, o algoritmo alpha-beta visitará exactamente as mesmas posições que visita o
algoritmo minimax simples, não havendo nesse caso vantagem deste algoritmo em relação ao
minimax exaustivo. No entanto, está provado que no melhor caso (quando a jogada mais forte é
considerada primeiro) o algoritmo alpha-beta terá apenas que avaliar a raiz do número de jogadas
terminais que teriam de ser avaliadas pelo algoritmo de pesquisa minimax exaustivo.
1.3 Heurísticas
Neste trabalho foram utilizadas 2 heurísticas para avaliação das possíveis jogadas. A
primeira foi proposta por [1] e é apresentada na seção 1.3.1. A segunda heurística foi proposta pela
equipe de desenvolvedores (Paulo Afonso e Rilson) e é apresentada na seção 1.3.2. A avaliação final
de uma jogada é feita a partir da média ponderada dos valores resultantes das 2 heurísticas
anteriormente citadas (ver Figura 4).
Avaliação Final Jogada = (Avaliação Heurística 1) * 0.7 + (Avaliação Heurística 2) * 0.3
Figura 4: Avaliação final de uma jogada
1.3.1 Heurísticas dos Pesos
A avaliação de um nó é dada da seguinte maneira: para todas as peças que possuída por
quem está na vez da jogada (Usuário/Computador), soma-se o seu valor baseado na seguinte matriz
de pesos (ver Tabela 2):
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
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
0
0
10
10
10
10
10
10
0
0
20
0
10
10
10
10
10
10
0
20
Tabela 2: Matriz de Pesos. Fonte: [2]
Considerações sobre a matriz de pesos [2]:
1. As casas do meio mudam freqüentemente o seu valor. Por isso achamos que não valia muito
possuir uma casa dessas.
2. As casas do canto são muito valiosas, uma vez que seu valor nunca poderá ser alterado.
3. As casas vizinhas às casas do canto são as piores casas do tabuleiro, uma vez que se você possuílas, você dará oportunidade do adversário dominar um canto.
4. Todas as outras casas têm um valor razoavelmente bom, e quanto mais você possuir, mais opções
de jogo você terá, reduzindo as chances de você ter que ceder a vez.
1.3.1 Heurísticas da Qunatidade de Peças Capturadas
Esta é uma heurística simples onde cada jogada é avaliada de acordo com a quantidade de
peças capturadas na mesma. Ou seja, uma jogada em que mais peças do adversário são capturadas,
para esta heurística, é considerada um boa jogada.
2 Desenvolvimento do Jogo
2.1 Descrição do trabalho
O objetivo desse trabalho é implementar algumas técnicas de busca competitiva que são
utilizadas em jogo clássicos em IA. Implementar um programa para jogos conhecidos como
“Reversi”. O Resversi é um de tabuleiro, onde dois jogadores (um branco e outro preto) tentam
preencher o maior numero de posição como suas peças. O tabuleiro tem 8X8 posições, e
inicialmente as posições centrais são preenchidas com 2 peças brancas e duas peças pretas formando
um X. O jogador preto começa e deve colocar sua peça de forma que exista pelo menos uma peça
branca “peça capturada” entre duas peças pretas, seja na vertical, horizontal ou diagonal. As peças
capturadas mudam de cor, e o jogo termina quando nenhum jogador possui mais nenhuma jogada
valida.
2.2 Diagrama de Casos de Uso
Esta seção apresenta o diagrama de Casos de Uso do sistema a ser desenvolvido. Como pode ser
visto na Figura 5, o usuário poderá iniciar um jogo e reiniciá-lo a qualquer momento, poderá
também selecionar uma jogada quando for sua vez de jogar, consultar ajuda e visualizar sobre.
Figura 5: Diagrama de Casos de Uso - Jogo Reversi.
O outro atuador do sistema, o ator “Computador”, representa a máquina que irá jogar contra o
usuário. Como pode-se observar, este ator apenas pode selecionar uma jogada quando for a sua vez
de jogar.
O detalhamento destes Casos de Uso pode ser visto na Tabela X.
Id Caso de Uso: 001
Nome: Iniciar Jogo
Casos de Uso Relacionados: -Descrição: O ator iniciar uma nova partida.
Ator(es): Usuário
Pré-Condições: O Ator ter selecionado um tema, com qual peça deseja jogar e o nível de
dificuldade do jogo.
Extension Points: -Execução Normal:
1. O Ator inicia o Caso de Uso selecionando “Iniciar Jogo”;
2. O Sistema atualiza o tabuleiro e exibe a tela para um novo jogo;
Pós-Condições: Um novo jogo é iniciado.
Exceções: -Fluxos Alternativos: -Interfaces: --
Id Caso de Uso: 002
Nome: Reiniciar Jogo
Casos de Uso Relacionados: -Descrição: O ator poderá reiniciar um jogo a qualquer momento.
Ator(es): Usuário
Pré-Condições: -Extension Points: -Execução Normal:
3.O Ator inicia o Caso de Uso selecionando “Reiniciar Jogo”;
4.O Sistema atualiza o tabuleiro e exibe a tela para um novo jogo;
Pós-Condições: Um novo jogo é iniciado.
Exceções: -Fluxos Alternativos: -Interfaces: -Id Caso de Uso: 003
Nome: Selecionar jogada
Casos de Uso Relacionados: -Descrição: O Ator informa a jogada que deseja realizar naquele momento;
Ator(es): Usuário, Computador
Pré-Condições: -Extension Points: Consultar Ajuda
Execução Normal:
1. O Ator inicia o Caso de Uso informando a jogada que deseja realizar, ou seja,
informando sobre qual casa deseja colocar uma peça sua;
2. O Sistema verifica se a jogada satisfaz as regras do jogo [E1];
3. O Sistema atualiza o tabuleiro e encerra o Caso de Uso;
Pós-Condições: Uma nova configuração do tabuleiro é representada;
Exceções:
Exceção E1 – Jogada Inválida.
1. O Sistema informa que a jogada não é válida; volta para o passo 1 do Fluxo Básico;
Fluxos Alternativos: -Interfaces: -Id Caso de Uso: 004
Nome: Consultar Ajuda
Casos de Uso Relacionados: -Descrição: O Ator obtém ajuda sobre as regras do jogo;
Ator(es): -Pré-Condições: -Extension Points: -Execução Normal:
1. O Ator inicia o Caso de Uso, selecionando “Consultar Ajuda”;
2. O Sistema exibe as informações sobre o jogo, bem como suas regras e dicas de boas
jogadas;
Pós-Condições: Informações sobre o jogo são exibidas.
Exceções: -Fluxos Alternativos: -Interfaces: --
Id Caso de Uso: 005
Nome: Consultar Sobre
Casos de Uso Relacionados: -Descrição: Exibe informações sobre a equipe que desenvolveu o jogo;
Ator(es): -Pré-Condições: -Extension Points: -Execução Normal:
1. O Ator inicia o Caso de Uso, selecionando “Consultar Sobre”;
2. O Sistema exibe as informações dos desenvolvedores do jogo;
Pós-Condições: Informações sobre os desenvolvedores são exibidas.
Exceções: -Fluxos Alternativos: -Interfaces: --
2.3 Diagrama de Classes
Esta seção apresenta o diagrama de Classes do jogo desenvolvido (ver Figura 6), bem como uma
breve descrição sobre cada uma das classes presentes no diagrama (ver Tabela 3).
Classe
Descrição
Tabuleiro
Classe que modela o tabuleiro do jogo. Possui métodos para manipulação
das peças no tabuleiro, bem como para a escolha das jogadas através dos
métodos de busca Minimax e Poda alfa-beta.
TabuleiroSingleton
Classe derivada do Design Pattern Singleton que garante a existência de
apenas uma instância da classe Tabuleiro durante o jogo.
CasaTabuleiro
Classe que modela uma casa do tabuleiro. Possui métodos que possibilitam
verificar se casa está vazia, ou com alguma peça.
JogadaValida
Consiste de um casa de destino e algumas casas que possuem peças a serem
capturadas. Ou seja, é uma classe que modela uma jogada, e esta jogada
necessariamente é válida, ou seja, é passível de ocorrer.
Jogo
Classe que modela o jogo reversi. É responsável por criar a interface do jogo
e garantir a interação com o usuário. Funciona como interface entre o
usuário e o tabuleiro do jogo, traduzindo os eventos gerados pelo jogador em
ações de movimentação de peças do tabuleiro.
Util
Classe utilitária, responsável por armazenar as mensagens e constantes
utilizadas pelo jogo.
Tema
Classe que modela um tema de jogo. É responsável por definir o formato das
peças do tabuleiro.
JApplet
Classe distribuída junto com a plataforma de desenvolvimento JDK da
linguagem JAVA. Permite a construção de Applets: componentes que podem
ser incoporados a páginas HTML e executados via web.
Tabela 3: Descrição das classes - Jogo Reversi
Figura 6: Diagrama de classes - Jogo Reversi
3 Ferramentas Utilizadas
Para o desenvolvimento deste trabalho foram utilizadas as seguintes tecnologias:
•
Plataforma de programação JAVA 1.5: tecnologia Applet;
•
Browser Mozila Firefox;
•
Ferramenta de modelagem de sistemas orientados a objetos baseado na UML – JUDE 5.0;
Considerações Finais
Com este trabalho foi possível aprender mais sobre as estratégias de IA (Minimax e Poda
Alfa-beta) utilizadas em jogos. Utilizando o algoritmo MiniMax, observou-se a diferença na
qualidade das jogadas encontradas pelo computador quando este é habilitado a vasculhar mais ou
menos o espaço de busca da solução. Percebeu-se também, que quanto mais alta era árvore de busca
(nível de dificuldade difícil), maior era o tempo dispensado para retornar uma jogada válida. Sendo
assim, foi implementado a estratégia de poda alfa-beta que garante um desempenho maior deste
algoritmo por realizar cortes na árvore de busca em regiões onde a melhor solução não se encontra.
O resultado do trabalho encontra-se disponibilizado na Internet e pode ser acessado através do
endereço endereço: http://alunos.dcc.ufla.br/~paulojr
6 Referências Bibliográficas
[1] Notas de aula. Disciplina: IA – Inteligência Artificial, UFLA: 2007/2.
[2] http://paginas.fe.up.pt/~eol/IIA/trabalhos/98_99/XADREZ/relatorio.html