Desenvolvimento de um Agente Inteligente para jogar

Departamento de Engenharia Informática

Instituto Superior de Engenharia do Porto

Instituto Politécnico do Porto

Desenvolvimento de um Agente Inteligente

para jogar Carcassonne

Bruno Miguel Araújo Cardoso

Projecto de Licenciatura

Setembro 2004

Desenvolvimento de um agente inteligente para jogar Carcassonne

Instituto Superior de Engenharia do Porto

Desenvolvimento de um agente inteligente para jogar

Carcassonne


Setembro 2004

Tema:


Autor:


nº 990283

Disciplina:

Projecto de Licenciatura

Curso:

Engenharia Informática, ramo de Computadores e Sistemas

Data de entrega:

Setembro de 2004

Orientador:

Eng.º António Jorge Santos


Resumo

Pretende-se através deste projecto desenvolver um agente inteligente que

possua capacidades para jogar Carcassonne, sendo este um jogo de tabuleiro

de 1 a 5 jogadores. Foi necessário enquadrar este jogo numa área de jogos, ou

seja, procurar determinar em que tipo de jogos este se insere, para estudar as

técnicas existentes de forma a adapta-las ao jogo em questão.

Para que o agente seja capaz de competir com um humano, será necessário

que este seja dotado de inteligência e raciocínio, que lhe permitam tomar

decisões sobre as jogadas a efectuar. Esta tomada de decisão deve ser

efectuada mediante 3 níveis de abstracção, sendo estes, o nível operacional, o

táctico e o estratégico. Cada um destes vai corresponder a um nível de

conhecimento.

No nível operacional estão compreendidas as estruturas e representações de

baixo nível necessárias à mecânica do jogo. No táctico entram os conceitos de

áreas e definem-se jogadas a efectuar para atingir objectivos de curto prazo.

No nível estratégico é efectuada a tomada de decisão tendo em conta os

objectivos definidos a longo prazo. Neste nível decide-se quais as tácticas a

aplicar mediante a situação corrente, sendo este o nível onde existirá mais e

melhor conhecimento. A melhor representação de entidades sobre este

conhecimento resulta numa aplicação mais eficiente, já que para o jogo em

questão podem ser adoptadas várias representações consoante o nível de

abstracção.


Aos meus pais

e ao meu irmão.


Agradecimentos

Quero agradecer à minha família pelo apoio que me demonstraram, e

nomeadamente ao meu irmão Paulo que teve um acompanhamento muito

próximo deste projecto e me ajudou em todos os momentos.

À minha namorada Telma que teve sempre toda a paciência para me aturar, e

apoiar nos bons e maus momentos por quais passei ao longo destes meses.

Ao meu orientador Jorge Santos, pelos seus conselhos e esclarecimentos ao

longo deste projecto, assim como o seu empenho. As suas opiniões e ideias

foram extremamente importantes para a fase de implementação.

Aos meus colegas de curso que frequentaram a licenciatura comigo, e que

sempre estiveram dispostos a ajudar. Quero deixar também a minha palavra

especial aos meus colegas e amigos que me apoiaram e ajudaram no

desenvolvimento do projecto.

Aos meus amigos mais próximos, que sempre me apoiaram e me incentivaram.

A todas estas pessoas um muito obrigado.


________________________________________________________________

2004 ISEP – Dep. De Engenharia Informática i

Índice de Conteúdos

Índice de Conteúdos ------------------------------------------------------- i

Índice de Figuras---------------------------------------------------------- iii

Índice de Listagens-------------------------------------------------------- iv

Índice de Tabelas-----------------------------------------------------------v

1. Introdução ---------------------------------------------------------------1

1.2 Motivação------------------------------------------------------------------------- 2

1.3 Estrutura do relatório ----------------------------------------------------------- 3

2. Teoria dos Jogos---------------------------------------------------------6

2.1 Raciocínio------------------------------------------------------------------------- 7

2.2 Conceitos ------------------------------------------------------------------------- 8

2.2.1 “Equilíbrio” de John Nash-------------------------------------------------10

2.3 Tipos de Jogos ------------------------------------------------------------------13

2.3.1 Jogos não Cooperativos---------------------------------------------------13

2.3.1.1 Teorema Minimax------------------------------------------------------------------ 14

2.3.2 Jogos Cooperativos--------------------------------------------------------15

2.3.3 Jogos de Informação perfeita e imperfeita -----------------------------16

2.3.4 Jogos de Informação Completa e Incompleta--------------------------16

2.4 História da Teoria dos Jogos --------------------------------------------------17

3. O Jogo Carcassonne --------------------------------------------------- 21

3.1 Introdução-----------------------------------------------------------------------21

3.2 Objectivo do Jogo --------------------------------------------------------------22

3.3 Regras do Jogo -----------------------------------------------------------------22

3.3.1 Material do Jogo -----------------------------------------------------------22

3.3.2 Preparação do Jogo -------------------------------------------------------24

3.3.3 Posicionamento de Peças -------------------------------------------------24

________________________________________________________________

2004 ISEP – Dep. De Engenharia Informática ii

3.3.4 Desenvolvimento do Jogo ------------------------------------------------25

3.3.5 Posicionamento de seguidores -------------------------------------------25

3.3.6 Pontuação ------------------------------------------------------------------27

4 Desenvolvimento do agente inteligente------------------------------ 32

4.1 Descrição do problema---------------------------------------------------------32

4.2 Caracterização do jogo---------------------------------------------------------33

4.3 Análise do problema------------------------------------------------------------33

4.3.1 Análise da complexidade do problema----------------------------------34

4.4 Arquitectura utilizada-----------------------------------------------------------37

4.5 Modelo de dados----------------------------------------------------------------38

4.6 Funcionamento agente/servidor ----------------------------------------------48

4.7 Algoritmos principais e funcionamento do agente --------------------------57

4.7.1 Jogar ------------------------------------------------------------------------57

4.7.1.1 Gerar Jogadas Válidas------------------------------------------------------------- 59

4.7.1.2 Pontuar Jogadas Localmente---------------------------------------------------- 64

4.8 Exemplo de uma jogada-------------------------------------------------------68

4.9 Nível Táctico e Estratégico-----------------------------------------------------70

4.10 Comunicação com um servidor de jogos na Internet ---------------------71

5. Conclusão -------------------------------------------------------------- 74

Bibliografia---------------------------------------------------------------- 77

________________________________________________________________

2004 ISEP – Dep. De Engenharia Informática iii

Índice de Figuras

Figura 1 – Árvore do algoritmo Minimax..................................................... 14

Figura 2 - Klaus-Jürgen Wrede.................................................................. 21

Figura 3 - Seguidores............................................................................... 22

Figura 4 – Placa de contagem dos pontos .................................................. 22

Figura 5 – Peças do Jogo ......................................................................... 23

Figura 6 – Posicionamento de peças .......................................................... 24

Figura 7 – Posicionamento de seguidores................................................... 25

Figura 8 – Colocações possíveis e impossíveis do peão ................................ 26

Figura 9 – Estrada acabada e inacabada .................................................... 28

Figura 10 – Cidade acabada e inacabada.................................................... 28

Figura 11 – Mosteiro acabado................................................................... 29

Figura 12 – Peça inicial do jogo Carcassonne.............................................. 34

Figura 13 – Níveis de decisão do agente .................................................... 35

Figura 14 – Arquitectura da aplicação ........................................................ 37

Figura 15 – Exemplo de uma peça do jogo Carcassonne .............................. 41

Figura 16 – Tabuleiro numa fase inicial ...................................................... 43

Figura 17 – Recurso fechado .................................................................... 44

Figura 18 – Recurso Aberto ...................................................................... 45

Figura 19 – Caixa de diálogo do jogador .................................................... 48

Figura 20 – Caixa de diálogo do servidor.................................................... 56

Figura 21 – Rotação de uma peça ............................................................. 61

________________________________________________________________

2004 ISEP – Dep. De Engenharia Informática iv

Índice de Listagens

Listagem 1 – Conexão ao servidor............................................................. 49

Listagem 2 – Handler de recepção de mensagens ....................................... 50

Listagem 3 – Interpretador Jogador........................................................... 50

Listagem 4 – Interpretador jogada ............................................................ 51

Listagem 5 – Gerar lista de posições livres ................................................. 52

Listagem 6 – Verificar posição................................................................... 52

Listagem 7 – Interpretador termo ............................................................. 53

Listagem 8 – Interpretador tabuleiro e lista_PosLivres ................................. 53

Listagem 9 – Interpretador peça ............................................................... 54

Listagem 10 – Gerar sequência de peças.................................................... 55

Listagem 11 – Gerar Peça ........................................................................ 56

Listagem 12 - Jogar................................................................................. 58

Listagem 13 – Gerar jogadas válidas.......................................................... 59

Listagem 14 - Rotação ............................................................................. 60

Listagem 15 - Vizinhos............................................................................. 62

Listagem 16 - Encaixa.............................................................................. 63

Listagem 17 – Pontuar jogadas ................................................................. 65

Listagem 18 – Avaliar jogadas .................................................................. 67

Listagem 19 – Comandos de um servidor de jogos...................................... 71

________________________________________________________________

2004 ISEP – Dep. De Engenharia Informática v

Índice de Tabelas

Tabela 1 – Consequências possíveis dos suspeitos ...................................... 12

Tabela 2 – Campos do tuplo Centro........................................................... 40

________________________________________________________________

2004 ISEP – Dep. De Engenharia Informática vi


2004 ISEP – Dep. De Engenharia Informática 1

1. Introdução

Os jogos são certamente um dos divertimentos preferidos para a maior parte

das pessoas. Desde que a informática existe, a hipótese dos computadores

serem capazes de jogar mediante o conhecimento adquirido, é admitida.

Assim, para os computadores possuírem características autónomas, a

Inteligência Artificial exerce um papel fundamental, através de métodos e

algoritmos que contribuem para uma boa tomada de decisão. A indústria dos

jogos de computador, já com um crescimento considerável, é um grande

estímulo para o desenvolvimento da Inteligência Artificial.

A avançada tecnologia de computação gráfica em tempo real torna os cenários

e personagens dos jogos impressionantemente realísticos, e o jogador passa a

esperar o mesmo nível de realidade no comportamento das personagens e de

outras entidades controladas pelo computador. Esta situação vem motivando,

nos últimos anos, o desenvolvimento de várias áreas na Inteligência Artificial,

como Agentes Inteligentes e Aquisição de Conhecimento. Isto porque começam

a ser desenvolvidos Sistemas de Agentes Inteligentes para coordenar as acções

das personagens do jogo controlados pelo computador. A interacção das

personagens com o jogador, e as reacções daqueles em virtude das atitudes

deste, passam a ser governadas por um sistema autónomo que, em alguns

casos, é capaz de aprender com situações passadas, adaptando-se

dinamicamente às novas situações de jogo.

Desde sempre que vários artigos são publicados com o intuito de evoluir no

campo da Inteligência Artificial, e desenvolver mecanismos e métodos cada vez

mais eficientes para competir com os seres humanos

________________________________________________________________

2004 ISEP – Dep. Engenharia Informática 2

A área dos jogos além de ser altamente motivante para o desenvolvimento de

técnicas da Inteligência Artificial, assume-se também como um excelente

domínio para a exploração da inteligência da máquina. Os jogos constituem

uma tarefa estruturada na qual a medição do sucesso ou fracasso é simples.

Assim para este projecto pretende-se o estudo e desenvolvimento de um

agente inteligente capaz de jogar Carcassonne, um jogo de tabuleiro

relativamente recente (2001), onde será necessário uma abordagem diferente

dos jogos normais neste campo, como o xadrez, damas, etc. Pretende-se o

desenvolvimento de um agente que seja capaz de competir com outro jogador

humano ou não. Para este será necessário um estudo profundo sobre o tipo de

jogo em questão, encontrar e avaliar soluções possíveis assim como tácticas e

estratégias utilizadas nos jogos em geral e como adaptar ao jogo Carcassonne.

Deve-se então escolher uma solução tentando adaptá-la ao pretendido, ou

então optar pela criação de métodos próprios para o problema.

Para o desenvolvimento do agente inteligente optou-se pela utilização da

linguagem PROLOG, dado o nível de abstracção proporcionado para a

representação de conhecimento e dada a sua eficácia na área da Inteligência

Artificial e agentes inteligentes. O interpretador utilizado foi o Win-Prolog 4.32,

sendo este o disponível no ISEP onde é utilizado na aprendizagem desta

linguagem ao longo do curso nas disciplinas da área da Inteligência Artificial.

1.2 Motivação

Dados os projectos disponíveis para escolha, este destacava-se. O fascínio

pelos jogos de computador e a aprendizagem do real funcionamento do jogador

representado pelo computador contra o utilizador estiveram na base da opção

deste entre os listados. Antes da tomada de decisão pela escolha deste projecto

teve lugar uma conversa com o orientador Jorge Santos sobre o projecto

propriamente dito, o que levantou mais interesse sobre o mesmo. Ser capaz de

________________________________________________________________


produzir um programa autónomo que pudesse vencer um utilizador é realmente

um desafio verdadeiramente interessante.

O facto do projecto implicar uma parte prática leva à ponderação sobre o

trabalho e empenho necessário para o desenvolvimento e, apesar de se

considerar um projecto bastante difícil em comparação com os de pesquisa

bibliográfica, o gosto pela linguagem PROLOG e pelos jogos motivaram

bastante a escolha.

1.3 Estrutura do relatório

A organização deste documento está subdividida em 5 capítulos partindo deste

capítulo introdutório, passando pela pesquisa teórica sobre o assunto em

questão, seguidamente pelo desenvolvimento do trabalho e finalmente a

conclusão.

No capítulo 2 é feita uma abordagem geral à teoria dos jogos e é efectuado o

enquadramento do jogo Carcassonne numa área de jogos, ou seja, num tipo de

jogo. São referidos alguns conceitos sobre a teoria dos jogos e história da

mesma.

Através do capítulo 3 é possível compreender o funcionamento do jogo assim

como as regras que o caracterizam.

No capítulo 4 está descrita a implementação realizada no decorrer do projecto,

assim como a análise do problema proposto e soluções possíveis. É abordada a

representação de entidades e explicados os algoritmos mais importantes

necessários à implementação do agente inteligente.

No capítulo 5 é efectuada uma reflexão geral sobre o desenvolvimento do

trabalho, a descrição de algumas dificuldades que surgiram, algumas

considerações sobre um possível trabalho futuro a ser acrescentado e aspectos

________________________________________________________________


a serem melhorados para um melhor e mais eficiente funcionamento do

agente.

Para a elaboração deste documento foi utilizado o tipo de letra tahoma com o

tamanho 12 e para referências a porções de código é utilizado o tipo de letra

Lucida Console, assim como linhas numeradas para as maiores porções.

________________________________________________________________




2. Teoria dos Jogos

A teoria dos jogos é o estudo da forma como as pessoas interagem e tomam

decisões. Esta larga definição aplica-se à maioria das ciências sociais, mas a

teoria dos jogos utiliza modelos matemáticos supondo que o comportamento de

cada pessoa interfere no bem estar dos intervenientes no jogo. Estes modelos

são normalmente abstracções completamente simplificadas de interacções do

mundo real.

A teoria dos jogos é a ciência da estratégia. Ela procura determinar matemática

e logicamente as atitudes que os “jogadores” devem tomar para garantir os

melhores resultados para si próprios num conjunto alargado de “jogos”. O

amplo leque de “jogos” vai do xadrez à educação dos filhos, do ténis à

economia.

A teoria dos jogos foi criada na década de 40 pelo matemático John Von

Newmann e recentemente, o matemático John Nash efectuou um novo estudo

sobre o “equilíbrio” e foi galardoado com o prémio Nobel de economia em

1994.

John Von Newmann desenvolveu esta teoria com o intuito de poder ser

aplicada em várias situações e não apenas aos jogos. Qualquer situação onde

exista competição, onde cada interveniente procura maximizar os seus ganhos

e perdas dos outros, é aplicável à teoria dos jogos. Situações essas que podem

abranger política, economia, tácticas de guerra, competitividade no comércio,

tendo estas factores facilmente quantificáveis. É de salientar que a teoria dos

jogos não envolve a componente humana e emocional que podem afectar

problemas reais tais como conflitos militares.

________________________________________________________________


A essência de um jogo está na interdependência estratégica: a sequencial e a

simultânea. Na primeira, os jogadores movem-se em sequência, estando cada

um deles consciente das acções anteriores dos outros. Na segunda, os

jogadores agem ao mesmo tempo, cada um deles ignorando as acções dos

outros.

Os jogos são fundamentalmente diferentes de decisões tomadas num ambiente

neutro. Quando um lenhador decide a forma de cortar uma árvore, não está à

espera de que esta se defenda; o ambiente é neutro. Mas quando um general

tenta derrotar o exército do inimigo, tem de prever e ultrapassar a resistência

dos planos do oponente. Tal como o general, um jogador deve reconhecer a

sua interacção com outras pessoas inteligentes e decididas. A sua própria

escolha deverá ter em linha de conta tanto as possibilidades de conflito como

as de cooperação. A teoria dos jogos não pretende resolver todos os tipos de

conflitos, porém permite uma melhor compreensão em situações complicadas,

através das suas variadas técnicas para analisar estes problemas

2.1 Raciocínio

Um dos princípios gerais pelo qual se deve guiar um jogador num jogo

sequencial é o de prever o futuro e raciocinar sobre o passado. Cada jogador

deve tentar perceber a forma de como os outros jogadores vão reagir à sua

jogada, e como ele próprio vai reagir na sua vez, e assim sucessivamente. O

jogador avalia as consequências das suas decisões iniciais, e utiliza essa

informação para definir a melhor opção em cada momento. Quando os

jogadores pensam nesta sequência de reacções, devem colocar-se na posição

do adversário e pensar como ele; não deve impor-lhe a sua própria linha de

raciocínio.

Em princípio, qualquer jogo sequencial que termine após uma sequência finita

de jogadas pode ser completamente “resolvido”. Para determinar a melhor

estratégia de cada jogador deve-se considerar qualquer resultado possível.

________________________________________________________________


Certos jogos simples, como o “jogo do galo”, podem ser resolvidos desta forma,

não constituindo, portanto, um grande desafio. Mas no caso de outros jogos,

como o xadrez, os cálculos são demasiado complexos para funcionarem na

prática, mesmo com o auxílio de computadores. Assim, os jogadores prevêem

algumas das jogadas seguintes e tentam avaliar as posições que daí resultem

com base na experiência.

Ao contrário da cadeia linear de raciocínios sequenciais, os jogos com jogadas

simultâneas implicam a existência de um circulo lógico. Embora os jogadores

tomem decisões ao mesmo tempo, ignorando as acções simultâneas dos

outros, cada um deles deve estar consciente de que existem outros jogadores

que, por sua vez, estão simultaneamente conscientes, e assim sucessivamente.

O raciocínio é o seguinte: “Eu penso que ele pensa que eu penso...”. Por

conseguinte, cada qual deverá colocar-se, em sentido figurado, na pele de

todos e tentar calcular o resultado. A melhor jogada de cada um é parte

integrante deste cálculo global.

2.2 Conceitos

• Jogo

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). Existem certas regras para cada jogo, que

fornecem as condições para que este comece e definem as jogadas

consideradas legais durante as diferentes fases do jogo, o número

total de jogadas que constitui uma partida completa e os possíveis

resultados quando a partida termina.

• Jogada

Uma jogada ou movimento é a forma como progride o jogo de uma

fase para outra, a partir da posição inicial até o último movimento.

Podem ser alternativas ou simultâneas; acontecem tanto por causa

de uma decisão pessoal quanto por azar. Assim, por exemplo, uma

________________________________________________________________


roleta gera uma determinada jogada, cuja probabilidade pode ser

calculada.

• Resultado

Designa o que acontece quando uma partida termina.

• Informação completa

Jogos com informação completa são aqueles em que todas as

jogadas são conhecidas pelos intervenientes. Assim, o xadrez é um

jogo com informação perfeita (completa), enquanto que o poker não

pode ser classificado como tal, já que um jogador não tem

conhecimento sobre a carta que o outro escolhe.

• Payoff

Ganho de uma 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 é equivalente ao ganho para o

adversário desse valor.

• Estratégia:

Uma estratégia é uma lista das escolhas óptimas para um jogador.

Nesta lista já estão previstas as situações possíveis que o jogador

poderá enfrentar. Assim, através de uma estratégia, este saberá o

que fazer em qualquer momento do jogo, sem se importar com o que

seu adversário possa fazer. Nesta fase, ao contrário das pontuações

locais, faz-se uma avaliação a longo prazo de uma determinada

jogada com o objectivo de ganhar o jogo.

Para esta análise existem 3 níveis até delinear uma estratégia.

Inicialmente no nível operacional interessam as regras do jogo e

pontuações imediatas, seguidamente o nível táctico em que está

________________________________________________________________


presente o conceito de áreas, defesa de recursos, etc, e um terceiro

nível que será o estratégico que pressupõe um conhecimento mais

vasto sobre o jogo e é mediante este conhecimento que se efectua a

tomada de decisão.

2.2.1 “Equilíbrio” de John Nash

O círculo lógico do raciocínio conduz a uma conclusão por meio de um conceito

de “equilíbrio” desenvolvido pelo matemático de Princeton, John Nash.

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*.

Procura-se um conjunto de escolhas, uma para cada jogador, de tal forma que

a estratégia de cada um seja a melhor quando os restantes estiverem a jogar

de acordo com as melhores estratégias deles. Por outras palavras, cada um

escolhe a melhor reacção àquilo que os outros fazem.

Por vezes, a melhor opção de uma pessoa é sempre a mesma,

independentemente daquilo que os outros fazem. A isto chama-se uma

“estratégia dominante”, enquanto que, outras vezes, um jogador tem uma

opção frequentemente má ao que se chama uma estratégia dominada1. A

procura de um equilíbrio deve começar pela procura de estratégias dominantes

e a eliminação das estratégias dominadas.

Quando se afirma que um resultado é um equilíbrio, não quer dizer que a

melhor escolha de cada jogador conduza a um resultado óptimo. De facto,

existem exemplos famosos, tal como o dilema dos prisioneiros de Albert W.

1 no sentido em que qualquer outra opção é melhor para ele independentemente daquilo que os outros façam

________________________________________________________________


Tucker em 1950 (descrito seguidamente), em que os jogadores são conduzidos

a um mau resultado seguindo cada um os seus interesses particulares.

A noção de equilíbrio de Nash permanece uma solução incompleta para o

problema do raciocínio circular em jogos de jogadas simultâneas. Alguns jogos

possuem muitos equilíbrios deste género, ao passo que outros não. E o

processo dinâmico que pode conduzir a um equilíbrio não chega a ser

especificado. Mas, apesar destas lacunas, o conceito revelou ser extremamente

útil para a análise de muitas interacções estratégicas.

A seguir é exemplificada uma interacção estratégica que ilustra alguns do

princípios fundamentais da teoria de jogos:

“O dilema dos prisioneiros”

Dois suspeitos A e B acusados do mesmo crime, são interrogados

separadamente, cada um deles podendo confessar ou manter-se em silêncio.

Se os dois suspeitos se mantiverem calados serão submetidos a uma pena de 1

ano. Se o suspeito A se mantiver em silêncio, o suspeito B pode obter um

melhor acordo confessando, sendo libertado e condenando A a uma pena de 3

anos. Se A confessar, B fará melhor em confessar também, para evitar um

tratamento especialmente severo, assim a sentença aplicada será de 2 anos

para cada um deles. As decisões são simultâneas e um não sabe nada sobre a

decisão do outro.

A confissão é a estratégia dominante de B. O mesmo é verdade para A. Assim,

em equilíbrio, ambos confessam, embora ambos pudessem ficar em vantagem

se se mantivessem calados. Semelhante comportamento cooperante pode ser

alcançado em repetidas jogadas do jogo, já que o ganho temporário que

resulta da “batota” (a confissão) pode ser suplantado pela perda a longo prazo

provocada pela quebra de cooperação.

________________________________________________________________


Assim sendo podemos sistematizar as possibilidades dos dois suspeitos na

tabela seguinte:

B fica calado B Confessa

1 ano para A B fica livre A fica calado

1 ano para B 3 anos para A

A fica livre 2 anos para A A confessa

3 anos para A 2 anos para B

Tabela 1 – Consequências possíveis dos suspeitos

Analisando a tabela 1, para qualquer um dos prisioneiros, o melhor resultado

possível é trair e o outro ficar calado. E até mesmo se o outro o trair, o suspeito

sai em vantagem por não colaborar também, já que ficando em silêncio está

sujeito a ser condenado a uma pena de três anos de cadeia, enquanto que se

confessar, só está sujeito a dois. Isto é, seja qual for a opção do outro, o

prisioneiro terá mais vantagens em confessar.

O único problema é que ambos chegarão a essa conclusão: a escolha mais

inteligente é trair. Essa lógica vai, desta forma, condenar a ambos dois anos de

cadeia. Se os dois se mantiverem em silêncio, existe um ganho maior para

ambos, mas a probabilidade de isso acontecer é menor.

O conceito de John Nash define uma solução estratégica ou equilíbrio de um

jogo como um ponto onde cada jogador não tem vantagens em alterar a sua

estratégia se os adversários não o fizerem. Ou seja, se um dos intervenientes

alterar a estratégia poderá piorar a sua situação porque o adversário poderá

alterar a dele e vencer.

________________________________________________________________


Considerando o dilema de prisioneiros, a situação em que ambos confessam, é

a única combinação em que se pode considerar o equilíbrio de Nash porque é a

única estratégia vantajosa para os dois suspeitos.

2.3 Tipos de Jogos

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. De acordo a possibilidade ou não de

comunicação e a quantidade e tipo de informação acessível, os jogos podem

ser divididos em:

• Jogos cooperativos (soma não zero)

• Jogos não-cooperativos (soma zero)

• Jogos de informação completa, incompleta, perfeita e imperfeita.

2.3.1 Jogos não Cooperativos

Os jogos não-cooperativos, onde estão incluídos os jogos de soma zero, são

caracterizados por um confronto de interesses estritamente competitivo. São

situações nas quais para um jogador vencer, o outro tem necessariamente de

perder, ou então as partes terminam o jogo sem saldo algum. Diz-se que um

jogo é de soma zero se o total dos ganhos ao final da partida é nulo, isto é, se

o total de ganhos é igual ao total de perdas. Considerando um jogo com dois

jogadores o total dos ganhos de um jogador é igual ao total de perdas do

adversário. Nos jogos de soma zero não há possibilidade de cooperação entre

dois agentes egoístas, já que os seus interesses são totalmente opostos.

Estes proíbem a comunicação prévia, apesar de existirem situações em que a

sinalização acontece, bem como o encontro de convenções que ajudam a

coordenar as acções dos agentes, com base no conhecimento comum

partilhado pela cultura, convívio social ou capacidade cognitiva dos jogadores.

________________________________________________________________


Nestas ocasiões, um efeito chamado de "telepatia" surge como forma de

comunicação implícita entre pessoas de uma mesma língua ou habitantes de

uma mesma região ou grupo social, dotados de mentes semelhantes e

conhecimento comum.

2.3.1.1 Teorema Minimax

Os jogos de dois jogadores com soma zero são o principal objecto de estudo da

teoria matemática dos jogos. É também bastante conhecido, senão o mais, o

algoritmo Minimax que permite gerar soluções propícias à vitória em jogos de

soma zero.

O Minimax é um procedimento de busca em profundidade, sendo esta limitada

[Elaine Rich, Kevin Knight, 1993]. A busca é efectuada através de uma árvore

de movimentos (Figura 1) em que se tenta maximizar a probabilidade de

vencer o jogo, enquanto que o adversário tenta fazer o contrário. Começando

na posição actual, gera-se movimentos possíveis para criar um conjuntos de

posições sucessoras possíveis. Depois da avaliação estática a cada uma destas

posições possíveis escolhe-se a melhor. O valor é retornado à posição inicial

para essa avaliação ser representada. A posição inicial é tão boa como a

posição gerada pelo melhor movimento a ser executado a seguir. O objectivo

neste ponto é obter o valor máximo da avaliação estática na próxima posição

do tabuleiro.

Max

Min

Max

Figura 1 – Árvore do algoritmo Minimax

50

50 32 28

73 50 32 28 33 62

________________________________________________________________


Sendo este o algoritmo mais usado no mundo da teoria dos jogos, o Minimax

não é aplicável a jogos com informação incompleta. Pelo contrário o algoritmo

Minimax pressupõe a informação completa sobre o jogo.

2.3.2 Jogos Cooperativos

Jogos cooperativos, ou jogos de soma não zero, são aqueles em que a

comunicação prévia é permitida entre os jogadores, antes de decidirem a

estratégia que usam durante o jogo. Para ser eficaz, a comunicação precisa ser

livre de distorção e sem qualquer custo para os intervenientes, isto é, a

emissão de mensagens não implica uma alteração directa da matriz original do

jogo.

Os jogos de soma não zero diferem 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. Neste tipo de jogos não

é necessário que o ganho de um jogador seja a perda do adversário. 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. Para os jogos de soma zero o teorema

Minimax garante uma boa solução, 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 referir que o conceito de equilíbrio de Nash descrito

na secção 2.3.1, não se aplica apenas aos jogos de soma não zero, mas

também aos jogos de soma zero, por verificar que neste caso esta teoria é

equivalente ao teorema Minimax.

________________________________________________________________


2.3.3 Jogos de Informação perfeita e imperfeita

Nos jogos de informação perfeita, por meio de indução inversa, os jogadores

podem conhecer toda história do jogo, antes mesmo de tomarem as suas

decisões. Todos os conjuntos de informação de uma árvore de jogo de

informação perfeita são unitários. O que permite dizer que cada parte sabe em

qual nó de um jogo sequencial está. Caso contrário, o jogo é chamado de

informação imperfeita. Os participantes que se lembram, a cada jogada, de

todas as anteriores efectuadas desde o início do jogo possuem memória

perfeita, enquanto que nos jogos em que não é possível ter toda essa

informação do passado possuem memória imperfeita.

2.3.4 Jogos de Informação Completa e Incompleta

Existindo ou não comunicação, quando os jogadores têm pleno conhecimento

do número de participantes, da posição que cada um ocupa em cada etapa do

jogo e dos resultados que todos podem obter, diz-se que o jogo é de

informação completa. Na falta de um desses elementos informativos, o jogo

é de informação incompleta e as características sobre o tipo dos jogadores

deixam de ser de conhecimento comum.

Uma forma de trabalhar a falta de informações na modelagem dos jogos é

introduzir a natureza como uma parte interveniente numa jogada. Assim, as

incertezas dos jogadores, em relação à definição das regras, podem ser

interpretadas como probabilidades subjectivas, que a psicologia dos jogadores

trata de estabelecer.

Em diversos textos do final dos anos 1960 - onde se destaca "Games with

Incomplete Information Played by 'Bayesian' Players" (1967-68) -, John

Harsanyi sistematizou essa situação tratando os agentes como jogadores

"bayesianos", isto é, aqueles cujas incertezas podem ser operadas através de

uma distribuição da probabilidade subjectiva conjunta partilhada por todos.

________________________________________________________________


Embora a aplicação destas ideias seja difícil de ser observada por humanos e

outros animais no seu dia-a-dia, o modelo de Harsanyi serviu para descrever as

circunstâncias em que a informação é assimétrica, quando alguém dispõe de

um conhecimento privilegiado sobre os ingredientes do jogo que não é do

domínio dos restantes envolvidos na mesma situação dos jogos chamados de

informação incompleta. Um exemplo já referido deste conhecimento

privilegiado é o poker, em que cada jogador antes de tomar uma decisão nunca

sabe qual o leque de cartas dos adversários.

A adopção desta sugestão trazia algumas dificuldades para a teoria, uma vez

que o equilíbrio de Nash tinha como condição a simetria entre os jogadores,

apesar da maioria dos casos interessantes envolver movimentos assimétricos. A

solução de Harsanyi produziu, então, equilíbrios Bayes-Nash para cada tipo de

jogador que maximiza os valores esperados de acordo com as estratégias

seguidas pelos outros, subentendendo a incerteza quanto ao tipo do outro

jogador, que pode ser diferente tendo em vista a crença subjectiva na

probabilidade prévia de distribuição desses tipos na natureza.

A crença prévia é a expectativa que todos jogadores têm sobre a forma de

como a natureza produz alternativas de forma aleatória. Esta crença não é mais

do que o conhecimento comum da probabilidade estimada de que um tipo de

jogador venha fazer parte do jogo. Na posse destas informações os jogadores

podem avaliar as suas escolhas a partir de probabilidades predeterminadas de

que estão a enfrentar um tipo diferente ou semelhante de adversários.

2.4 História da Teoria dos Jogos

Jogos de tabuleiro, dados, cartas ou, em geral, jogos de salão são objecto de

diversão dos humanos desde a formação das primeiras civilizações. Escavações

feitas em sítios arqueológicos localizados na região do Oriente Médio conhecida

como Mesopotâmia encontraram em túmulos de nobres e membros da família

real da antiga cidade de Ur, importante centro da civilização Suméria, por volta

________________________________________________________________


de 3000 a.C., um jogo de tabuleiro que passou a ser conhecido como Jogo Real

de Ur, um provável antecessor do jogo moderno do gamão. Através de crenças

em lendas indianas, a actividade lúdica, além de entreter os praticantes,

também serviria como simulação alegórica de batalhas ou deliberações que as

pessoas têm de fazer ao longo de sua vida quotidiana, sendo exemplos disto o

xadrez e o já mencionado gamão. Por colocar as pessoas em situações nas

quais ganhar ou perder dependem das escolhas feitas adequadamente logo no

início das partidas, os jogos mostraram-se como uma excelente ferramenta

para o desenvolvimento da personalidade e da inteligência das crianças.

Entretanto, apesar desse aspecto pedagógico, os jogos raramente eram

considerados objectos de estudo sério. Foi a curiosidade do Cavaleiro de Méré e

habitual jogador, Antoine Gombaud (1607-1684), que, em 1654, incentivou o

filósofo francês Blaise Pascal (1623-1662) a iniciar correspondência com outro

matemático francês, Pierre de Fermat (1601-1665), no intuito de solucionar

com maior rapidez o problema dos pontos, num jogo de dados que fora

interrompido, e cujo dinheiro das apostas teria de ser dividido justamente de

acordo com as probabilidades iguais de ganho de cada jogador, caso o jogo

tivesse continuado até o final. A resposta fornecida por ambos ao problema de

Gombaud revelou as regras matemáticas que subjazem aos jogos de azar,

desenvolvendo a teoria da probabilidade que de um modo independente, outro

matemático e famoso “batoteiro”, o italiano Girolamo Cardano (1501-1576),

tinha iniciado antes. Contudo, a solução encontrada por Pascal e Fermat só foi

publicada mais tarde através do primeiro livro exclusivo sobre teoria da

probabilidade, chamado “Sobre o Raciocínio em Jogos de Azar”, do físico e

astrónomo holandês Christian Huygens (1629-1695), lançado em 1657. Isso

porque, na metade do século XVII, a matemática era considerada uma

actividade amadora de eruditos que não deveria ter consequências sérias para

as vidas dos mortais.

Em 1730, a matemática já tinha alcançado um respeito considerável, devido ao

sucesso dos trabalhos do cientista inglês Isaac Newton (1642-1727). Nesta

________________________________________________________________


época, o suíço Daniel Bernoulli (1700-1782), membro de uma família de

matemáticos, já podia ser visto como um solucionador de problemas

profissional, contratado para ensinar as suas matérias em diversas cortes

europeias.

Em São Petersburgo, Rússia, Bernoulli concebeu o conceito de utilidade como

um valor de incremento inversamente proporcional à quantidade inicial. Isto é,

tendo em vista o comportamento dos jogadores, existiria uma medida

subjectiva de satisfação que explicaria a reacção das pessoas em situações de

risco, nos termos de maximização da sua utilidade. Circunstância que só dois

séculos depois, receberia uma formulação moderna pela mão do matemático

francês Émile Borel (1871-1956), na forma do teorema Minimax. Usando a

noção de estratégias mistas2, em 1927, Borel conseguiu resolver jogos com

duas pessoas que tivessem até cinco opções de estratégias a sua escolha. Uma

solução geral, entretanto, só viria a ser alcançada pelo matemático húngaro

John Von Neumann (1903-1957), em 1928, consolidando as bases de uma

moderna teoria dos Jogos, em que o conceito de utilidade é fundamental.

Outro conceito chave desta teoria começou a ser trabalhado pelo filósofo e

economista francês Antoine Augustin Cournot (1801-1877). Nas suas análises

sobre os casos de duopólio, Cournot formalizou uma versão restrita do conceito

de equilíbrio que iria ser generalizada, no século seguinte, por John Forbes

Nash Jr. em trabalhos que tornaram a teoria dos jogos pertinente a situações

em que um lado pode vencer sem precisar, necessariamente, de derrotar o

adversário.

Assim onde pode existir conflito de interesses entre duas ou mais partes

capazes de deliberarem sobre uma acção que implique uma reacção recíproca

consequente, a teoria dos jogos tenta encontrar uma formulação passível de

ser tratada de uma forma tão rigorosa quanto possível, a fim de gerar

respostas possíveis.

2 Aplicam as estratégias puras a uma taxa de variação proporcional aos ganhos

________________________________________________________________




3. O Jogo Carcassonne

3.1 Introdução

A cidade de Carcassonne no sul de França foi fundada numa importante rota de

comércio entre o mediterrâneo e o Atlântico. Devido à sua posição estratégica,

a cidade foi conquistada várias vezes e conheceu muitos povos. Em

consequência desta variada história, a cidade é famosa pela sua mistura

original de fortificações romanas e medievais.

Assim o autor do jogo, Klaus Jürgen Wrede (Figura 2), desenvolveu um jogo

denominado de Carcassonne.

Figura 2 - Klaus-Jürgen Wrede

Os jogadores desenvolvem a área em torno de Carcassonne colocando peças

de terreno. Cada área torna-se maior enquanto que os jogadores expandem e

adicionam troços ou partes de estradas, campos, cidades e mosteiros. Os

jogadores podem também colocar seguidores que assumem diferentes papeis

em função do recurso que se pretende defender, por exemplo: monge no caso

do mosteiro, ladrões nas estradas, agricultores nos prados e cavaleiros nas

cidades. Como cada jogador apenas possui 8 seguidores, um bom jogador terá

que delinear uma estratégia para efectuar os movimentos com cuidado e

colocar os seguidores quando e onde possa ganhar mais pontos.

________________________________________________________________


3.2 Objectivo do Jogo

Os jogadores, jogada a jogada, colocam as peças de terreno criando estradas,

cidades, campos e mosteiros sobre os quais os jogadores podem colocar os

seus seguidores, de forma a somar pontos. Os jogadores ganham pontos

durante o jogo e também no final do mesmo. O vencedor só será definido no

final do jogo após a última contagem que inclui os prados, sendo que, aquele

que reunir maior número de pontos vencerá.

3.3 Regras do Jogo

3.3.1 Material do Jogo

• 40 seguidores em 5 cores (Figura 3):

o Cavaleiros; o Ladrões; o Monges; o Agricultor.

Figura 3 - Seguidores

• 1 Placa de contagem de pontos ( Figura 4 )

Figura 4 – Placa de contagem dos pontos

________________________________________________________________


• 72 peças de terreno (Figura 5):

o peça inicial com fundo escuro; o pedaços de cidade; o pedaços de estrada; o pedaços de campo; o cruzamentos; o mosteiros.

Figura 5 – Peças do Jogo3

3 As peças da figura 5 apresentam duas numerações, sendo a numeração preta o número de peças existentes, e a numeração branca o identificador de cada peça.

________________________________________________________________


3.3.2 Preparação do Jogo

A peça inicial é colocada do meio da mesa. As restantes peças são colocadas

aleatoriamente com o verso voltado para cima. A placa de contagem deve ser

colocada numa extremidade da mesa

Cada jogador tem direito a 8 seguidores de uma cor entre cinco à escolha, em

que um deles será colocado como contador de pontos na placa de contagem.

3.3.3 Posicionamento de Peças Para colocar a peça é necessário obedecer a certas regras:

• A peça extraída tem que ser colocada com um dos seus lados junto

com um lado livre de uma das peças anteriormente colocadas;

• Os pedaços de campo, cidade ou estrada têm que ser continuados,

ou seja, os lados que ficarão juntos efectuam um encaixe coerente de

forma a manter o desenho lógico como exemplificado na Figura 6;

Figura 6 – Posicionamento de peças

________________________________________________________________


• Se não for possível colocar a peça em nenhuma posição, esta será

retirada do jogo, e o jogador retira uma nova peça.

3.3.4 Desenvolvimento do Jogo

• O Jogo decorre no sentido dos ponteiros do relógio;

• O Jogador tira uma peça à sorte e coloca-a;

• O Jogador pode posicionar um seguidor na carta que colocou;

• Caso o jogador tenha fechado uma estrada, cidade ou mosteiro com

a peça colocada, procede-se a uma contagem de pontos e à recolha

dos peões.

3.3.5 Posicionamento de seguidores

Depois de colocada uma peça, o jogador pode colocar sobre esta um seguidor.

Para isso é necessário obedecer a certas restrições:

• Só pode ser colocado apenas um seguidor;

• Só podem ser utilizados seguidores da reserva do jogador;

• O seguidor só pode ser colocado na peça extraída;

• O jogador tem que decidir em que parte da peça será colocado o

seguidor. Pode ser usado como demonstrado na Figura 7:

Figura 7 – Posicionamento de seguidores

________________________________________________________________


Os seguidores assumem diferentes papeis em função do local em que são

colocados:

o Na cidade o cavaleiro; o Na estrada o ladrão; o No campo o agricultor; o No mosteiro o monge.

• Nos pedaços de campo ou cidade ligados à nova peça, não pode

existir nenhum outro seguidor, independentemente da distância a

que este se encontre;

Na imagem em cima o jogador não pode colocar o

cavaleiro, mas já pode colocar um agricultor. Na imagem

em baixo o jogador pode colocar o peão como ladrão ou

cavaleiro. Como Agricultor pode colocar apenas no campo

mais pequeno, o campo maior já se encontra ocupado.

Figura 8 – Colocações possíveis e impossíveis do peão

• Caso durante o jogo, acabem os seguidores de um jogador, este só

poderá colocar as peças. Apenas pode reaver seguidores aquando de

uma contagem de pontos em que é fechado um recurso;

________________________________________________________________


• Depois de uma cidade ou uma estrada estar fechada e depois de ter

sido feita a contagem, os ladrões, cavaleiros ou monges voltam para

a reserva dos jogadores que os tinham anteriormente colocado, de

forma a que o jogador os possa utilizar novamente;

• É possível, na mesma jogada, colocar um seguidor para efectuar uma

contagem de pontos, e reavê-lo novamente. Isto pode acontecer

quando o jogador coloca uma nova peça e completa uma cidade ou

estrada sem que esta tenha pelo menos um seguidor.

3.3.6 Pontuação

No decorrer do jogo cada jogador vai colocando os seus peões de acordo com

as suas tácticas e estratégias. Estes peões aquando do fecho de um recurso,

retornam ao seu jogador. Em cada contagem de pontos por um recurso

fechado todos os peões são libertados e voltam à reserva de cada jogador.

Exceptua-se o caso dos prados, onde, os peões que forem colocados nunca são

libertados pois os prados são contabilizados apenas no fim do jogo.

• Estrada

Acabada - Uma estrada está acabada quando a mesma estiver

delimitada por um cruzamento, cidade ou mosteiro, ou então quando

esta formar um círculo fechado (figura 9). O jogador que possuir um

seguidor nesta estrada ganha tantos pontos quanto o tamanho da

estrada (número de peças);

Inacabada – Uma estrada está inacabada quando a mesma não

formar um circuito fechado (figura 9). O jogador nesta situação

apenas possui pontos potenciais, sendo estes contabilizados pelo

número de peças que a estrada constitui;

________________________________________________________________


Figura 9 – Estrada acabada e inacabada

• Cidade

Acabada - Uma cidade está acabada quando os seus pedaços são

completamente cercados por muros e o seu terreno não apresenta

nenhum buraco (figura 10, duas cidades acabadas). Por cada cidade

completa o jogador que possuir um cavaleiro na mesma ganha 2

pontos por cada pedaço de cidade (número de peças);

Inacabada – Uma cidade está inacabada quando este não está

completamente cercada por muros ou possui buracos (figura 10).

Nesta altura o jogador apenas pode contabilizar pontos potenciais, 2

por pedaço de cidade.

Figura 10 – Cidade acabada e inacabada

________________________________________________________________


• Quando mais que um seguidor está colocado numa cidade ou estrada

acabada os pontos vão para o jogador que tiver mais seguidores na

cidade ou estrada fechada. Em caso de empate os pontos são

atribuídos aos dois jogadores;

• Mosteiro acabado: Um mosteiro está acabado quando este fica

cercado por 8 peças de terreno (figura 11). O jogador que possuir um

monge no mosteiro ganha 9 pontos;

Figura 11 – Mosteiro acabado

• Nas estradas ou cidades fechadas que têm numa das peças um

brasão, recebem dois pontos extra além da pontuação normal.

Analisando a figura 10 a cidade da esquerda receberá 2 pontos extra;

• Os campos ou pedaços de campo não são contados. Os campos são

separados por estradas ou cidades. Estes só servem para colocar os

seguidores. Os jogadores que colocaram os seguidores como

agricultores só recebem os pontos no final do jogo. Assim, os

agricultores não podem voltar para o jogador, depois de colocados;

• No final do jogo, depois de colocada a última peça, procede-se à

contagem final dos pontos. Inicialmente contam-se as estradas,

cidades, e mosteiros ainda não acabados. O jogador que possuir um

________________________________________________________________


seguidor nestas peças recebe um ponto por peça. O brasão neste

caso também só contará 1 ponto;

• Ainda na contagem final, cada cidade acabada contará 3 pontos

independentemente do seu tamanho. Aqui neste caso os agricultores

vão decidir a atribuição dos pontos.

________________________________________________________________




4 Desenvolvimento do agente inteligente

4.1 Descrição do problema

Para o problema proposto pretende-se o desenvolvimento de um agente dotado

de inteligência que seja capaz de tomar boas decisões no decorrer de um jogo

mediante as jogadas do adversário, ou adversários. Torna-se necessária essa

inteligência uma vez que existe a possibilidade de jogarem mais que dois

jogadores e o estado actual do tabuleiro também difere de jogo para jogo.

Cada jogador, depois de conectado a um servidor do jogo, recebe

constantemente informação sobre o mesmo. O estado inicial do tabuleiro é

sempre o mesmo, sendo a informação desse estado também possuída pelos

jogadores. Depois de um jogador efectuar uma jogada, o servidor valida essa

mesma jogada e caso essa validação seja bem sucedida, o servidor envia a

cada jogador inscrito no jogo a informação sobre a jogada, de modo a que cada

um deles possa actualizar o seu conhecimento sobre o jogo, nomeadamente:

tabuleiro, posições livres para jogar, recursos e pontuação do(s) adversário(s).

Estes servidores de jogos na Internet fornecem também outros jogos, e mais

mesas em simultâneo para cada jogo. Esta forma de envio de informação e

actualização da informação é a mais eficiente já que não torna os servidores

lentos e pesados aquando do processamento da informação. Neste cenário, o

servidor apenas confirma a validação da jogada. Cada jogo terá uma

identificação assim como a mesa de jogo, permitindo assim aos vários

jogadores, em qualquer parte do mundo, jogar ao mesmo tempo.

O agente jogador depois de receber a informação sobre a jogada e actualizar

as entidades necessárias, vai avaliar um conjunto de jogadas possíveis e os

seus benefícios, para finalmente poder efectuar uma escolha. Para esta

________________________________________________________________


escolha, o agente, tem que seguir uma determinada estratégia e uma série de

tácticas mediante a situação actual de jogo.

4.2 Caracterização do jogo

Antes de qualquer tentativa de criação do agente foi necessário efectuar uma

pesquisa profunda referente ao jogo Carcassonne e respectivas regras (ver

descrição na secção 3). Relativamente a este projecto, o jogo Carcassonne está

incluído no tipo de jogos com informação incompleta. Cada jogador, a cada

jogada, nunca vai saber qual o desenrolar do jogo, nem sabe todas as jogadas

possíveis até ao fim deste. O tabuleiro não está definido inicialmente, apenas

contém a peça inicial do jogo, sendo a partir daí desenvolvido mediante as

decisões dos jogadores intervenientes.

Para o caso do Carcassonne, o payoff define-se pelos recursos fechados, em

que a pontuação deste recurso reverte para o jogador que possuir mais peões

que o adversário, ou em caso de empate, reverte para os dois ou mais

jogadores.

Muitas das dificuldades na criação de agentes devem-se em grande parte ao

nível da complexidade do jogo, já que não se trata de um jogo básico e torna-

se necessário dispender algum tempo para a interiorização das suas regras e da

sua dinâmica.

4.3 Análise do problema

Inicialmente cada jogador possui 8 seguidores de uma determinada cor que lhe

é atribuída e existe um tabuleiro apenas com uma peça colocada (a peça inicial

que possui uma tonalidade escura nas costas, figura 12).

________________________________________________________________


Figura 12 – Peça inicial do jogo Carcassonne

Inicialmente existem 4 posições possíveis para colocar uma peça. Peça esta que

é gerada pelo servidor e que poderá ou não encaixá-la nas posições livres para

jogar. No decorrer do jogo à medida que são efectuadas jogadas a lista de

posições livres é actualizada por cada jogador. Não existe então um número de

jogadas fixo por jogador, sendo que este pode variar de jogada para jogada. A

cada jogada o jogador não possui toda a informação possível até ao fim do jogo

o que o torna, como já foi referido, um jogo de informação incompleta. O

algoritmo Minimax referido no capítulo 2 aborda um jogo com dois jogadores, e

cada jogador, a cada jogada, tem o conhecimento de todas as jogadas

possíveis até ao fim do jogo. Esta abordagem maciça não se aplica ao

Carcassonne já que podem existir mais do que 2 jogadores e não existe, a cada

jogada, a informação completa do jogo.

4.3.1 Análise da complexidade do problema

Inicialmente o jogador possui 4 posições para colocar a peça e existem 71

peças disponíveis para serem extraídas. Cada peça possui 4 rotações.

Desta forma admite-se o número de jogadas representadas pela seguinte

fórmula:

Número de peças * 4 Rotações * Posições livres para jogar = Jogadas possíveis

________________________________________________________________


Inicialmente o jogador tem então 71 * 4 * 4 jogadas possíveis para

efectuar. O jogar seguinte terá 70*4*(4-1)+(3 ou menos). Na jogada

seguinte sendo n o número de peças as jogadas possíveis teremos n-1 * 4 *

((nº de posições livres anterior -1) + (3 ou menos)). Ou

seja a cada jogada o jogador tem menos uma peça no amontoado de peças

para serem extraídas, em que essa peça possui 4 rotações possíveis para ser

colocada, e subtrai 1 ao nº de posições livres anterior colocando a peça, assim

como adiciona novas posições livres podendo estas ser 3, 2, 1 ou nenhuma,

mediante o tabuleiro actual4. O número de peças tem um decrescimento

constante mas o número de posições livres tem um crescimento exponencial. O

primeiro jogador tem 71*4*4, se estiverem a jogar 6 jogadores o sexto jogador

terá um número superior, e à 12ª jogada terá um número ainda maior de

jogadas possíveis, mas desconhecido. Um jogador humano tendo dezenas de

jogadas possíveis anula automaticamente uma série de jogadas que não

interessam, processo que é complexo a nível de agente inteligente. Como já foi

referido, não é possível efectuar uma abordagem maciça. Será então necessário

implementar a aplicação com uma abordagem diferente.

Para o desenvolvimento do agente inteligente, existe o problema da tomada de

decisão. O processo de tomada de decisão subdivide-se em 3 níveis como

apresentado na figura 13:

Estratégico Conhecimento

Táctico Informação

Operacional Dados

Figura 13 – Níveis de decisão do agente

4 Por exemplo no caso de existir um buraco numa cidade, e colocando a peça nesse mesmo buraco, ocupa-se uma posição livre e não é adicionada nenhuma.

________________________________________________________________


Para cada nível de decisão existe um nível de abstracção distinto ou de

informação associado.

• Operacional

O nível mais baixo de decisão. Toda a matéria relacionada com a

mecânica do jogo: representação de entidades, comunicação com o

servidor, inscrição no jogo, recepção de tabuleiros e listas de posições

livres, geração de listas de jogadas possíveis, pontuações locais, etc.

São considerados neste nível dados como jogadores, peças,

seguidores, etc, que são admitidos como (elemento, peça). É definida

a estrutura básica para o tabuleiro e respectivas validações. Neste

nível não existe uma boa tomada de decisão já que a informação que

existe a este nível representa apenas dados que não permitem tirar

quaisquer conclusões, fornecendo apenas o suporte básico para os

níveis seguintes.

• Táctico

Um nível superior de abstracção que permite fornecer uma visão mais

global do jogo em si: representação de recursos, ataque e defesa dos

recursos, tácticas, etc. Neste nível já existe um conceito de áreas em

que o objectivo é conhecer as áreas em construção (cidades,

estradas, prados ou mosteiros), saber quem as possui, qual o valor

das mesmas, se estão ou não defendidas, etc. São admitidos

conceitos como jogada ou sequência de jogadas. Neste nível a

informação recolhida é mais valiosa relativamente ao nível

precedente, uma vez que já permite ajudar na tomada de decisão da

escolha de uma jogada.

• Estratégico

O nível de abstracção mais alto e complexo do projecto, que engloba

o desenvolvimento de uma estratégia de jogabilidade. O agente

inteligente jogará segundo uma determinada estratégia mediante o

decorrer do jogo já que, como foi referido antes, o Carcassonne é um

________________________________________________________________


jogo de estratégia dinâmico e aberto. É o nível de conhecimento em

que a informação é mais vasta e que é mais difícil de representar. É

necessário aceder ao conhecimento adquirido de uma forma rápida e

tomar a decisão também de uma forma rápida. Já existe

conhecimento sobre o jogo e a estratégia a aplicar em cada situação.

Este nível está de certa maneira relacionado com o anterior já que

existem formas de representação que serão usadas em ambos os

níveis. Jogo ou fase de jogo são conceitos associados a este nível.

Para esta implementação é também importante ter um mecanismo de teste e

controlo e, nesse sentido, é necessário desenvolver um servidor fictício que

permita gerir as peças, receber a informação sobre as jogadas de cada jogador

e actualizar constantemente o tabuleiro. Ou seja, este servidor faz uma gestão

do jogo, guardando os dados de cada jogador e as entidades do jogo

(tabuleiro, peças, recursos, pontuações, etc). Existe também um módulo em

separado com algoritmos auxiliares para tratamento de informação a mais

baixo nível.

4.4 Arquitectura utilizada Para o desenvolvimento da aplicação em questão é necessário definir uma

estrutura à qual estão associados 3 módulos (figura 14):

• Auxiliares;

• Agente Inteligente do Jogador;

• Agente Inteligente do Servidor.

Figura 14 – Arquitectura da aplicação

Agente Jogador

Agente Servidor

Módulo auxiliar

________________________________________________________________


Um dos referidos módulos contém apenas predicados auxiliares de baixo nível,

onde são processados vários tipos de informação, servindo de apoio tanto ao

agente jogador como ao agente servidor. Para a aplicação propriamente dita, é

também necessário desenvolver o agente jogador e um agente servidor para

teste.

O agente jogador estabelece uma conexão com o servidor através do qual

recebe as peças para jogar na sua vez, assim como o tabuleiro actualizado.

Posteriormente será descrito em pormenor o funcionamento do agente, tanto a

nível de comunicações como a nível de jogo.

Como já foi anteriormente referido, para o desenvolvimento do agente jogador

é necessária a implementação de um servidor fictício, sendo este responsável

pela gestão do jogo e sorteio aleatório das peças.

4.5 Modelo de dados

Na implementação de algoritmos para tratamento de informação recebida e

tomada de decisão, é necessário antes representar as entidades necessárias ao

jogo. Esta eficiência vai depender da representação. É de salientar que neste

jogo as entidades são muito complexas de representar, o que levantou muitas

dificuldades e sucessivas alterações na representação das entidades no

decorrer da implementação dos algoritmos. Seguidamente serão descritos os

itens mais importantes de representação das entidades necessárias ao jogo:

• Peça

Seguramente, a entidade mais importante do jogo e também uma

das mais difíceis de representar. Note-se que além de ser necessário

representar as suas faces para a validação do encaixe da peça numa

posição livre, é também necessário ter uma boa representação do

centro pois poderá ter várias posições para colocar o peão.

________________________________________________________________


Uma peça é representada através do tuplo peca/4:

peca(ID,ListaFaces,Centro,Brasao).

sendo que os seus campos são preenchidos pelos seguintes

parâmetros:

o ID - identificador da peça. Existem 72 peças, sendo 24

diferentes. A peça inicial tem o ID “inicial”. As restantes peças

possuem um ID que é representado por um número inteiro

entre 1 e 24.

o ListaFaces - Uma lista com as faces da peça que estão

ordenadas no sentido dos ponteiros do relógio ou pelos pontos

cardeais ([W,N,E,S]).

o Centro – o tuplo centro/5 contém 5 campos identificando o

centro de cada peça, estritamente necessário para a colocação

dos peões e para uma posterior contagem de pontos. O limite

de um determinado recurso dependerá também do centro de

uma peça, em que esta permite fechar um recurso ou

continuá-lo. Os 5 campos necessários estão descritos na tabela

2 e são todos do tipo booleano.

________________________________________________________________


Centro Designação Descrição Exemplo

Estrada–Fim

indica que o percurso da estrada acabou. No caso de ser

verdadeiro, a peça permite limitar ou fechar a estrada actual

Estrada–Pass

permite continuar uma estrada. Significa que sendo verdadeiro,

a estrada continua na peça seguinte

Cidade

caso o seu valor seja verdadeiro, significa que no caso da face da

peça ser cidade, o recurso cidade continua na peça vizinha. Se o seu valor é falso e uma das

faces é cidade, significa que permite fechar um recurso do

tipo cidade

Mosteiro

a peça possui ou não um mosteiro no seu centro. Note-se

que pode ser um mosteiro isolado assim como uma estrada

que termina no mosteiro. Considerando este último, os

campos Estrada–Fim e Mosteiro seriam instanciados

como valor verdadeiro (1)

Campo

caso seja verdadeiro, significa que na peça em questão apenas existe campo no seu centro, não existindo, portanto, estrada ou

cidade

Tabela 2 – Campos do tuplo Centro

o Brasao – Campo booleano, mediante a presença de um

brasão na peça ou não. Este brasão só aparece nas peças com

pedaços de cidade. Como já foi referido, o brasão adiciona

________________________________________________________________


dois pontos extra na pontuação de um recurso fechado do tipo

cidade.

Seguidamente será exemplificada a notação utilizada numa das 72

peças do jogo através de uma peça escolhida aleatoriamente.

Figura 15 – Exemplo de uma peça do jogo Carcassonne

Para o exemplo da Figura 15 os campos são preenchidas da seguinte

forma:

ID = 18.5 ListaFaces = [campo,cidade,estrada,estrada]. Centro = centro(0,1,0,0,0). Brasao = 0.

Representação:

peca(18, [campo,cidade,estrada,estrada], centro(0,1,0,0,0), 0).

• Tabuleiro

A entidade tabuleiro é uma lista, sendo cada um dos seus elementos

preenchido com a posição ocupada do tabuleiro. Em cada posição

ocupada do tabuleiro está colocada uma peça com uma determinada

rotação em que está, ou não, posicionado um peão. Saliente-se

novamente que o tabuleiro não está definido inicialmente e não é um

5 Através da figura 5 é possível consultar o ID de cada peça.

________________________________________________________________


tabuleiro físico, mas sim uma associação dinâmica definida pela

colocação sequencial das peças ao longo do jogo, que pelas regras do

jogo, impossibilita a ocorrência de ilhas (peças isoladas).

O tuplo tabuleiro/1 é representado por:

tabuleiro(LPosicoes).

o LPosicoes – uma lista de tuplos com 4 campos

caracterizando cada posição ocupada do tabuleiro.

Em que cada um dos elementos de LPosicoes é representado pelo

tuplo posicao/4:

posicao(PosicaoXY, ID, Rotacao, Peao).

o Este tuplo será preenchido com a posição cardeal (deslocação

relativa à posição original (0,0)), o ID da peça, a rotação em

que está colocada e se existe ou não um peão posicionado na

mesma. A variável Rotacao apenas pode ser instanciada com

4 valores: 1, 2, 3 ou 4, sendo estes as 4 rotações possíveis da

peça, rodando esta no sentido dos ponteiros do relógio. O

peão pode ser representado por: nao, estrada, cidade,

campo ou mosteiro.

________________________________________________________________


Exemplo de um tabuleiro numa fase inicial do jogo (figura 16) e sua

representação:

(0,0) inicial (1,0) 10 (0,-1) 16 (1,-1) 19 (2,-1) 17

Figura 16 – Tabuleiro numa fase inicial

Representação:

tabuleiro([posicao((0,0), inicial, 1, nao), posicao((1,0), 10, 2, nao), posicao((0,-1), 16, 3, nao), posicao((1,-1), 19, 3, nao), posicao((2,-1), 17, 1, nao)]).

• Recurso

A representação de um recurso é uma entidade necessária ao nível

táctico e estratégico, já que a escolha de uma jogada depende dos

recursos já existentes, e se estes estão já defendidos ou não. O item

recurso/5 existe no servidor e no jogador, assim como outras

representações, mas de formas diferentes. No servidor existe uma

lista de recursos inserida no tuplo do jogador e na lista de jogadores

que será descrita a seguir. A nível de jogador, existe em base de

conhecimento a sua lista de recursos. O jogador também tem acesso

à lista de jogadores onde estão contidos também os respectivos

recursos.

________________________________________________________________


O tuplo recurso/5 é representado da seguinte forma:

recurso(TipoRecurso,Area,Dono,Estado,Valor).

onde os seus campos são representam pelos seguintes parâmetros:

o TipoRecurso – identifica o tipo de recurso. Este pode ser:

cidade, estrada, mosteiro ou campo.

o Area – peças que constituem o recurso. Lista de tuplos de

dois campos apenas com o identificador da peça e sua

posição.

o Dono – dono ou lista de donos do recurso, caso o número de

peões seja igual entre os jogadores que possuem o recurso.

o Estado – estado do recurso no momento, sendo este

fechado ou aberto.

o Valor – pontuação do recurso no momento, sendo esta uma

pontuação potencial caso o recurso esteja aberto, ou então

caso o recurso esteja fechado, uma pontuação já

contabilizada.

Seguidamente são apresentados dois recursos ligeiramente pequenos

(figuras 17 e 18), e respectiva representação, diferenciando apenas

seu estado.

(-1,0) 24 (0,0) inicial (1,0) 19 (-1,-1) 24 (0,-1) 23 (1,-1) 19

Figura 17 – Recurso fechado

________________________________________________________________


Representação:

Area = [((0,0),inicial), ((1,0),19), ((1,-1),19), ((0,-1),23), ((-1,-1),24), ((-1,0),24)].

recurso(estrada, Area, jogador1, fechado, 6). (0,1) 11 (1,1) 12 (2,1) 10 (0,0) inicial

Figura 18 – Recurso Aberto

Representação:

Area2 = [((0,0),inicial), ((0,1),11), ((1,1),12), ((2,1),10)].

recurso(cidade, Area2, jogador1, aberto, 6).

• Jogador

Na aplicação desenvolvida, optou-se por duas representações: uma

representação para as comunicações e outra para o jogo

propriamente dito. No agente inteligente do jogador não são

necessários o canal e a porta de comunicação do adversário já que as

suas comunicações são exclusivamente estabelecidas com agente

servidor. Apenas o servidor possui uma segunda representação dos

jogadores com os respectivos dados para comunicação.

________________________________________________________________


O conceito jogador, como já foi referido, é representado por dois

tuplos distintos de acordo com as diferentes necessidades.

Para comunicação:

jogador(Nome,Port,Channel).

A representação anterior apenas tem efeito a nível de servidor, já que

está implementado um servidor fictício, para envio de informação.

Este apenas contem 3 campos: nome do jogador, porta e canal

de comunicação.

A representação para o jogo em si, possui os dados relativos ao jogo.

Esta existe tanto no servidor como em cada jogador, na forma de

uma lista de tuplos jogador/6.

jogador(Nome,Cor,ListaRecursos,PontosActuais, PontosPotenciais,NumPeoesLivres).

Analisando a representação anterior, conferem-se os seguintes

parâmetros para o tuplo jogador:

o Nome

o Cor – uma cor atribuída aleatoriamente entre as cores: azul,

amarelo, verde, vermelho e preto.

o ListaRecursos – lista de recursos que o jogador possui em

aberto e também fechado, sendo esta inicializada vazia

aquando da inscrição do jogador. Os tuplos desta lista serão

descritos posteriormente.

o PontosActuais – pontuação do jogador no momento.

o PontosPotenciais – pontos que o jogador poderá ganhar,

sendo contabilizados pelos recursos que ainda não foram

fechados e onde o jogador ainda possui peões. É de referir

que para um jogador ser dono de um recurso tem que possuir

________________________________________________________________


mais peões que os adversários nesse mesmo recurso. Aquando

do fecho de um recurso se o jogador possuir o mesmo número

de peões que o adversário no mesmo recurso, a pontuação

será igual para os dois. Isto poderá acontecer para mais do

que dois jogadores com seguidores no recurso.

o NumPeoesLivres – número de peões que o jogador ainda

possui no momento, fora do tabuleiro.

Um exemplo possível para este tuplo seria:

a nível de comunicação:

jogador(jogador1,2000,_37548).

e para o jogo:

ListaRecursos = [

recurso(cidade,Area, jogador1, aberto, 6), recurso(estrada,Area2, jogador1, fechado, 6)].

jogador(jogador1,azul,ListaRecursos,6,6,6).

Nota: o jogador1 apenas possui dois recursos, um fechado e

outro aberto, estando no momento a dispender 1 peão

possuindo em mão 6 peões.

• Jogada

O tuplo jogada/3 existe obrigatoriamente tanto no jogador como no

servidor. Após a decisão do agente jogador um tuplo deste tipo é

enviado ao servidor, o qual trata esta informação com o interpretador

correspondente. Este processo será descrito mais

pormenorizadamente na secção 4.6. A representação de uma jogada

é a seguinte:

jogada(ID, Posicao, Rotacao).

________________________________________________________________


Analisando a representação anteriormente descrita o tuplo jogada/3

possui 3 parâmetros sendo estes o ID da peça, a posição em que a

peça vai ser colocada representada por (X,Y), e a sua rotação que

pode tomar um valor de 1 a 4. Um exemplo de uma representação

pode ser o seguinte:

jogada(23, (4,5), 3).

4.6 Funcionamento agente/servidor

Numa primeira fase de desenvolvimento, procede-se à implementação das

comunicações entre o jogador e o servidor, ou seja, a inscrição do jogador no

servidor. Note-se que para a comunicação entre o jogador e o servidor ser

estabelecida, o pedido de conexão do jogador tem que ser feito à máquina

onde corre o servidor. Esta ligação é efectuada através do predicado descrito

na linha 2 da listagem 1, no qual o agente jogador neste caso tenta estabelecer

conexão com a máquina Xp2400 através da porta 1000.

Figura 19 – Caixa de diálogo do jogador

Para a implementação foram construídas caixas de diálogo simples para apenas

ter controlo na conexão e distribuição de peças. Não foi feita qualquer interface

________________________________________________________________


gráfica para o jogo já que, este ponto não foi considerado crucial para o

projecto. A ferramenta utilizada para desenvolver a aplicação (LPA PROLOG

4.320), foi escolhida com o intuito de criar um agente inteligente para jogar e

raciocinar sobre o jogo, já que esta será a mais indicada para o pretendido. Se

o intuito fosse criar a interface gráfica para a representação do jogo a escolha

poderia recair sobre a linguagem Java por exemplo.

A figura 19 representa a caixa de diálogo do jogador, em que apenas será

usado o botão Connect para estabelecer uma conexão com o servidor. Após a

conexão do jogador com o servidor fictício, está associado ao agente jogador

um handler que envia ao servidor a sua identificação, isto é, quando o jogador

está ligado ao servidor este handler envia a sua identificação para o mesmo

(linha 4 a 6).

1. . . .

2. agent_post_event(start,(`Xp2400`,1000)).

3. . . .

4. jogador_msg_handler(connected,_):-

5. agent_connected(_,Canal,_),

6. agent_send(Canal,jogador(jogador1,2000)).

7. . . . Listagem 1 – Conexão ao servidor

No servidor está implementado um handler para a recepção de informação de

forma a que qualquer termo seja tratado independentemente. Para a tradução

destes termos existe um interpretador para cada tipo que é invocado neste

handler, para ser devidamente tratada a informação recebida (linhas 9 a 13).

8. . . .

9. servidor_msg_handler(incoming_msg,(MesNo,Channel)):-

10. one agent_incoming(MesNo,Channel,Msg,_), ttyflush,

11. agUtil_msg2term(Msg,Termo,Error),

________________________________________________________________


12. interpretador(Termo,Channel),

13. retractall(agent_incoming(MesNo,_,_,_)).

14. . . . Listagem 2 – Handler de recepção de mensagens

Interpretador esse que no servidor trata dois tipos de termos, ou seja recebe

dois tipos de informação. Um dos termos é a inscrição do jogador no servidor

para entrar no jogo (linhas 16 a 20).

15. . . .

16. interpretador(jogador(Nome,Port),Channel):-

17. assert(jogador(Nome,Port,Channel)),

18. retract(lista_jogadores(L)),

19. append(L,[Nome,Cor,[],0,0,8],LR),

20. assert(lista_jogadores(LR)).

21. . . . Listagem 3 – Interpretador Jogador

Como é referido anteriormente o servidor possui duas representações do

jogador. Depois de recebida a informação, inicialmente o servidor adiciona à

sua base de conhecimento o nome do jogador juntamente com a porta e o

canal pelo qual se conectou (linha 17). Seguidamente é adicionado à lista de

jogadores (linha 19).

Outro dos termos recebidos pelo servidor é a jogada efectuada pelo jogador

(linha 23 a 28).

22. . . .

23. interpretador(jogada(ID,(X,Y),Rot), Ch):-

24. retract(tabuleiro(Tab)),

25. append(Tab, [posicao((X,Y),ID,Rot,nao)], TabRes),

26. assert(tabuleiro(TabRes)),

27. retract(lista_PosLivres(_)),

________________________________________________________________


28. gerar_lista_posicoes_livres(TabRes,TabRes,Lista_pos_livres).

29. . . . Listagem 4 – Interpretador jogada

O interpretador recebe o ID da peça, a posição em que será colocada e a sua

rotação. Seguidamente procede-se à actualização do tabuleiro para na altura do

envio de uma peça para o próximo jogador a jogar, lhe ser enviado também

este tabuleiro devidamente actualizado sobre o qual deverá raciocinar.

Assim como o tabuleiro, a lista de posições livres para jogar é actualizada. Para

efectuar a referida actualização procede-se à implementação do predicado da

listagem 5.

30. . . .

31. gerar_lista_posicoes_livres([],Tab,Lista):- assert(lista_PosLivres(Lista)).

32. gerar_lista_posicoes_livres([posicao((X,Y),_,_,_)|T],Tabuleiro,Lista_Pos_Livres):-

33. Xaux1 is X+1,

34. Xaux2 is X-1,

35. Yaux1 is Y+1,

36. Yaux2 is Y-1,

37. (

38. list(Lista_Pos_Livres)->Laux=Lista_Pos_Livres;

39. Laux=[]

40. ),

41. verifica((Xaux2, Y),Tabuleiro, Laux,Lres1),

42. verifica((X, Yaux1),Tabuleiro, Laux,Lres2),

43. verifica((Xaux1, Y),Tabuleiro,Laux,Lres3),

44. verifica((X, Yaux2),Tabuleiro, Laux,Lres4),

45. append(Lres1, Lres2, L1),

46. append(Lres3, Lres4, L2),

47. append(L1, L2, L3),

________________________________________________________________


48. append(L3, Laux, LRes),

49. gerar_lista_posicoes_livres(T, Tabuleiro, LRes).

50. . . . Listagem 5 – Gerar lista de posições livres

Depois de receber o tabuleiro actualizado este predicado verifica, para cada

peça, se as 4 posições à sua volta já foram adicionadas à lista de posições livres

ou se já existem também no tabuleiro. Caso contrário, é adicionada a posição à

lista de posições livres para jogar. O predicado auxiliar que faz a verificação é o

predicado verifica/2 apresentado na listagem 6.

51. . . .

52. verifica((X,Y),Tab,LPosLivres,L):-

53. (

54. member(posicao((X,Y),_,_,_),Tab)->L=[];

55. member((X,Y),LPosLivres)->L=[];

56. L=[(X,Y)]

57. ).

58. . . . Listagem 6 – Verificar posição

Depois de percorrido o tabuleiro e as 4 posições adjacentes a cada peça, este

predicado gera uma lista de posições livres onde será permitido colocar uma

peça na próxima jogada, em que cada elemento dessa lista é constituído

apenas pelas coordenadas X e Y. Inicialmente surgiram vários problemas com a

instanciação da lista de posições livres que é passada por argumento (linha 32).

Na primeira iteração do predicado a lista não vinha instanciada e tinha um valor

abstracto. Como solução para este problema é necessário testar se a variável

recebida por argumento Lista_Pos_Livres está instanciada com uma lista

ou um valor abstracto (linhas 37 a 40). Se estiver instanciada com uma lista,

essa mesma lista é usada para fazer a verificação referida anteriormente, caso

contrário, é usada uma lista vazia para fazer a verificação.

________________________________________________________________


Assim como no servidor, está implementado no agente do jogador um handler

para a recepção de informação por forma a tratar os termos

independentemente. O código deste handler é semelhante ao do servidor

(linhas 9 a 13), com a excepção de que a variável Channel não é necessária

para o jogador (linha 60).

59. . . .

60. interpretador(Termo),

61. . . . Listagem 7 – Interpretador termo

O interpretador do agente jogador trata 3 tipos de termos enviados pelo

servidor. O jogador recebe o tabuleiro actualizado (linhas 63 a 65), a lista de

posições livres para jogar (linhas 67 a 69) e a peça a jogar (linhas 72 a 76).

62. . . .

63. interpretador(tabuleiro(L)):-

64. retract(tabuleiro(_)),

65. assert(tabuleiro(L)).

66. . . .

67. interpretador(lista_PosLivres(L)):-

68. retract(lista_PosLivres(_)),

69. assert(lista_PosLivres(L)).

70. . . . Listagem 8 – Interpretador tabuleiro e lista_PosLivres

Depois da recepção do tabuleiro actualizado, este é adicionado à base de

conhecimento. O mesmo se passa com a lista de posições livres para jogar.

________________________________________________________________


Seguidamente é recebido o ID da peça gerada para colocar (linha 72).

71. . . .

72. interpretador(peca(ID)):-

73. peca(ID, L, C, B),

74. retract(pecaAJogar(_)),

75. assert(pecaAJogar(peca(ID, L, C, B))),

76. jogar_peca(ID).

77. . . . Listagem 9 – Interpretador peça

Os interpretadores para o tabuleiro e para a lista de posições livres, apenas

recebem estes argumentos, adicionando-os à base de conhecimento. Já no

interpretador, que recebe o ID da peça a jogar, são verificados os dados da

peça que existe em base de conhecimento através do seu ID (linha 73) e

seguidamente, esta é adicionada à base de conhecimento como o facto

pecaAJogar/1. As peças existem em base de conhecimento no agente do

jogador. Através do ID da peça é possível obter a lista de faces da mesma, o

centro e saber se possuem brasão ou não, no caso das peças com cidade.

Depois de adicionada a peça a jogar à base de conhecimento do agente

jogador, é invocado o predicado jogar/1 que apenas receberá como

parâmetro o ID da peça. Este predicado será descrito posteriormente na

secção 4.7.1.

Refira-se também que para esta aplicação foi implementado no módulo auxiliar

um algoritmo para gerar aleatoriamente uma peça (listagem 10 e 11).

78. . . .

79. gerar_seq_pecas:-

80. lista_ids(L),

81. gerar_lista_pecas(L,ListaSort),

82. retract(lista_sorteada(_)),

83. asserta(lista_sorteada(ListaSort)),

84. (print_list(ListaSort))~>Str,

________________________________________________________________


85. wtext((log,1),Str).

86.

87. gerar_lista_pecas([],[]).

88. gerar_lista_pecas(Lista,[X|LR]):-

89. Lista\==[],

90. length(Lista,N),

91. Pos is int(rand(N))+1,

92. member(X,Lista,Pos),

93. remove(X,Lista,Resto),

94. gerar_lista_pecas(Resto,LR). Listagem 10 – Gerar sequência de peças

O predicado gerar_seq_pecas/0 é invocado na inicialização do servidor. O

procedimento é o seguinte: o predicado supracitado (linhas 79 a 85) invoca o

método gerar_lista_pecas/0 que retorna uma lista aleatória de peças

ListaSort (linha 81). Este método recebe por parâmetro a lista de ID’s e, até

ficar vazia, vai ser retirado um elemento à sorte (linha 91) e adicionado a uma

nova lista. O procedimento repete-se recursivamente até que a primeira lista

fique vazia e a segunda (ListaSort) constituída por 71 elementos aleatórios.

Dado que o predicado rand/1 retorna um número racional, é necessário

aplicar o predicado int/1 para retornar o inteiro do número gerado,

seguidamente é adicionada uma unidade já que pode ser retornado o número

0, ID que não está presente em nenhuma peça (linha 91).

95. . . .

96. gerar_peca([ID|Resto]):-

97. (write(ID))~>Str,

98. wtext((dia,1),Str),

99. agent_connected(_,Channel,_),

100. tabuleiro(LTab),

101. agent_send(Channel, tabuleiro(LTab)),

102. lista_PosLivres(LPos),

________________________________________________________________


103. agent_send(Channel, lista_PosLivres(LPos)),

104. agent_send(Channel, peca(ID)),

105. retract(lista_sorteada(_)),

106. assert(lista_sorteada(Resto)).

107. gerar_peca([]):-

108. wtext((dia,1), `O Jogo Acabou! Procedendo à contagem de pontos...`).

109. . . . Listagem 11 – Gerar Peça

A lista sorteada é adicionada à base de conhecimento do servidor. Aquando do

pedido de uma peça para um jogador é invocado o predicado gerar_peca/1

(linhas 96 a 108). Para ser invocado existe um botão na caixa de diálogo do

servidor, apresentada na figura 20, de modo a efectuar a simulação desse

pedido. O servidor está encarregue de distribuir as peças sequencialmente

mediante o número de jogadores.

Figura 20 – Caixa de diálogo do servidor

No predicado referido (gerar_peca/1) é retirado da lista sorteada o primeiro

elemento, que está instanciado com o ID da peça. Seguidamente através do

canal de comunicação do jogador a jogar, é-lhe enviado o tabuleiro actualizado,

a lista de posições livres e finalmente o ID da peça sorteada. Quando a lista

sorteada ficar vazia (linha 107), o jogo termina e procede-se à contabilização

________________________________________________________________


dos pontos referentes aos prados. Será necessário existir uma boa

representação de recursos para efectuar a referida contagem.

4.7 Algoritmos principais e funcionamento do agente

Nesta fase de implementação pressupõe-se que já existem alguns dados para

raciocinar sobre o tabuleiro, sobre a peça a jogar e sobre qual a jogada a

efectuar. Existem inúmeros factores a ter em conta para a implementação das

regras existentes e a dificuldade de representação das várias entidades.

4.7.1 Jogar Inicialmente admitiu-se o cálculo da lista de posições livres para jogar como

uma função do agente inteligente, mas optou-se nesta aplicação por efectuar

esse cálculo no lado do servidor, pelo surgimento de vários problemas no

retorno da lista. Analisando a linha 31, sendo este um critério de paragem, a

intenção e o lógico seria o retorno da lista calculada instanciando Lista com

esse mesmo cálculo. Mas após várias tentativas e várias soluções o cenário

apresentava-se com o facto de que Lista era instanciada com o conteúdo

pretendido, mas não era retornada. Optou-se então por, neste critério de

paragem, adicionar a lista de posições livres para jogar à base de conhecimento

do servidor e enviá-la aquando do envio do tabuleiro e da peça para jogar.

Como já foi referido o jogador na sua vez de jogar, recebe 3 tipos de

informação: o tabuleiro, a lista de posições livres para jogar e a peça para jogar

respectivamente.

Como está representado anteriormente na listagem 9, o interpretador do termo

peca/1 no agente jogador, recebe o ID da peça e depois de consultar os

dados da peça (linha 73), é invocado o principal predicado do agente, o

jogar/1 (listagem 12).

________________________________________________________________


110. . . .

111. jogar_peca(ID):-

112. lista_PosLivres(LPos),

113. gerar_jogadas_validas(ID, LPos, LJog_Validas),

114. (print_list(LJog_Validas))~>St,

115. wtext((log,1),Str),

116. pontuarJogadas(LJog_Validas, LJog_Validas_Pontuadas),

117. (print_list(LJog_Validas_Pontuadas))~>Str,

118. wtext((log,1),Str),

119. selecionarJogada(LJog_Validas_Pontuadas, Jog),

120. enviarJogada(Jog).

121. . . . Listagem 12 - Jogar

Depois de receber o ID da peça e consultar na sua base de conhecimento a

lista de posições livres para jogar, o predicado gerar_jogas_validas/3 é

invocado passando como parâmetros os referidos anteriormente, e

LJog_Validas é instanciado com a lista de jogadas permitidas para aquela

lista de posições livres para jogar, com aquela peça. Seguidamente procede-se

ao cálculo da pontuação local que advém de cada jogada através do predicado

pontuarJogadas/2, o qual retorna uma lista de jogadas pontuadas. O

predicado selecionarJogada/2 fica encarregue de aplicar os critérios de

selecção e tomar uma decisão para posteriormente a jogada escolhida ser

enviada para o servidor. Para cada um destes predicados supracitados é feita

um descrição mais precisa e pormenorizada seguidamente.

É nesta altura onde surgem maiores dificuldades que não permitem um avanço

tão rápido quanto o desejado. É importante referir que a procura das melhores

soluções através do falhanço de outras, acaba por ser um processo complicado

e moroso. O método escolhido é a solução apresentada no corrente estado de

desenvolvimento, depois de várias remodelações integrais de alguns algoritmos.

Embora fique em aberta a possibilidade de implementação de novas soluções

________________________________________________________________


mais eficientes para um estado superior a nível táctico ou mesmo a nível

estratégico. A questão do tempo disponível é sempre um factor que “choca de

frente” com o tempo necessário para a resolução dos problemas que surgem.

4.7.1.1 Gerar Jogadas Válidas

Como já foi referido o predicado gerar_jogas_validas/3 (listagem 13)

permite gerar uma lista de jogadas válidas de acordo com as regras do jogo,

para as posições livres para colocar a peça extraída. Seguidamente é explicado

o funcionamento deste algoritmo, envolvendo outros predicados auxiliares

também não menos importantes.

122. . . .

123. gerar_jogadas_validas(IDPeca,ListaPosLivres,ListaResultado):-

124. findall((Pos,Rotacao),

125. (

126. member(Pos,ListaPosLivres),

127. peca(IDPeca,ListaFaces,_,_),

128. rotacao(ListaFaces,NR,Rotacao),

129. vizinhos(Pos, LFacesPret,_),

130. encaixa(Rotacao,LFacesPret)

131. ),

132. ListaResultado

133. ).

134. . . . Listagem 13 – Gerar jogadas válidas

Inicialmente foi feita uma tentativa de percorrer as faces da peça e em cada

uma das faces compará-la com a face do vizinho respectivo, caso este existisse.

Mais uma vez neste contexto, o tempo disponível apresenta-se como um factor

contra-producente, dada a dificuldade desta implementação, e devido ao facto

________________________________________________________________


da mesma não se apresentar como uma solução para o problema pretendido.

Inicialmente a representação da peça não possuía o campo ListaFaces e sim

4 campos com as 4 faces da peça ordenadas pela sequência W, N, E e S. A

adaptação dessas faces para uma lista de faces resultou num tratamento de

dados mais simples. O pretendido é uma lista de tuplos (Pos, Rotacao) que

respeitem as regras do jogo no estado actual, isto é, uma lista de

posições/rotações onde a peça pode ser colocada mediante uma determinada

rotação, podendo a mesma posição admitir várias rotações da peça, e que essa

posição seja uma das posições livres para jogar. Posto isto, é necessária a

procura dos pares (Pos, Rotacao) que são permitidos para a jogada actual,

e para isso, é usado o predicado findall/3 (linha 124) onde no segundo

parâmetro são feitas as devidas validações através de 3 predicados auxiliares.

Este método percorrerá a lista de posições livres para jogar e irá tentar colocar

a peça em qualquer uma das suas rotações. Apenas os pares de

posições/rotações que satisfaçam as validações são adicionados à

ListaResultado (linha 132), sendo os restantes pares desprezados.

Inicialmente tem de se garantir que Pos pertence à lista de posições livres para

jogar (linha 126), seguidamente através do ID da peça é consultada na base de

conhecimento a lista de faces da peça a colocar (linha 127). Através do

predicado rotacao/3 (linha 128) obtém-se a lista de faces de uma das 4

rotações disponíveis. Todas as rotações serão testadas. O parâmetro NR é

instanciado com valores de 1 a 4.

135. . . .

136. rotacao([F1,F2,F3,F4],1,[F1,F2,F3,F4]).




140. . . . Listagem 14 - Rotação

________________________________________________________________


Para melhor compreensão do predicado é demostrado o seguinte exemplo, para

uma peça do jogo:

ID=19. ListaFaces=[estrada,cidade,campo,estrada]. NR=3. Rotacao=[campo,estrada,estrada,cidade].

Rotacao=1 Rotacao=3

Figura 21 – Rotação de uma peça

Neste momento o número de pares a ser testado é 4 vezes o número de

posições livres para jogar.

Através do método vizinhos/3 (linhas 142 a 146) obtém-se a lista de faces

pretendidas para cada posição (linha 129), ou seja, a peça para ser colocada na

posição que está a ser testada no momento terá que possuir uma Rotacao

igual a esta lista de faces pretendidas.

141. . . .

142. vizinhos(Pos, [F1,F2,F3,F4], [PosW,PosN,PosE,PosS]):-

143. vizinho(Pos, -1,0, F1, w, PosW),

144. vizinho(Pos, 0,1, F2, n, PosN),

145. vizinho(Pos, 1,0, F3, e, PosE),

146. vizinho(Pos, 0,-1, F4, s, PosS).

147.

148. vizinho((X,Y),IncX,IncY,Face,Sentido, (NewX,NewY)):-

________________________________________________________________


149. NewX is X + IncX,

150. NewY is Y + IncY,

151. tabuleiro(LT),

152. (

153. member(posicao((NewX,NewY), ID, Rot, _),LT) ->

154. peca(ID,L,_,_),

155. rotacao(L,Rot,[VF1,VF2,VF3,VF4]6),

156. (

157. Sentido=s -> Face=VF2;

158. Sentido=w -> Face=VF3;

159. Sentido=n -> Face=VF4;

160. Sentido=e -> Face=VF1

161. )

162. ;

163. Face=null

164. ).

165. . . . Listagem 15 - Vizinhos

O método da listagem 15 recebe por parâmetro a posição a ser testada,

instancia cada uma das faces vizinhas e a posição do vizinho que possui essa

face vizinha.

Para saber qual a face de cada vizinho utiliza-se um predicado auxiliar

vizinho/6 (linhas 148 a 164). Este é invocado 4 vezes correspondentes aos 4

vizinhos. Em cada uma das chamadas é-lhe passado o incremento necessário

para o sentido respectivo: Norte Y+1, Sul Y-1, Oeste X-1 e Este X+1.

Seguidamente, depois de consultar na base de conhecimento o tabuleiro actual,

é verificado se na posição vizinha existe alguma peça. Caso não exista

nenhuma peça na posição vizinha à que está em teste, a face correspondente é

instanciada com null (linha 163).

6 Nota: As listas de faces estão sempre na ordem [W,N,E,S].

________________________________________________________________


No caso contrário, é obtido o ID e Rot da peça que existe em tabuleiro nessa

posição do tabuleiro (linha 153). Através do ID obtém-se a lista de faces

correspondentes, e invocando o predicado rotacao/3 instanciando o segundo

parâmetro com Rot sabe-se exactamente de que forma está posicionada a

peça, isto é, em que rotação está colocada.

Através do parâmetro Sentido sabe-se se o vizinho está a W, N, E ou S, e

retira-se a face pretendida. Por exemplo se o vizinho estiver a Norte, ou seja se

Sentido=n, a face retirada é a face Sul da posição vizinha (linha 159).

Depois de instanciadas as faces vizinhas existirá uma espécie de peça virtual,

ou seja uma lista de faces que a peça a jogar terá de possuir em qualquer uma

das suas rotações, caso contrário a posição a ser testada é desprezada.

Para verificar o encaixe da peça nessa posição, isto é, para efectuar a

comparação entre a lista de faces pretendidas e as 4 rotações da peça é

utilizado o predicado encaixa/2 apresentado na listagem 16.

166. . . .

167. encaixa([VF1,VF2,VF3,VF4],[F1,F2,F3,F4]):-

168. liga(VF1,F1),

169. liga(VF2,F2),

170. liga(VF3,F3),

171. liga(VF4,F4).

172. . . .

173. %Face1=Face2

174. liga(X,X):-!.

175.

176. %uma da faces esta vazia

177. liga(null,_):-!.

178. liga(_,null):-!.

179. . . . Listagem 16 - Encaixa

________________________________________________________________


O procedimento anterior apenas verifica a igualdade entre faces, ou então se

um das faces pretendidas está instanciada com null. Para isso utiliza-se

predicado liga/2. No caso de uma das faces não ligar, a rotação que está em

teste é desprezada.

Finalmente os pares (Pos, Rotacao) que satisfazem as condições impostas

são adicionados à lista resultado.

4.7.1.2 Pontuar Jogadas Localmente

Depois de se saber quais as jogadas possíveis a efectuar no momento, é

necessário saber quais os benefícios locais de cada jogada. Para isso é

importante saber quais as faces adjacentes à peça colocada na posição em

questão. Depois será necessário percorrer esse recurso, sendo este estrada,

campo, cidade ou mosteiro, até o próximo vizinho ser vazio ou então limitar

esse recurso fechando-o.

180. . . .

181. pontuarJogadas(LJogValidas, LJog_Validas_Pontuadas):-

182. LRes = [],

183. pontua(LJogValidas, LRes, LJog_Validas_Pontuadas).

184.

185. pontua([], L,L).

186. pontua([(Pos,Rotacao)|T],L, LJog_Validas_Pontuadas):-

187. vizinhos(Pos, [FW,FN,FE,FS], [PosW,PosN,PosE,PosS]),

188. Pont = 0,

189. avalia(FW, Pos,PosW, Pont, Pont1, w,LViz, LViz2),

190. avalia(FN, Pos,PosN, Pont, Pont2, n,LViz2,LViz3),

191. avalia(FE, Pos,PosE, Pont, Pont3, e,LViz3,LViz4),

192. avalia(FS, Pos,PosS, Pont, Pont4, s,LViz4,LViz5),

193.

________________________________________________________________


194. Pont_Total is Pont1 + Pont2 + Pont3 + Pont4 + 1,

195. append(L, [(Pos,Rotacao, Pont_Total)], NL),

196. pontua(T, NL, LJog_Validas_Pontuadas).

197. . . . Listagem 17 – Pontuar jogadas

Para calcular os benefícios locais de cada jogada possível o predicado

pontuarjogadas/2 é invocado sendo passado por parâmetro a lista de

jogadas possíveis e instanciando o segundo parâmetro com essa mesma lista

em que aos seus elementos é acrescentado um campo com o resultado desse

cálculo. Por cada par (Pos, Rotacao), o método pontua/3 usa novamente

o predicado vizinhos/3 (linha 187) para obter a face junta à peça de cada

vizinho, assim como a posição do mesmo. Seguidamente por cada vizinho (4) o

predicado avalia/8 (listagem 18) vai percorrer os vizinhos com faces do

mesmo tipo de recurso que está a ser avaliado.

Este é invocado 4 vezes já que podem ser 4 os vizinhos, caso não exista

vizinho, não é contabilizado qualquer ponto (linha 199). Em cada uma das

chamadas é passada cada uma das 4 faces; a posição que está a ser testada na

chamada de pontua/3 (Pos); cada uma das posições dos 4 vizinhos (PosW,

PosN, PosE, PosS); uma variável de pontuação para ser usada

recursivamente; é instanciada a pontuação resultante do percurso efectuado

(Pont1, Pont2, Pont3, Pont4); o sentido em que está o vizinho; e a lista de

vizinhos por onde já passou.

Esta é usada para evitar passar duas vezes por um mesmo vizinho, para não

ser contabilizada a pontuação desse duas vezes, já que os vizinhos da peça que

é colocada também têm os seus vizinhos, e por conseguinte os vizinhos podem

ser percorridos duas vezes.

Seguidamente as pontuações de cada percurso pelos 4 vizinhos são somadas

(linha 194), e posteriormente é adicionado à lista de jogadas válidas pontuadas

o par (Pos, Rotacao) junto da sua pontuação (linha 195). Os restantes pares

são avaliados em seguida até ser preenchida a lista.

________________________________________________________________


O método avalia/8 baseia-se no tipo de recurso (cidade, estrada, campo

ou mosteiro) para efectuar o cálculo da pontuação local. É mediante a face

vizinha à peça que vai ser colocada que o predicado avalia/8 trabalha.

Seguidamente está listado o predicado relativamente ao tipo de recurso

estrada.

198. . . .

199. avalia(null,_,_,Pont,Pont,_,L,L).

200. avalia(_,Pos,Pos,Pont,Pont,_,L,L).

201. avalia(estrada, PosOriginal,(X,Y), Pont,PontT,Sent,LViz,LVizNova):-

202. (

203. lst(LViz)->(

204. member((X,Y),LViz)->!;

205. append(LViz, [(X,Y)], LVizNova)

206. );

207. LVizNova = [(X,Y)]

208. ),

209. tabuleiro(LTab),

210. member(posicao((X,Y), ID, Rot, _), LTab),

211. Pontaux is Pont + 1,

212. peca(ID,_,centro(EF,EP,CID,MOST,PRAD),_),

213. (

214. EF == 1->avalia(null,_,_,Pontaux,PontT,_, LVizNova,_);

215. (

216. Sent = w->vizinhos((X,Y), [F1,F2,_,F3], [Pos1,Pos2,_,Pos3]),

217. S1=w,S2=n,S3=s;

218. Sent = n->vizinhos((X,Y), [F1,F2,F3,_], [Pos1,Pos2,Pos3,_]),

219. S1=w,S2=n,S3=e;

220. Sent = e->vizinhos((X,Y), [_,F1,F2,F3], [_,Pos1,Pos2,Pos3]),

221. S1=n,S2=e,S3=s;

222. Sent = s->vizinhos((X,Y), [F1,_,F2,F3], [Pos1,_,Pos2,Pos3]),

223. S1=w,S2=e,S3=s

224. ),

225. findall(

226. (Pos, Sentido),

227. (

228. Face = estrada,

229. member((Face,Pos,Sentido), [(F1,Pos1,S1), (F2,Pos2,S2), (F3,Pos3,S3)])

230. ),

231. L),

232. (

233. L == []->avalia(null,_,_,Pontaux, PontT,_,LVizNova,_);

234. member((Posaux,Sentaux), L),

________________________________________________________________


235. avalia(estrada,PosOriginal,Posaux,Pontaux,PontT, Sentaux, LVizNova,_)

236. )

237. ).

238. . . .

Listagem 18 – Avaliar jogadas

Inicialmente é testada a existência de vizinhos que já foram percorridos (linha

203), caso existam vizinhos é verificada a existência do vizinho que está a ser

testado nessa lista de vizinhos, o que se for verdade o algoritmo termina nesse

momento (linha 204), se falso é adicionado à lista. Caso não existam vizinhos já

percorridos é criada uma nova lista apenas com o vizinho actual que

posteriormente será utilizada.

Depois de consultar na base de conhecimento, o tabuleiro e qual a peça que

está colocada na posição vizinha que está a ser testada, é necessário saber se o

recurso é continuado. Neste caso o tipo de recurso é estrada, o vizinho

possui também mais 3 vizinhos, já que o outro já foi percorrido, e um destes 3

vizinhos está ligado à peça da posição actual por uma face estrada. Existe

também a possibilidade do vizinho corrente fechar um recurso e para isso é

necessário saber as características do centro da peça (linha 212 a 214). Vários

problemas surgem à volta deste facto já que analisando a figura 5 o centro das

peças pode tomar várias formas, e então optou-se por uma representação mais

detalhada do centro, sendo esta explicada na secção 4.5.

Se o vizinho em questão não fechar o recurso é então necessário saber se os

restantes 3 vizinhos continuam o recurso em questão. Caso o vizinho esteja a

norte, os restantes vizinhos estão a oeste, norte, e sul. Para os restantes casos

o mesmo raciocínio é aplicado (linhas 216 a 223). Para cada sentido são

instanciados o vizinhos pretendidos (faces, posição e sentido) através do

predicado já antes referenciado vizinhos/3. Seguidamente apenas um7 dos 3

vizinhos poderá continuar o recurso estrada, e por conseguinte procura-se

saber qual deles liga com face estrada. Se nenhuma das 3 faces vizinhas estiver

7 As peças com cruzamento fecham o recurso, o que quer dizer que os vizinhos destas já foram contabilizadas.

________________________________________________________________


instanciada com estrada, significa que uma dessas 3 posições do tabuleiro

não possui nenhuma peça colocada, e então a contagem termina invocando o

critério de paragem (linha 233). Se existir uma face vizinha estrada o recurso

será continuado e o predicado avalia/8 é invocado novamente para o vizinho

em questão (linha 235).

Dada a dificuldade de representação das entidades, torna-se também bastante

difícil trabalhar com estas, o que torna também muito difícil explicar o modo de

funcionamento de determinados procedimentos.

Além do recurso estrada existem também mais 3 tipos de recursos possíveis

que necessitam de ser tratados separadamente, já que por exemplo, o recurso

cidade poderá continuar por mais do que um vizinho.

Note-se que na linha 194 além das pontuações retornadas por cada vizinho é

necessário contar com a peça colocada que pode valer 1 ponto ou dois pontos

no caso da cidade. Actualmente a peça colocada apenas conta 1 ponto, mas

aquando da representação a nível de recursos, será necessário efectuar outra

avaliação, já que para o caso da peça com o ID=18 a pontuação

correspondente será 1 para o recurso estrada e 2 para o recurso cidade.

4.8 Exemplo de uma jogada

Este secção destina-se a explicar um exemplo de processamento da informação

numa jogada.

Admitindo que o tabuleiro actual é:

Tabuleiro = [posicao((0,0),inicial,1,0), posicao((-1,0),10,1,0), posicao((1,0),18,3,0), posicao((0,-1),8,3,0), posicao((1,1),23,1,0)].

________________________________________________________________


E a lista de posições livres respectiva é:

LPos_Livres = [(1,2),(2,1),(0,-2),(2,0),(1,-1),(-2,0), (-1,1),(-1,-1),(0,1)].

A peça extraída:

ID = 20.8

O jogador depois de receber estes dados invoca o predicado

gerar_jogas_validas/3 (linhas 123 a 133) e é criada uma lista de jogadas

válidas:

LJog_Validas = [ ((1,2),[campo,estrada,cidade,estrada]), ((1,2),[cidade,estrada,campo,estrada]), ((2,1),[campo,estrada,cidade,estrada]), ((0,-2),[estrada,cidade,estrada,campo]), ((2,0),[campo,estrada,cidade,estrada]), ((-2,0),[campo,estrada,cidade,estrada]), ((-1,1),[estrada,campo,estrada,cidade]), ((-1,-1),[cidade,estrada,campo,estrada])].

Seguidamente são calculadas as pontuações locais. É de referir que

actualmente apenas o tipo de recurso estrada está a ser pontuado.

LJog_Validas_Pontuadas = [ ((1,2),[campo,estrada,cidade,estrada],5), ((1,2),[cidade,estrada,campo,estrada],5), ((2,1),[campo,estrada,cidade,estrada],1), ((0,-2),[estrada,cidade,estrada,campo],1), ((2,0),[campo,estrada,cidade,estrada],1), ((-2,0),[campo,estrada,cidade,estrada],1), ((-1,1),[estrada,campo,estrada,cidade],1), ((-1,-1),[cidade,estrada,campo,estrada],5)].

8 Consultar figura 9.

________________________________________________________________


4.9 Nível Táctico e Estratégico

Depois de contabilizados os benefícios locais será necessário escolher a jogada

a efectuar (linha 119). Para isso torna-se fulcral a representação dos recursos

correspondentes a cada jogada possível e estudar os passos futuros. O nível

táctico abrange a noção de áreas, e tácticas propriamente ditas.

Na altura da tomada de decisão surgem perguntas que o próprio jogador se

interroga:

• Possuo peões suficientes para defender este recurso?

• Existe ainda alguma peça que não foi extraída que me permite fechar

o recurso futuramente?

• É mais importante defender a estrada ou a cidade?

• Vale a pena começar a apostar nos prados?

• Posso atacar alguma cidade com a peça que tenho na mão?

• ...

Várias outras questões surgem aquando da selecção da jogada ideal. Podem

ser adoptadas tácticas nas quais se defendem mais as cidades e noutras os

prados, apostar no ataque de cidades ou de estradas, formar prados depois de

metade das peças terem sido extraídas, etc.

Após a implementação de algumas tácticas é importante saber em que situação

aplicar a respectiva táctica. Situação que tem que ser resolvida no nível

superior, o estratégico. Neste nível será necessária a existência de mais

conhecimento adquirido no decorrer do jogo, sobre o qual se pode raciocinar.

Podem ser implementadas estratégias a longo ou a curto prazo. Uma solução

possível seria o cálculo de jogadas segundo cada táctica, e posteriormente

seleccionar a jogada que mais vezes foi escolhida de todas as tácticas.

________________________________________________________________


Este desenvolvimento a nível superior não será implementado neste projecto

devido a falta de tempo disponível.

4.10 Comunicação com um servidor de jogos na Internet

É possível, e também pretendido, que o agente possa ser utilizado para jogar

na Internet. Para o referido é necessário saber de que forma funciona o

servidor de jogos e que representações admite.

No site http://www.gamerz.net/pbmserv/commands.html , é possível

encontrar um vasto conjunto de comandos para se efectuar a comunicação

entre o agente inteligente e o servidor de jogos dos quais se destacam os

comandos para jogar da listagem 19:

239. . . .

240. game challenge userid1 userid2 [-options]

241. game move board userid password move[#moveno]

242. game move board userid password pass[#moveno]

243. . . . Listagem 19 – Comandos de um servidor de jogos

De entre os vários comandos descritos no site o que é mais relevante para a

implementação do agente é o comando para efectuar uma jogada, ou

movimento (linha 241).

O servidor aceita “strings” nos formatos listados, onde os parâmetros realçados

com o estilo “negrito”, podem tomar vários valores. Board é o código que

identifica o tabuleiro na lista de tabuleiros do servidor porque neste podem

existir vários jogos com vários jogadores em simultâneo. Userid representa o

identificador do jogador, o qual possui password para que o servidor possa

aceitar o pedido de jogada. Os valores referidos são gerados pelo servidor e

________________________________________________________________


disponibilizados ao jogador antes do início de um jogo. Assim o servidor fornece

também o tabuleiro e atribui a cada jogador uma cor com a qual irá jogar.

O agente inteligente desenvolvido no âmbito deste projecto não foi testado na

Internet devido a falta de tempo disponível para o fazer. Como já foi referido

seria necessário saber exactamente como funciona o servidor de jogos e quais

as representações que este aceita e envia ao jogador, como por exemplo, o

tabuleiro, jogadas efectuadas pelos outros jogadores, etc.

________________________________________________________________




5. Conclusão

Os objectivos inicialmente propostos para este projecto assentavam claramente

numa componente bastante prática que visava essencialmente o

desenvolvimento de um agente inteligente capaz de jogar Carcassonne.

Os jogos são um atractivo bastante influente no interesse pelo desenvolvimento

deste tipo de agentes inteligentes. No entanto, o processo que integra a sua

construção implica um estudo bastante profundo acerca da dinâmica de cada

jogo, enquadrando-a num determinado tipo de jogo. As soluções e métodos

variam mediante o tipo de jogo em questão. Para o projecto propriamente dito

revelou-se bastante complexa a pesquisa de soluções nesta área, assim como

de fundamentos teóricos para a interiorização do problema exposto.

A Inteligência Artificial é então uma componente extremamente importante

para dotar um programa de flexibilidade, dinamismo e de capacidade para

tomar decisões numa determinada situação e num determinado momento,

tendo em conta todas as variáveis externas que rodeiam o ambiente em que

está a ser desenvolvido.

Uma vez que a maioria da informação disponível, após a pesquisa, apenas trata

tipos de jogos de tabuleiro com informação completa, assim como o xadrez,

damas, etc, esse facto revelou-se um obstáculo considerável já que o

Carcassonne é um jogo com informação incompleta.

Apesar dos problemas que acompanharam este projecto ao longo da sua

implementação, o trabalho revelou-se bastante interessante e também um

grande desafio. Perante esta abordagem, torna-se possível concluir que este

projecto não se trata dum mero trabalho proposto numa disciplina do curso,

mas sim um projecto real em que é necessária bastante investigação e muitas

________________________________________________________________


horas despendidas a “partir pedra”. Em consonância com esta abordagem,

existe também uma quantidade considerável de factores que se posicionam por

detrás da implementação de um agente inteligente para um jogo deste tipo. Em

última análise, o tempo disponível foi, sem dúvida, uma barreira para a

conclusão do projecto. Não obstante desse facto, algum trabalho futuro poderá

ser considerado e acrescentado:

• Desenvolver tácticas para a competição no jogo. Neste campo será

importante uma boa representação de áreas e, se necessário, altera-

las de modo a facilitar o desenvolvimentos das mesmas;

• Criar estratégias de jogo de forma a determinar qual a táctica a

aplicar em cada situação, efectuando, consequentemente, a tomada

de decisão. Estas estratégias devem permitir visionar o jogo 1,2, ..., n

jogadas à frente.

• Testar o agente inteligente num servidor de jogos na Internet. Será

necessário conhecer os formatos de informação que o servidor

disponibiliza e o modo como comunica com os jogadores; neste caso

agentes.

É de salientar que assim como o humano desenvolve a sua inteligência ao

longo do tempo para jogar um jogo, o desenvolvimento de boas estratégias

para implementar num agente inteligente a partir da aprendizagem num

ambiente também leva o seu tempo. É incrível a quantidade de informação que

uma criança com apenas dois anos adquire e aprende, informação essa que

seria praticamente impossível de representar através de um computador para

responder a situações na vida real à imagem de uma criança.



________________________________________________________________


Bibliografia

• Inteligência Artificial, Elaine Rich e Kevin Knight – McGraw Hill

• Game review - Carcassonne

http://www.io.com/~beckerdo/games/reviews/CarcassonneReview.html

Data acesso: 15 de Março de 2004

• Review of Carcassonne, RPGNet

http://www.rpg.net/reviews/archive/9/9737.phtml


• Teoria dos Jogos, Departamento de Matemática da Universidade Católica

do Rio de Janeiro, Brasil

http://www.mat.puc-rio.br/%7Einicient/3_jogos/index_jogos.htm


• Game theory dictionary, Mike Shor – Teoria dos jogos e alguns conceitos

http://www.gametheory.net/Dictionary/


• Economistas, Bruno Lana, Brasil – Teoria dos Jogos

http://geocities.yahoo.com.br/economistasbr2001/teoriadosjogos.htm


• Teoria dos jogos e da cooperação dos filósofos

http://geocities.yahoo.com.br/discursus/tjcf/112tjcfc.html


________________________________________________________________


• Help for Common PBeM Server Commands, Gamersz.Net – Comando

para um servidor de jogos

www.gamerz.net/pbmserv/commands.html


• AI Depot, Alex J. Champandard - Inteligência Artificial e alguns

algoritmos

http://ai-depot.com/Main.html

Data acesso: 10 de Abril de 2004

• Pós-graduação em engenharia de produção – Cap. 6, Ambiente

inteligentes, Luis Alberto Alfaro Casas, Universidade Federal de Santa

Catarina – Brasil

http://www.eps.ufsc.br/teses99/casas/


• Guia de Estratégias do Carcassonne, Goard Game Geek

http://www.boardgamegeek.com/article/22560


• Inteligência Artificial em jogos 3D, Gilliard Lopes dos Santos,

universidade federal fluminense, Brasil

http://www.paralelo.com.br/documentos/Real-Time%20BSP-Based%20Path%20Planning%20with%20A-Star%20(Full-Portuguese).pdf

Data acesso: 15 de Julho de 2004

________________________________________________________________



Documents

Desenvolvimento de um Agente Inteligente para jogar