Instituto Politécnico do Porto
Instituto Superior de Engenharia
Departamento de Engenharia Informática
Implementação de um
Agente Inteligente para jogar
Elaborado por:
Marlene da Graça Santos nº 980975
Ramo de Computadores e Sistemas
Orientador
Eng. António Jorge dos Santos Pereira
Setembro 2004
Marlene Santos nº 980975
II
Realizado por
Marlene da Graça Santos
Aluna nº 980975
Ramo Computador e Sistemas
Setembro 2004
Orientador
Eng. António Jorge dos Santos Pereira
III
IV
Resumo
Este projecto consiste no desenvolvimento de um agente inteligente que seja capaz
de jogar o Dvonn, sendo que o Dvonn é um jogo de tabuleiro para dois jogadores.
Para que o agente possa “substituir” um jogador humano necessita de possuir
algumas capacidades de raciocínio que lhe permitam tomar “boas” decisões
relativamente às jogadas a realizar. Esta tomada de decisão por parte do agente,
deverá ser feita tendo em conta diferentes níveis de abstracção, designadamente,
estratégico, táctico e operacional. Cada um destes níveis compreende diferentes
objectivos ou metas a cumprir.
No que diz respeito ao projecto em questão, foram considerados os seguintes
aspectos em cada um dos níveis. No operacional, são representadas as estruturas de
dados de baixo nível que suportam a implementação do jogo bem como as regras do
jogo e validações necessárias. No nível táctico são definidas e estruturadas as metas
atingir a curto prazo, designadamente “jogadas” envolvendo um conjunto de
movimentos. No nível estratégico são definidos objectivos a atingir a longo prazo,
sendo necessário considerar elementos difusos de raciocínio como por exemplo,
jogada “boa” ou “má”, para além disso é levada em consideração a necessidade de
ponderar não só os ganhos imediatos mas também os ganhos a obter no final do
jogo. Este último nível, por dificuldades várias é aquele que se encontra num estado
mais insipiente. Finalmente, para atingir a vitória, objectivo último do jogo, os níveis
teriam de cooperar entre si.
No desenvolvimento do agente foi utilizada a linguagem Prolog, principalmente
devido ao nível de abstracção que a linguagem proporciona para a representação de
diferentes camadas de conhecimento e também pelo facto de fornecer um motor de
raciocínio nativo. O interpretador de Prolog utilizado foi Win-Prolog 4.32 por ser a
existe disponível no ISEP e também pelo facto de disponibilizar bibliotecas que
permitem a implementação facilitada de agentes.
V
VI
Dedicatória
À minha querida mãe, aos meus irmãos e toda a minha família em Cabo Verde.
VII
VIII
Agradecimentos
Em primeiro lugar quero agradecer a Jeová Deus de todo o coração pela força, ânimo
e consolo que me deu durante estes últimos meses que foram muito difíceis e
decisivos para mim a nível pessoal e também por todas as bênçãos que tive durante
todo o meu percurso escolar aqui em Portugal.
Agradeço também ao meu orientador pelos esclarecimentos, pelo apoio na fase de
implementação do projecto, pelas ideias que me transmitiu e pelo seu empenho em
me ajudar neste projecto.
Gostaria de agradecer a minha querida irmã Natasha que tem me aturado bastante
durante estes últimos meses e a toda a minha família que também mesmo de longe
me tem motivado a seguir em frente e não desistir.
Quero agradecer aos meus irmãos do peito Ricardo e João, e também as minhas
queridas amigas Rosa e Anabela e também ao Miguel pela paciência e amizade que
tiveram por mim durante estes anos de muita luta.
À todos os meus irmãos na congregação que de uma forma prática têm me ajudado
em especial a Filomena e a Alcina, um obrigado de coração.
Quero agradecer a todos os meus colegas de casa que me têm apoiado mais de
perto e viveram estes momentos de stress comigo.
E de uma forma geral, quero agradecer a todos aqueles que de uma forma directa ou
indirecta contribuíram para a realização deste projecto.
IX
Índice
Capítulo 1 ________________________________________________1
Introdução __________________________________________________1
1.1 -
Motivação para a escolha do projecto _____________________________2
1.2 -
Organização do relatório _______________________________________3
1.3 -
Notação utilizada no relatório ___________________________________4
Capítulo 2 ________________________________________________7
Teoria dos Jogos ______________________________________________7
2.1 -
Conceitos associados __________________________________________9
2.2 -
Tipo de jogos de estratégia ____________________________________11
2.2.1 -
Jogos de soma zero _______________________________________12
2.2.2 -
Jogos de soma não zero ___________________________________14
2.3 -
Equilíbrio de Nash ___________________________________________15
Capítulo 3 _______________________________________________19
Técnicas de busca para exploração de árvores de decisão _____________19
3.1 -
Estratégias de Busca Tradicionais _______________________________22
3.1.1 -
Busca por largura ________________________________________22
3.1.2 -
Busca em profundidade ____________________________________24
3.1.3 -
Busca bidirecional ________________________________________25
3.1.4 -
Busca de custo uniforme ___________________________________26
3.1.5 -
Busca heurística _________________________________________26
3.2 -
Análise de algoritmos de busca _________________________________27
Capítulo 4 _______________________________________________31
O Algoritmo MiniMax e alguns refinamentos _______________________31
4.1 -
Descrição do algoritmo MiniMax ________________________________31
X
4.2 -
Cortes ALFA-BETA ___________________________________________38
4.3 -
Desvantagens do MiniMax _____________________________________42
4.4 -
Jogos implementados usando o MiniMax __________________________43
Capítulo 5 _______________________________________________45
Implementação de um agente inteligente para o Dvonn ______________45
5.1 -
Regras do Dvonn ____________________________________________45
5.2 -
Descrição do Problema a resolver _______________________________50
5.3 -
Análise de espaço do problema _________________________________51
5.4 -
Estruturação do problema proposto______________________________52
5.5 -
Implementação das regras do jogo ______________________________58
5.5.1 -
Validação das jogadas _____________________________________58
5.5.2 -
Como calcular os benefícios de uma jogada? ___________________61
5.5.3 -
Calcular o Isolamento de peças______________________________63
5.5.4 -
Fim do Jogo _____________________________________________69
5.6 -
Tácticas propostas para o jogo _________________________________69
5.6.1 5.7 -
Implementação das tácticas propostas ________________________71
Comunicação do agente com o servidor de jogos na Internet__________77
Capítulo 6 _______________________________________________79
Conclusão __________________________________________________79
Bibliografia e Referências ______________________________________81
Acrônimos__________________________________________________83
XI
Índice de figuras
Figura 1 - Busca em largura ___________________________________________23
Figura 2 – Busca em profundidade ______________________________________25
Figura 3 - Método MiniMax ____________________________________________33
Figura 4 – Busca numa árvore uma e duas posições a frente [1]_______________34
Figura 5 – Cortes Alfa e Beta [1]________________________________________39
Figura 6 – Corte usando o valor de Alfa __________________________________39
Figura 7 – Corte usando o valor Beta ____________________________________39
Figura 8 - Peças no tabuleiro que não podem ser movidas____________________47
Figura 9 - Movimento das peças ________________________________________48
Figura 10 - Perda de peças ____________________________________________48
Figura 11 – Fim do jogo ______________________________________________49
Figura 12 - Diferentes níveis de abstração no jogo Dvonn ____________________52
Figura 13 – Organização dos ficheiros____________________________________54
Figura 14 – Tabuleiro Dvonn [19] _______________________________________56
Figura 15 – Formato de apresentação do tabuleiro__________________________57
Figura 16 – Direcções para onde uma pilha pode movimentar _________________59
Figura 17 – Movimentar uma pilha ______________________________________60
Figura 18 – Isolamento de peças _______________________________________63
Figura 19 – Tabuleiro inicial gerado pelo servidor___________________________63
Figura 20 – Divisão do tabuleiro em áreas ________________________________64
Figura 21 – Movimentar pilhas entre áreas ________________________________67
Figura 22 – Comunicação entre os participantes do jogo _____________________78
XII
XIII
Capítulo 1
Introdução
Os jogos exercem um fascínio inexplicável sobre muitas pessoas. Desde o
surgimento dos computadores que os especialistas se aperceberam das grandes
hipóteses de poder usar o computador para criar programas de jogos capazes de
competir com humanos.
Assim desde esse tempo muito se tem feito para concretizar a ideia de que
programas de computador seriam capazes de jogar e aprender com os seus próprios
erros melhorando o seu próprio desempenho.
A Inteligência Artificial tem um papel relevante neste contexto contribuindo com
métodos e algoritmos para que possam ser criados programas com capacidades de
agir cada vez mais como humanos podendo assim actuar e tomar boas decisões ao
longo do jogo. Na área dos jogos, estas técnicas foram inicialmente aplicadas a jogos
como xadrez, damas e jogo do galo. Actualmente, as técnicas de Inteligência
Artificial aplicadas em jogos de computador estão mais desenvolvidas, permitindo a
criação de jogos mais complexos, que permitem a criação de programas mais
inteligentes e de ambientes mais reais para interagir com os mesmos.
Tendo em conta o desenvolvimento acelerado das tecnologias computacionais, quer
a nível de hardware e software há cada vez mais melhores condições técnicas e
computacionais que permitem a exploração da inteligência artificial em jogos muito
pesados.
Os jogos de computador são uma excelente plataforma para testes e validações de
novas metodologias e algoritmos, devido a própria natureza dos jogos e a
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
1
Instituto Superior de Engenharia do Porto
Capítulo 1 - Introdução
complexidade dos ambientes que requerem, bem como a existência de inúmeros
voluntários humanos para a realização dos testes. Uma vez que estes ambientes são
controlados, proporcionam as condições ideais para teste de procedimentos
complexos.
Através dos jogos de computador pode-se verificar a validade das mais diversas
técnicas de inteligência artificial, desde o reconhecimento da linguagem natural,
modelos de cognição e interacção, até mecanismos complexos de planeamento,
busca e aprendizagem.
Muitos pioneiros da ciência da informação e computação contribuíram para uma
nascente literatura sobre jogos em computador. Muitos descreveram mecanismos
que poderiam ser usados em programas para diversos tipos de jogos tais como
xadrez e damas. Os problemas principais que se colocam nos jogos são sem dúvida
que tácticas e estratégias poderão ser usados para ganhar o adversário [1].
Tendo em conta que muitos desses problemas obviamente já foram resolvidos ao
longo do tempo, assim este projecto foi proposto com o objectivo de desenvolver um
estudo e a implementação de um agente inteligente capaz de jogar o Dvonn, um
jogo de tabuleiro que se encontra disponível na Internet para dois jogadores on-line.
Pretende-se uma implementação do jogo onde um jogador possa jogar com o
próprio computador, neste caso o agente inteligente. Mais importante ainda do que a
implementação do próprio agente inteligente, será o estudo pormenorizado dos
algoritmos já existentes sobre teoria de jogos, avaliação do desempenho desses
algoritmos, as tácticas e estratégias de jogo usados em geral, e como poderiam ser
adaptados ao jogo Dvonn. Após esse estudo, escolher um algoritmo que melhor se
adapta ao problema específico ou então optar por adaptar um determinado algoritmo
ao problema em especifico, ou até mesmo criar um algoritmo próprio para o
problema de acordo com as teorias disponíveis.
1.1 -
Motivação para a escolha do projecto
A primeira vista, na listagem de projectos propostos pelos professores nenhum dos
projectos me despertou muito interesse. Confesso que no início tive muitos
problemas em escolher o projecto devido ao facto da questão muitas vezes
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
2
Instituto Superior de Engenharia do Porto
Capítulo 1 – Introdução
levantada quanto a possibilidade de os alunos que escolhessem projectos com uma
grande componente prática serem penalizados por essa mesma escolha. Depois dos
esclarecimentos dados pelo responsável Paulo Ferreira e de falar muita abertamente
com o orientador sobre o problema decidi ir em frente com o projecto. A explicação
inicial que o orientador me deu, e a simpatia e empenho que demonstrou
motivou-me muito na mesma escolha, apesar de considerar que o projecto seria
bastante difícil e exigiria de mim um grande empenho tanto na componente prática
como teórica. Contudo decidi aceitar o desafio uma vez que é uma coisa diferente
que não estou habituada a fazer. E também porque na altura quando estudei a
cadeira Computação gráfica percebi realmente a quantidade de trabalho envolvido a
nível gráfico nos jogos e isso me fascinou. Neste trabalho não teria que trabalhar
com computação gráfica mas teria que trabalhar com estratégias e tácticas de jogo,
e isso também me despertam muito interesse.
1.2 -
Organização do relatório
Este relatório encontra-se subdividido em 6 capítulos que serão descritos a seguir.
Capítulo 1
Faz uma introdução ao projecto e descreve de uma forma resumida o problema
proposto.
Capitulo 2
Este capítulo se dedica essencialmente ao estudo da teoria dos jogos de uma forma
que nos permite ter um conhecimento mais abrangente sobre o tipo de problemas
que podemos deparar ao tentarmos analisar o que se encontra por detrás de um
jogo de computador. Descreve os conceitos e termos mais utilizados nesta área e em
outras áreas onde a tomada de decisões pode ser comparada a um jogo. O capítulo
faz também uma pequena distinção entre os vários tipos de jogos existentes, e os
mais estudados. Descreve também de uma forma de fácil perceptibilidade como os
estudos efectuados por Nash e a própria teoria desenvolvida por ele são de uma
forma prática usados em jogos.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
3
Instituto Superior de Engenharia do Porto
Capítulo 1 - Introdução
Capítulo 3
Este capítulo faz uma introdução relacionado com Inteligência Artificial, Agentes
inteligentes e a necessidade dos agentes terem alguma inteligência que lhes
possibilita tomar decisões por si próprio. Também, descreve-se algumas estratégias
de busca em árvores, suas vantagens e desvantagens a nível de requisitos de
hardware e capacidade de processamento.
Capítulo 4
Este capítulo é dedicado ao algoritmo MiniMax que é o algoritmo mais conhecido e
mais usado em teoria dos jogos. Faz-se uma descrição pormenorizada do algoritmo,
como foi pensado, as vantagens, as desvantagens, o grau de desempenho, as
condições de processamento e requisitos de memória que exige e alguns
melhoramentos.
Capítulo 5
De uma forma resumida este capítulo faz uma análise do problema proposto, avalia
as situações possíveis de implementação, estrutura a organização da informação que
será preciso para o próprio funcionamento do agente, e descreve a implementação
feita e alguns predicados mais importantes.
Capítulo 6
Este capítulo é destinado para a conclusão, a descrição das dificuldades encontradas
na elaboração e implementação do projecto, aspectos interessantes e considerações
sobre
como
poderia
melhorar
o
desempenho
do
agente,
ou
ainda
que
funcionalidades poderiam ser acrescentado futuramente.
1.3 -
Notação utilizada no relatório
Ao longo do relatório foi utilizada a font Verdana tamanho 10 e alinhamento
justificado. Para termos em inglês e a descrição de conceitos foi usada o mesmo tipo
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
4
Instituto Superior de Engenharia do Porto
Capítulo 1 – Introdução
de letra mas com o estilo Itálico. Para a descrição de métodos ou predicados usados
na implementação do agente foi usada a font Fixedsys tamanho 10 com estilo Itálico.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
5
Instituto Superior de Engenharia do Porto
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
Capítulo 1 - Introdução
6
Capítulo 2
Teoria dos Jogos
A Teoria dos Jogos foi criada na década de 40 pelo matemático John Von Neumann e
recentemente, o matemático John Nash fez um novo estudo sobre o equilíbrio em
jogos não cooperativos e conseguiu obter o prémio Nobel de economia em 1994.
Esta teoria com base matemática é uma ferramenta muito importante na tomada de
decisões [4].
A teoria dos jogos trata de situações de concorrência ou competição entre dois ou
mais participantes cada um com os seus próprios objectivos e estratégias definidas.
Nestas situações de concorrência ou competição cada participante terá que ter
alguma capacidade de tomar decisões acertadas. Estas decisões são muito
importantes porque são elas que irão permitir ou não que os objectivos predefinidos
pelos participantes sejam atingidos.
De acordo com a referência [11], esta é uma teoria baseada em conflitos porque
existe uma concorrência entre os diversos participantes. Ao mesmo tempo a teoria
pode ser considerada de colaboração entre os vários participantes, quando existe a
possibilidade de haver um acordo entre os participantes. Tendo em vista que cada
um dos intervenientes tem como objectivo tirar o máximo ganho, ou seja, cumprir
com os seus objectivos anteriormente delineados, então as jogadas poderão
favorecer ou contrariar as decisões de jogadas uns dos outros. Em relação aos jogos
em si, a escolha das jogadas deve ter em conta as possibilidades de jogadas dos
outros jogadores, e se necessário uma mudança de estratégia de acordo com o
estado do jogo. Para que um jogador consiga obter bons resultados é preciso
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
7
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
considerar todas as hipóteses de jogadas dos adversários e assim poderá fazer uma
avaliação minuciosa dessa informação e tomar decisões que favoreçam os seus
objectivos anteriormente delineados.
Para alguns jogos, a teoria pode indicar uma solução para o jogo, isto é, pode indicar
as melhores jogadas para cada jogador. No entanto, na maioria dos jogos que
descrevem problemas reais, a teoria apenas fornece uma visão geral da situação,
desprezando jogadas que não levarão a bons resultados.
Existem inúmeras situações que podem ser tratadas como jogos. John Von Newmann
desenvolveu esta teoria com o intuito de poder ser aplicada em muitas outras
situações e não apenas aos jogos. Qualquer situação onde existem interesses
competitivos, onde cada envolvente procura maximizar os seus ganhos e perdas dos
outros é considerado um problema de teoria dos jogos. Nesta descrição se encaixam
as tácticas de guerra, a política nacional e internacional, os problemas económicos,
problemas de competitividade comercial e até mesmo a evolução biológica, que tem
factores facilmente quantificáveis. De salientar que a teoria dos jogos não envolve a
componente humana e emocional que poderão afectar problemas reais tal como nos
conflitos militar.
Devido a natureza dos jogos, os jogadores ou participantes estão constantemente a
alterar as suas estratégias de jogo. Quando se toma uma decisão de efectuar uma
determinada jogada, pode-se calcular qual será a reacção dos adversários e preparar
uma jogada ou estratégia para contra-atacar os adversários.
Quanto mais
adversários existirem mais difícil será a tomada de decisões.
Ao contrário dos jogos, em ambientes reais onde existem factores humanos a ter em
conta, é muito mais difícil determinar qual a jogada que o adversário fará, uma vez
que os humanos são muito imprevisíveis devido a componente emocional que não
existe nos jogos. Isto acontece porque na maioria das vezes não estão dispostos a
acordo, ou então uma ou mais partes não segue o princípio acordado. Isto aplica-se
na maior parte das vezes em casos de conflito militar.
No que diz respeito aos jogos em si, existem jogos com dois ou mais jogadores,
cooperativos ou não. Entre os tipos de jogos possíveis estão os recreativos, tais
como póquer, monopólio e jogo do galo, os jogos de tabuleiro, como xadrez, damas,
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
8
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
nos quais se inclui o Dvonn, e os de problemas económicos, políticos e sociológicos.
Os jogos podem ser representados através de uma árvore ou através de matrizes de
payoff (utilidade, ganho).
De acordo com a referência [6] para que a teoria dos jogos possa ser usada em
diversas situações é preciso pressupor que:
™ Os jogadores sejam racionais e que pretendem vencer (ou maximizar seus
resultados) acima de tudo, e tenham a preocupação de adivinhar o próximo
passo do adversário;
™ Cada jogo possui um conjunto de regras próprias e pré-definidas;
™ Existe uma paridade de conhecimento e habilidade entre todos os jogadores;
™ Os jogos acontecem em ambientes abertos e integrados;
™ Deve existir uma interdependência entre os movimentos dos jogadores, em
que cada escolha sucessiva de um jogador incita o outro a alterar suas
escolhas subsequentes;
™ Recompensas que podem ter significados diferentes para cada jogador
dependendo de seus sistemas de valores.
2.1 -
Conceitos associados
Na teoria de jogos, a palavra jogo refere-se a um tipo especial de conflito no qual
tomam parte n indivíduos ou grupos (conhecidos como os jogadores). Há certas
regras do jogo, que dão as condições para que este comece e definem as jogadas
consideradas válidas durante as diferentes fases do jogo. É necessário considerar
também o tipo de informação que temos que poderá ser completa ou incompleta,
consoante as funções de payoff (tácticas e estratégias) dos jogadores são ou não de
conhecimento geral e também é preciso saber se a informação é perfeita ou
imperfeita. A informação é perfeita se em cada jogada, o jogador que vai jogar
sabe toda a história do jogo, caso contrário então a informação é imperfeita.
De acordo com o projecto em desenvolvimento, na implementação do agente para
jogar o Dvonn temos o terreno que no nosso caso é o tabuleiro, temos um jogador
que se encontra do outro lado do servidor e o agente inteligente. Temos as jogadas,
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
9
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
as regras do jogo que definem as jogadas válidas, as tácticas de jogo definidos como
payoff (que serão definidas a curto prazo, ou seja, beneficio da jogada no momento)
e as estratégias de jogo (definidas a longo prazo, ou seja, a avaliação do efeito de
uma jogada após o progresso do jogo a nível global).
Podemos definir esses elementos essenciais do seguinte modo:
Jogada – é a maneira segundo a qual o jogo progride de um estado para o outro.
Podem ser alternadas entre os jogadores de uma forma especificada ou ocorrer
simultaneamente. Existem jogos onde um jogador vai jogando um número
indeterminado de vezes seguido até chegar a uma situação em que é obrigado a
passar a jogada ao(s) adversário(s). Uma jogada então é a decisão de um dos
jogadores de concretizar um determinado objectivo de jogo mediante a avaliação dos
benefícios das várias hipóteses de jogo. Atenção que no caso do Dvonn um dos
jogadores pode jogar mais do que uma vez seguida, se o adversário não tiver
hipótese de realizar jogadas válidas, no caso de nenhum dos dois possuir jogadas
válidas o jogo termina. Tirando estas excepções as jogadas são efectuadas
alternadamente entre os jogadores.
Payoff – benefício de uma jogada. Esse benefício é o pagamento da jogada.
Dependendo do tipo de jogo, os valores de payoff terão uma interpretação diferente.
Pode tomar um valor negativo, nulo ou positivo. Se esse benefício for negativo
significa que se efectuarmos esta jogada teremos uma perda nesse valor. Nos jogos
de soma zero, essa perda será um ganho para o adversário desse valor.
No caso do Dvonn, foi definida no âmbito deste projecto uma fórmula que permite
atribuir um determinado peso a uma jogada. Este peso será calculado em função dos
ganhos e perdas não só do agente inteligente mas também do adversário, porque
para uma determinada jogada, tanto o jogador pode ganhar peças como também
poderá perder peças se a jogada provocar o isolamento de algumas peças (ficam
sem ligação a pelo menos um Dvonn). Essas peças isoladas tanto podem ser do
jogador como do adversário.
Estratégias – descrição das decisões a tomar em todas as situações possíveis.
Nesta fase, ao contrário do custo beneficio a curto prazo, faz-se uma avaliação a
longo prazo de uma determinada jogada sempre com o objectivo de ganhar o jogo.
Dependendo do tipo de jogo a analisar, o desenvolvimento das estratégias de jogo é
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
10
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
bastante difícil e complicado e exige bastante recurso de memória e do processador
uma vez que exige a criação de uma árvore ou um grafo com todas as jogadas
possíveis. Mais a frente falaremos melhor de alguns algoritmos de busca utilizados
na maior parte dos jogos de tabuleiro.
De uma forma matemática, temos associado a um jogo os seguintes elementos, o
conjunto dos jogadores que podemos representar por G = {g1, g2, g3, ..., gn}. Cada
jogador gi ∈ G possui um conjunto finito Si = {s1, s2, s3, ..., smi} de hipóteses de
jogada, que são denominadas de estratégias puras do jogador gi (mi ≥ 2 porque
logicamente o jogador tem que ter pelo menos duas opções de jogada). Após termos
as estratégias puras de cada jogador, então transforma-se estes conjuntos num só.
O novo conjunto será o S que é a combinação de todas as hipóteses de jogada dos n
jogadores, ou seja, isto é obtido através do produto cartesiano. Este conjunto
resultante é denominado espaço de estratégia pura do jogo [23].
S =
n
∏S
i
i =1
Também associado as jogadas de cada jogador podemos ter um peso que
identificará os ganhos das mesmas jogadas. Este peso é representado por ui.
µi : S → ℜ
S → µ i (S )
2.2 -
Tipo de jogos de estratégia
A teoria de jogos distingue vários tipos de jogos, de acordo com o número de
jogadores e com as circunstâncias do jogo. Existem diferentes tipos de jogos e estes
são caracterizados de acordo com o tipo de informação que os jogadores têm acesso,
e com as características dessa mesma informação.
Podemos distinguir vários tipos de jogos entre os quais destacam-se os seguintes:
™ Jogos de soma zero
™ Jogos de soma não zero
™ Jogos de informação completa
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
11
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
™ Jogos de informação incompleta
De entre estes serão descritos muito abreviadamente os jogos de soma zero e jogos
de soma não zero por serem os mais estudados.
2.2.1 -
Jogos de soma zero
Os jogos de soma zero são aqueles onde o ganho de um jogador é a perda do
adversário (considerando jogos de dois jogadores). Deste modo o jogo é de soma
zero porque o total dos ganhos no final da partida é nulo, isto é, o total de ganhos é
igual ao total de perdas. Os jogos de soma zero com dois jogadores são o principal
objecto de estudo da teoria matemática dos jogos.
Este tipo de jogo envolve um intenso esforço competitivo entre dois jogadores,
porque os jogadores ganham às custas um do outro. Desta maneira não existe
vantagem nenhuma na colaboração por parte dos jogadores. Não importa o que os
jogadores façam, o valor que um jogador ganha é sempre igual ao valor que o seu
adversário perde, de modo que o ganho total de ambos os jogadores é
necessariamente zero. De acordo com os conceitos associados à teoria dos jogos, e
com as características dos jogos de soma zero, pode-se definir a seguinte matriz de
payoff [9], se considerar que existem dois jogadores A e B com m e n estratégias
cada um respectivamente. Para o jogador A, o jogo poderá ser representado pela
matriz de payoff que se encontra a seguir. Esta representação indica que se A usa
uma estratégia i e B usa uma estratégia j, o payoff para A é pij e consequentemente
o payoff para B é -pij.
B1
B2
...
Bn
A1
P11
P12
...
P1m
A2
P21
P22
...
P2m
...
:
:
:
:
Am
Pm1
Pm2
...
Pmn
Após a definição da matriz de payoff, os jogadores terão que analisar o jogo e definir
a melhor estratégia. As referências [9] e [13] demonstram a utilização do algoritmo
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
12
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
MiniMax neste tipo de jogos. Este algoritmo que será descrito pormenorizadamente
no capítulo 4 corresponde ao seguinte: o adversário tenta minimizar o Máximo que o
outro jogador poderá ganhar. E este por sua vez tenta maximizar o mínimo possível
de ganho. Considere um exemplo de concorrência no mercado de venda de marcas
de vacina para gripe, onde temos as companhias A e B.
A companhia A pode anunciar o seu produto na rádio (estratégia A1), na televisão
(estratégia A2) ou no jornal (estratégia A3). A companhia B pode anunciar o seu
produto na rádio (estratégia B1), na televisão (estratégia B2), no jornal (estratégia
B3) ou mala directa (estratégia B4). Dependendo da criatividade e da intensidade
dos anúncios, cada companhia pode ganhar uma porção do mercado da outra
companhia. A matriz de payoff a seguir resume a percentagem de mercado ganho ou
perdido pela companhia A.
B1
B2
B3
B4
A1
8
-2
9
-3
A2
6
5
6
8
A3
-2
4
-9
5
Para a companhia A, o critério de escolha das estratégias é considerar o “Melhor
resultado entre os piores” que a companhia pode obter. Assim, para a estratégia A1
o pior resultado que a companhia A poderá obter é –3 se a companhia B escolher a
estratégia B4. Para a estratégia A2 o pior resultado possível é 5, e para A3 o pior
resultado é –9. Avaliando então estes resultados, o melhor dos piores resultados é a
companhia A optar-se pela estratégia A2. No entanto, para a companhia B, o critério
de escolha já é diferente, ou seja, pretende-se o “Pior resultado entre os melhores”
que a concorrência poderá ter. Então, a melhor escolha para a companhia B seria o
pior resultado que a companhia A poderá obter se aplicar a estratégia A2. A solução
óptima para o jogo é A2 – B2, ambas as companhias devem anunciar os seus
produtos na televisão.
O payoff será a favor da companhia A, porque seu mercado ganhará 5% do mercado
de B. Quando os valores “Melhor resultado entre os piores” e “Pior resultado entre os
melhores” forem iguais diz-se que existe um ponto de equilíbrio. Neste caso como
esses valores são iguais a 5 diz-se que o valor do jogo é 5.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
13
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
A solução de equilíbrio garante que nenhuma companhia tentará seleccionar uma
estratégia melhor porque poderá acontecer o que em vez de ganhar perca. Se B
escolher outra estratégia (B1, B3 ou B4), a companhia A pode ficar com a estratégia
A2, que garante que B perderá mais mercado para A (6% ou 8%). Da mesma
maneira, A não quer usar uma estratégia diferente (A1 ou A3) porque se escolher
A3, B poderá escolher B3 e ganhar 9% do mercado de A. Também se A escolher a
estratégia A1, B poderá escolher B3 e então ganha 9% do mercado de A.
Para o caso de os valores “Melhor resultado entre os piores” e “Pior resultado entre
os melhores” não serem iguais John Von Newmann sugeriu a utilização de
estratégias mistas. Nesta situação não é vantajoso para nenhum dos jogadores usar
as mesmas estratégias a cada novo jogo.
Cada vez que um novo jogo começa, os jogadores escolhem aleatoriamente qual
estratégia adoptar. Deve-se observar que o uso deste tipo de estratégia exige que o
jogo seja jogado repetidas vezes.
2.2.2 -
Jogos de soma não zero
Os jogos de soma não zero se diferenciam dos de soma zero pelo facto de que neste
tipo de jogos os jogadores não são completamente opostos uns aos outros, ou seja,
a relação de ganho e perda que existe nos jogos de soma zero não se aplica para
todos os resultados para este tipo de jogos. Ao contrário dos jogos de soma zero, os
jogos de soma não zero se baseiam apenas no princípio “Melhor resultado entre os
piores”. Isto quer dizer que tanto um jogador como o outro pretendem sempre
melhorar os seus ganhos, ou seja, ambos os jogadores optam por estratégias que
maximizam seus payoffs mínimos. O que B ganha não é necessariamente igual ao
que A perde.
Então, a grande diferença entre os jogos de soma zero e os de soma não zero é que
neste último não há um conceito óbvio de solução do jogo, como o que foi descrito
para os de soma zero.
Enquanto que para estes últimos a solução é garantida pelo Teorema MiniMax, para
os jogos de soma não zero, John Nash provou, em 1951, uma generalização desse
teorema, utilizando o conceito de pares de equilíbrio. De notar que a teoria de
equilíbrio de Nash que será desenvolvida mais pormenorizadamente na secção
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
14
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
2.3, não se restringe aos jogos de soma não zero, na realidade pode-se constatar
que também se aplica aos jogos de soma zero, por verificar que neste caso esta
teoria é equivalente ao teorema MiniMax.
Concluindo o raciocínio, apesar de a teoria do equilíbrio garantir que existe sempre
pelo menos um par de equilíbrio no jogo, ele não diz como encontrá-lo. Assim
torna-se difícil construir algoritmos para determinar todos os pares de equilíbrio de
um jogo de soma não zero com dois jogadores. [15]
2.3 -
Equilíbrio de Nash
Partindo do pressuposto de que cada jogador desenvolve sempre a melhor estratégia
para fazer face as estratégias dos seus adversários, pode-se definir o equilíbrio de
Nash da seguinte forma:
Para um jogo com dois Jogadores (A e B), um par de estratégias (a*, b*) representa
uma solução de equilíbrio, se a* for uma estratégia óptima para o Jogador A
enfrentar a estratégia b*, e se simultaneamente b* for a estratégia óptima para o
Jogador B enfrentar a estratégia a*.
Para demonstrar este teorema de Nash considere o exemplo mais conhecido da
teoria dos jogos, o dilema dos prisioneiros. Este foi formulado por Albert W. Tucker
em 1950 num seminário para psicólogos na Universidade de Stanford, para ilustrar a
dificuldade de se analisar certos tipos de jogos.
A situação é a seguinte: dois ladrões Al e Bob são capturados e acusados cada um
individualmente do mesmo crime. São presos em celas separadas e sem poderem se
comunicar entre si e são confrontados com a seguinte proposta do chefe da polícia:
cada um pode escolher entre confessar ou negar o crime. Se nenhum deles
confessar, ambos serão submetidos a uma pena de 1 ano. Se os dois confessarem o
crime, então ambos serão condenadas a cumprir uma pena de 5 anos. Mas se um
dos ladrões confessar e o outro negar, então o ladrão que confessou é liberto e o
outro é condenado a dez anos de prisão.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
15
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
Esquematizando o problema usando estratégias puras temos:
G = {Al, Bob}
SAl = {confessar, negar}
SBob = {confessar, negar}
S = {(confessar, confessar), (confessar, negar), (negar, confessar), (negar, negar)}
As combinações possíveis que podemos ter são:
Para AL
uAl(confessar, confessar) = −5, uAl(confessar, negar) = 0,
uAl(negar, confessar) = −10, uAl(negar, negar) = −1,
Para BOB
uBob(confessar, confessar) = −5, uBob(confessar, negar) = 0,
uBob(negar, confessar) = −10, uBob(negar, negar) = −1
De acordo com as combinações estabelecidas para cada ladrão e respectiva pena que
terão de cumprir mediante as suas escolhas, define-se a seguinte matriz de payoff.
Bob
Al
confessar
Negar
confessar
(-5,-5)
(0,-10)
negar
(-10,0)
(-1,-1)
Assim sendo, qual é a melhor estratégia a escolher por cada ladrão?
Considerando que cada uma dos ladrões pretende minimizar a sua pena, então para
encontrar uma solução favorável para os ladrões, pode-se fazer uma previsão das
consequências de cada escolha dos ladrões. Para isso, analise primeiramente a
situação de Al.
Podemos raciocinar da seguinte forma:
Duas coisas podem acontecer: Bob pode confessar ou pode negar. Se Bob confessar,
então é melhor para AL confessar. Se Bob não confessar, então AL fica livre se
confessar. Em qualquer dos casos, é melhor para AL confessar. Então, a melhor
estratégia é confessar.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
16
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
Pode-se também aplicar o mesmo raciocínio para Bob e chegar a conclusão que a
melhor estratégia para os dois ladrões é ambos confessarem o crime e cumprirem a
pena de 5 anos cada.
Existem vários conceitos para encontrar uma solução de equilíbrio para este tipo de
problemas mas neste relatório só iremos referir ao conceito de Nash.
O conceito de Nash define uma solução estratégica ou equilíbrio de Nash de um jogo
como um ponto onde cada jogador não tem incentivo para mudar a sua estratégia se
os demais jogadores não o fizerem. Ou seja, se um dos participantes mudar a
estratégia poderá piorar a sua situação porque o outro poderá mudar a sua
estratégia e vencer.
Considerando o dilema de prisioneiros, o perfil de estratégia (confessar, confessar) é
a única combinação que podemos considerar como equilíbrio de Nash porque é a
única estratégia boa para os dois ladrões. Os dois cumprirão uma pena de 5 anos,
caso contrário um dos dois poderia sair em desvantagem em relação ao outro.
Considere o exemplo da Batalha dos sexos onde existem mais do que uma solução
de equilíbrio.
Problema: Um homem e a sua mulher desejam sair para passear. O homem prefere
assistir a um jogo de futebol enquanto que sua mulher prefere ir ao cinema. Se eles
forem juntos ver o futebol, então o homem tem satisfação maior do que a mulher.
Por outro lado, se eles forem juntos ao cinema, então a mulher tem satisfação maior
do que o homem. Finalmente, se eles saírem sozinhos, então ambos ficam
igualmente insatisfeitos.
G = {Homem, Mulher}
SHomen = {Futebol, Cinema}
SMulher = {Futebol, Cinema}
S = {(Futebol, Futebol), (Futebol, Cinema), (Cinema, Futebol), (Cinema, Cinema)}
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
17
Instituto Superior de Engenharia do Porto
Capítulo 2 – Teoria dos Jogos
Considere para a satisfação máxima o valor 10 e insatisfação o valor 0. Define-se a
seguinte matriz de payoff:
Mulher
Homem
futebol
cinema
futebol
(10,5)
(0,0)
cinema
(0,0)
(5,10)
Neste caso, pode-se verificar que existem duas estratégias de equilíbrio (Futebol,
Futebol) e (Cinema, Cinema) porque para as outras duas estratégias tanto o homem
como a mulher ficam insatisfeitos. Portanto a melhor escolha poderá ser uma das
duas estratégias de equilíbrio. Ainda existem casos em que não é possível chegar a
um ponto de equilíbrio usando estratégias puras. Isto acontece quando todas as
estratégias possíveis apresentam valores parecidos ou idênticos. Neste caso há um
conflito que impossibilita a escolha de uma estratégia.
Para resolver este tipo de problemas Nash propôs a utilização de estratégias mistas
onde se recorre ao uso de distribuições de probabilidade.
Sobre cada estratégia pura definida é atribuída uma medida de probabilidade. Essa
medida de probabilidade varia de 0 a 1, sendo que a soma das probabilidades de
todas as estratégias possíveis para o mesmo jogador é 1.
A referência [23] especifica mais pormenorizadamente fórmulas que permitem
chegar a soluções usando o teorema de Nash para estratégias mistas.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
18
Capítulo 3
Técnicas de busca para exploração de árvores de
decisão
Os jogos de computador têm cativado há muito tempo o interesse da comunidade de
sistemas inteligentes, especialmente os jogos tradicionais, como xadrez e damas.
Depois da vitória do computador Deeper Blue sobre Kasparov, tanto a comunidade
científica como o público perceberam a relevância do uso de IA em jogos de
computador. Esta vitória não se deve apenas as inovações no campo de sistemas
inteligentes (SI), mas principalmente aos avanços de hardware. Estes avanços
tecnológicos permitiram aos computadores usar de “força bruta” para ganhar os
opositores humanos.
Por outro lado, os jogos modernos de computador se apresentam como uma nova
plataforma desafiadora para testes de técnicas mais avançadas de sistemas
inteligentes, provendo ambientes altamente dinâmicos e complexos, com múltiplos
objectivos e decisões a serem tomadas em tempo real, sendo assim muito diferentes
dos jogos tradicionais. Para estes tipos de jogos são necessárias outras técnicas de
SI mais apropriadas, como a inteligência computacional e a inteligência artificial
distribuída. [16]
Apesar de se conseguir atingir grandes resultados através do uso da IA, quando se
pretende construir um determinado sistema depara-se com vários problemas
tipicamente relacionados com a IA. A referência [1] dá alguns exemplos das técnicas
que a IA oferece para resolver tais problemas. A mesma referência define três
passos principais que são necessários para resolver um problema em particular que
de seguida serão destacados:
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
19
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
™ Definir o problema com precisão. Esta definição deverá incluir especificações
precisas do que será a situação inicial, bem como que situações finais
constituem soluções aceitáveis para o problema.
™ Analisar o problema. Alguns recursos muito importantes podem ter um forte
impacto sobre a adequação de várias técnicas possíveis para resolver o
problema.
™ Escolher a melhor técnica e aplicá-la ao problema em particular.
Muitos dos problemas que se enquadram dentro do âmbito da inteligência artificial
são demasiadamente complexos para serem resolvidos por técnicas directas. No
entanto, para a resolução de tais problemas deverão ser usados métodos
apropriados, com o auxílio de qualquer técnica directa disponível de busca. Além
disso, as capacidades da máquina a usar condicionam decisivamente a resolução do
problema. Para jogos simples talvez não seja relevante, mas para jogos mais
complexos já teriam algumas complicações. Por exemplo, considere o exemplo do
xadrez:
™ O factor de ramificação médio está ao redor de 35. Isto significa que o
número de jogadas em média para um determinado estado do tabuleiro é 35.
™ No jogo em média cada jogador poderá efectuar 50 movimentos, ou seja,
cada jogador faz em média 50 jogadas durante o jogo todo.
™ Assim, para examinar a árvore completa do jogo, teria que examinar 35100
posições. Este número corresponde a analisar 35 jogadas possíveis para cada
2 jogadores. Sendo que cada jogador faz em média 50 movimentos logo o
total serão 100 jogadas. E assim a árvore terá 35100 nós.
Desta forma consegue-se perceber que um programa que pretenda tirar conclusões
através de uma árvore não poderá fazer simplesmente uma busca directa da árvore
de jogo. A busca na árvore seria praticamente impossível de ser feita e o programa
não conseguiria tomar decisões. Deste modo será necessária a utilização de algum
tipo de procedimento de busca heurística.
Uma heurística é uma técnica auxiliar na descoberta de soluções de problemas,
apesar de que não dá nenhuma garantia de que ela nos guiará sempre na direcção
certa [1]. Existem técnicas heurísticas de aplicabilidade muito geral e outras que
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
20
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
representam conhecimentos específicos, relevantes para a solução de um problema
em particular.
Segundo a referência [1] existem duas formas principais em que a informação
heurística específica pode ser incorporada dentro de um procedimento de busca
baseado em regras:
™ Nas próprias regras, por exemplo, as regras para um sistema de jogo de
xadrez poderiam descrever não só o conjunto de movimentos válidos, mas
também desse conjunto quais os movimentos mais apropriados.
™ Pode-se ter também uma função heurística que avalia todos os estados do
problema individualmente e determina um peso, que representará se o
estado é favorável ou não. Este peso normalmente é definido em números,
podendo ser negativo, positivo ou nulo.
Tendo estas ajudas torna-se mais fácil num processo de busca num nó, dado a
estimativa feita pela função heurística, consegue-se saber se o nó está no melhor
caminho para a solução.
Neste sentido torna-se claro a importância que é pensar bem no problema a
resolver, descrever de forma pormenorizada o problema e assim estudar a situação
de modo a definir heurísticas simples capazes de fornecer estimativas boas. É
importante a confiança que se tem nas heurísticas porque serão elas a nos dar as
orientações no processo de busca de soluções. É através dos valores fornecidos pelas
heurísticas que se sabe se um determinado caminho é bom ou não.
Em outras situações, devem ser utilizadas funções heurísticas mais complexas.
A finalidade de uma função heurística é orientar o processo de busca na direcção
mais lucrativa, sugerindo qual o caminho seguir quando existem mais do que um
caminho disponível. Quanto mais precisas e concretas forem as estimativas da
função heurística de cada nó na árvore ou grafo de busca, tanto mais directo será
encontrar a solução. Assim quanto mais boa for a função tanto menos busca será
preciso efectuar para se chegar a solução. E assim o sistema de uma forma directa
encontra uma solução. No entanto, para muitos programas, o custo de calcular o
valor de tal função seria maior que o despendido no processo de busca. Em geral, há
um ajuste entre o custo de avaliar uma função heurística e a economia de tempo de
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
21
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
busca que a função fornece. A seguir iremos descrever de uma forma resumida
algumas técnicas de busca tradicionais.
3.1 -
Estratégias de Busca Tradicionais
De forma genérica, as estratégias de busca tradicionais envolvem busca em árvores
que descrevem todos os estados possíveis do jogo a partir do estado inicial.
Formalmente, o espaço de busca é constituído por nós n, ligados através de arcos
(ligação entre dois nós). Cada arco pode ter ou não associado um valor, que
corresponde ao custo c de transição de um nó para outro. Cada nó tem associado
uma profundidade p, sendo que a mesma tem valor 0 se for o nó raiz e um valor
diferente de zero que corresponde ao número de nós percorrida da raiz até ao nó.
A aridade a de um nó é a quantidade de filhos que o nó possui, e a aridade de uma
árvore é a maior aridade de qualquer um de seus nós. O objectivo da busca é assim
encontrar um caminho (óptimo ou não) do estado inicial até a um estado final,
explorando sucessivamente os nós ligados aos nós já explorados até a obtenção de
uma solução para o problema. As técnicas mais comuns são:
™ Busca em largura
™ Busca em profundidade
™ Busca bidirecional
™ Busca por custo uniforme
™ Busca heurística
De notar que as estratégias de busca tradicionais são amplamente utilizadas em
jogos tradicionais (xadrez e damas), especialmente porque nos mesmos o ambiente
é determinístico e não dinâmico. [16]
3.1.1 -
Busca por largura
Esta técnica de busca consiste em efectuar a busca inicialmente no nó raiz, e depois
explorar todos os nós filhos do mesmo, e em seguida todos os filhos dos filhos, e
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
22
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
assim sucessivamente (Figura 1). Desta forma todos os nós de profundidade n são
percorridos antes que os nós de profundidade n+1 sejam percorridos.
Vantagens
O algoritmo garante encontrar a solução mais "rasa" (se existir), e a solução óptima
se o custo de um caminho for crescente e dependa apenas da profundidade do nó.
Uma das grandes vantagens desta busca é que está não cairá na armadilha de
explorar um beco sem saída.
Desvantagens
No entanto, apesar das vantagens apresentadas, a busca em largura apresenta um
grande problema: todos os nós explorados devem ser armazenados para futura
expansão, o que pode ser extremamente custoso em termos de memória,
especialmente para problemas de elevada aridade. Além disso, o tempo de execução
também é relativamente alto: para uma árvore de aridade a, e a profundidade da
solução possua um valor d, o algoritmo possui complexidade de O(ad), ou seja, é
exponencial com relação à profundidade da solução. [16]
Figura 1 - Busca em largura
Algoritmo recursivo: Busca em Largura ([17])
1. Crie uma variável Lista-de-nós e ajuste-a para o estado inicial.
2. Até ser encontrado um estado meta ou Lista-de-nós ficar vazia, faça o
seguinte:
(a) Remova o primeiro elemento da Lista-de-nós e chame-o de E. Se
Lista-de-nós estiver vazia, termina.
(b) Para cada maneira como cada regra pode ser casada com o estado
descrito em E, faça o seguinte:
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
23
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
i.
Aplique a regra para gerar um novo estado.
ii.
Se o novo estado for um estado meta, saia e retorne este estado.
iii.
Caso contrário, acrescente o novo estado ao final da Lista-de-nós.
3.1.2 -
Busca em profundidade
No processo de busca em profundidade é analisado sempre o nó com maior
profundidade, ou seja, explora-se o caminho para o objectivo, dando preferência aos
nós mais distantes da raiz.
Esta estratégia garante que uma solução será encontrada, mas não garante a
solução óptima. Em termos de complexidade é a mesma da busca em largura O(ad),
onde a é a aridade e d é a profundidade máxima das soluções.
Vantagens
Em termos de requisitos de memória, esta estratégia de busca consome menos
memória do que a busca em largura, pois só é preciso armazenar o caminho
corrente. Na prática, para problemas com muitas soluções a busca em profundidade
tende a ser mais rápida que a busca em largura.
Desvantagens
Para problemas com muitas soluções a busca pode ficar presa em ramos que não
contenham a solução, o que pode se tornar ainda pior se a árvore tiver profundidade
infinita. Para resolver este problema, para árvores muito profundas, ou ainda árvores
de profundidade infinita, o que se faz é limitar a profundidade de busca, de forma a
permitir que toda a árvore até a profundidade escolhida seja explorada.
Entretanto, surge outro problema que é escolher a profundidade adequada para se
encontrar uma solução. Este problema pode ser melhorado permitindo que a
profundidade limite aumente iterativamente. Entretanto surge a necessidade de se
definir de forma adequada o grau de aumento do limite de profundidade, valor este
que dependente dos recursos computacionais disponíveis e do problema específico a
ser analisado [16].
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
24
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
Figura 2 – Busca em profundidade
Algoritmo recursivo: Busca em profundidade ([17])
1. Se o estado inicial é um estado de meta, sair e retornar sucesso.
2. Caso contrário, faça o seguinte até a sinalização de sucesso ou fracasso:
(a) Gere um sucessor, E, do estado inicial. Se não houver mais
sucessores, sinalize fracasso.
(b) Chame Busca em Profundidade com E como estado inicial.
(c) Se for retornado sucesso, sinalize sucesso. Caso contrário, continue
em ciclo explorando outros sucessores.
3.1.3 -
Busca bidirecional
Na busca bidirecional a busca é realizada de forma concorrente uma a partir do
estado inicial e outra do estado solução. Para cada uma das buscas a ser realizada,
pode-se adoptar uma estratégia diferente. É interessante notar que é preciso obter
operadores que realizem tanto o percurso de ida (à partir do estado inicial) quanto
de volta (partindo do(s) estado(s) final(is)). Além disso, deve ser possível verificar
rapidamente se um estado já foi analisado, para saber se já foi encontrada ou não
solução foi encontrada. Esta forma de busca requer que sejam conhecidos de
antemão os estados solução, informação que em alguns casos pode não estar
disponível [16].
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
25
Instituto Superior de Engenharia do Porto
3.1.4 -
Capítulo 3 – Sistemas Inteligentes em Jogos
Busca de custo uniforme
Na busca de custo uniforme cada arco possui um custo dado por uma função g(n), e
é escolhido sempre o nó de menor custo total acumulado até o momento para ser
explorado. Assim, a busca de custo uniforme é similar à busca em largura, com
profundidade igual ao último custo total calculado.
A busca de custo uniforme também garante que uma solução seja encontrada, e
ainda
garante
que
esta
solução
será
óptima,
caso
um
caminho
seja
monotonicamente crescente. Entretanto, a busca de custo uniforme continua a
apresentar os mesmos problemas que a busca em largura em relação ao seu custo
computacional.
3.1.5 -
Busca heurística
Na busca heurística procura-se associar a cada arco (ligação entre dois nós) um
custo determinado por uma função heurística, que determina a distância do nó até
uma solução. A estratégia mais simples baseada em heurística consiste em realizar
uma busca egoísta, na qual segue-se sempre o nó (obtido através da função
heurística h(n)) que se julga mais próximo do objectivo.
No entanto, tal estratégia não garante nem a solução óptima nem garante que seja
encontrada uma solução.
Para melhorar a busca egoísta descrita acima pode-se aliar a esta busca à busca por
custo uniforme, que apesar de ser ineficiente, garante resultados óptimos. O
algoritmo A* [1] é o resultado dessa união, sendo razoavelmente eficiente, e
garantindo resultados óptimos para funções h(n) adequadas.
A estratégia A* trabalha de forma similar à busca de custo uniforme, com a diferença
que a função para determinação do próximo nó a ser explorado é dada por:
onde g(n) é o custo total do estado inicial ao estado corrente, e h(n) é o custo
estimado até um estado final escolhido. A função f(n) representa o custo estimado
da solução de menor custo do estado inicial até a solução (nó final), passando pelo
nó n.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
26
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
Como referido acima, o algoritmo A* garante a obtenção de uma solução óptima.
Além disso, o algoritmo é optimamente eficiente, isto é, nenhum outro algoritmo que
obtenha uma solução óptima garantidamente explora menos nós que o A*.
Apesar disso o A* possui algumas limitações, a sua complexidade é exponencial, e o
algoritmo pode consumir rapidamente grandes volumes de armazenamento uma vez
que precisa guardar todos os nós explorados.
Para atenuar este problema foi criado o Iterative Deepening A* (IDA*) – A* iterativo
com níveis de corte – que usa o algoritmo A* até um valor fixo de f(n), valor este
que aumenta iterativamente. Este algoritmo é usado para evitar a exploração de
caminhos que podem vir a contribuir apenas para tornar a pesquisa mais demorada.
Assim, para o IDA* define-se um patamar de custo, ou seja, só se aceita uma
solução com um custo inferior ou igual ao desse patamar. Sempre que a soma g + h
for superior ao patamar, então rejeita-se esse caminho. Se no final não houver
solução então aumenta-se o valor do patamar.
O processo repete-se até que seja encontrada uma solução. Deste modo as
preocupações na criação do IDA* foram no sentido de poupar memória durante a
pesquisa. O IDA* não garante que se possa voltar a qualquer nó que ficou para trás
e há problemas que este não consegue resolver.
Neste seguimento, surge outro algoritmo que procura corrigir alguns problemas
presentes com o IDA*. Este é o Simplified memory-bounded A* (SMA*). Necessita
de mais memória que o IDA*, mas usa menos memória que o A* puro.
Resumidamente o IDA* pode ser óptimo, completo e optimamente eficiente, dados
certos requisitos de memória.
De notar ainda que o A* e suas variantes constituem actualmente os algoritmos mais
utilizado nos jogos para resolver problemas de determinação de caminho em
ambientes bidimensional e tridimensional. [16]
3.2 -
Análise de algoritmos de busca
As perguntas que poderão ser levantadas, nesta altura quanto as técnicas de busca
anteriormente referidas são: Será que são boas e eficientes? Será que as soluções
fornecidas são óptimas? Tradicionalmente, o que se faz é codificar os algoritmos,
processá-los no computador e observar o seu comportamento em alguns problemas
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
27
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
e assim verificar o seu desempenho. Isto contrasta com algumas outras áreas da
ciência da computação, onde se dá maior ênfase a análise matemática dos
algoritmos. Em outros casos faz-se uma análise estatística do desempenho do
algoritmo após terem sido efectuados testes tendo em conta um conjunto de
problemas cuidadosamente escolhidos. Os especialistas dão duas razões para o
processo de análise dos algoritmos serem feitos desta maneira:
™ É mais estimulante ver o funcionamento do programa e assim visualizar o seu
desempenho na prática do que provar teoricamente que o programa tem
capacidades para fazer algo.
™ Os domínios de problemas da IA são suficientemente complexos para impedir
que se produza uma prova analítica convincente de que um procedimento
funcionará. Muitas vezes nem é possível descrever a gama de problemas de
modo a tornar significativas as análises estatísticas do comportamento do
programa.
Segundo a referência [1] esta segunda razão é de extrema importância. Devido a
complexidade das estruturas usadas para o conhecimento a maior parte dos
programas de IA torna-se praticamente impossível a análise matemática dos
programas dos programas.
A referência também salienta a importância de se ter como prioridade principal
manter as questões de desempenho sempre em primeiro lugar ao se pensar em
projectar aplicações que utiliza algoritmos e técnicas de busca. Deve-se ter em
mente sempre estas questões mesmo que não seja possível cumpri-las com
exactidão.
Uma das análises mais importantes, embora desmoralizante, do processo de busca é
o facto de o número de nós numa árvore de busca completa, de profundidade D e de
ramificação F ser FD. Esta análise leva a dois pontos importantes:
™ Necessidade de aperfeiçoar o procedimento de busca exaustiva, pois um
processo
cujo
tempo
de
busca
cresce
exponencialmente
não
é
computacionalmente viável.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
28
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
™ Necessidade de estabelecer um limite superior para o tempo de busca que
será gasto, de modo a que seja possível comparar melhoramentos propostos
num procedimento de busca exaustiva.
Existem várias maneiras de proceder que são melhores do que uma busca exaustiva.
Elas podem ser divididas em três classes, de acordo com os principais problemas
colocados por cada uma delas.
™ Métodos gerais que tenham a garantia de encontrar uma resposta tão boa
como a que seria encontrada pela busca exaustiva, mas em menos tempo.
Qual o método mais rápido que se pode encontrar nesta área?
™ Métodos que poderão levar tanto tempo quanto a busca exaustiva nalguns
problemas, mas que operam bem mais rápido para a maior parte dos
problemas mais comuns. Que velocidade esperar para que tais métodos
processem um conjunto de problemas?
™ Métodos que poderão encontrar uma solução pior do que a que seria
encontrada pela busca exaustiva. Para obter essa resposta dentro de algum
tempo desejado, quanta discrepância poderá haver entre a solução que se
encontrou e a melhor solução? [1]
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
29
Instituto Superior de Engenharia do Porto
Capítulo 3 – Sistemas Inteligentes em Jogos
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
30
Capítulo 4
O Algoritmo MiniMax e alguns refinamentos
Este capítulo descreve o algoritmo MiniMax, um dos algoritmos mais utilizados em
jogos de tabuleiro (xadrez e damas) e também algumas variantes do mesmo
algoritmo. Este algoritmo se baseia na busca de uma solução numa árvore de
jogadas possíveis, sendo que a profundidade da árvore poderá ser elevada ou não de
acordo com as possibilidades de jogo. A aridade dos nós poderá ser variável de
acordo com as possibilidades de jogada numa determinada posição. Além da
descrição dos algoritmos iremos fazer uma análise do desempenho do mesmo
algoritmo, requisitos de memória e computacionais que exige, algumas vantagens e
desvantagens. Por fim faremos uma avaliação deste algoritmo, com respeito a
implementação do agente inteligente que terá que ser desenvolvido neste projecto.
4.1 -
Descrição do algoritmo MiniMax
Este algoritmo é muito usado em teoria dos jogos, apesar de poder ser usado em
muitas outras situações onde se pode supor a existência de um jogador e um ou
mais adversários. Este é muito usado quando se pretende tomar decisões sobre que
estratégias e tácticas usar para se defender de ataques dos inimigos ou
concorrentes.
O MiniMax [1] é um procedimento de pesquisa em profundidade limitada. A busca é
feita numa árvore de movimentos possíveis, onde supomos que em níveis alternados
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
31
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
tentaremos maximizar a probabilidade de vencer, enquanto o adversário tentará
minimizar a probabilidade de ganharmos o jogo.
Este algoritmo parte do principio de que o jogador efectua sempre a jogada que
maximiza o seu próprio ganho enquanto que o adversário jogará sempre a jogada
que minimiza o ganho do outro.
O acto de jogar pode ser visto como sendo o desenvolvimento de uma árvore onde
os nós representam estados do jogo e os ramos representam jogadas possíveis. Os
ramos poderão ter associado um peso que ajudará na escolha de qual a melhor
jogada a efectuar em determinado instante. A figura 3 mostra de uma forma clara a
ideia do procedimento.
Os níveis onde há uma maximização dos pesos dos nós filhos correspondem as
nossas jogadas e os níveis onde há uma minimização correspondem as jogadas do
adversário. De acordo com o peso1 dos nós, que corresponde ao valor de uma
determinada jogada, decide-se qual a melhor sequência de jogadas que deve ser
efectuado para obter vantagens sobre o adversário.
O procedimento MiniMax consiste no seguinte:
Partindo da posição actual (neste caso a raiz da árvore), usa-se um gerador de
movimentos que produz o conjunto de posições sucessoras possíveis. Poderia se
aplicar uma função de avaliação estática a cada posição e escolher a posição que
apresenta a melhor avaliação. Retorna-se esse valor de avaliação a posição inicial de
busca como forma de representar a avaliação feita do nó.
A posição actual é tão importante quanto a posição gerada como melhor movimento
a executar a seguir. Assume-se que a função de avaliação estática retorna valores
altos para indicar situações favoráveis, assim a meta a atingir será maximizar o valor
da função de avaliação estática na próxima posição do tabuleiro.
1
Valor calculado sempre com relação ao jogador em questão.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
32
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
Figura 3 - Método MiniMax
Uma vez que a função de avaliação estática não é totalmente precisa por ser uma
avaliação feita apenas a um nível de profundidade. Esta avaliação apenas uma
jogada a frente não dá garantias de que a meta estipulada que é ganhar o jogo será
atingida. Desta forma a busca deveria continuar para além de uma jogada e poder
obter resultados mais satisfatórios. Isto pode ser muito importante, por exemplo, em
jogos de tabuleiro tais como o xadrez, as damas, e também no caso do Dvonn.
Falando directamente do Dvonn consideremos o que acontece numa jogada.
Após o movimento de uma peça, a situação poderá parecer favorável, mas se
analisar um movimento a frente, vê-se que a escolha não foi realmente boa porque
se calhar já não existem hipóteses de jogadas válidas ou a jogada que o adversário
possa fazer faça com que se perca o jogo. Portanto a situação não era tão favorável
quanto parecia. Assim é útil e prudente olhar e analisar o que acontecerá com cada
uma das novas posições no movimento a ser feito a seguir pelo adversário. Desta
maneira teoricamente quando maior for a profundidade de visualização melhor serão
as hipóteses de ter sucesso na escolha das jogadas. Como refere a referência, a
avaliação dos nós apenas usando os valores da função estática (de forma directa)
deixa de fazer sentido. Será preciso a partir daqui explorar as ramificações dos nós.
Isso é possível por usar um gerador que vai gerando um conjunto de nós sucessores
de um nó inicial até uma profundidade predefinida. Depois de atingir essa
profundidade então aplica-se a função de avaliação estática para se saber qual o
estado do jogador nesse estado do tabuleiro [17].
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
33
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
Figura 4 – Busca numa árvore uma e duas posições a frente [1]
Na figura 4 pode-se ver melhor qual a diferença entre avaliar uma jogada um nível a
frente (alínea a da figura) e dois níveis a frente (alínea b da figura).
Pode-se ver na alínea b que a tomada de decisão na escolha da jogada é feita tendo
em conta a jogada que o adversário poderá efectuar a seguir a nossa. Em cada nó
temos um peso que nos ajudará a tomar decisões de qual a melhor jogada.
Suponha que se jogue o movimento B. Então o adversário terá que escolher entre os
movimentos E, F e G. O objectivo do adversário é minimizar o valor da função de
avaliação, assim é de esperar que escolha o movimento F. De acordo com os valores
apresentados na Figura 4b, se efectuarmos o movimento B, então após a jogada do
adversário (F), estaremos numa posição muito desfavorável. Apesar da posição E a
primeira vista representar um valor bom para nós, contudo será ruim para nós após
a jogada do adversário.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
34
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
Como se pode ver na Figura 4c, em resultado de uma análise dois níveis a frente,
passam a existir novos valores para A, B, C e D. Estes valores foram escolhidos
tendo em conta que o jogador maximiza os seus ganhos e o adversário minimiza o
ganho do jogador.
Portanto, uma vez retornados os valores da segunda jogada, fica claro que o
movimento correcto nesse primeiro nível, dadas as informações que se tem
disponíveis, é C, já que não há nada que o adversário possa fazer para produzir um
valor pior que -2.
Tendo em conta o exemplo apresentado na figura 4 vê-se que quanto maior for a
nossa capacidade de visão no jogo (ter uma visão dos ganhos e perdas uma, duas ou
n jogadas a frente), maior será a probabilidade de vencer o jogo, por escolher
jogadas que trarão benefícios a longo prazo. Contudo, este processo de escolha da
melhor jogada através de uma árvore precisa de algumas restrições. Até que
profundidade deve ser efectuada a busca, ou durante quanto tempo deve-se
continuar a busca para encontrar uma jogada boa?
De seguida será descrito de uma forma mais precisa os pontos essenciais a ter em
conta neste algoritmo.
A Referência [17] propõe um algoritmo genérico que é um procedimento recursivo
directo, e que toma por base dois procedimentos auxiliares, especifico do jogo que
está sendo jogado:
1. GERMOV(Posição, Jogador) – o gerador de movimentos que retorna uma lista
de nós que representam os movimentos que podem ser feitos por Jogador em
Posição. No caso do jogo Dvonn chama-se os jogadores pelo nome de WHITE
(w) e BLACK (b).
2. ESTÁTICA(Posição, Jogador) – a função de avaliação estática, que retorna um
número que representa a qualidade de posição do ponto de vista de Jogador.2
2
Em todos os exemplos apresentados (Figura 4b e 4c) foi assumido que todos os valores de ESTÁTICA
são do ponto de vista do jogador inicial (maximização). Porém, é mais fácil, na hora de definir o
algoritmo, que ESTÁTICA alterne as perspectivas, para que não seja preciso escrever procedimentos
separados para os dois níveis (jogador e adversário). É mais fácil modificar ESTÁTICA para essa
finalidade. Simplesmente calculamos o valor de Posição do ponto de vista de WHITE, depois invertemos o
valor caso o parâmetro de ESTÁTICA seja BLACK.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
35
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
Como em qualquer programa recursivo, um problema crítico com relação ao
desenvolvimento do procedimento MiniMax é quando parar a recursão e chamar a
função de avaliação estática. Há vários factores que podem influenciar essa decisão,
estes são:
™ Algum dos jogadores já ganhou?
™ Quantas jogadas já foram exploradas?
™ Qual a precisão desse caminho? Será que este é o ideal?
™ Quanto tempo nos resta?
™ Qual o grau de estabilidade dessa configuração?
Pretende-se que o procedimento MiniMax descrito anteriormente, efectue uma
procura profunda o suficiente e assumindo que o procedimento faz uma avaliação de
todos os factores referidos anteriormente, então retorna TRUE se a busca tiver de
ser interrompida ao nível corrente, ou FALSE nos casos contrários.
Para isso foi preciso criar a função PROFUNDO_O_SUFICIENTE com dois parâmetros
(Posição, Profundidade). Esta função ignora o parâmetro Posição e simplesmente
retorna TRUE caso o parâmetro Profundidade exceder o valor da constante de
interrupção.
Assumindo que o procedimento recursivo MiniMax retorna uma estrutura de dados
com o valor do caminho escolhido e o caminho em si, a seguir apresenta-se o
algoritmo descrito pela mesma referência [17].
O Algoritmo MiniMax
MiniMax(Posição, Profundidade, Jogador)
1. Se PROFUNDO_O_SUFICIENTE(Posição, Profundidade), então retorna a
estrutura
VALOR = ESTATICA(Posição, Jogador)
CAMINHO = nil
2. Caso contrário, gere mais uma camada da árvore chamando a função
GERMOV(Posição, Jogador) e atribuindo a SUCESSORES a lista que ela
retornar.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
36
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
3. Se SUCESSORES estiver vazio, então não há nenhum movimento a fazer.
Retorne a mesma estrutura em 1.
4. Se SUCESSORES não estiver vazio, então examine cada elemento e
mantenha o registro do melhor. Inicialize MELHOR_CONTAGEM com o valor
mínimo que ESTATICA consiga retornar. Ele será actualizado para reflectir o
melhor valor que pode ser atingido por qualquer elemento de SUCESSORES.
Para cada SUC de SUCESSORES, faz-se o seguinte:
(a) Atribua a RESULTADO_SUC
MiniMax(SUC,Profundidade + 1,OPOSTO(Jogador))3
Esta chamada recursiva na verdade executará a exploração de SUC.
(b) Atribua a NOVO_VALOR – VALOR (RESULTADO_SUC). Isto reflectirá os
méritos da posição do ponto de vista oposto ao do próximo nível mais
abaixo.
(c) Se NOVO_VALOR > MELHOR_CONTAGEM, então encontra-se um
sucessor melhor que qualquer outro que já tenha sido examinado até
ao momento.
i. Atribua a MELHOR_VALOR NOVO_VALOR
ii. O melhor caminho conhecido agora é de CORRENTE para SUC e
depois para o caminho apropriado abaixo de SUC, conforme
determinada pela chamada recursiva MiniMax. Portanto, atribua
a MELHOR_CAMINHO o resultado da inclusão de SUC à frente
de CAMINHO(RESULTADO_SUC).
5. Agora que todos os sucessores foram examinados, sabe-se o valor de Posição
e também do caminho que deve ser seguido para chegar a esse parâmetro.
Então retorne a estrutura
VALOR = MELHOR_CONTAGEM
CAMINHO = MELHOR_CAMINHO
Quando a chamada do procedimento retornar, o melhor movimento de Posição4 é o
primeiro elemento de CAMINHO (Lista com a sequência de jogadas).
3
Usamos a função ESTÀTICA do ponto de vista do jogador (maximização).
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
37
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
Este procedimento MiniMax que foi descrito é muito simples, mas o seu desempenho
pode
ser
significativamente
melhorado.
Alguns
desses
melhoramentos
serão
descritos a seguir.
4.2 -
Cortes ALFA-BETA
Sendo o MiniMax um procedimento de busca em profundidade normalmente usa-se
como critério de paragem da busca um tempo. Quando esse tempo for atingido são
retornados valores para cada nó da árvore. Apresenta a vantagem de ser possível
melhor a sua eficiência através de técnicas de “ramificar-e-limitar”. Como isso são
descartados ramos da árvore ou até mesmo sub-arvores que apresentam um valor
pior que a solução conhecida. Para isso se usa dois limites um para cada jogador.
Estes valores limites são alfa e beta, sendo alfa o limite inferior que um nó
maximizante poderá receber em último caso e o beta o limite superior que o nó
minimizante poderá ter.
Para ilustrar a operação de cortes alfa-beta considere a figura 5. Nos níveis de
maximização apenas o beta é utilizado e nos níveis de minimização o alfa será
usado.
Para se fazer a busca na árvore A começa-se pela sub-arvore B. O valor que B
tomará será o correspondente ao mínimo entre os valores de D e E (nível de
minimização). Portanto o valor para B é 3. Sendo que A se encontra no nível de
maximização, então A terá um valor >= 3. Se alfa é o limite inferior de um nó
maximizante, então alfa é 3 (figura 6). Analisando agora a sub-arvore C, vê-se que
ao se examinar o nó M o I (nó de minimização) tomará valores <= 0, assim sendo o
máximo que poderá ter é 0. Isto quer dizer que F terá valores >= 0, ou seja,
garantidamente tem um mínimo de 0. Sendo este este valor inferior ao alfa
encontrado anteriormente (3) então nenhum outro ramo de I precisa ser
considerado. Portanto, o jogador maximizante sabe que não deverá fazer a jogada C,
e depois I porque a contagem resultante não será melhor que 0, e então escolhe a
jogada B que garante um mínimo de 3.
4
De notar que sempre que tomamos a decisão de chamar o procedimento definido, a raiz da árvore é
sempre a posição que queremos analisar, e assim o procedimento vai gerando uma seqüência de posições
sucessoras.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
38
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
O valor beta é usado para o jogador minimizante. Continuando a exploração da
árvore, passamos então ao nó J já que não é preciso explorar o outro ramo do nó I.
O J tem um valor 5, então F terá o valor 5 que é o máximo entre 0 e 5. Sendo que o
nó C é de minimização então este terá valores <= 5, ou seja, terá um valor máximo
de 5. E assim, de acordo com a descrição de beta que é o máximo entre os mínimos
possíveis que o nó poderá tomar, temos que beta é 5 no nó C (figura 7).
Expandindo agora o no G, passamos a analisar o nó K que tem um valor 7. Isto
significa que sendo G (nó de maximização) terá um valor >= 7. Ora, uma vez que no
nó C o jogador tentará minimizar. Comparando o valor 7 com beta (5) vemos que é
superior. Então não interessa explorar o outro ramo de G. Passamos a avaliar o H, e
tem o valor 4 que é inferior ao beta. Se o nó C tivesse mais ramos então o beta
passaria a ter o valor 4 e continuávamos a percorrer a árvore.
Figura 5 – Cortes Alfa e Beta [1]
Figura 6 – Corte usando o valor de Alfa
Figura 7 – Corte usando o valor Beta
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
39
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
Em suma, nos níveis maximizantes podemos eliminar logo um movimento se ficar
claro que seu valor será menor que o alfa actual, enquanto que nos níveis
minimizantes a busca será terminada se forem descobertos valores maiores que o
beta actual. De notar também que ao descartarmos um nó no nível maximizante,
então se o mesmo nó tiver ramos que derivam dele, então no nível de minimização
essas derivações do nó não serão consideradas, o que provoca uma melhoria muito
significativa em termos de desempenho no nosso algoritmo MiniMax [1][17].
A referência [17] propõe alguns acréscimos ao algoritmo MiniMax definido
anteriormente, originando assim um novo procedimento. Este passa a ter em vez de
três, cinco parâmetros sendo que os dois últimos são alfa e beta. Este procedimento
é usado tanto nos níveis de maximização como também nos níveis de minimização.
Como o procedimento é recursivo, então no nível de maximização é usado o beta
para determinar onde a busca deve ser interrompida e o alfa é usado na chamada
recursiva do procedimento MiniMax que depois será usado no nível a seguir. E no
nível de minimização só é usado o alfa para ver onde a busca deve ser interrompida
e beta neste caso apenas será usado para a chamada recursiva do procedimento.
Portanto, ambos os níveis precisam dos dois valores, um para ser usado na busca e
o outro para ser usado na passagem recursiva para o nível seguinte.
Este procedimento trata os níveis de maximização e minimização da mesma
maneira, invertendo apenas o sinal das avaliações sempre que há uma mudança de
nível. Para simplificar a compreensão do algoritmo, foram usados em vez da notação
alfa e beta, foram usados USAR-LIMITE (valor a ser usado para a interrupção da
busca) e PASSAR-LIMITE (valor que apenas será usado para a chamada recursiva).
Na chamada recursiva, os valores USAR-LIMITE e PASSAR-LIMITE serão trocados
devido a mudança de nível.
O Algoritmo MiniMax com cortes alfa e beta
MiniMax-A-B(Posição, Profundidade, Jogador, Usar-Limite, Passar-Limite)
1. Se PROFUNDO_O_SUFICIENTE(Posição, Profundidade), então retorna a
estrutura
VALOR = ESTATICA(Posição, Jogador)
CAMINHO = nil
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
40
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
2. Caso contrário, gere mais uma camada da árvore chamando a função
GERMOV(Posição, Jogador) e atribuindo a SUCESSORES a lista que ela
retornar.
3. Se SUCESSORES estiver vazio, então não há nenhum movimento a fazer.
Retorne a mesma estrutura em 1.
4. Se SUCESSORES não estiver vazio, então examine cada elemento e
mantenha o registro do melhor.
Para cada SUC de SUCESSORES, faremos:
(a) Atribua a RESULTADO_SUC
MiniMax-A-B(SUC, Profundidade+1,OPOSTO(Jogador),
- Passar-Limite, - Usar-Limite)
(b) Atribua a NOVO-VALOR – VALOR (RESULTADO_SUC)
(c) Se NOVO_VALOR > Passar-Limite, então encontramos um sucessor
melhor do que qualquer outro examinado até ao momento. Registre o
facto fazendo o seguinte:
i.
Atribua Passar-Limite – NOVO_VALOR
ii.
O melhor caminho conhecido agora é de CORRENTE para
SUC e depois para o caminho apropriado, conforme
determinada
pela
chamada
recursiva
MiniMax-A-B.
Atribua a MELHOR_PERCURSO o resultado da inclusão
de SUC à frente de CAMINHO (RESULTADO_SUC).
(d) Se Passar-Limite (refletindo o melhor valor actual) não for melhor que
Usar-Limite, então deveremos parar de examinar essa ramificação.
Mas tanto os limites quanto os valores foram invertidos. Portanto, se
Passar-Limite = Usar-Limite, então retorne imediatamente com o valor
VALOR = Passar-Limite
CAMINHO = MELHOR-CAMINHO
5. Retorne a estrutura
VALOR = Passar-Limite
CAMINHO = MELHOR_PERCURSO
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
41
Instituto Superior de Engenharia do Porto
4.3 -
Capítulo 4 – O Minimax e alguns refinamentos
Desvantagens do MiniMax
A referência [17] propõe mais uma série de melhoramentos, que permite melhorar o
desempenho do procedimento MiniMax. Contudo, sabe-se que em jogos complicados
é praticamente inexeqüível olhar para o jogo como um todo e analisar a configuração
actual do jogo e conseguir extrair qual o movimento correcto. É impossível construir
um catalogo que consegue manter as informações necessárias para se tomar as
decisões de que jogada fazer em determinado momento. Para estes tipos de jogos a
referencia aconselha usar “movimentos de livros” que é uma lista com os
movimentos que poderão ser feitos na abertura e no encerramento do jogo. A meio
do jogo aconselha-se o uso do procedimento MiniMax. Esta combinação produzirá
melhores resultados do que aplicar cada uma das técnicas isoladamente.
Apesar de serem possíveis estes melhoramentos já referidos, ainda assim pelo facto
do MiniMax ser um algoritmo de profundidade, portanto apresenta as mesmas
desvantagens que qualquer procedimento de busca em profundidade como referido
no capitulo anterior.
E ainda mais do que isso é o facto do procedimento se basear fortemente na
suposição de que o adversário escolhe sempre o movimento ideal, ou seja, que
escolhe a jogada que minimiza os nossos ganhos. Tal suposição só é aceitável em
caso de vitória em que o jogador pode encontrar uma jogada que realmente é boa
para ele. Em caso de derrota poderá ser melhor arriscar que o adversário cometerá
um erro. Para ilustrar isso podemos considerar um caso em que temos duas jogadas
possíveis ambas ruins para nós, sendo uma delas mais desfavorável que a outra.
Podemos supor que o movimento menos promissor poderá ser bom para nós se o
jogador cometer um erro. Contudo, o MiniMax nunca o escolheria, mas sim o outro
que apresenta um valor melhor. Mas nós se calhar arriscaríamos a escolher o pior
movimento contando que o jogador poderá errar e assim tirarmos ganho. Existem
várias situações que fazem com que o MiniMax tenha uma base teórica bastante
fraca. Além do mais alguns entendidos da matéria demonstraram que em certas
árvores de jogos, quanto mais profunda for a busca piores serão os resultados
obtidos pelo MiniMax.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
42
Instituto Superior de Engenharia do Porto
4.4 -
Capítulo 4 – O Minimax e alguns refinamentos
Jogos implementados usando o MiniMax
A maioria dos jogos de tabuleiro como é o caso do Xadrez e as Damas
implementados em computador usam o algoritmo MiniMax. Nestes tipos de jogos há
um balanceamento entre o conhecimento e a busca, ou seja, não há um equilíbrio
entre o conhecimento e a busca. Quanto maior for o nível de conhecimento que um
programa tiver menor será a busca exigida. E o mesmo acontece com a busca, se
tivermos um nível bastante elevado então praticamente não precisaremos de
conhecimento. A distinção que se faz entre os humanos e um programa de
computador é que enquanto os humanos têm limitações quanto a busca em
profundidade,
estes
apresentam
bastante
conhecimento.
Um
programa
de
computador ao contrario do homem tem a capacidade de efectuar uma busca mais
profunda e exaustiva na árvore de jogadas, não sendo necessário então ter muitos
conhecimentos.
O conhecimento que este tem se limita a uma função de avaliação estática. Essa
tendência para programas baseados essencialmente em busca com força bruta
permite maior rapidez nos movimentos. Para a obtenção de níveis bastante elevados
basta efectuar uma busca profunda e com cortes.
O HITECH e o DEEP THOUGTH são exemplos de máquinas que derrotaram grandes
mestres humanos e ambos usam hardware paralelo feito sob medida para acelerar a
geração de movimentos válidos e a avaliação heurística das jogadas. Nas Damas
também existem programas para jogar esse mesmo jogo, sendo que o primeiro
programa foi desenvolvido por Arthur L. Samuel (IBM) em 1963. O programa tinha
um componente de aprendizagem que permitia que o desempenho da máquina fosse
aumentando com a experiência. O próprio programa derrotou o próprio criador. [17]
A referencia [21] fala também de um programa desenvolvido recentemente o DEEP
BLUE. Este foi desenvolvido por uma equipa de 6 programadores. Esta maquina
conseguiu vencer o maior jogador de xadrez vivo, Gary Kasparov. Mais uma vez a
provar que a inteligência artificial é uma área muito importante na ciência.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
43
Instituto Superior de Engenharia do Porto
Capítulo 4 – O Minimax e alguns refinamentos
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
44
Capítulo 5
Implementação de um agente inteligente para o
Dvonn
Este capítulo se destina à implementação do agente proposto para este projecto.
Depois de estudar a pesquisa bibliográfica é hora de decidir como implementar o
agente e que caminho seguir. Se implementar o MiniMax ou escolher outro caminho.
Neste capítulo falaremos essencialmente das regras do jogo, de seguida faremos
uma breve descrição do problema a resolver, como foi estruturado a aplicação, como
foi implementado.
5.1 -
Regras do Dvonn
As regras do jogo que serão descritas nesta secção encontram-se no site do Dvonn
http://www.gipf.com/Dvonn/.
O Dvonn é um jogo entre dois jogadores, sendo que para este trabalho teremos
apenas um jogador que jogará contra o computador, que será um agente inteligente.
Esse jogo é composto pelos seguintes componentes: o tabuleiro, 3 peças Dvonn
vermelhas, 23 peças brancas e 23 peças pretas.
O objectivo do jogo consiste em controlar o maior número possível de peças
empilhando ou amontoando as peças umas em cima das outras, tentando sempre
manter contacto com as peças Dvonn vermelhas. Quando mais nenhuma jogada
poder ser efectuada, o jogador que controla o maior número de peças ganha o jogo.
Estas regras do jogos se encontram descritas na referência.
Para iniciar o jogo, escolhe-se à sorte qual o jogador que começará o jogo, neste
caso, se é o agente ou o adversário. O primeiro jogador é o jogador que terá a cor
branca e fica com duas peças Dvonn e o segundo jogador fica com uma peça Dvonn.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
45
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Portanto, as peças brancas ficam para o primeiro jogador e as pretas para o
segundo.
O tabuleiro deve ser colocado entre os dois jogadores de maneira a que cada jogador
tenha a sua frente 9 lugares (A – I).
O jogo está dividido em duas fases, sendo que na primeira fase cada jogador
alternadamente vai colocando as peças (uma a uma) pelas posições livres no
tabuleiro, e a segunda fase o jogo em si.
Fase 1 – Colocação das peças no tabuleiro
™ O jogo começa com o tabuleiro vazio. Alternadamente, cada um dos
jogadores, coloca uma peça no tabuleiro até estarem todas as peças no
tabuleiro. As peças Dvonn são as primeiras a serem colocadas no tabuleiro e
só depois as peças da própria cor como mostra o exemplo a seguir.
Branco: primeira peça Dvonn
Preto: segunda peça Dvonn
Branco: terceira peça Dvonn
Preto: primeira peça preta
Branco: primeira peça branca
Preto: segunda peça preta ...
™ As peças Dvonn são neutras, enquanto estiverem no tabuleiro não pertencem
a qualquer dos jogadores.
™ Uma peça pode ser colocada em qualquer espaço livre, sem restrições.
™ Quando todas as peças estiverem colocadas no tabuleiro, não haverá espaços
livres no tabuleiro e assim termina a primeira fase.
Fase 2 – Empilhamento de peças
™ Nesta fase o jogador que terminou a fase anterior, é o primeiro a jogar ou seja
o jogador que tiver a peça branca é o primeiro a jogar. As jogadas dos
jogadores são efectuadas de forma alternada.
™ Os jogadores só podem jogar com peças da sua própria cor. Quando duas ou
mais peças estão empilhadas em cima umas das outras a cor da peça do topo
determina de quem é a pilha, ou seja, qual o jogador que a pode mover.
™ Em cada turno, o jogador tem de mover uma peça ou uma pilha (se a peça
que se encontra no topo da pilha é da cor que pertence ao jogador). Uma
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
46
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
única peça pode mover-se um espaço em qualquer direcção, mas apenas para
um espaço ocupado. Após o movimento a peça ficará em cima de uma outra
peça ou pilha qualquer cor.
™ Uma peça ou pilha que está cercada por todos os 6 lados não pode ser movida.
A cor das peças e/ou pilhas vizinhas não tem qualquer importância. Assim, no
início do jogo apenas as peças da orla do tabuleiro podem ser movimentadas.
As peças que não estão posicionadas na orla permanecem bloqueadas
enquanto estiverem totalmente cercadas. Na Figura 8 as peças e as pilhas
marcadas com um “x” estão cercadas por todos os 6 lados e não podem ser
movidas.
Figura 8 - Peças no tabuleiro que não podem ser movidas
™ Um movimento nunca pode terminar num espaço vazio (tem sempre que
terminar no topo de uma peça ou pilha, de qualquer cor e que pode ser um
Dvonn), mas é permitido o movimento através de um ou mais espaços
vazios. Ao efectuar um movimento, cada espaço deve ser contado,
independentemente de estar vazio ou ocupado (Figura 9).
™ Uma pilha tem sempre que ser movida como um todo e move-se tantos
espaços quantas as peças existentes na pilha (independentemente das suas
cores). Por exemplo, uma pilha de 3 peças tem que ser movida 3 espaços. Tal
como uma peça única, uma pilha pode ser movida em qualquer direcção, mas
sempre em linha recta e tem que terminar sempre num lugar que esteja
ocupado Figura 9.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
47
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Figura 9 - Movimento das peças
™ Uma peça Dvonn não pode ser movida, mas uma peça ou pilha pode ser
movida para cima dela. Quando uma peça Dvonn é parte de uma pilha,
pode-se mover a pilha contendo a peça Dvonn, mas, como explicado acima,
apenas pelo jogador que controla a pilha.
™ Não se pode passar a vez de jogar ao adversário, a não ser que o jogador
não tenha hipótese de jogadas válidas.
Perda de Peças
™ Todas as peças e pilhas devem permanecer de algum modo em contacto com
pelo menos uma peça Dvonn. Em contacto significa que deve sempre existir
um elo (directamente ou através de outras peças) com pelo menos uma peça
Dvonn. Qualquer peça e/ou pilha que não tenha ligação a uma das peças
Dvonn, tem de ser imediatamente removida do tabuleiro. Assim, pode
acontecer que um grande número de peças e pilhas sejam subitamente
removidas, como resultado de um simples movimento. Considere o exemplo
na Figura 10. Se a peça branca fizer o movimento indicado, todas as peças à
esquerda perderão o contacto com uma peça Dvonn. Terão que ser todas
removidas do tabuleiro.
Figura 10 - Perda de peças
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
48
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
™ Não importa quem faz o movimento que origina a separação das peças e/ou
pilhas com as peças Dvonn. Todas as peças e/ou pilhas isoladas seja de um
ou do outro jogador são removidas do tabuleiro. Este é um facto a ter em
atenção, especialmente no fim do jogo, uma vez que não se pode passar a
vez para o adversário, pode acontecer que um jogador isole uma ou mais das
suas peças/pilhas devido a um movimento que é obrigado a fazer (Figura 11).
Figura 11 – Fim do jogo
™ As 3 peças Dvonn permanecem em jogo até ao fim do jogo. Embora as peças
Dvonn possam ser movidas quando incluídas numa pilha, elas continuam a
ter a propriedade de manter as peças em jogo. Como se pode ver na Figura
11 é a vez do jogador com a cor branca jogar mas, este tem apenas uma
hipótese de jogada válida (mover a pilha com a peça Dvonn para a posição
indicada). Portanto o jogador é obrigado a efectuar essa jogada por não ter
outra escolhao que provoca a eliminação das pilhas marcadas com um “x”.
Fim do Jogo
™ Os jogadores devem jogar enquanto lhes for possível fazê-lo. Se um jogador
não tiver hipóteses de jogadas válidas, o outro continuar a jogar até que
tenha efectuado a sua última jogada possível. No caso raro, de um jogador
que, sendo obrigado a passar a vez ao adversário, consegue mais tarde uma
oportunidade de se mover, ele é obrigado jogar.
™ O jogo termina assim que a última jogada for efectuada. Quando esta fase é
alcançada, o jogador que controla o maior número de peças ganha o jogo. Os
dois jogadores empilham as peças e pilhas que controlam no final do jogo, o
jogador com a maior pilha, tem mais peças e, portanto ganhou! Se ambos os
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
49
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
jogadores terminarem com uma pilha igual, então o jogo termina num
empate.
5.2 -
Descrição do Problema a resolver
Pretende-se um agente com certas capacidades de inteligência, e que seja capaz de
tomar decisões de jogada mediante a avaliação do estado do tabuleiro e das jogadas
do adversário.
Na Internet existem servidores de jogos onde qualquer pessoa pode conectar-se e
escolher o jogo que quer jogar. O jogador escolhe se quer jogar com um adversário
humano ou com o computador (neste caso activa-se o agente inteligente). Após isso,
o servidor prepara as coisas para se começar a jogar. Um dos passos que o servidor
supostamente terá que fazer é gerar um tabuleiro, e enviar a cada jogar um ficheiro
com a informação contida no tabuleiro.
Cada jogador (aplicação que funciona de jogador) internamente efectua as
actualizações necessárias no ficheiro correspondente ao tabuleiro. Estas alterações
só são efectuadas aquando há confirmação de uma jogada. O servidor após aceitar
uma jogada como válida, envia aos participantes a informação de confirmação com
os elementos necessários para se fazer a referida actualização.
Esta politica é boa porque, tendo em conta que o servidor se encontra na Internet
então poderá estar em qualquer ponto do globo e os participantes também. De modo
que facilita muito a operação uma vez que o servidor não tem que estar sempre a
enviar aos participantes o ficheiro com os alterações do tabuleiro o que se torna
bastante pesado para o proprio servidor. É mais facil haver uma confirmação de
aceitação de uma jogada por parte do servidor e a própria aplicação dos dois lados
dos participante efectuarem as respectivas actualizações aos seus ficheiros.
O servidor como é óbvio também tem que actualizar o seu ficheiro com a informação
sobre o tabuleiro. Este poderá ter que controlar vários jogos (o servidor tem vários
jogos disponíveis e várias pessoas a jogar o mesmo tipo de jogo) por isso cada jogo
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
50
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
tem uma identificação e cada tabuleiro5 também tem uma identificação que permite
ao servidor controlar os jogos.
Assim sendo, o agente que se comporta como um jogador normal, receberá no inicio
do jogo um ficheiro com a informação sobre o tabuleiro gerado pelo servidor.
Podemos supor que o ficheiro se encontra em formato texto. Após isso também o
agente terá que receber do servidor uma cor (white ou black). Esta cor é gerada pelo
servidor e é ela que indica qual dos jogadores terá que começar a jogar. As regras
do jogos e como funciona se encontram anexadas no fim deste documento.
O agente terá que avaliar um conjunto de jogadas possíveis, calcular os beneficios
das mesmas jogadas, e no final escolher uma jogada. Será necessário definir
estratégias para a escolha das jogadas. O agente recebe do servidor alguma
informação de confirmação ou rejeição de uma jogada. Quando o servidor confirma
uma jogada, seja a jogada do agente ou do outro jogador, o agente actualiza a
informação do tabuleiro com a informação fornecida pelo servidor.
O mais importante nisso tudo é que além de implementar as regras do jogo é preciso
desenvolver estratégias e tácticas de jogada. Podemos aproveitar o raciocínio
utilizado no MiniMax e criar as nossas próprias estratégias.
5.3 -
Análise de espaço do problema
No inicio do jogo Dvonn cada jogador possui 23 peças para movimentar, sendo que
em média cada jogador terá 10 peças em condições de serem movimentadas, cada
uma das peça terá 3 ou 4 movimentos válidos nesta fase.
Desta maneira existem mais ou menos 30 jogadas possíveis para cada jogador.
Considerando um cálculo aproximado, cada jogador fará durante o jogo uma média
de 15 jogadas, então para os dois jogadores teremos 30 jogadas. Assim a árvore
completa de pesquisa terá aproximadamente 3030 nós para analisar. Ao longo do
jogo as hipóteses de jogada vão diminuindo a medida que os jogadores vão
perdendo peças o que significa que as ramificações vão diminuindo mas essa
5
Para cada instância de um jogo qualquer que o servidor gere, este terá que gerar também uma
identificação para o tabuleiro. Associada a identificação do tabuleiro o servidor guarda informações como:
dados sobre o tabuleiro, quem são os participantes, que tipo de jogo é, a informação das regras do jogo,
etc.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
51
Instituto Superior de Engenharia do Porto
diminuição não é fixa. Assim sendo,
Capítulo 5 – Implementação agente Dvonn
a abordagem “maciça” não se demonstrou
aplicável ao problema em questão. Note-se que o algoritmo implementado pelo
método MiniMax considera uma abordagem maciça com um nível de profundidade
máximo, por exemplo 8 jogadas, tendo-se optado por implementar uma abordagem
que considera tácticas e heurísticas para o jogo.
5.4 -
Estruturação do problema proposto
Analisar o jogo em si, é um problema comum da tomada de decisão num jogo
qualquer de tabuleiro. O processo de tomada de decisão subdivide-se em 3 níveis:
Estratégico, Táctico e Operacional como representado na pirâmide na Figura 12.
Figura 12 - Diferentes níveis de abstração no jogo Dvonn
Em cada um destes níveis existem informações diferentes e estruturas de
conhecimento também diferentes.
O nivel mais baixo é o nível operacional. Neste nível define-se a estrutura básica da
informação sobre o tabuleiro, define-se a forma de implementação das regras do
jogo e validações necessárias. Neste nível os objectivos são a nível de ganho de
peças e como podemos ver na segunda pirâmide neste nível existem apenas dados,
ou seja, a informação que temos não permite tirar conclusões quanto a que
movimentos efectuar. Essa informação não é apropriada para a tormada de decisões.
No nível a seguir, o táctico, os objectivos já são mais elaborados, já se associa
conceitos como de áreas. Pode-se definir como objectivo criar áreas sem Dvonn para
poder diminuir as hipóteses de jogada do adversário. Os objectivos para este nível já
é a nível de pilhas. Isolamento das pilhas do adversário, ganhar pilhas do adversário,
etc.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
52
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Neste nível a qualidade de informação é muito melhor que no nível anterior e por
isso na pirâmide é considerado o nível da informação. Neste nível são implementadas
tácticas de jogo como forma de recolher o maior número possível de informação do
tabuleiro. De notar que essa informação é uma informação tratada com objectivo de
poder ajudar na tomada de decisão no nível superior.
O nível estratégico é o nível mais elevado e por isso de conhecimento. Este é o nivel
mais dificil de implementar. Neste nível já existe o conhecimento em si do jogo. Por
exemplo, que estratégias aplicar em cada situação. Existe a capacidade de
aprendizagem. Consegue-se perceber a jogada que o adversário irá efectuar por
estudar os seus movimentos efectuados anteriormente. Existe a capacidade de
induzir o adversário a fazer uma jogada que o leve a perder. Neste nível o
conhecimento é muito mais difícil de representar uma vez que teremos bastante
informação adquirida e torna-se necessário aceder a tais informações de forma
rápida e tomar decisões também de forma rápida. Também terá que existir métodos
muito bem elaborados que consiga recolher essas informações e efectuar as
melhores escolhas de jogada.
Neste projecto, pretende-se estudar e implementar os 3 níveis de tomada de
decisão.
Para
cada
nível
teremos
um
módulo
associado
onde
teremos
os
procedimentos necessários para cumprir com os objectivos definidos em cada um
destes níveis. Desta forma definiu-se a seguinte estrutura para a aplicação (Figura
13):
™ Agente inteligente;
™ Área de processamento de tomada de decisões;
™ O tabuleiro em formato texto que posteriormente será transformado num
facto dinâmico que guardará em memória a informação sobre o tabuleiro;
™ Um ficheiro de regras do jogo;
™ Um ficheiro de tácticas para o jogo;
™ Um ficheiro de estratégias para o jogo.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
53
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Tabuleiro em
formato de texto
Estratégias
Tácticas
Agente
Main
Inteligente
Processamento
Regras
Operacional
Tabuleiro
Figura 13 – Organização dos ficheiros
Descrição dos Módulos
Agente inteligente
Este agente será a nossa aplicação em si, uma vez que todas as comunicações serão
feitas através dela. Cria-se o agente e este fica a espera de um pedido de ligação por
parte do servidor. Esta ligação ou conexão envolve não só o pedido de ligação mas
também após isso o servidor terá que enviar ao nosso agente inteligente um
identificador (servidor) e também o porto onde se encontra para futuras trocas de
informações. De notar que na fase do estabelecimento da ligação o servidor terá que
saber a localização do agente e assim ser possível efectuar a referida conexão.
O agente encontra-se programado para receber certas mensagens em específico,
sendo elas as seguintes:
id(servidor,Porto) – o servidor envia ao agente esta mensagem com o
identificador id e o primeiro parâmetro é um túpulo “servidor” e o
Porto
é
uma
variável
que
terá
o
valor
correspondente
ao
porto
do
Servidor.
cor(servidor,Cor) – após ser gerado o tabuleiro pelo servidor, este
terá que enviar ao agente esta mensagem onde a variável Cor corresponde
a cor com a qual o agente irá jogar.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
54
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
sua_vez – enquanto não receber esta mensagem do servidor não consegue
efectuar qualquer jogada garantindo que o agente não tentará jogar
quando não é a sua vez de jogar.
confirma_jogada(ID,(Col1,Lin1),(Col2,Lin2),Resposta)
-
quando
o
servidor recebe um pedido de jogada, o servidor avalia o pedido e dá
uma
confirmação
ao
emissor.
O
emissor
é
identificado
através
da
variável ID que pode ser “pc” (se for o agente inteligente) e “jogador”
(se for o adversário). A confirmação é recebida através da variável
Resposta que pode ser “aceite” ou “invalida”. Caso aceite a jogada,
então envia também ao outro jogador a mesma mensagem para que o jogador
ou o agente possa alterar o estado do seu tabuleiro.
Qualquer mensagem que o agente receba que não esteja neste formatos
especificados anteriomente não serão tratados.
Depois de o agente ter todas as informações necessárias para haver trocas de
mensagens entre este e o servidor, então podemos assim dizer que começa o jogo.
As jogadas serão feitas por trocas de mensagens entre o agente e o servidor. Mais
adiante será descrito mais pormenorizadamente o funcionamento do agente.
Área de processamento
Esta área como o proprio nome indica é uma área que se destina ao processamento
de todo o tipo de informação. Teremos aqui todos os predicados mais importantes.
Mais adiante será explicado mais em pormenor o raciocinio utilizado para o
desenvolvimento do agente.
Tabuleiro
Depois de receber o ficheiro de texto correspondente ao tabuleiro gerado pelo
servidor, o agente precisa tratar essa informação. Esta terá que ser transformada em
informação de fácil processamento pelo Prolog. Tendo em conta o formato do nosso
tabuleiro (Figura 14) definimos uma estrutura que seja de fácil percepção e
principalmente que permita uma melhor manipulação da informação pelo programa.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
55
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Figura 14 – Tabuleiro Dvonn [19]
O tabuleiro tem 5 linhas de 1 a 5, e 11 colunas de A a K. Para tornar mais rápido o
acesso a informação existente no tabuleiro as colunas serão definidas de 1 a 11.
Criou-se o facto dinâmico tabuleiro/26 com dois parâmetros. O primeiro parâmetro
é a coluna (1 - 11) e o segundo é uma lista onde teremos a informação sobre as
linhas.
De notar que existem colunas que não têm 5 linhas, portanto para algumas colunas
teremos uma lista mais pequena. A lista com a informação sobre as linhas contém a
seguinte informação no formato (Linha, Cor, N_Peças, Dvonn). A variável Linha
identifica qual a linha em questão (1 - 5), a Cor corresponde a cor (poderá ser w, b,
d) da peça que se encontra no topo da pilha nessa posição, a variável N_Peças é o
número de peças que compõe a pilha e Dvonn é uma flag que tem o valor 0 ou 1
consoante a pilha tiver uma peça Dvonn ou não. Considere o exemplo da
representação do tabuleiro da Figura 14. Neste exemplo temos 11 predicados, cada
um com o seu identificador (coluna) de 1 a 11 e uma lista com as informações sobre
as linhas de cada coluna.
tabuleiro(1,[(1,w,1,0),(2,b,1,0),(3,w,1,0)]).
tabuleiro(2,[(1,b,1,0),(2,b,1,0),(3,b,1,0),(4,b,1,0)]).
tabuleiro(3,[(1,b,1,0),(2,w,1,0),(3,w,1,0),(4,b,1,0),(5,w,1,0)]).
tabuleiro(4,[(1,w,1,0),(2,b,1,0),(3,b,1,0),(4,d,1,1),(5,w,1,0)]).
tabuleiro(5,[(1,b,1,0),(2,b,1,0),(3,w,1,0),(4,w,1,0),(5,w,1,0)]).
tabuleiro(6,[(1,b,1,0),(2,w,1,0),(3,w,1,0),(4,b,1,0),(5,w,1,0)]).
tabuleiro(7,[(1,w,1,0),(2,b,1,0),(3,b,1,0),(4,d,1,1),(5,b,1,0)]).
tabuleiro(8,[(1,w,1,0),(2,w,1,0),(3,w,1,0),(4,b,1,0),(5,b,1,0)]).
tabuleiro(9,[(1,b,1,0),(2,w,1,0),(3,w,1,0),(4,b,1,0),(5,w,1,0)]).
tabuleiro(10,[(2,w,1,0),(3,w,1,0),(4,w,1,0),(5,b,1,0)]).
tabuleiro(11,[(3,b,1,0),(4,d,1,1),(5,b,1,0)]).
6
Em Prolog utiliza-se a notação nome_predicado/N onde N é o número de argumentos que o método
tem.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
56
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
A aplicação disponibiliza um predicado tabuleiro que desenha no ecrã o tabuleiro
existente em memória. Na Figura 15 pode-se ver que para cada posição do tabuleiro
(Coluna, Linha) existem 3 identificadores (atributos decisivos). Nas posições onde
não existe Dvonn o primeiro identificador é um ponto (.) e quando existe é um
asterisco (*). O segundo identificador é a cor que domina a pilha e pode ser um w, b
ou d (neste caso a pilha ainda não pertence a nenhum dos jogadores). O terceiro
identificador que também é importante corresponde ao tamanho da pilha, e é a
partir deste valor que o jogador sabe quantas posições poderá mover.
5
4
3
2
1
-
.w1 .w1 .w1 .w1 .b1 .b1 .w1 .b1 .b1
.b1 .b1 *d1 .w1 .b1 *d1 .b1 .b1 .w1 *d1
.w1 .b1 .w1 .b1 .w1 .w1 .b1 .w1 .w1 .w1 .b1
.b1 .b1 .w1 .b1 .b1 .w1 .b1 .w1 .w1 .w1
.w1 .b1 .b1 .w1 .b1 .b1 .w1 .w1 .b1
\
\
\
\
\
\
\
\
\
\
A
B
C
D
E
F
G
H
I
J
\
K
Figura 15 – Formato de apresentação do tabuleiro
Como nota queremos referir que estes 3 identificadores utilizados para fazer o
desenho do tabuleiro foram escolhidos tendo em conta que são informações
importantes para um jogador conhecer o estado do tabuleiro, quais as suas jogadas
válidas e também qual ao situação do seu adversário. Para isso é preciso localizar as
peças Dvonn e também saber quais as pilhas que poderá mover e as posições para
onde poderão mover.
Regras do jogo (nível operacional)
Este nível fornece o suporte básico e imprescindível aos níveis superiores. Para isso
contém métodos que serão utilizados para validar os movimentos ou jogadas dos
jogadores mediante a informação do estado do tabuleiro. Por exemplo, um jogador
que joga com a cor w não poderá movimentar uma pilha de cor b ou d. Outro
exemplo, uma pilha de tamanho 2 não poderá efectuar um salto de 1 ou 3. Na fase 2
não é possível efectuar movimentos para posições vazias, um jogador não pode
jogar quando não é a sua vez. Existem várias situações que terão de ser validadas
como descrito da secção 5.1 e isso tudo se encontra neste módulo.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
57
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Tácticas de jogo (nivel tático)
Este ficheiro é destinado a implementação de algumas táticas para o jogo. Estas
táticas utilizam predicados que se encontra no módulo processamento e faz uma
conjunção delas de modo a se conseguir implementar as táticas propostas. As
tácticas são objectivos que o agente pretende atingir a curto prazo. Considera-se por
exemplo como objectivo a curto prazo fazer jogadas que dão mais beneficios
imediato ao agente.
Estratégias de jogo (nivel estratégico)
Neste módulo serão implementadas estratégias ou objectivos do agente a longo
prazo. Sendo este o nível mais elevado, não existirão muitos pormenores a nivel de
como implementar as estratégias e por isso os níveis mais baixos terão que fornecer
o suporte para a implementação das estratégias definidas. Por outras palavras, o
nível estratégico terá predicados simples que recorrem a outros predicados criados
nos níveis de baixo.
5.5 5.5.1 -
Implementação das regras do jogo
Validação das jogadas
A partir das instruções fornecidas na secção 5.1 é preciso definir formas de validar as
jogadas, formas de identificar as jogadas válidas possíveis do agente, como poderão
ser efectas as jogadas, etc. Desta maneira, criou-se o conceito de vizinho (Figura
16a), que corresponde as posições a volta de uma determinada posição. De salientar
que uma das régras expressa no documento em anexo é de que as pilhas que se
encontram completamente cercadas não poderão ser movidas (Figura 8). Atendendo
a Figura 16 verifica-se que cada posição tem no máximo 6 direcções para onde
poderá mover. Essas direcções estão numeradas de 1 a 6.
Vamos de seguida analizar o resultado de um movimento para cada uma das
direcções (Figura 16b).
Se quisermos mover a pilha P na direcção 1 da posição 1 para a posição 2 então
para determinarmos as “coordenadas” da posição 2, apenas a coluna irá variar,
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
58
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
mantendo-se a linha. Como foi referido aquando da criação do predicado tabuleiro/2,
a coluna é numerada de 1 a 11 facilitando assim a conta. Assim o resultado será
Coluna2 = Coluna1 – N_Peças (tamanho da pilha P a mover).
Na direcção 4 segue-se o mesmo raciocinio mas com a diferença de que em vez de
diminuir a coluna aumenta.
Nas direcções 2 e 5 mantem-se a coluna e as linhas aumentam e diminuem N_Peças
respectivamente.
Na direcção 3 aumenta tanto a linha como a coluna N_Peças. E finalmente para a
direcção 6 diminui N_Peças tanto a linha como a coluna.
Figura 16 – Direcções para onde uma pilha pode movimentar
Definimos alguns predicados que são muito importantes para a continuidade do
raciocício descrito. O predicado mais básico e que suporta toda a implementação do
agente é o predicado vizinho(+Pos,+Size,-Vizinho)7.
Este predicado tem os seguintes parâmetros: o primeiro é a posição no formato
(Coluna,Linha) sobre o qual queremos procurar vizinhos. O segundo parâmetro toma
o valor 1 quando o predicado é usado para encontrar os vizinhos de uma
determinada posição e toma o valor N_Peças quando queremos saber quais as
posições para onde a pilha, que esteja na posição referida no parâmetro 1, pode
mover.
Para exemplificar a situação considere a Figura 17. Para sabermos os vizinhos da
posição na figura consideramos Size = 1 e temos dois vizinhos. Se considerar agora
o Size como N_Peças (tamanho da pilha), que neste caso é 3, então segundo a
figura teremos 3 jogadas possíveis considerando um salto de 3 posições (os saltos
estão representadas na figura com setas brancas). Considere ainda que o tamanho
7
A notação que será usada para a definição dos predicados será a mesma que é usada na linguagem
Prolog.
(+): campo de entrada – é preciso fornecer este valor ao método.
(–): campo de saída – valor de retorno do método.
(?): campo que poderá ser tanto de saída como de entrada – este pode ser fornecido ou não.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
59
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
da pilha era 1, então o salto seria 1 também. Por isso teriamos 2 jogadas possíveis
iguais aos vizinhos encontrados. O terceiro argumento corresponde a um vizinho
encontrado para a posição, ou um movimento possível da pilha.
O predicado vizinho/3 será utilizado por outros predicados, tais como:
calcular_vizinhos(+Pos,+Size,-Lista) – que devolve uma lista com todas
as posições vizinhas. Esta lista se encontra no formato [(Col,Lin),...]
encontrar_vizinhos_ocupados(+Pos,+Size,-Lista) - que devolve uma lista
das vizinhas que estão ocupadas com peças. Não podemos esquecer de que
na fase 2 só é possível efetuarmos um movimento para uma posição que
esteja
ocupada.
Portanto
este
predicado
é
conveniente
para
esta
situação.
contar_vizinhos_ocupados(+Pos,+Size,-Tam) – uma das régras do próprio
Dvonn é de que as peças que estiverem completamente cercadas não podem
ser
movimentadas.
Assim,
este
predicado
devolve
na
variável
Tam
o
número de vizinhos da posição (C,L) ocupados. Se o Tam = 6 então a
posição está completamente cercada e não se pode movimentar.
jogadas_possiveis_validas(+Cor,-Jogadas_Validas)
–
conjugando
os
predicados acima descritos, este devolve uma lista de jogadas válidas
para uma determinada cor. Se usar a cor w, o predicado devolve uma
lista de todas as jogadas válidas para o estado actual do tabuleiro,
para o jogador que joga com a cor w. Se fizer o mesmo para a b,
delvolverá a lista das jogadas válidas para o jogador com a cor b. Esta
lista se encontra no formato [(Col,Lin),...]
Figura 17 – Movimentar uma pilha
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
60
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Estes predicados são muito importantes quer para a definição de jogadas válidas que
o agente poderá efectuar, como também para a criação das estratégias do jogo.
Outro aspecto que é importante considerar na validação das jogadas é que cada
jogador só pode mover peças da sua cor. Portanto, o agente inteligente terá que
conseguir saber quais as posições no tabuleiro que pode mover. Vimos anteriomente
que o facto tabuleiro/2 foi pensado de forma a tormar fácil a manipulação da
informação sobre o tabuleiro. Assim sendo, após identificarmos as posições onde se
encontram as peças da nossa cor, aí então poderemos avaliar quais as possibilidades
de jogada que cada posição nos oferece através do predicado vizinho. De notar que
uma posição tem no máximo 6 hipóteses de jogada, e também pode não ter
nenhuma hipótese de jogada (isto acontece muitas vezes quando a pilha é muito
grande).
5.5.2 -
Como calcular os benefícios de uma jogada?
Cálcular os benefícios de uma jogada é relativamente difícil uma vez que não se
pode, de uma forma directa identificar quais as peças que o jogador ganha e
também as perdas associadas a mesma jogada. Considere portanto a figura 14.
Nesta figura vemos que o jogador com a cor branca pretende efectuar uma jogada
onde o seu ganho é de uma peça e no entanto essa jogada provoca o isolamento de
várias peças do tabuleiro entre elas duas peças da sua cor. Assim, vemos que apesar
de ter um ganho de uma peça da cor preta, perde duas peças da cor branca.
Esta avaliação que estamos fazendo, é uma avaliação de imediato, ou seja, a curto
prazo. Se calhar interessa para o jogador efectuar essa jogada porque o adversário
perde 5 pilhas com tamanhos diferentes. Essa perda por parte do adversário é boa
para nosso jogador em questão.
Portanto, no cálculo dos benefícios é necessário incluirmos também não só o ganho e
a perda do jogador também a perda do adversário. Chegar a uma fórmula que seja
razoávelmente boa é difícil, dependendo do raciocínio que o programador tiver em
mente. Uma vez que o custo das jogadas influencia muito na escolha das jogadas
por parte do agente é preciso ter muito cuidado na sua definição. Apesar de a
tomada de decisão ser feita de acordo com as estratégias implementadas, a fórmula
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
61
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
terá uma peso também elevado que fará com que o agente consiga tomar decisões
boas ou más tendo em conta o critério usado para a pontuação dos custos das
jogadas.
Mas neste projecto não se preocupou muito com este aspecto. Contudo, foi definida
uma fórmula que é relativamente simples mas que leva em contas as parcelas
importantes no como as perdas do jogador e do adversário e também os ganhos.
A fórmula definida é a seguinte: Custo = PGJ - PPJ + PPA
PGJ – são as peças ganhas pelo jogador
PPJ – são as peças que o jogador perde
PPA – são as peças que o adversário perde.8
Depois de estar definido a fórmula e de calcularmos os pesos das jogadas, então
será preciso tirar conclusões sobre qual é a melhor jogada que poderá ser feito. Nem
sempre as conclusões serão boas. Como se pode ver após o cálculo do custo
perde-se a informação sobre os ganhos e perdas quer do jogador quer do adversário.
Desta maneira a fórmula terá que ser muito bem pensada de modo a que os custos
calculados para as jogadas sejam boas para a tomada de decisões. Se existir um
grau de confiança elavado em relação aos resultados que a fórmula nos dá então
existirá um equilíbrio entre este ganho e as perdas de informação referidas
anteriormente.
Para permitir a alteração da fórmula criou-se o seguinte predicado onde podemos
reestruturar ou redefinir uma nova fórmula para o cálculo do custo das jogadas:
determinar_custo(PGJ,PPJ,PPA,Custo)
8
Notar que os ganhos ou perdas são a soma do tamanho de todas as pilhas da referida cor, ou seja,
quando o jogador ganha uma pilha do adversário o seu ganho corresponde ao tamanho da pilha. E no
caso de perdas é a mesma coisa temos que somar todas as pilhas da cor.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
62
Instituto Superior de Engenharia do Porto
5.5.3 -
Capítulo 5 – Implementação agente Dvonn
Calcular o Isolamento de peças
O cálculo do ganho que se pode ter com uma jogada é fácil de fazer, basta saber a
cor da pilha que irá ser movimentada e para onde quer mover. Sabe-se que na
posição para onde se irá mover tem uma cor associada, assim basta verificar se as
cores são iguais para se saber se haverá ganho de peças ou não. Se as cores forem
iguais o PGJ = 0, e se forem diferentes o ganho que o jogador terá é o tamanho que
a pilha para onde quer mover tem. Neste caso PGJ = N_Peças da posição 2.
Se a pilha tiver um Dvonn pode-se acrescentar 1 ponto como bónus para fazer com
que os jogadores tenham por objectivo controlar as peças Dvonn.
O problema se põe em calcular as peças que ficam sem ligação a um Dvonn, ou seja,
encontrar as peças isoladas. Para avaliar esta situação considere a Figura 18.
Figura 18 – Isolamento de peças
Na figura pode-se ver que depois de se concretizar a jogada ou movimento, haverá
duas áreas distintas (formou-se como que dois grupos de peças um grupo de lado
esquerdo e outro do lado direito) no tabuleiro. Nestas duas áreas vê-se que as peças
pertencentes a área da esquerda terão que ser eliminadas por não ter ligação Dvonn,
ou seja, não existe nenhum Dvonn nessa área. Como implementar isso?
Figura 19 – Tabuleiro inicial gerado pelo servidor
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
63
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Uma solução é pensar da seguinte forma: o tabuleiro tem 3 peças Dvonn o que faz
como que no máximo seja possível formar 3 áreas distintas. Quando dizemos 3
áreas referimos as áreas com ligação Dvonn porque como referido na secção 5.1 as
peças isoladas serão retiradas do tabuleiro.
A figura 19 é um exemplo de um tabuleiro no seu estado inicial, neste estado existe
apenas uma única área porque não existem separações entre as peças.
Considerando que existe uma lista com todas as posições ocupadas do tabuleiro no
formato (Coluna,Linha) e que a mesma lista se encontra ordenada. Para a Figura 20
teremos uma lista com 26 elementos. A lista das posições é a seguinte:
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,1),(3,4),(3,5),(4,1),(4,2),(4,4),(5,1),(5,2),(5,3),
(5,5),(6,1),(7,1),(7,3),(7,4),(8,1),(9,3),(9,4),(10,2),(10,3),(11,3),(11,4)]
Figura 20 – Divisão do tabuleiro em áreas
Para cada elemento da lista, calcula-se as suas posições vizinhas e de entre estas
veremos se algum pertence a lista inicial. Antes de se começar a explorar uma
posição, guarda-se essa indicação numa lista auxiliar. Neste caso vê-se que a
posição (1,1) tem 3 posições vizinhas (1,2), (2,1) e (2,2). De entre estes vizinhos
(1,2), e (2,2) pertencem a lista portanto, serão os próximos a ser explorado.
Seguindo a ordem (1,2) será explorado primeiro, e vê-se que tem as posições (1,1),
(1,3), (2,2), e (2,3) como vizinhas e todas elas pertencem a lista contudo, a posição
(1,1) não será explorada porque já se encontra na lista auxiliar, e o processo se
repete até se obtermos (todas as posições da área já foram exploradas).
No final a lista auxiliar terá as posições ligadas por uma linha na figura. Estas
posições ([(1,1),(1,2),(1,3),(2,3),(2,2),(3,4),(3,5),(4,4),(5,5)]) são as posições que
formam a área 1. Depois de encontrar uma área verifica-se se existe alguma posição
da área que tenha um Dvonn. Se sim então estas posições têm ligação, senão serão
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
64
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
marcadas como peças para remover do tabuleiro. Sempre que encontra uma área
nova remove-se da lista inicial todas as posições que pertencem a referida área.
O processo se repete até que todas posições da lista tenham sido exploradas. Da
Figura 20 vemos que 8 posições serão marcadas para serem removidas. Estas são:
[(3,1),(4,1),(4,2),(5,1),(5,2),(5,3),(6,1),(7,1)]
A lista de posições a remover pode ter n elementos, e estes elementos podem ser da
cor branca (w) ou preta (b). Faz-se a contabilização das peças existentes nessas
posições para se saber o que cada jogador perde. De notar que por exemplo, para a
cor branca perde-se três pilhas, e o total é a soma do tamanho de cada pilha. Na
imagem as pilhas têm apenas uma peça por isso o total é 3.
Depois de saber que peças cada jogador perde, usa-se a fórmula definida na secção
5.4.2. para determinar o custo da jogada. Associado a cada jogada válida do agente
acrescenta-se este custo.
O predicado jogadas_beneficio(+Lista_jogadas,-ListaNova)
é um método
recursivo que é usado para fazer a actualização da lista de jogadas válidas do
agente, e para isso também utiliza o predicado calcular_beneficio_jogada/2.
O formato da lista de jogadas válidas é a seguinte: [[Pos1,Pos2], ... ] em que as
variáveis Pos1 e Pos2 se encontram no formato (Coluna, Linha). [Pos1,Pos2]
significa que é possível efectuar o movimento da pilha que se encontra na posição
Pos1 para a posição Pos2. A ListaNova resultante terá o seguinte formato:
[[Pos1,Pos2,Custo], ... ].
O
predicado
calcular_beneficio_jogada(+Jogada,-Jogada_custo)
é
muito
importante, porque é ele que cuida dos pormenores referentes a como calcular os
efeitos da referida jogada sobre o tabuleiro. Isso inclui simular a jogada, e após isso
verificar quais as peças que o agente ganha, quais as peças que perde e também
quais as peças que o adversário perde. Todas essas simulações são feitas sempre
através da criação de áreas no tabuleiro. A variável Jogada como já se referido no
predicado anterior tem o formato [Pos1,Pos2] e a variável Jogada_custo será
[Pos1,Pos2,Custo].
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
65
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Na implementação deste predicado deparamos como muitas dificuldades, como é o
caso de quando queremos calcular os benefícios de uma lista relativamente grande
de jogadas possíveis. A aplicação Prolog apresentava sempre uma mensagem de
erro dizendo a hip está cheia. Este problema foi difícil de resolver por não
conseguirmos detectar a razão para os predicados funcionarem com listas pequenas
e para listas com mais alguns elementos já não funcionava. Depois chegou-se a
conclusão que realmente quando se usa listas relativamente grandes para se testar
os predicados a aplicação não conseguia terminar a execução e abortava. Por isso
teria que ser preciso arranjar uma forma de solucionar o problema.
Após muitos dias sem conseguir resolver o problema chegou-se a uma situação
interessante: para explicar o raciocínio considere a figura 21. Na figura existem 3
áreas, e as jogadas ou movimentos podem ser feitos dentro da mesma área ou para
fora da área. Para começar vamos analisar os movimentos da pilha de cor branca da
primeira área. Esta pilha tem tamanho 2 e portanto tem 3 hipóteses de jogada, uma
para a área 2 e duas dentro da mesma área. Como a pilha não contém nenhum
Dvonn então os efeitos resultantes do seu movimento é o mesmo (a nível de peças
perdidas) quer seja dentro da área ou para fora. Portanto, para essa posição só
preciso calcular as perdas uma só vez. Como podemos constatar na figura, as peças
perdidas são as mesmas quer movemos para dentro da área ou para fora. Com a
excepção do caso do movimento ser para uma posição que ficará sem ligação, neste
caso também perde-se a pilha (não existe ganho) e portanto será acrescentado ao
total de perdas o tamanho da pilha.
E se a pilha tiver um Dvonn?
Vamos considerar a pilha de cor preta da área 1. Esta pilha tem tamanho 3 e contém
uma peça Dvonn. Os movimentos possíveis para esta pilha são dois. Um na direcção
1 e o outro na direcção 4. O movimento na direcção 1 é dentro da mesma área, e o
outro é para a área 2. Se o movimento for para fora da área as peças que ficam sem
ligação são as mesmas seja qual for a posição para onde se move. Neste caso só
temos uma hipótese de jogada mas, se tivéssemos mais bastaria calcular as perdas
para uma dessas jogadas e guardar essa informação. Neste caso, o movimento
provocaria muitas perdas porque todas as posições da área 1 dependem dessa pilha.
Quando o movimento for dentro da área aí temos que ter um pouco mais de cuidado
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
66
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
porque nem sempre as perdas são as mesmas portanto temos que fazer os cálculos
sempre.
Figura 21 – Movimentar pilhas entre áreas
Portanto, como vimos esta ideia melhora muito a performance do agente, porque
consegue ter as informações mais rápida e não é preciso estar sempre a efectuar
cálculos de perdas para todas as jogadas. Isto não quer dizer que desconsideramos
as outras jogadas possíveis mas sim, que já não precisamos efectuar cálculos
desnecessários porque pordemos obter estes valores a partir de outros cálculos já
efectuados anteriormente. Antes fazia-se a avaliação para as 6 jogadas possíveis e
agora considera-se apenas duas situações (dentro e fora da área). Desta maneira a
aplicação prolog não aborta a execução a meio e consegue-se um melhor
desempenho.
Os predicados criados para o cálculo das perdas formam os seguintes:
calcular_areas(+ListaPosicoesOcupadas) – este predicado é muito útil
porque é através dele que podemos calcular as perdas dos jogadores. As
perdas são calculadas em função das áreas existentes no tabuleiro. O
predicado recebe no argumento a lista de posições ocupadas do tabuleiro
e depois cria um facto auxiliar areas/1 que será usado para qualquer
cálculo necessário.
Este facto areas tem o formato [[(Col,Lin,Cor,Tam,DV), ... ], ... ] e
pode ter no máximo 3 elementos (3 listas). Cada lista pode ter o número
qualquer de elementos sendo que as listas representam áreas existentes
no tabuleiro e os elementos das listas são as posições do tabuleiro
correspondentes a área.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
67
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Considere um como exemplo o seguinte tabuleiro:
5
4
3
2
1
-
.0. .b1 .b1 .0. .0. .b3 .0. .w2 .0.
.b2 .0. .b1 .0. .0. .b1 .w2 .0. .b1 .0.
.w1 .b1 .w2 .0. .w2 .b3 .0. .0. *d1 .0. .0.
.0. *b2 .0. .w1 .0. .w1 .0. .0. .0. .0.
.w2 .0. *d1 .w1 .w1 .w1 .0. .0. .0.
\
\
\
\
\
\
\
\
\
\
A
B
C
D
E
F
G
H
I
J
\
K
Para este tabuleiro as lista de áreas é a seguinte:
[
[(1,1,w,2,0),(1,3,w,1,0),(2,2,b,2,1),(2,3,b,1,0),(2,4,b,2,0),(3,3,w,2,0
),(4,4,b,1,0),(4,5,b,1,0),(5,5,b,1,0)]
,
[(3,1,d,1,1),(4,1,w,1,0),(4,2,w,1,0),(5,1,w,1,0),(5,3,w,2,0),(6,1,w,1,0
),(6,2,w,1,0),(6,3,b,3,0),(7,4,b,1,0),(8,4,w,2,0),(8,5,b,3,0)]
,
[(9,3,d,1,1),(10,4,b,1,0),(10,5,w,2,0)]
]
Nesta lista temos 3 listas de áreas e em cada área temos a informação
sobre as posições que pertecem a área.
calcular_efeitos_jogada_tabuleiro(+Pos1,+Pos2,-Tipo)
–
este
predicado
com 3 argumentos serve para sabermos qual o efeito de um movimento
sobre o tabuleiro. O primeiro argumento é a posição a mover e o segundo
é a posição para onde queremos deslocar a pilha. O terceiro argumento é
o tipo que poderá ter três valores, dentro, fora ou qualquer. Estes
valores indicam se o movimento é para dentro ou fora da área se a pilha
tiver um Dvonn e no caso de ser uma pilha normal o valor da variável é
qualquer porque tanto faz se o movimento for para fora ou para dentro
as posições perdidas serão as mesmas. Depois disso o predicado cria um
facto dinâmico auxiliar pecas_perdidas_jogada/3 que guarda a informação
sobre o movimento e a lista das posições que ficam sem ligação depois
do movimento.Este facto terá o seguinte formato:
pecas_perdidas_jogada(Posicao,TipoMov,PecasPerdidas).
pecas_ganhoJ_perdidasA(+Cor1,+Cor2,+Tam2,+DV2,+P_S_Lig_Adv,-PGJ,-PPA)–
calcula os parâmetros correspondentes ao ganho do jogador e as perdas
tanto do jogador como do adversário. Os valores para as variáveis Cor
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
68
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
da posição, Cor da posição 2, tamanho da pilha da posição 2 e se
existem Dvonn na posição 2 e também o nímero de peças do adversário sem
ligação são fornecidos como a própria notação indica e os dois últimos
parâmetros serão calculados pelo método e serão retornados a aplicação.
parametros_calculo_custo_jogada(+[Pos1,Pos2],-PGJ,-PPJ,-PPA)–
predicado
auxiliar que usa alguns destes predicados já definidos, como o caso do
predicado definido anteriormente para encontrar os parâmetros que serão
usados no cálculo do beneficio da jogada [Pos1,Pos2].
determinar_custo(+PGJ,+PPJ,+PPA,-Custo)
–
predicado
responsável
por
calcular o custo da jogada mediante a fórmula definida para esse fim.
5.5.4 -
Fim do Jogo
No jogo os jogadores vamos perdendo peças, as pilhas vão aumentando, e o número
de jogadas possíveis varia. Contudo, durante o desenrolar do jogo, pode haver
situações em que um dos jogadores não tenha jogadas válidas. Neste caso o outro
jogador continua a jogar até que o outro tenha hipótese de jogar. Quando nenhum
dos jogadores tiver jogadas possíveis então o jogo acaba. Nesta altura faz-se a
contagem das peças na posse de cada jogador. O jogador que tiver o maior número
de peças ganha o jogo. Para a contagem das peças faz-se o somatório do tamanho
de cada pilha.
5.6 -
Tácticas propostas para o jogo
A página http://www.gipf.com/Dvonn/ dá-nos algumas sugestões de táticas e
estratégias que podemos definir para o jogo. O jogo tem duas fases mas a primeira
fase não foi referida ao longo do relatório porque tem a ver com a arrumação das
peças no tabuleiro. Nesta fase as jogadas não constituem movimentos por isso é fácil
de ser efectuada, só precisamos efectuar a alteração do tabuleiro. Uma vez que os
servidores na Internet permitem a opção de gerar um tabuleiro, então não nos
preocupamos muito com esta fase.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
69
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Para a fase 2 é que temos que ter mais cuidados em termos de que tácticas
escolher. As condições dos jogadores variam e assim sendo os jogadores têm a
necessidade de mudar as suas tácticas de jogo consoante o estado do tabuleiro e as
jogadas do adversário. Desta maneira, propõe-se uma série de tácticas cada uma
para situações distintas. De salientar que este projecto também tem como objectivo
estudar e propor tácticas e estratégias de acordo com informação que se tem do
tabuleiro.
Tácticas propostas:
1. Uma vez que no início do jogo as hipóteses de jogada são poucas (só as
peças a volta do tabuleiro podem ser movidas porque as outras estão
completamente cercadas), podemos optar por fazer as jogadas que libertam
as peças da nossa cor. Assim passamos a ter mais jogadas possíveis. Esta
táctica é aconselhada no início do jogo, nas primeiras jogadas.
2. Podemos optar por fazer os movimentos sempre para posições com peças de
cor do adversário.
3. Capturar as peças ou pilhas do adversário com possibilidades de capturar
uma pilha nossa que contenha um Dvonn.
4. Efectuar movimentos para posições do adversário com possibilidades de
capturar um Dvonn. Assim podemos diminuir a probabilidade do adversário
capturar o Dvonn. Esta táctica já inclui implicitamente a captura de peças do
adversário vizinhas de algum Dvonn.
5. Efectuar jogadas de modo a capturar pilhas com Dvonn por fazer o
movimento para a posição onde se encontra o Dvonn.
6. Evitar o crescimento demasiado das nossas pilhas porque depois será difícil o
seu movimento. Para isso devemos evitar jogadas em que a posição destino
passará a ter um tamanho elevado após o acréscimo das peças da outra
pilha.
7. Ter o cuidado quando o adversário controla uma pilha com Dvonn, e avaliar
que perdas poderá ter a nível de peças se o adversário mover a pilha para
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
70
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
uma outra posição. Avaliar os movimentos da pilha e diminuir as hipóteses de
movimento da pilha.
8. Efectuar jogadas que proporcionam o menos número de perdas possíveis.
Como o custo benefício de uma jogada é dados pela conjunção de vários
atributos usando uma fórmula então torna-se difícil através desse custo tomar
decisões quanto ao número de posições que ficam movíveis no tabuleiro após
a jogada. Talvez essas perdas sejam muito significativas a ponto de o jogador
ficar sem jogadas válidas.
9. Escolher a jogada que nos dá uma melhor pontuação em relação ao nosso
adversário a nível de:
•
Mais jogadas validas
•
Mais peças em nosso poder
•
Mais posições livres para jogada
•
Menos perdas a nível de posições que o adversário
5.6.1 -
Implementação das tácticas propostas
Para este capítulo vamos descrever de uma forma sucinta como foi implementada as
tácticas propostas. Não vamos considerar muitos pormenores com respeito a
métodos implementados por serem relativamente complexos de descrever. Cada
táctica é identificada por um número, tactica(+Número,+CorJog,-Jogada). As
tácticas consideram sempre o parâmetro CorJog recebido em argumento que permite
uma resposta sobre qual a melhor jogada, tanto para o jogador como para o
adversário mediante a táctica. Por isso se quisermos podemos usar essas tácticas do
lado do adversário para ele obter sugestões de jogada.
Táctica 1
Para a táctica 1 é preciso como sempre saber quais as jogadas possíveis para a
nossa cor. Para cada uma das jogadas calcula-se o número de posições vizinhas da
nossa cor e associamos essa informação a jogada. Depois no final a jogada que tiver
um valor maior será a melhor jogada mediante esta táctica. Se tivermos mais do que
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
71
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
uma jogada com o mesmo valor, escolhe-se a jogada que tenha maior custo
beneficio. Para isso foram usados os seguintes métodos:
jogadas_possiveis_validas(+Cor,-Jogadas_Validas) – este predicado como
o próprio nome mostrar se destina a encontrar as jogadas válidas para
uma determinada cor.
A lista de retorno tem o formato: [[Pos1,Pos2], ... ] e Pos1 e Pos2 têm
o formato (Coluna,Linha).
vizinhos_a_libertar(+Jogadas_Validas,-LF) – este predicado usa a lista
de jogadas válidas para determinar quantos vizinhos da nossa cor cada
jogada liberta. Para isso terá que usar outros predicados como por
exemplo
contar_vizinhos_mesma_cor_cercados/3.
A
lista
LF
resultante
terá um parâmetro a mais que a lista Jogadas_validas que é o número de
vizinhos da nossa cor que cada jogada liberta. Portanto o formato da
lista será [[Pos1,pos2,NVizinhos], ... ].
Depois de termos a lista com a informação sobre o número de vizinhos
que cada jogada liberta usa-se o predicado
jogadas_liberta_mais_vizinhos/4
para
encontrar
a
jogada
que
liberta
mais vizinhos. Se existirem mais do que uma escolha então usa-se os
predicados
jogadas_beneficio/2
anteriormente
e
jogada_maior_custo/4
já
definidos
para escolher a jogada que tiver maior benefício em
termos de custo.
Táctica 2
A implementação desta táctica é muito simples tendo em conta alguns predicados já
definidos anteriormente. Queremos capturar as peças do adversário, para isso temos
a lista de jogadas válidas. Escolhemos avaliar apenas as jogadas (Pos1, Pos2) cuja
Pos2 pertence ao adversário. Após isso calcula-se os benefícios das mesmas jogadas
e a que tiver melhor custo é a escolhida. Métodos usados:
jogadas_para_posicoes_diferentes(+Cor,-Jogadas) – este predicado recebe
uma
determinada
cor
e
procura
as
jogadas
possíveis
apenas
para
as
posições do adversário. A lista Jogadas que é retornada tem o mesmo
formato que a lista de jogadas válidas.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
72
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
jogadas_beneficio/2 e jogada_maior_custo/4 já descritos anteriormente.
Táctica 3
Encontrar as nossas jogadas válidas para posições pertencentes ao adversário,
depois disso temos também que conhecer as jogadas possíveis do adversário para
posições onde se encontram as nossas pilhas com algum Dvonn. Depois disso temos
que ver se existe alguma jogada que possamos fazer antes, para que o adversário
não tenha mais jogadas válidas para a posição onde se encontra a pilha que
queremos proteger. Se encontrarmos alguma jogada possível então calculamos o
custo beneficio da mesma jogada. Se existirem mais do que uma jogada possível
escolhemos a que tiver maior ganho. Para essa implementação foram usados os
seguintes métodos:
jogadas_para_posicoes_diferentes/2,
jogadas_beneficio/2
e
jogada_maior_custo/4 já descritos anteriormente e ainda os predicados
que serão descritos a seguir.
jogadas_para_posicoes_com_Dvonn(+Cor,-Jogadas)
–
este
procedimento
é
parecido com o jogadas_para_posicoes_diferentes/2 com a diferença de
que aqui pretende-se encontrar os movimentos para as posições que do
adversário que do agente que controle uma peça Dvonn. A lista Jogadas
retornada terá o mesmo formato que a lista das jogadas válidas.
Dvonn_controlado_cor(+Cor,-ListaDvonn)
–
devolve
uma
lista
com
as
posições onde existe um Dvonn controlado pelo jogador com a Cor. Caso
não exista nenhuma pilha com a Cor requerida que controle algum Dvonn
retorna-se lista vazia.
Táctica 4
Esta táctica é relativamente parecida com a táctica descrita anteriormente, com um
pormenor de não avaliar apenas os movimentos do adversário para posições da
nossa cor que tenha um Dvonn mas também no caso de um Dvonn ainda não
pertencer a nenhum dos jogadores. De notar que esta táctica também faz a captura
de peças ou pilhas do adversário que são vizinhas de um Dvonn.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
73
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Táctica 5
A implementação desta táctica é igual a táctica 2 com a diferença de que queremos
capturar não as peças do adversário mas sim os Dvonns.
Táctica 6
Para esta táctica calculou-se para cada jogada possível o tamanho da pilha
resultante. Estabelecemos uma variável N, que poderá ser alterado consoante a
interpretação que quisermos, para o tamanho máximo das pilhas. Para esta
implementação foi escolhido o valor 4 para a variável N uma vez que como temos
apenas 5 linhas no tabuleiro, se uma pilha tiver tamanho maior que 4, então a pilha
terá no máximo 2 movimentos possíveis (nas direcções 1 e 4). Depois disso, como
nas outras tácticas, calculamos os benefícios para a lista encontrada e no fim
escolhe-se a jogada com maior benefício. Nesta táctica foram usadas os seguintes
predicados:
jogadas_possiveis_validas/2, jogadas_beneficio/2 e jogada_maior_custo/4
descritos acima e ainda os seguintes predicados:
calcular_tamanho_pilha_resultante(+Jogadas_Validas,-LRes) – este método
devolve uma lista resultante com o formato [[Pos1,Pos2,Tam], ... ] onde
o Tam é o tamanho que a pilha na posição 2 terá após o movimento da
pilha da posição 1 para a posição 2. Este valor será importante para
depois ser possível saber qual ou quais as jogadas que originam um
crescimento demasiado excessivo das nossas pilhas e poder descartar
essas jogadas se possível.
Para isso recorre-se ao predicado jogada_pilha_resultante_menor_N/4 que
devolve a lista com as jogadas que originam uma pilha menor que N. Este
valor fica ao critério do programador, mas neste projecto foi usado o
valor 4.
Táctica 7
Esta táctica é relativamente complexa. Para isso teremos que procurar se existe
alguma pilha que tenha um Dvonn e seja controlado pelo adversário. Depois disso
precisamos analisar as jogadas possíveis a partir da posição onde se encontra a
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
74
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
pilha. Para cada jogada possível calculamos os benefícios mas os valores serão
inversos, ou seja, como o cálculo do benefício nos dá valores para o adversário então
para nós o ganho do adversário é perda para nós. Por isso se o benefício do
adversário for 6, o benefício para nós é –6. Depois de ter esses valores podemos
optar por analisar as jogadas (Pos1,Pos2) com piores valores. O que nos interessa
neste caso são os Pos2. Para estas posições calculamos as jogadas possíveis e após
isso calcula-se os benefícios de se efectuar tais jogadas e escolhemos a jogada que
tiver maior beneficio. Resumindo, o que se pretende desta táctica é antecipar em
efectuar uma jogada que contraria um ganho que o adversário poderia ter. Ao
efectuarmos essa jogada minimizamos de alguma forma o ganho do adversário. Os
predicados usados para a implementação da táctica são:
Dvonn_controlado_cor/2, jogadas_posicao/2, jogadas_beneficio/2,
jogada_maior_custo/4 definidas anteriomente e os métodos
posicao_destino_minha_cor(+Lista,+Cor,-LRes)
uma
lista
das
jogadas
possíveis
e
a
–
Cor
este
e
predicado
procura
na
recebe
lista
os
movimentos cuja posição destino é uma posição dominada pela Cor, e
devolve na lista Lres esses movimentos. A lista terá o mesmo formato
que a lista de jogadas válidas [[Pos1,Pos2], ... ].
analisar_perdas(+Jogadas_Validas,+L,-LRes)
jogadas
válidas
adversário
sobre
do
adversário
e
o
tabuleiro.
Este
–
calcula
recebe
o
efeito
beneficio
é
uma
das
lista
de
jogadas
do
calculado
usando
o
predicado calcular_beneficio_jogada_adversario(+Jogada,-Custo). Como já
foi referido este custo é o inverso do beneficio que o adversário tem
se efectuar essa jogada.
Táctica 8
Esta táctica é muito simples de implementar considerando alguns predicados já
definidos
como
jogadas_possiveis_validas/2,
jogada_menor_custo/4,
jogada_maior_custo/4
jogadas_beneficio/2,
e
e foi preciso criar o método
jogada_perda_posicoes/3 para ser possível sabermos as perdas, em termos de
posições para cada jogada possível. Depois de efectuarmos os cálculos, de entre as
jogadas com menos perdas escolhemos a jogada com maior benefício.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
75
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
jogada_perda_posicoes(+Lista_Jogadas,+Cor,-LRes) – recebe uma lista com
as jogadas válidas e contabiliza o número de perdas da Cor em termos de
posições livres. Isto é importante porque as vezes podemos ter uma em
termos
de
peças
grande
mas
continuamos
a
ter
jogadas
válidas.
Mas
quando as perdas provocam a diminuição de muitas jogadas válidas isso
provoca quase de certeza a perda do jogo por parte do jogador.
Táctica 9
Esta táctica apresenta um grau de dificuldade maior uma vez que é preciso fazer a
recolha de muita informação tanto sobre as nossas jogadas como as do adversário.
A recolha é feita através dos métodos a seguir apresentados, onde podemos fazer
variar os argumentos de acordo com o ponto de vista a analisar. De acordo com o
identificador do jogador (cor) podemos por exemplo calcular as jogadas possíveis
validas do jogador com a cor w ou b.
jogadas_possiveis_validas/2, contar_n_pecas_pertencente_a_cor/2,
contar_posicoes_cor/2, jogada_perda_posicoes/3, jogadas_beneficio/2 e
jogada_maior_custo/4
Além destes predicados temos também o predicado calcular_ganhos/6 que irá
calcular um peso para cada jogada de acordo com a informação recolhida nos
predicados anteriores. Após isso, as jogadas com maior peso serão avaliadas
segundo os benefícios e escolhe-se a que tiver maior benefício imediato.
Para o cálculo do peso foi definida a seguinte fórmula:
DifPecas = NPecasJog - NPecasAdv,
DifPos_livres = NPosCorJog - NPosCorAdv,
Dif_Jogadas_validas = NJogadasJog - NJogadasAdv,
Peso = PerdAdv - PerdJog + DifPecas + DifPos_livres +
Dif_Jogadas_validas
Após a implementação destas tácticas surge então a necessidade de saber em que
situação aplicar cada táctica. Esta situação é respondida no nível superior, o
estratégico. Nesse nível seria necessário implementar mecanismos de escolha das
tácticas definidas e ainda a criação de algumas estratégias de jogo a longo prazo.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
76
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
Algumas possibilidades para a escolha da jogada adequada seriam:
™ Processar todas as tácticas e obter para cada táctica uma jogada e ver qual é
a melhor em termos de beneficio;
™ Escolher entre as hipóteses fornecidas pelas tácticas, a jogada escolhida por
um maior número de tácticas. Se existirem mais do que uma jogada
escolhida através de várias tácticas então opta-se como sempre por aquela
com maior benefício.
Este nível não será implementado neste projecto devido a falta de tempo disponível
para o fazer.
5.7 - Comunicação do agente com o servidor de jogos na
Internet
Como referido anteriormente pretende-se que o agente tenha uma ligação com um
servidor de jogos na Internet.
No site http://www.gamerz.net/pbmserv/commands.html, encontra-se um conjunto
de comandos para se efectuar a comunicação entre o nosso agente e o referido
servidor.
Comandos de administração como por exemplo:
signup userid password [ e-mail address(es) ]
change password userid current-password new-password
signoff userid password
Comandos de Informação
game help
game games userid* [ all | active | inactive | next ]
game show board[#moveno]+ [ -t ]
Comandos de jogar
game challenge userid1 userid2 [-options]
game move board userid password move[#moveno]
game move board userid password pass[#moveno]
etc…
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
77
Instituto Superior de Engenharia do Porto
Capítulo 5 – Implementação agente Dvonn
De entre os vários comandos descritos no site que nos poderá servir ao longo de um
jogo, o que nos interessa mais para a implementação do agente é o comando de
movimentar as pilhas de um lado para o outro (game move board userid password
move[#moveno]).
Como vemos o servidor aceita uma string neste formato onde o os parâmetros com
o estilo de letra bold serão valores que variam conforme a informação que temos do
jogo. Board é o código que identifica o tabuleiro na lista de tabuleiros do servidor
porque este poder ter vários jogos com vários jogadores a jogar ao mesmo tempo
em vários pontos da Internet. Userid é o identificador do jogador e também precisa
também de uma password para que o servidor possa aceitar o pedido de jogada.
Estes valores board, userid e password são gerados pelo servidor e disponibilizados
ao jogador antes de inicio um jogo. Assim o servidor fornece também o tabuleiro e a
cada jogador uma cor com a qual irá jogar. Finalmente o agente terá que gerar o
movimento tendo em conta as suas capacidades de avaliar qual a melhor jogada e
envia a string construída ao servidor. O servidor deverá confirmar ou não a jogada e
quando o adversário efectuar uma jogada o servidor deverá também enviar ao
agente a jogada efectuada pelo adversário.
O nosso agente inteligente não foi testado na Internet devido a falta de tempo
disponível para o fazer. Para fazer o teste teríamos que ter um conjunto de
informações exactas, como por exemplo qual o formato do tabuleiro que o servidor
de jogos envia aos participantes, saber a localização do mesmo servidor e as
possibilidades de poder existir esta mesma comunicação. A figura 22 mostra-nos de
uma forma simplificada a ligação que existirá entre o agente, o servidor e o jogador.
O servidor se encontra no meio e é ele que controla o jogo, os participantes não se
comunicam entre si directamente.
Figura 22 – Comunicação entre os participantes do jogo
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
78
Capítulo 6
Conclusão
Durante o desenvolvimento do projecto e a elaboração do relatório foram
encontrados diversos problemas, relatados ao longo do relatório. Realmente os
princípios da teoria de jogos podem ser aplicados a muitas situações da vida real. No
entanto, encontrar informação específica sobre como os princípios são aplicados nos
jogos em si é difícil.
Sabemos que se usa muito a Inteligência Artificial como forma de dotar os
programas de alguma capacidade de tomar decisões em determinado momento,
tendo em conta sempre os factores externos e internos do jogo. Nesta ordem de
ideias para foi relativamente muito difícil elaborar este documento e principalmente o
desenvolvimento da parte prática deste projecto que não ficou concluída. Quanto a
como a inteligência artificial é usada nos jogos encontramos apenas informação
teórica e também alguma informação breve sobre os requisitos de memória e
processamento que tais programas de jogos exigem.
Apesar destes problemas este trabalho foi muito desafiador e interessante. Devido a
falta de tempo o projecto não fica concluído, como se pode perceber existe uma
quantidade enorme de coisas por detrás duma aplicação de jogos deste tipo.
Alguns melhoramentos que futuramente poderiam ser acrescentadas são os
seguintes:
™ Estudar as estratégias de modo a saber em cada instante quais as melhores
tácticas aplicar;
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
79
Instituto Superior de Engenharia do Porto
Capítulo 6 – Conclusão
™ Encontrar um servidor na Internet e tentar estudar uma forma de se poder
efectuar uma ligação entre o agente e o servidor. Que parâmetros seriam
precisos, como por exemplo localização do servidor, porto, etc. Também seria
preciso conhecer o ficheiro com a informação do tabuleiro que o servidor
envia ao agente para ser analisado e para que o agente possa tratar essa
informação;
™ Criar estratégias com grau de visibilidade boa (estratégias que consigam
efectuar uma analise 2, 3, ..., n jogadas a frente).
Se o tempo permitisse ainda poderiam ser exploradas outras hipóteses para
melhorar a tomada de decisão do agente. Assim como um humano vai aumentando
o seu grau de inteligência a medida em que se familiariza com um jogo, poderiamos
também com o tempo descobrir outras tácticas que poderiam ajudar a melhorar a
inteligêcia do agente. Enfim existe muita coisa que poderia ser acrescentado mas,
considera-se bom ter chegado até aqui.
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
80
Instituto Superior de Engenharia do Porto
Bibliografia e Referências
[1]
Inteligência Artificial, Elaine Rich - McGraw-Hill
[4]
Carlos Duarte Costa e Kely C. Paintner Hauser - documento sobre
Teoria dos Jogos
http://oeconomista.com/wm/wmview.php?ArtID=689
Data acesso: 12 Março 2004
[6]
Centro Universitário Ibero-Americano
Teoria dos Jogos
http://www.unibero.edu.br/nucleosuni_neriteo05.asp
Data acesso: 12 Março 2004
[9]
Nogueira,
Fernando
–
Apontamentos
de
DISCIPLINA:
MODELAGEM
E
SIMULAÇÃO.
Universidade Federal de Juiz de Fora, Brasil.
[11]
Alunos
de
Pós-Graduação
do
Departamento
de
matemática,
Pontifícia
Universidade Católica do Rio de Janeiro, Brasil
http://www.mat.puc-rio.br/~inicient/3_jogos/index_jogos.htm
Data acesso: 15 Março 2004
[13]
Alunos
de
Pós-Graduação
do
Departamento
de
matemática,
Pontifícia
Universidade Católica do Rio de Janeiro, Brasil
http://www.mat.puc-rio.br/~inicient/3_jogos/somazero.htm
Data acesso: 15 Março 2004
[15]
Alunos
de
Pós-Graduação
do
Departamento
de
matemática,
Pontifícia
Universidade Católica do Rio de Janeiro, Brasil
http://www.mat.puc-rio.br/~inicient/3_jogos/somanaozero.htm
Data acesso: 15 Março 2004
[16]
Tatai,
Victor
Kazuo
-
Técnicas
de
Sistemas
Inteligentes
Aplicadas
Desenvolvimento de Jogos de Computador Agosto 2003.
Universidade Estadual de Campinas
Faculdade de Engenharia Eléctrica e de Computação
Departamento de Engenharia de Computação e Automação Industrial
[17]
Inteligência Artificial, Elaine Rich e Kevin Knight
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
81
ao
Instituto Superior de Engenharia do Porto
[18]
http://www.gipf.com/Dvonn/
Data acesso: 10 Março 2004
[19]
http://www.gamerz.net/pbmserv/Dvonn.html
Data acesso: 10 Março 2004
[21]
Pedro Luis Kantek Garcia Navarro
http://www.pr.gov.br/batebyte/edicoes/1997/bb65/deepblue.htm
Data acesso: 5 de Agosto de 2004
[23]
Polyane Alves Santos
Universidade Estadual de Danta Cruz - Brazil
Departamento de Ciências exatas e tecnológias
Introdução a teoria dos jogos
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
82
Instituto Superior de Engenharia do Porto
Acrônimos
IA – Inteligência Artificial
SI – Sistemas Inteligentes
IDA* – Iterative Deepening A*
SMA* – Simplified memory-bounded A*
MiniMax – Algoritmo de busca em profundidade numa árvore
Marlene da Graça Santos nº 980975 Ramo de Computadores e Sistemas
83