universidade federal da bahia implementac¸˜ao de um agente

Transcrição

UNIVERSIDADE FEDERAL DA BAHIA
INSTITUTO DE MATEMÁTICA
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
CÍCERO AUGUSTO MAGALHÃES DA SILVA NEVES
IMPLEMENTAÇÃO DE UM AGENTE REATIVO
UTILIZANDO REDES NEURAIS
EVOLUCIONÁRIAS
Salvador
2006
CÍCERO AUGUSTO MAGALHÃES DA SILVA NEVES
IMPLEMENTAÇÃO DE UM AGENTE
REATIVO UTILIZANDO REDES
NEURAIS EVOLUCIONÁRIAS
Monografia apresentada ao Curso de
graduação em Ciência da Computação,
Departamento de Ciência da Computação,
Instituto de Matemática, Universidade
Federal da Bahia, como requisito parcial
para obtenção do grau de Bacharel em
Ciência da Computação.
Orientador: Prof Augusto Loureiro da Costa
Salvador
2006
RESUMO
Este trabalho visa utilizar o NEAT, um algoritmo que permite evoluir redes neurais através
de algoritmos genéticos, para implementar o controle de mira de um BOT no jogo Unreal
Tournament 2004. Serão mostradas as ferramentas utilizadas para realizar os experimentos
e também os resultados dos mesmos. Ao final serão comentados as dificuldades enfrentadas
durante a implementação de tal BOT e serão sugeridas possibilidades de trabalhos futuros com
redes neurais no jogo.
Palavras-chave: redes neurais, algoritmos genéticos, unreal tournament
LISTA DE FIGURAS
1
Exemplo de um neurônio . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2
Redes Alimentada Adiante com Múltiplas Camadas . . . . . . . . . . . . . . .
9
3
Rede Recorrente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
4
Ciclo de evolução dos algoritmos genéticos . . . . . . . . . . . . . . . . . . .
11
5
Componentes para implementação de um agente para UT usando a API JavaBot
19
6
Representação genética do genoma usado pelo NEAT . . . . . . . . . . . . . .
21
7
Mutação por adição de conexão e por adição de nó respectivamente . . . . . .
21
8
Comparação entre cromossomos para realiazação do crossover . . . . . . . . .
22
9
Fenótipo da RNA com melhor fitness no experimento de XOR . . . . . . . . .
25
10
Fenótipo da RNA com melhor fintess no experimento do Forex Trading . . . .
25
11
Mapa feito no Unreal Editor para treinamento das redes neurais . . . . . . . . .
28
12
Rede resultante de 63 gerações com uma população de 60 indivı́duos . . . . . .
31
13
Resultado conseguido com uma das redes das primeiras gerações do processo
de evolução. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
14
Resultado conseguido com uma a rede da 63a geração. . . . . . . . . . . . . .
32
15
Rede obtida da 63a geração acertando o Alvo. . . . . . . . . . . . . . . . . . .
32
SUMÁRIO
1
Introdução
6
2
Conceitos
8
2.1
Redes Neurais Artificiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2
Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.3
Agentes Autônomos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.3.1
14
3
Ferramentas Utilizadas
16
3.1
Unreal Tournament 2004 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.1.1
UnrealScript e Mutators . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.2
GameBots e a API JavaBot . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.3
NEAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.3.1
Codificação genética . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.3.2
Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.3.3
Marcação do Histórico e a operação Crossover . . . . . . . . . . . . .
21
3.3.4
Proteção de inovações através da segredação por espécies
. . . . . . .
22
3.3.5
Minimização do espaço de busca através da
complexificação de estruturas . . . . . . . . . . . . . . . . . . . . . .
23
NEAT4J . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.4
4
Agentes Reativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Descrição do problema e Implementação
26
4.1
26
Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2
5
6
Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
Resultados e Dificuldades
31
5.1
Resultados obtidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5.2
Dificuldades encontradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
Conclusão
34
6.1
34
Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Apêndice A -- Protocolo de mensagens trocadas através do GameBots
36
Apêndice B -- Parâmetros de configuração para o Algoritmo Genético utilizado pelo
NEAT4J
45
Referências
51
6
1
INTRODUÇÃO
O uso da Inteligência Artificial em jogos eletrônicos tem se mostrado de grande valia tanto
para a área de IA quanto para o desenvolvimento de jogos (LAIRD; LENT, 2000).
Para a área de IA os jogos de computador representam um grande laboratório, onde é
possı́vel testar diferentes técnicas e pôr a prova teorias sem que seja necessário se preocupar
com aspectos pouco relevantes para a área. Os jogos eletrônicos se beneficiam graças aos novos
nı́veis de desafio e imersão que a IA tem trazido para esta área, tanto em jogos cujo intuito é
somente divertir como nos Serious Games, jogos feitos com o objetivo de simular situações reais
e permitir que atividades normalmente caracterizadas como de alto risco, possam ser executadas
com a finalidade de treinamento sem o perigo de haver danos a alguém.
A Neuro-Evolução tem se mostrado como uma grande promessa para a resolução problemas
complexos na área de aprendizado por reforço. Esta abordagem oferece uma alternativa aos
métodos estatı́sticos convencionais que tentam estimar a validade de uma determinada ação em
estados particulares do mundo (STANLEY, 2004).
Este trabalho tem por objetivo utilizar o NEAT (Neuro Evolution of Augmenting Topologies)
na implementação de um BOT reativo para o jogo Unreal Tournament 2004. O NEAT é um
algortimo que possui como função evoluir não só os pesos, mas também as estruturas de Redes
Neurais Artificiais através do uso de Algoritmos Genéticos. Este algoritmo foi proposto em
(STANLEY, 2004) e tem sido alvo de interesse de muitos pesquisadores além de estar sendo
utilizado no desenvolvimento de jogos (NERO, 2005).
As redes neurais serão utilizadas para implementar o controle de mira do BOT, que poderá
prever em que posição é indicado atirar a fim de que se acerte um inimigo em movimento.
A predição desta localização é um importante fator durante o combate com um oponente,
principalmente se o personagem controlado estiver portando uma arma cuja munição possui
uma velocidade baixa. Uma vez que não há como saber a aceleração do oponente nem a
velocidade do projétil referente a arma que está sendo usada, esta predição não pode ser feita
de forma determinı́stica. Será feito então o uso de redes neurais para calcular o fator tempo da
7
equação horária de Movimento Uniforme e assim obter uma localização aproximada para onde
deve ser feito o disparo.
A implementação deste controle de mira tornará o comportamento BOT mais convincente
para um jogador humano, pois ele estará executando exatamente o que uma pessoa faria. Ao
invés de tentar atirar a esmo em um inimigo, ou somente na localização atual do mesmo, o BOT
tentará prever a próxima posição em que o oponente estará, de tal forma que o tiro disparado da
arma chegue a tempo de interceptá-lo.
A seguir, no Capı́tulo 2, será dada uma explanação dos conceitos e abordagens da Inteligência
Artificial que serão utilizados neste trabalho. No Capı́tulo 3 serão apresentadas as ferramentas
utilizadas para a implementação do BOT e para a obtenção da rede neural desejada, sendo
explicado no Capı́tulo 4 como foi realizada a implementação dos BOTs utilizados no processo
de evolução das redes neurais. Após esse capı́tulo serão comentados os resultados obtidos e
as dificuldades encontradas durante a realização dos experimentos (Capı́tulo 5) e por fim, no
Capı́tulo 6 será feita uma breve conclusão sobre o trabalho e algumas sugestões para trabalhos
futuros serão citadas.
8
2
CONCEITOS
2.1
REDES NEURAIS ARTIFICIAIS
As rede neurais artificiais (RNAs) foram inspiradas no funcionamento do cérebro humano,
o qual é constituı́do por diversas células nervosas (neurônios) que conectam-se entre si através
de sinapses.
Segundo (HAYKIN, 2001) uma rede neural é um processador paralelamente distribuı́do de
forma maciça constituı́do de unidades de processamento simples, que têm a propensão natural
para armazenar conhecimento experimental e torná-lo disponı́vel para o uso. Ela se assemelha
ao cérebro em dois aspectos:
• O conhecimento é adquirido pela rede a partir de seu ambiente através de um processo de
aprendizagem.
• Forças de conexão entre neurônios, conhecidas como pesos sinápticos, são utilizadas para
armazenar o conhecimento adquirido.
Cada unidade de processamento, ou neurônio, é constituı́da basicamente por um conjunto
de sinapses ou elos de conexão, que por sua vez possuem um peso próprio; uma função para
somar os sinais de entrada, que passam pelas sinapses, ponderados por seus respectivos pesos
(combinador linear); e uma função de ativação ou função restritiva que tem como objetivo
limitar a amplitude da saı́da de um neurônio (Figura 1), impedindo dessa forma que o mesmo
seja ativado caso o estı́mulo recebido não ultrapasse um valor de ativação pré-definido (threshold).
Além disso um neurônio pode possuir também um bias aplicado externamente, com o objetivo
de realizar uma transformação afim à saı́da do combinador linear (HAYKIN, 2001) .
O motivo do uso de uma função de ativação nos neurônios deve-se à analogia que se faz com
as sinapses que ocorrem no cérebro humano inibindo ou excitando um determinado neurônio a
depender do estı́mulo recebido por este.
9
Figura 1: Exemplo de um neurônio
Dá-se o nome de arquitetura de rede à maneira como os neurônios de uma RNA estão
dispostos na mesma. Existe em geral três classes de arquiteturas diferentes:
• Redes Alimentadas Adiante com Camada Única: se trata de uma rede em camadas que
possui apenas uma camada de entrada, formada pelos nós de fonte que receberão os
estı́mulos externos, conectada a uma camada de saı́da de neurônios que representam os
nós computacionais dessa rede.
• Redes Alimentadas Adiante com Múltiplas Camadas: difere da arquitetura anterior por
possuir uma ou mais camadas ocultas entre a camada de entrada e a camada de saı́da.
Esta camada oculta provê um maior poder de generalização para a rede, permitindo que
esta seja capaz de extrair estatı́sticas de ordem elevada (HAYKIN, 2001).
• Redes Recorrentes: ao contrário das outras duas arquiteturas que não possuem ciclos
em suas estruturas, esta apresenta pelo menos um laço de realimentação influenciando
bastante a capacidade de aprendizagem e o desempenho da rede.
Figura 2: Redes Alimentada Adiante com Múltiplas Camadas
10
Figura 3: Rede Recorrente
2.2
ALGORITMOS GENÉTICOS
Os Algoritmos Genéticos (AGs) tiveram sua origem nos trabalhos de John Holland quando
este publicou em 1975 seu livro, ”Adaptation in Natural and Artificial Systems”. Os AGs
baseiam-se na teoria da evolução e seleção natural de Darwin, onde os indivı́duos que melhor se
adaptam ao meio em que estão inseridos têm maiores chances de sobreviver e gerar descendentes.
Em vista disso a terminologia adotada no contexto de Algoritmos Genéticos vêm também
da teoria da evolução natural e da genética. Cada possı́vel solução para um problema é apresentada
por um indivı́duo que faz parte de uma população de soluções. Este indivı́duo é representado
por um cromossomo, que por sua vez possui a codificação genética, ou genótipo, para uma
possı́vel solução de um problema (fenótipo). Cada cromossomo é implementado na forma de
uma lista de atributos, onde cada atributo é chamado de gene e os valores que um gene pode
assumir são chamados de alelos.
O uso de algoritmos genéticos se baseia na busca, em uma população de possı́veis soluções,
para um problema objetivando o equilı́brio entre duas metas: o aproveitamento das melhores
soluções e a exploração do espaço de busca. Uma caracterı́stica importante dos algoritmos
genéticos é que o processo de busca, diferentemente de outros métodos, ocorre de forma paralela
e estruturada (REZENDE, 2003). Apesar dos Algoritmos Genéticos serem aleatórios, a busca
feita através deles é direcionada, uma vez que é feito o uso de informações históricas para
encontrar novos pontos de busca onde são esperados melhores desempenhos.
Os algoritmos genéticos operam dentro de um ciclo (Figura 4) constituı́do das seguintes
etapas:
1. Geração de uma população de soluções potenciais
2. Submissão dos indivı́duos a uma função de fitness
3. Geração de uma nova população privilegiando os indivı́duos que tiveram melhor fitness
11
4. Geração de novos indivı́duos através de mutação ou crossover de alguns indivı́duos do
novo grupo
5. Repetição de todo o processo até que uma quantidade de iterações seja atingida ou até
que um determinado nı́vel de adaptação seja alcançado
Figura 4: Ciclo de evolução dos algoritmos genéticos
O método mais utilizado para a geração de uma população inicial é a inicialização aleatória.
Contudo, se forem conhecidas soluções que estejam próximas a(s) solução(ões) ótima(s), não
há nada que impeça que os cromossomos da população inicial sejam codificados de forma
determinı́stica. A seleção dos indı́viduos mais aptos da população é feita baseada em uma
função de aptidão ou função de fitness. Esta função recebe como entrada os valores do genótipo
do cromossomo e fornece como resultado o quão boa uma solução codificada por um indivı́duo
é para o problema que se quer resolver. Depois de feita a avaliação dos indivı́duos da população,
o processo de seleção escolherá um subconjunto de indivı́duos desta população para que seja
criada a próxima geração de indivı́duos, sendo que existem diferentes tipos de seleção quase
todas privilegiando os indivı́duos com maior aptidão, mas não de forma exclusiva, a fim de
manter-se a diversidade (REZENDE, 2003).
É preciso ter cuidado para que duas ocorrências indesejáveis sejam evitadas durante o
processo de seleção: um é a existência de um indivı́duo com um fitness muito maior que
os outros que poderá acabar monopolizando as seleções, gerando populações com indivı́duos
muito parecidos. Este evento é chamado de convergência precoce (BITTENCOURT, 2005). Outro
evento indesejável é a eliminação de indivı́duos com um fitness muito baixo. A baixa aptidão
desses indivı́duos provavelmente irá fazer com que eles não sejam escolhidos para gerar descendentes, o que não é aconselhável, uma vez que eles representam a fonte de diversidade das
soluções. Caso sejam eliminados de forma prematura isso também irá resultar numa convergência precoce da população.
12
A importância da diversidade nas populações se dá pelo motivo das funções objetivos serem
em sua maioria multimodais. Isso faz com que uma convergência precoce ocorra geralmente
em um máximo local. Com a diversidade nas populações as chances de se chegar a um máximo
global aumentam consideravelmente (BITTENCOURT, 2005).
É importante observar que pelo fato dos AGs serem processos estocásticos, indivı́duos com
boas aptidões podem ser eliminados durante o processo evolutivo ao não serem escolhidos para
gerar descendentes. Esse problema é resolvido muitas vezes utilizando-se o elitismo, onde os n
melhores indivı́duos sempre são selecionados para a próxima geração.
O surgimento de uma nova população a partir dos indivı́duos selecionados ocorre através
dos operadores genéticos, mutação e crossover . Estes operadores têm a função de gerar uma
população totalmente nova mas que ao mesmo tempo carregue consigo caracterı́sticas de seus
pais.
O operador de mutação age modificando aleatoriamente o valor de um ou mais genes de
um cromossomo, sendo que a probabilidade de um gene ser alterado por ele é chamada de taxa
de mutação, e a esta normalmente são atribuı́dos valores baixos, pois o objetivo da mutação é
apenas criar uma variação extra na população sem, contudo, danificar o progresso alcançado
com a busca. Além disso, a mutação ajuda a contornar o problema dos mı́nimos locais por
causar uma pequena alteração na direção da busca feito pelo Algoritmo Genético (REZENDE,
2003).
O crossover é o operador genético predominante na geração da nova população. O conceito
básico do operador de crossover é que ele realiza a troca de informações entre dois indivı́duos
candidatos criando novas soluções que contêm informações combinadas destes indivı́duos.
Alguns dos operadores de crossover que existem são os de um-ponto, multipontos e uniforme.
O crossover de um ponto seleciona aleatoriamente um ponto de corte nos cromossomos pais e os
segmentos gerados a partir deste corte são trocados dando origem a dois novos indivı́duos. Já no
crossover de multipontos, como o próprio nome já diz vários pontos de corte são selecionados
nos cromossomos pais e a partir daı́ troca-se o material genético entre eles. Por último tem-se o
crossover uniforme que realiza a combinação genética escolhendo, através de uma probabilidade
fixa, qual dos pais vai fornecer informações para cada gene do filho, isso faz com que cada gene
possua uma informação independente da sua posição relativa no cromossomo.
Além dos operadores genéticos e método de seleção a ser escolhido, outros parâmetros
também têm grande influência no desempenho de Algoritmos Genéticos como o tamanho da
população, a taxa de crossover e mutação, o intervalo de geração e o critério de parada (REZENDE,
2003). O tamanho da população afeta o desempenho de um AG pois caso essa população
13
seja muito pequena, haverá apenas uma pequena cobertura do espaço de busca, por outro
lado trabalhar com populações grandes demanda mais recursos computacionais além de um
tempo maior de trabalho do algoritmo. A taxa de crossover alta irá resultar no surgimento
mais rápido de novas estruturas na população, o que pode inclusive causar a retirada muito
rápida de indivı́duos com boas aptidões da população, enquanto que uma taxa muito baixa irá
estagnar o processo de evolução. Já com a taxa de mutação ocorre o contrário: não é desejável
que ela seja alta pois pode tornar o processo de busca aleatório. O ideal é que esta taxa seja
baixa o suficiente para impedir que a busca fique estagnada em algum sub-espaço, além de
permitir que qualquer ponto do espaço de busca seja atingido. O intervalo de geração indica
a porcentagem da população que será substituı́da para a próxima geração. Um valor muito
elevado para este parâmetro pode resultar na perda de estruturas com boa aptidão, enquanto
que um valor baixo causará lentidão no processo evolutivo. O critério de parada indica em
que momento o Algoritmo Genético deve parar, quer seja depois de um determinado número
de gerações ou quando as aptidões dos melhores indivı́duos não mudarem depois de um certo
tempo.
2.3
AGENTES AUTÔNOMOS
A definição do que é um agente não é universal, sendo uma das mais abrangentes a seguinte
segundo (REZENDE, 2003) :
Um agente é uma entidade real ou virtual, capaz de agir num ambiente, de se
comunicar com outros agentes, que é movida por um conjunto de inclinações (sejam
objetivos individuais a atingir ou uma função de satisfação a otimizar); que possui
recursos próprios; que é capaz de perceber seu ambiente (de modo limitado); que
dispõe (eventualmente) de uma representação parcial deste ambiente; que possui
competência e oferece serviços; que pode eventualmente se reproduzir e cujo comportamento tende a atingir seus objetivos utilizando as competências e os recursos
que dispõe e levando em conta os resultados de suas funções de percepção e comunicação, bem como suas representações internas.
Agentes são normalmente vistos como instrumentos integradores das técnicas de IA (REZENDE,
2003) e possuem alguns ingredientes-chave que os caracterizam: Autonomia de Decisão, Autonomia de Execução, Competência para Decidir, Existência de uma Agenda Própria, Reatividade,
Adaptabilidade, Mobilidade, Personalidade, Interatividade com o Usuário, Ambiente de Atuação,
14
Comunicabilidade. Além dessas caracterı́sitcas os agentes também podem ser classificados
segundo alguns eixos tais como o eixo Cognitivo, o de Foco, o de Atuação e o eixo Ambiental.
No que diz respeito ao eixo Cognitivo o agente pode ser um Agente Cognitivo onde suas
ações são baseadas em um planejamento feito a partir de um modelo do ambiente construı́do
pelo próprio agente; ou um Agente Reativo, que somente reage a estı́mulos provocados pelo
ambiente onde está.
Todo agente deve possuir componentes que o auxiliem na execução ou na sugestão das
ações a serem tomadas, considerando seus objetivos, ambiente e perfil de atuação. A essas três
caracterı́sticas dá-se o nome de modus operandi, podendo este ser constituı́do do mapeamento
da percepção sensorial do ambiente para ações ou então de um planejador de ações.
2.3.1
AGENTES REATIVOS
Agentes reativos são agentes baseados no modelo de funcionamento estı́mulo-resposta e
possuem as seguintes caracterı́sticas:
• não há representação explı́cita do conhecimento: o conhecimento do agente é implı́cito
(as suas regras de comportamento) e sua manifestação se externa através do seu comportamento;
• não há representação do ambiente: o comportamento (resposta) do agente é baseado no
que ele percebe (estı́mulo) a cada instante. Não há uma representação interna explı́cita do
ambiente;
• não há memória das ações: os agentes reativos não mantém nenhum tipo de histórico
de suas ações, ou seja, o resultado de uma determinada ação passada não influencia
diretamente na decisão de uma ação futura.
O processo de realizar uma ação a partir de dados sensoriais normalmente é dividido em
duas fases. Uma fase em que o processamento sensorial produz um vetor de caracterı́sticas e
uma fase de computação da ação onde uma determinada ação é selecionada baseada nos valores
contidos neste vetor. Tais caracterı́sticas são escolhidas por quem está implementando o agente
de forma a manterem uma correlação com as caracterı́sticas do ambiente que são relevantes
para a escolha da ação a ser tomada no estado atual do mesmo (NILSSON, 1998).
As técnicas descritas neste capı́tulo servirão de base para as ferramentas que serão utilizadas
neste trabalho bem como para a execução dos experimentos descritos no Capı́tulo 4.
15
3
FERRAMENTAS UTILIZADAS
3.1
UNREAL TOURNAMENT 2004
O jogo Unreal Tournament 2004 (UT2004) é um jogo tri-dimensional de tiro em primeira
pessoa1 criado pela Epic Games em parceria com a Digital Extremes, e foi concebido para jogos
do tipo multiplayer, permitindo que um ou mais jogadores disputem partidas em time, de forma
cooperativa, ou em partidas em que cada jogador busca a realização de objetivos individuais.
Cada jogador controla um personagem do jogo, sendo que um jogador pode ser tanto uma
pessoa como um BOT. Um BOT é um agente autônomo que tem a função de controlar um
personagem durante as partidas da forma mais parecida com um humano possı́vel, enquanto
tenta cumprir seus objetivos que podem incluir matar seus oponentes e/ou proteger seus aliados
no caso de uma partida cooperativa.
Um BOT é alimentado pelo servidor com informações sensoriais e atua sobre o ambiente
a partir de comandos dados ao personagem controlado por ele, comandos esses que incluem:
olhar para uma determinada direção, andar, saltar, agachar-se e atirar. Cada personagem possui
alguns dados que informam o seu status atual no jogo. Essas informações incluem a arma que
está usando, quanto de munição possui (Ammo), qual o seu nı́vel de saúde (Health), qual seu
nı́vel de proteção (Armor) e a sua pontuação ou pontuação do seu time (Score). Durante uma
partida, é possı́vel coletar itens no ambiente que aumentem os nı́veis de Health, Armor ou de
Ammo do jogador.
As partidas no jogo UT2004 ocorrem em levels, cada um desses possuindo um mapa que
representa o ambiente fı́sico em que os jogadores irão se enfrentar. Os objetivos para se alcançar
a vitória variam para cada formato de partida existente, podendo ir da simples contagem de
inimigos que foram mortos por um jogador até o cumprimento de tarefas mais complexas,
como dominação de um determinado ponto do mapa em que ocorre a partida. Alguns dos tipos
1 Jogos
de tiro em primeira pessoa (do inglês First Person Shooter) são jogos em que o jogador compartilha o
mesmo ponto de vista e as mesmas percepções sensoriais do personagem controlado por ele, e faz uso de armas
para alcançar determinados objetivos durante as partidas.
16
de partida existentes são:
• Deathmatch (DM): É o mais comum dos formatos de partida existentes para jogos de
tiro em primeira pessoa. O objetivo deste tipo de jogo é eliminar tantos outros jogadores
quanto possı́vel até que um certo limite de tempo ou de inimigos eliminados seja atingido.
Vence o jogador que tenha eliminado mais oponentes.
• Team DeathMatch (TDM): neste formato de partida muito semelhante do DM, os jogadores são divididos em dois times, cada time tendo um Score próprio. O objetivo deixa de
ser eliminar qualquer jogador da partida e passa a ser eliminar qualquer jogador que não
esteja no seu time.
O jogo UT2004 oferece uma boa diversidade de armas que podem ser utilizadas pelos
jogadores durante as partidas. Cada uma dessas armas possui uma munição e velocidade de tiro
especı́ficas. Cada tipo de munição existente em UT2004 possui também caracterı́sticas próprias
como velocidade, quantidade de dano que causa, além dos efeitos colaterais quando esta se
choca com algo no ambiente do jogo.
3.1.1
UNREALSCRIPT E MUTATORS
A série de jogos Unreal Tournament (UT), incluindo aı́ o UT2004, possui uma linguagem de
script, chamada UnrealScript, que pode ser utilizada para realizar alterações nas caracterı́sticas
do jogo por terceiros. Tal ferramenta foi criada com o intuito de prover ao time de desenvolvimento de UT uma linguagem de programação voltada para as necessidades e nuances da programação
para jogos.
Ela oferece um estilo de programação simples, semelhante à linguagem Java, com checagem
de erros em tempo de compilação. As principais caracterı́sticas que o UnrealScript herdou
da linguagem Java são: inexistência de ponteiros, ambiente com uso de garbage collector
automático, herança simples entre classes, tipagem forte e checada em tempo de compilação,
sintaxe semelhante a Java e C/C++ e geração de bytecodes, permitindo o uso dos códigos
gerados com ela em diferentes plataformas (ex.: Windows, Unix, Mac) (SWEENEY, 1998).
Utilizando o UnrealScript é possı́vel escrever códigos para alterar determinados aspectos
do jogo como armas disponı́veis e itens que podem ser coletados. A estas modificações dá-se o
nome de Mutators. Os Mutators podem ser classificados como plugins que realizam uma ação
em resposta a eventos que ocorram no jogo. Um exemplo de Mutator é o do tipo Arena, ao usar
esse Mutator todas as armas disponı́ves em uma partida são substituı́das por um único tipo de
17
arma, todos os itens referentes a munição são substituı́dos por munição para a arma escolhida e
todos os jogadores começam com esta arma e nenhuma outra mais (JBP, 2000).
3.2
GAMEBOTS E A API JAVABOT
GameBots é um projeto que se iniciou no Information Sciences Institute da University of
Southern California (USC-ISI) com o objetivo de permitir o uso do jogo Unreal Tournament
para pesquisas na área de Inteligência Artificial. O principal produto deste projeto é uma
modificação para o jogo UT que fornece a funcionalidade de se controlar personagens do
jogo através de sockets (GAMEBOTS, 2002). Através desta modificação o personagem recebe
informações sensoriais do jogo (servidor) através da conexão de rede e baseado nestas informações, uma aplicação cliente (BOT) pode decidir que ações o personagem irá tomar: andar, pular,
falar, entre outras.
Inicialmente a modificação foi feita para o jogo UT, contudo, uma implementação parcial do
GameBots foi feita para Unreal Tournament 2003 (UT2003) por John Manoloviche e posteriormente terminada por Jessica Bayliss e Tim Garwood do Rochester Institute of Technology (RIT).
Junto com a adaptação do GameBots para UT2003 também foi feita uma versão da modificação
para UT2004, que além de corrigir alguns bugs existentes na primeira versão e adicionar novos
tipos de mensagens também sofreu um processo de refactoring2 a fim de reduzir a redundância
em inúmeras hierarquias de classe e deixar o código base mais fácil de se manter (RIT, 2005).
O protocolo de envio e recebimento de mensagens do GameBots é bastante simples. Todas
as mensagens vindas do servidor possuem a seguinte estrutura: ”Tipo arg1 val1 arg2 val2
...”, onde Tipo indica a qual tipo de informação esta mensagem se refere; arg1 e arg2 são os
atributos que podem vir junto com a mensagem dando informações adicionais (coordenadas
de localização ou um valor quantificado); val1 e val2 são os respectivos valores dos atributos.
Os comandos enviados ao personagem também possuem este mesmo formato. Um exemplo
de uma mensagem recebida pelo servidor seria: MSG {Id Player-1} {String Attack the base!}
{Location 12,23,34} (ver apêndice A).
Os tipos de mensagens recebidas pelo cliente constituem dois tipos básicos: mensagens
sı́ncronas e mensagens assı́ncronas. Mensagens sı́ncronas são enviadas a um cliente em lotes
dentro de um intervalo de tempo pré-configurado. Tais mensagens incluem informações do que
o personagem enxerga e sobre o status do mesmo. Todo lote de mensagens sı́ncronas começam
2 O termo refactoring é utilizado na área de engenharia de software para se referir ao ato de alterar o código-fonte
de um programa a fim de facilitar o entendimento e manutenibilidade do mesmo, sem alterar o seu comportamento
externo.
18
com uma mensagem do tipo ”BEG”contendo um valor indicando o instante de tempo do jogo
em que foi enviado (timestamp). Todas as mensagens subsequentes farão parte do mesmo lote
até que seja recebida uma mensagem do tipo ”END”com o mesmo timestamp da mensagem
”BEG”correspondente. Como todas essas mensagens são enviadas durante o mesmo instante
de tempo de jogo, elas representam um único estado da partida (RIT, 2005).
Mensagens assı́ncronas, por sua vez, representam eventos que podem ocorrer a qualquer
momento do jogo, como por exemplo sofrer dano ou se chocar com uma parede. É importante
notar que apesar de poder ser enviada a qualquer momento do jogo, uma mensagen assı́ncrona
nunca irá ser enviada entre uma mensagem do tipo ”BEGIN”e uma do tipo ”END”de um lote
de mensagens sı́ncronas (RIT, 2005) e que também não há como saber o timestamp destas
mensagens.
Com o intuito de facilitar a realização de pesquisas na área de Inteligência Artificial utilizando o GameBots, Andrew Marshall da USC-ISI implementou a API JavaBot. Essa API tem como
principal objetivo permitir que desenvolvedores consigam programar BOTs para jogos da série
UT sem se preocuparem em lidar com aspectos especı́ficos do protocolo do GameBots, como
por exemplo o parsing das mensagens recebidas pelo BOT ou programação de sockets. Desta
forma a programação em Java de uma aplicação que faça uso de Inteligência Artificial para
trabalhar com o GameBots se torna bastante direta, sendo necessário somente implementar a
interface BOT do pacote JavaBot (ROZICH, 2002).
Figura 5: Componentes para implementação de um agente para UT usando a API JavaBot
19
3.3
NEAT
A Neuro-Evolução é a área que estuda a evolução de RNAs (Redes Neurais Artificiais) e
uma das abordagens usadas para tal é chamada de TWEANN (Topology and Weight Evolutionary
Neural Networks). Esta abordagem busca evoluir tanto a topologia das redes como os pesos de
suas conexões utilizando Algoritmos Genéticos (AGs). Contudo, verificam-se alguns problemas
referentes ao uso de AGs para evoluir estruturas de RNAs. Entre estes problemas estão a escolha
da codificação mais adequada que possua representação tanto da topologia quanto das conexões
da rede e permita haver cromossomos de tamanhos diferentes; a realização do cruzamento de
cromossomos que representam estruturas completamente distintas; a preservação de inovações
nas estruturas, evitando que estas se percam durante o processo de evolução; e a minimização
do espaço de busca de soluções.
Pensando nisso, Kenneth O. Stanley propôs em (STANLEY, 2004) um algoritmo chamado
NEAT (Neuro Evolving Augmenting Topologies) o qual segue princı́pios básicos que o tornam
capaz de evoluir complexas estruturas de redes neurais juntamente com seus pesos. Estes
princı́pios incluem a implementação de um método para detectar estruturas homólogas, proteção
de inovações que venham a surgir durante o processo de evolução e minimização do espaço de
busca.
A codificação genética no NEAT é feita visando permitir que as estruturas das redes neurais
possam ser modificadas de forma dinâmica. Este requisito é importante pois, para permitir
que as estruturas se tornem cada vez mais complexas, o genoma não pode ter um tamanho
fixo, senão a complexidade da sua solução poderá estar limitada ao tamanho máximo de genes
permitido pela sua representação genética.
3.3.1
CODIFICAÇÃO GENÉTICA
O genoma no NEAT possui duas listas de genes, uma representando os neurônios (node
genes) e a outra as conexões existentes entre esses neurônios (connection genes). Cada node
gene possui um número de identificação e uma indicação do seu tipo (entrada, oculto ou saı́da)
e cada gene de conexão possui uma identificação global chamada Innovation Number , uma
identificação dos neurônios que estão conectados, sendo um de entrada e outro de saı́da, o peso
desta conexão e uma flag de habilitação, que indica se esta conexão deve ser representada no
fenótipo, ou seja, na RNA.
20
Figura 6: Representação genética do genoma usado pelo NEAT
3.3.2
MUTAÇÃO
A mutação em Sistemas Neuro-Evolucionários normalmente é efetuada aplicando uma
perturbação, com probabilidade fixa, nos pesos das conexões, adicionando a eles um número de
ponto flutuante escolhido a partir de uma distribuição uniforme de valores positivos e negativos.
Utilizando a representação genética citada, o NEAT permite que outros dois tipos de mutação
sejam efetuados além deste: a adição de conexões e a adição de neurônios à estrutura da rede.
Na adição de conexões uma nova conexão é criada entre dois neurônios que não estavam
conectados anteriormente (Figura 7). Já a adição de neurônios desabilita uma conexão préexistente entre dois neurônios e cria duas novas conexões, uma ligando um neurônio de entrada
com o novo neurônio e outra ligando este neurônio ao neurônio de saı́da (ver Figura 7). A
conexão estabelecida entre o neurônio de entrada e o novo neurônio recebe o valor 1 (um) para
o seu peso, enquanto que a conexão entre o novo neurônio e o neurônio de saı́da permanece
com o peso da conexão que foi desfeita. Essa ”divisão”de uma conexão em duas, acaba por
inserir não-linearidade ao sistema, possibilitando o desenvolvimento de caracterı́sticas novas
em cima do comportamento já existente, ao mesmo tempo em que não destrói a estrutura da
rede pré-existente.
Figura 7: Mutação por adição de conexão e por adição de nó respectivamente
21
3.3.3
MARCAÇÃO DO HISTÓRICO E A OPERAÇÃO CROSSOVER
O problema de como realizar a operação de crossover é resolvido no NEAT utilizandose a marcação do histórico dos genes. Isso é possı́vel graças ao uso do Innovation Number ,
que representa a cronologia dos genes no sistema e permite verificar se dois genes quaisquer
possuem a mesma origem histórica. Tendo esta informação, pode-se dizer a qual indivı́duo da
população um gene se refere. Basicamente o Innovation Number é um contador global que é
incrementado quando um novo gene surge e associado então a este gene. Enfim, para realizar
o crossover é preciso comparar os genomas dos pais entre si. Cada genoma é alinhado um
contra o outro, de forma que haja uma ordem crescente do Innovation Number (IN). Os genes
de um pai que não possuam correspondentes (mesmo IN) no outro são chamados de disjoint,
caso o outro pai possua genes mais velhos(IN baixo), ou podem ser chamados de excess caso
o outro pai não possua genes mais velhos. Os genes disjoint e excess são herdados do pai com
melhor fitness , mas se este for igual, eles podem ser herdados randomicamente. Genes com
o mesmo IN podem ser cruzados de duas maneiras. Na primeira, o gene passado ao filho é
escolhido aleatoriamente entre os pais. A outra maneira consiste em passar um gene para o
filho com a média do peso dos genes dos pais. Além disso, genes desabilitados têm uma chance
de serem reativados nos novos indivı́duos dando margem às redes de fazerem uso de genes
mais antigos novamente. Estas marcações do histórico dos genes permitem ao NEAT realizar o
crossover sem uma análise sobre a topologia da rede, pois a compatibilidade entre as estruturas
é garantida apenas pelo IN.
3.3.4
PROTEÇÃO DE INOVAÇÕES ATRAVÉS DA SEGREDAÇÃO POR
ESPÉCIES
De acordo com Stanley (STANLEY, 2004) redes recentemente evoluı́das têm inicialmente o
seu fitness diminuı́do, mas isso ocorre apenas porque a rede ainda não teve o tempo necessário
para se otimizar. Aliado a isso, redes menos complexas tendem a se otimizar mais rapidamente,
provocando um sério problema que consiste na perda de inovações em potencial caso o tempo
necessário não seja dado à nova rede e ela seja superada por redes menores, que por sua vez
podem não levar a uma solução ótima global.
O NEAT realiza a segregação das soluções existentes em uma população, em espécies.
Essa segregação tem como objetivo dar tempo às inovações topológicas de aprimorarem suas
estruturas antes de terem que competir com um número maior de indivı́duos. Para realizar tal
segregação, é feita uma medida de ”‘distância histórica”, que indica o quanto em comum dois
22
Figura 8: Comparação entre cromossomos para realiazação do crossover
indivı́duos têm em termos cronológicos. Utilizando-se as marcações de histórico dos genes, a
distância entre dois indivı́duos é medida através da seguinte equação:
δ = c1 × NE + c2 × ND + c3 ×W
Onde E representa a quantidade de genes excedentes entre os dois genomas, D é a quantidade
de genes disjuntos e W a diferença de pesos média entre genes que se combinam. As constantes
c1 , c2 e c3 servem para dar o devido peso para cada um desses elementos e N é a quantidade de
genes no maior genoma.
A organização e classificação dos genomas (cromossomos) em espécies se dá da seguinte
maneira: no inı́cio do processo evolucionário é criada a espécie de número 1 e o primeiro
genoma criado é designado a ela. Os cromossomos subsequentes são comparados com todos
as outras espécies existentes. Caso a distância δ entre o genoma que está sendo comparado e
o representante da espécie corrente for menor que um limite inferior δt , tal genoma é colocado
nesta espécie. Caso o cromossomo não se classifique em nenhuma das espécies, uma nova
espécie é criada para acolher este indivı́duo. Esse processo de comparação se inicia pelas
espécies mais antigas, o que dá a elas a chance de receber novos indivı́duos. Dessa forma,
o NEAT é capaz de identificar espécies que não apresentaram melhoramentos durante muitas
gerações (onde não houve adição de novos genomas) e removê-las da população. O NEAT faz
23
uso da divisão de fitness explı́cita, onde cada indivı́duo compartilha de um fitness comum ao seu
nicho, evitando que uma espécie se torne muito grande ou que um indivı́duo tome conta de toda
uma espécie. Baseado nisto a cada espécie é designado um número máximo de descendentes
que esta pode ter. Por fim, a escolha de quem vai ser parte da próxima geração é feita do seguinte
modo: a fração de indivı́duos que teve o pior fitness é eliminada, os pais que irão gerar novos
indivı́duos para a próxima geração são escolhidos aleatoriamente dos indivı́duos remanescentes
e o melhor indivı́duo de cada espécie é mantido para a próxima geração.
3.3.5
MINIMIZAÇÃO DO ESPAÇO DE BUSCA ATRAVÉS DA
COMPLEXIFICAÇÃO DE ESTRUTURAS
A população inicial do NEAT é constituı́da por indivı́duos com a mesma estrutura topológica
(todos os nós de entrada conectados a todos os nós de saı́da, sem camadas ocultas), variando
somente os pesos das conexões entre um indivı́duo e outro. Através do processo de evolução
novas estrututras são introduzidas através da mutação.
O NEAT consegue minimizar o espaço de busca de soluções através do processo de complexificação, evitando que estruturas desnecessárias sejam introduzidas no conjunto de soluções
existentes. Isto é feito mantendo na população de soluções somente as novas estruturas que se
mostrem aptas através da avaliação de fitness . Desta maneira o NEAT consegue realizar uma
busca através de um número mı́nimo de dimensões de pesos, reduzindo de forma significante o
número de gerações necessárias para se achar uma solução e garantindo que as redes se tornarão
não mais complexas do que o necessário. A este processo dá-se o nome de complexificação,
O uso da complexificação, permite que o NEAT busque por espaços de soluções reduzidos,
pois uma vez que uma nova estrutura é introduzida, os pesos das conexões já existentes já
estão otimizados, sendo necessário apenas realizar o ajuste fino dos pesos das novas conexões
para que estas trabalhem bem com as já existentes, ou vice-versa. Em outras palavras, as
estruturas mais simples já existentens no inı́cio do processo evolucionário podem não satisfazer
o problema de forma global, contudo soluções locais ótimas provavelmente aparecerão nesses
momentos iniciais. Com o aumento da complexidade no decorrer do tempo, aumenta-se também
a dimensão do espaço de soluções a ser vasculhado. Pelo fato das soluções ótimas para espaços
menores de buscas, representados pelas espécies, já terem sido encontradas anteriormente, a
busca em um espaço dimensionalmente maior será acelerada pois menos parâmetros precisarão
ser otimizados simultaneamente.
24
3.4
NEAT4J
O algoritmo criado por Kenneth Stanley possui diversas implementações para diferentes
linguagens (Java, C++, C, Delphi e Matlab). Das opções existentes a implementação escolhida
para realização dos experimentos foi o NEAT4J, desenvolvida em Java por Matt Simmerson
(SIMMERSON, 2006). A escolha de uma implementação feita em Java do NEAT, foi direcionada
por estar sendo usado neste trabalho a API JavaBot, também feita em Java, o que facilitaria a
integração das duas ferramentas. Apesar de existirem outras duas implementações para a mesma
linguagem (ANJI e JNEAT), o NEAT4J foi escolhido por apresentar uma maior facilidade de
uso, com tutoriais disponibilizados pelo autor no site do projeto explicando como estender o
framework para experimentos que não aqueles que acompanham a distribuição.
Para criar um experimento o que precisa ser feito basicamente é criar uma classe que
extenda a classe org.neat4j.neat.core.NeuralFitnessFunction, que representa a função de fitness
a ser utilizada durante o processo de evolução do Algoritmo Genético, e implementar o método
evaluate(Chromosome genotype) de acordo com a avaliação que será feita. Este método recebe
como parâmetro um genótipo e a depender da implementação realizada, avalia este mesmo
genótipo retornando o valor desta avaliação.
Além disso é preciso criar um arquivo de configuração que será lido pela aplicação que irá
gerenciar o processo de evolução (org.neat4j.neat.applications.train.NEATGATrainingManager).
Este arquivo contém informações relacionadas ao processo evolucionário (probabilidade de
mutação, quantidade de épocas, fitness máximo) e à estrutura inicial das redes (quantidade de
nós de entrada e de saı́da). Mais detalhes podem ser vistos no Apêndice B. O framework dispõe
também de uma classe (org.neat4j.neat.applications.core.NEATApplicationEngine) que permite
a visualização do fenótipo de um cromossomo, ou seja, a estrutura da RNA propriamente dita
(veja Figuras 9 e 10). Neste modelo de representação pode-se identificar:
Nós laranjas - neurônios de saı́da da rede
Nós cinzas - neurônios pertecentes à(s) camada(s) oculta(s)
Nós verdes - neurônios sem conexões de entrada e agem como bias na rede
Nós verdes - neurônios de entrada
Arestas vermelhas - conexões diretas
Arestas amarelas - conexões recorrentes que conectam dois neurônios distintos
25
Arestas azuis - conexões recorrentes que conectam um neurônio a ele mesmo
Figura 9: Fenótipo da RNA com melhor fitness no experimento de XOR
Figura 10: Fenótipo da RNA com melhor fintess no experimento do Forex Trading
No capı́tulo seguinte será explicado como essas ferramentas foram utilizadas em conjunto
para que fosse possı́vel realizar os experimentos relacionados a este trabalho bem como o
ambiente necessário para a execução dos mesmos.
26
4
DESCRIÇÃO DO PROBLEMA E
IMPLEMENTAÇÃO
4.1
PROBLEMA
O uso de técnicas de Inteligência Artificial em jogos de computador visa fazer com que os
personagens de um jogo consigam simular inteligência e erros humanos, apresentando portanto
um desafio maior aos jogadores, ao mesmo tempo em que propicia uma maior imersão e melhor
experiência do jogo (KISHIMOTO, 2004).
No jogo UT2004, a caracterı́stica mais importante é o combate. Quando se enfrenta um
adversário, o principal objetivo é tentar acertá-lo com disparos de forma a eliminá-lo da partida.
Algumas armas em UT2004 como o Assault Rifle e a Machine Gun possuem projéteis com
velocidades muito rápidas, fazendo com que seja possı́vel, mesmo com o oponente estando
longe e se movimentando acertá-lo apenas mirando na sua localização atual. Contudo existem
armas como o Rocket Launcher e a emphLink Gun cujos projéteis são sensivelmente mais
lentos, tornando necessário predizer a posição futura do inimigo baseando-se na sua direção,
velocidade, distância do atirador e velocidade do projétil referente à arma que está sendo usada
no momento.
Para se resolver este problema, o uso da fórmula para cálculo de deslocamento com velocidade constante poderia ser usada. Contudo, a velocidade de um jogador em UT2004 não é
constante, podendo mudar bruscamente devido a fatores externos (ser atingido por um projétil)
e internos (jogador decide mudar o rumo que estava tomando). Além disso, não é possı́vel obter
também a aceleração do jogador tão pouco a velocidade do tipo de munição que está sendo
usado, impossibilitando desta forma que a posição futura do inimigo possa ser calculada de
forma determinı́stica.
Esta predição seerá realizada através do uso de Redes Neurais Artificiais devido ao fato
destas apresentarem bons resultados em tarefas de aproximação de funções (REZENDE, 2003).
27
Tais redes estarão inseridas em um agente reativo, pois a predição da posição futura do oponente
deve ser feita baseada no modelo estı́mulo-resposta para que mesmo mudanças bruscas na
velocidade do inimigo possam ser percebidas a tempo.
4.2
IMPLEMENTAÇÃO
Como solução para o problema proposto na seção anterior foram implementados dois BOTs
para o jogo UT2004 com o intuito de se construir um ambiente para realizar o processo de
evolução das redes neurais proposto pelo algoritmo NEAT. Os dois BOTs foram implementados
na linguagem Java e fazem uso da API JavaBOTs para se comunicarem com o servidor do jogo.
Um dos BOTs, chamado de Alvo, possui a única função de se movimentar constantemente
pelo ambiente a fim de prover um alvo móvel para o BOT que faz uso das redes neurais. O
Alvo implementa um comportamento reativo bastante simples que pode ser descrito da seguinte
forma:
Se estiver correndo {
não faça nada
} Se não {
Se viu um ponto de navegação {
corra para ele
} Se não {
gire para a esquerda ou para a direita
}
O outro BOT, chamado de Atirador, também implementa um comportamento reativo simples.
Sua única ação é atirar em um outro BOT caso o veja se movendo. A localização onde o Atirador
deve atirar é calculada pela rede neural que está sendo usada no momento. Esta rede possui 8
nós de entrada e um de saı́da. Os três primeiros nós de entrada recebem respectivamente as
coordenadas x, y e z da localizaçãoo atual do alvo que está se movimentando; os três nós
seguintes recebem as componentes vetoriais da direção para a qual o Alvo se desloca (x, y e z);
e os dois últimos nós recebem, respectivamente, a velocidade do BOT Alvo e distância atual
entre o Atirador e o Alvo. O nó de saı́da da rede representa a componente t da seguinte fórmula
que é usada para o cálculo da posição futura do alvo onde o projétil da arma irá interceptá-lo:
S = S0 + v × t
28
Apesar do movimento do Alvo não ser totalmente uniforme no que diz respeito à velocidade,
a Equação horária do Movimento Uniforme foi escolhida pois a aceleração e desaceleração dos
personagens em UT são bastante bruscas, possibilitando que esta equação obtenha um resultado
aproximado do que seria o ideal.
O ambiente de treinamento utilizado foi construı́do com a ajuda do Unreal Editor, um
editor de mapas de Unreal que acompanha a distribuição do jogo. Este ambiente é constituı́do
basicamente de um grande espaço que possui uma extensão de 6000 unidades de medida do
jogo UT para cada uma das dimensões espaciais (ver Figura 11). Neste espaço foram colocados
4 spawn points1 . Além disso foram colocados, aleatoriamente, diversos pontos de navegação
para que o Alvo pudesse se movimentar na maior variedade de direções possı́veis e assim tentar
recriar a situação real de jogo onde os personagens se movimentam em um número variado de
direções.
Figura 11: Mapa feito no Unreal Editor para treinamento das redes neurais
O Atirador expressa como único comportamento, a ação de atirar em um outro jogador
que estiver se movendo, sem se preocupar com outros aspectos do jogo, como quantidade de
munição restante. Este BOT foi assim implementado para que durante todo o tempo em que
uma rede estivesse sendo avaliada, o BOT tivesse somente a preocupação de atirar no seu alvo.
Caso fosse implementado um comportamento de busca de itens, por exemplo, o tempo que uma
rede teria para ser avaliada poderia estar sendo gasto com outras ações não relevantes para o
processo evolucionário.
Para evitar, portanto, que o Atirador acabasse sem munição e consequentemente prejudicasse
a avaliação das redes, foram criados uma nova arma e um Mutator utilizando-se a linguagem
UnrealScript. A arma criada é uma variação do Rocket Launcher e sua principal caracterı́stica
é que após um disparo ter sido feito, a munição não é consumida, garantindo assim que o
1 Spawn
points são localizações no mapa do jogo onde o personagem controlado pelo jogador surge no mapa
no inı́cio da partida ou a cada vez que é morto e retorna à essa partida.
29
Atirador nunca chegue a ficar sem munição. O Mutator criado simplesmente faz com que todos
os jogadores comecem com este Rocket Launcher modificado.
Para realizar a avaliação de uma rede foi criada a classe UTFitnessFunction cujo método
evalutate(Chromossome chromo) passa a rede neural a ser avaliada para a classe BOTLoader,
responsável por conectar um BOT ao jogo. O BOTLoader então atribui essa rede ao BOT, que
já está conectado no servidor do jogo, e espera 10 segundos para que ela tenha tempo de ser
avaliada. Terminado este tempo, é recolhida a quantidade de acertos que o BOT conseguiu
fazer com a rede neural corrente e este número de acertos é passado para o algoritmo genético
do NEAT4J como o valor do fitness da mesma.
Apesar do Atirador atirar somente em alvos móveis, é possı́vel que ele acabe por acertar
o Alvo quando este estiver parado. Caso o Atirador tenha previsto uma posição em que o
tiro chegaria normalmente atrasado, isto é, o Alvo já tenha passado por essa posição, e por
não conseguir ver outro ponto de navegação o Alvo tenha se mantido parado procurando outra
direção para ir, haverá a possibilidade deste tiro acertar o mesmo.
Como o objetivo de todo o processo é obter uma rede neural que possibilite ao Atirador
acertar alvos em movimento, somente é conferida pontuação para acertos em alvos cuja a
velocidade esteja acima de zero.
O método de avaliação escolhido se baseia na contagem direta de acertos que o Atirador
conseguiu utilizando uma determinada rede. Uma outra forma de avaliação, que se mostraria
mais eficiente, seria o favorecimento dos indivı́duos que conseguissem gerar uma saı́da que
fornecesse a localização com menor erro. Com a abordagem escolhida, se tornou impraticável
diferenciar uma rede que fornecesse uma localização totalmente dı́spare a aquela desejada, de
uma rede cuja saı́da resultasse numa localização muito próxima do ideal, uma vez que as duas
respostas não resultam em acertos, nenhuma das duas redes recebe pontuação e serão avaliadas
de forma igual pelo algoritmo genético. Isto dificultou a convergência do algoritmo para uma
solução ótima ou próxima da ótima. Caso a rede que forneceu uma resposta próxima da correta
pudesse ser pontuada esta teria maiores chances de ser selecionada para gerar descendentes
e passar para a próxima geração e desta forma tentar-se-ia chegar a uma solução através da
minimização do erro.
Tal abordagem somente não foi utilizada no processo de evolução das redes pois não é
possı́vel conhecer de antemão qual seria a resposta correta para um determinado conjunto de
entradas, nem tão pouco saber em que momento o projétil disparado alcançou sua localização
de destino. Diante disto buscou-se através dos parâmetros utilizados pelo algoritmo genético
do NEAT (ver apêndice B), incentivar o surgimento de inovações mais rapidamente, a fim de
30
que surgisse um indivı́duo que conseguisse fornecer saı́das corretas para alguns conjuntos de
entrada e assim gerar descendentes que por sua vez poderiam chegar a uma solução melhor que
o seu ancestral.
Os dados de entrada passados às redes neurais encontravam-se todos em unidades de UT,
variando da casa das centenas até a casa dos milhares e as funções de ativação dos neurônios
das camadas de saı́da e escondidas utilizadas pelo NEAT4J são do tipo sigmóide2 e tangente
hiperbólica3 respectivamente, que por sua vez fornecem resultados somente dentro do intervalo
[0, 1]. Em consequência disto, durante alguns dos experimentos os resultados gerados pelas
redes se restringiam a 0 ou 1, devido aos altos valores de entrada, fazendo com que o algoritmo
acabasse por convergir para um mı́nimo local. Viu-se então a necessidade de diminuir esses
valores para uma faixa de valores computáveis, faixa esta localizada entre os números 0 e 1
(respostas fornecidas pela função sigmóide), dividindo-os por 104 antes destes serem passados
à uma rede, e multiplicando a saı́da da rede por 104 . A convergência do algortimo a partir deste
momento deixou de se aproximar para um mı́nimo local e passou a não apresentar resultados
significativos. Através das experiências anteriores pôde-se observar que os valores próximos
do ideal para as respostas das redes estavam localizados na faixa de valores que vai de 0 a
10 aproximadamente. Para que a rede conseguisse dar respostas que chegassem a essa faixa,
seria necessário que as saı́das fornecidas por elas estivessem entre os valores 10−4 e 10−3 , o
que se mostrou inviável de se alcançar devido ao tempo necessário para que o processo de
evolução chegasse a este nı́vel, uma vez que a maior parte dos menores valores encontrados
pelas redes chegavam somente à faixa de 10−1 . Por isso, tentando acelerar o processo de
convergência do algoritmo ao invés de multiplicar as saı́das das redes pelo valor de 104 , optouse por multiplicá-las por 10 somente, para assim obter uma faixa de respostas que permitisse ao
processo evolucionário encontrar melhores soluções para o problema de forma mais rápida.
1
função sigmóide pode ser representada pela fórmula: P(t) = 1+e
t
3 Um função tangente hiperbólica pode ser representada pela fórmula: tahn(x) =
2 Uma
e2x −1
e2x +1
31
5
RESULTADOS E DIFICULDADES
5.1
RESULTADOS OBTIDOS
Como resultado dos experimentos obteve-se uma rede neural recorrente e com mútliplas
camadas (ver Figura 12). Esta rede apresenta ainda uma performance baixa se comparada com
o esperado, sendo que a mesma calcula de forma razoável a posição ideal para distâncias médias
e longas
Figura 12: Rede resultante de 63 gerações com uma população de 60 indivı́duos
Esta rede foi gerada após um processo de evolução com uma população de 60 indivı́duos
durante 63 gerações, parâmetros muito baixos se comparados com os valores normalmente
usados em algoritmos genéticos. Devido aos problemas relatados na seção seguinte, como a
impossibilidade de utilizar a funcionalidade de aprendizado distribuı́do no processo de evolução,
houve uma limitação na quantidade de indivı́duos e gerações a serem utilizadas dentro do tempo
hábil deste trabalho. Contudo a diferença da rede obtida para uma rede no inı́cio do processo de
evolução é perceptı́vel. Enquanto que os melhores indivı́duos das primeiras gerações realizavam
32
disparos para localizações muito distantes da localização do Alvo (ver Figura 13), a rede obtida
ao final do experimento consegue acertar, a uma distância média, cerca de 70% a 85% dos
disparos efetuados e a uma longa distância efetua disparos que acompanham de forma próxima
a trajetória percorrida pelo Alvo (ver Figuras 14 e 15), mostrando que mesmo sem conseguir
avaliar os indivı́duos através da minimização dos seus erros, o NEAT é capaz de achar uma
solução, ainda que parcial, para aproximação da função desejada. Nas figuras 13 e 14 as linhas
verdes representam as trajetórias dos tiros dados pelo Atirador. O marco azul no ambiente
representa o BOT Atirador e o marco vermelho representa o BOT Alvo. Nessas duas figuras e
na Figura 15 o placar na parte superior localizado ao lado esquerdo representa a quantidade de
inimigos mortos pelo BOT Alvo e o placar ao lado direito indica quantas vezes o BOT Atirador
matou um oponente.
Figura 13: Resultado conseguido com uma das redes das primeiras gerações do processo de
evolução.
33
Figura 14: Resultado conseguido com uma a rede da 63a geração.
Figura 15: Rede obtida da 63a geração acertando o Alvo.
34
5.2
DIFICULDADES ENCONTRADAS
Durante o desenvolvimento do projeto algumas problemas com as ferramentas utilizadas
foram encontrados.
No que diz respeito ao GameBots surgiram problemas relacionados ao recebimento e envio
de mensagens e como o personagem reagia a elas. Os principais problemas foram:
• Quando enviado o comando ”SHOOT” com o ID como parametro comandos posteriores
como o ”RUNTO” apresentam anomalias
• Ao contrário do que é dito no protocolo de mensagens, quando um projétil está vindo em
direção a um jogador, não é enviada a mensagem do tipo ”PRJ”
• O atributo ”PlayerScores” da mensagem do tipo ”GAM” contém somente a pontuação
do próprio jogador
• Mensagens indentificando o time do jogador também chegam com problemas
Durante os experimentos foram observados alguns problemas de comunicação entre o BOT
e o jogo, ocasionando muitas vezes na ausência de qualquer tipo de ação do BOT Alvo pelo
fato deste não estar recebendo as informações sensoriais corretamente. Em consequência disso,
muitos experimentos foram prejudicados, sendo necessário então iniciar um outro processo
desde o inı́cio a cada vez que isso ocorria.
Além disso, o jogo Unreal Tournament 2004 apresentou o problema de conectar um BOT do
próprio jogo no instante em que um BOT implementado com o uso do JavaBOT ou um jogador
humano deixava a partida. Isso impediu que a funcionalidade de aprendizado distribuı́do do
NEAT4J, onde um servidor distribui indivı́duos para serem avaliados por aplicações remotas
(SIMMERSON, 2006), pudesse ser integrada a tempo com o UT2004. Caso a integração da
funcionalidade com o jogo pudesse ter sido feita a tempo seria possı́vel realizar experimentos
com populações maiores e durante mais gerações, uma vez que mais de um indivı́duo da
população de possı́veis soluções estariam sendo avaliados de forma paralela.
Com relação ao NEAT4J, o único problema encontrado foi a falta da possibilidade de salvar
uma determinada população para, caso o experimento fosse parado, este pudesse ser continuado
posteriormente do ponto de parada. Existe o método implementado para tal, contudo ao carregar
uma população salva previamente, o programa acaba por lançar uma exceção no momento em
que se termina a avaliação desta população e irá ser realizada a segregação dos indivı́duos por
espécie.
35
6
CONCLUSÃO
Este trabalho realizou portanto, a implementação de um Bot, no jogo Unreal Tournament
2004, que faz uso de uma Rede Neural Artificial com o intuito de prever a posição ideal
para se fazer um disparo com uma arma de forma que haja tempo para o projétil atingir um
alvo em movimento. Tal rede foi obtida através do uso de algoritmos genéticos utilizandose o framework NEAT4J, uma implementação do algoritmo NEAT, capaz de evoluir tanto as
conexões sinápticas como a estrutura topológica de redes neurais.
O uso de tal algoritmo permitiu que durante os experimentos realizados, não fosse necessário
haver nenhum estudo com relação à melhor topologia de rede a ser utilizada para o problema
proposto, pois o processo evolucionário se encarregou de adicionar às redes somente estruturas
úteis para a resolução do problema, conseguindo gerar uma rede com uma topologia complexa
como a da Figura 12. Caso fosse adotada a abordagem convencional de se utilizar uma rede
com estrutura fixa, seriam necessários um tempo e esforço muito maiores para se descobrir que
a estrutura encontrada através do NEAT deveria ser utilizada para resolver o problema.
Devido a problemas com as ferramentas utilizadas bem como à falta de determinadas
informações no ambiente de simulação, a obtenção de uma rede que generalizasse de forma
ideal a função desejada não foi possı́vel. Contudo, mesmo com estas dificuldades, a melhoria
nas redes é facilmente percebida, mostrando que dispondo-se de mais tempo é possı́vel encontrar
uma solução satisfatória para o problema proposto, colocando o NEAT como uma opção viável
para o estudo e desenvolvimento da Inteligência Artificial na área de jogos eletrônicos, sendo
contudo necessário escolher cuidadosamente os parâmetros a serem utilizados pelo algoritmo
genético a fim de que o processo evolucionário não fique estagnado e tampouco se torne aleatório.
6.1
TRABALHOS FUTUROS
Sugere-se como trabalhos futuros a realização de uma melhor integração do framework
NEAT4J com o jogo UT2004, com a finalidade de se utilizar a funcionalidade de aprendizado
36
distribuı́do e também a realização de experimentos a fim de se obter uma rede através do NEAT
que generalize:
• a mesma função citada neste trabalho, mas que possibilite a predição da localização ideal
para o disparo independente da arma que o BOT estiver portando.
• uma função que indique para qual estado um BOT que utilize Máquinas de Estado Finito
deve ir a depender de um conjunto de informações sensoriais.
37
APÊNDICE A -- PROTOCOLO DE MENSAGENS
TROCADAS ATRAVÉS DO
GAMEBOTS
Mensagens sı́ncronas:
BEG - inı́cio de um lote de mensangens sı́ncronas.
Time - timestamp do jogo.
SLF - informação do estado do personagem.
Id - id única, atribuı́da pelo jogo.
Rotation - para qual direção o personagem está voltado, em termos absolutos.
Location - localização absoluta.
Velocity - velocidade absoluta medida em unidades do jogo (unidades UT).
Name - nome que é utilizado pelo personagem.
Team - a qual time o jogador pertence. 255 significa que ele não está em time algum.
0-3 são os times vermelho, azul, verde e dourado respectivamente
Health - quanto de Health ainda resta para o personagem. Começa em 100 e varia de 0
a 200.
Weapon - qual arma o personagem está usando. Os nomes das armas incluem:
ImpactHammer, Enforcer, Translocator, GESBioRifle, ShockRifle, PulseGun, Minigun2,
UT FlakCannon, UT Eightball, WarheadLauncher.
CurrentAmmo - o quanto de munição da arma que está usando no momento resta.
Armor - o quanto de proteção o BOT possui. Começa em 0 e pode ir até 200.
GAM - informação sobre o jogo.
38
PlayerScores - Lista dos scores de cada jogador da partida. Cada elemento dessa lista
possui dois valores. O primeiro é o id do personagem que aquele jogador controla e
o segundo o valor do score.
TeamScores - funciona do mesmo jeito que a mensagen do tipo PlayerScores só que
aplicada a times, onde os ids mostrados são os que identificam os times. Esse tipo
de mensagen não é enviado quando a partida é no formato DeathMatch.
DomPoints - lista de pontos dominados por cada time para o formato de partida
Domination.
HaveFlag - usado nas partidas do formato Capture The Flag (CTF) caso o personagem
controlado pelo BOT esteja com a bandeira de outro time. O valor informado é o
número do time dono da bandeira
EnemyHasFlag - usado nas partidas de CTF caso um personagem de outro time esteja
com a bandeira de outro time
PLR - Informações sobre outro jogador no jogo. Mostra somente informações sobre jogadores
que são visı́ves.
Id - id único atribuı́da pelo próprio jogo.
Rotation - para qual direção o personagem controlado pelo jogador está voltado, em
termos absolutos.
Velocity - velocidade absoluta medida em unidades do jogo (unidades UT).
Team - a qual time o jogador pertence.
Reachable - tem valor True se é possı́ve alcançar esse jogador diretamente, o valor será
False caso contrário. Possı́veis razões para este atributo ser False é a existência de
alguma espécia de obstáculo entre os dois jogadores.
Weapon - que tipo de arma o personagem está segurando.
NAV - informações sobre um pathnode do jogo. Pathnodes são objetos invisı́veis colocados
pelo mapa do jogo que definem caminhos para os BOTs do jogo poderem se guiar,
gerando um grafo totalmente conexo que abrange quase todo mapa da partida.
Id - um id único atribuı́do a esse pathnode pelo próprio jogo.
Reachable - tem valor True se o jogador pode correr diretamente para este pathnode.
39
MOV - informações sobre objetos que podem se mover (portas, elevatores, etc).
Id - id único atribuı́do esse objeto móvel pelo próprio jogo.
Reachable - tem valor True se o jogador pode correr para este objeto.
DamageTrig - tem valor True se é necessário atirar no objeto para ativá-lo.
Class - classe do objeto móvel.
DOM - ponto de dominação de uma partida de Domination.
Controller - qual time controla este ponto.
FLG - informações sobre uma bandeira. (Somente em partidas de CTF).
Id - id único atribuı́do a essa bandeira pelo próprio jogo.
Holder - id do jogador que está carregando a bandeira.
Team - time ao qual a bandeira pertence.
Reachable - True se o jogador pode correr diretamente para ela.
State - indica se a bandeira está com alguém (Held), caı́da no chão (Droped) ou está na
base (Home)
INV - informações sobre um objeto no chão que pode ser pego (item de inventário).
Id - id único atribuı́do a esse item de inventário pelo próprio jogo.
Reachable - tem valor True se o jogador pode correr diretamente para este objeto.
Class - uma string representando o tipo do objeto.
END - indica final do lote de mensagens sı́ncronas.
Time - timestamp do jogo.
Mensagens assı́ncronas:
NFO - informações sobre o jogo logo após a conexão com o servidor ter sido estabelecida.
O BOT deve esperar esta mensagem antes de enviar uma mensagen do tipo INIT para o
servidor.
40
Gametype - Qual o formato da partida (BotDeathMatchPlus, BotTeamGame, BotDomination).
Level - nome do mapa em que se está jogando.
TimeLimit - tempo máximo que o jogo irá durar.
FragLimit - número de mortes necessárias para vencer o jogo (somente para o formato
BotDeathMatchPlus).
GoalTeamScore - número de pontos necessários para um time ganhar a partida (BotTeamGame,
BotDomination).
MaxTeams - número máximo de times. Varia de 0 a (MaxTeams - 1) (BotTeamGame,
BotDomination).
MaxTeamSize - número máximo de jogadores por time (BotTeamGame, BotDomination)
AIN - enviada pelo servidor quando o personagem adquire um novo item para o inventário.
Id - id único atribuı́do a este item pelo próprio jogo. Id baseado em uma string que
descreve o tipo do item.
Class - uma string representando o tipo do item.
VMS - mensagem recebida do canal de chat global.
String - mensagem enviada por outro jogador no jogo através do canal de chat global.
VMT - mensagem recebida do canal de chat privado.
String - mensagem enviada por um jogador do mesmo time através do canal de chat
privado do time.
VMG - mensagem padrão do jogo recebida de outro jogador.
Sender - id único do jogador que enviou a mensagem.
Type - tipo da mensagem (comando, xingamento).
Id - id da mensagem.
ZCF - pés do personagem mudaram de uma zona artificial do jogo para outra. (se entrou na
água ou na lava)
Id - id único da zona que os pés estão agora.
ZCH - a cabeça do personagem mudou de uma zona artificial para outra.
Id - id único da zona que a cabeça está agora.
41
ZCB - personagem mudou de uma zona artificial para outra.
Id - id único da zona que o personagem está agora.
CWP - o personagem trocou de arma (através de comando ou porque a munição da arma
terminou.
Id - id único da nova arma, baseado no nome da arma.
Class - uma string representando o tipo da arma
WAL - houve colisão com uma parede.
Id - id único da parede onde colidiu.
Normal - normal do ângulo que o personagem colidiu.
Location - localização absoluta do personagem no momento da colisão.
FAL - BOT atingiu a beirada de algum lugar alto. Se o personagem estava caminhando ele não
terá caı́do, caso esteja correndo já estará caindo no recebimento desta mensagem.
Fell - True se caiu, False se parou na beirada.
Location - localização absoluta do personagem
BMP - se chocou com outro ator.
Id - id único do ator (atores são outros players ou qualquer objeto que posso bloquear
seu caminho).
Location - localização do objeto com o qual o jogador se chocou.
HRP - o BOT escutou alguém pegar algum objeto do chão.
Player - id único do jogador que pegou o objeto.
HRN - o BOT escutou um barulho (um outro jogador andando ou atirando, uma bala acertando
o chão ou um elevador se movendo).
Source - id único do ator que fez o barulho.
SEE - o BOT viu um outro jogador. Mensagem gerada pelo jogo entre 1 e 2 vezes a cada
segundo quando outro jogador está visı́vel. Útil quando o delay entre as mensagens
sı́ncronas é muito grande É possı́vel que esteja depreciado.
Id - id único do jogador, atribuı́do pelo jogo.
42
Rotation - para qual direção o jogador está voltado em termos absolutos.
Location - localização absoluta do personagem controlado por este jogador.
Velocity - localização absoluta em unidades de UT.
Team - em qual time o jogador está.
Reachable - True se o é possı́vel correr em direção a este jogador.
Weapon - qual arma o personagem controlado por este jogador está usando.
PRJ - projétil vindo em direção ao personagem controlado pelo BOT.
Time - tempo estimado para o impacto.
Direction - valor de rotação de onde o projétil está vindo.
KIL - algum outro jogador morreu.
Id - id único do jogador.
Killer - id único do jogador que o matou, caso exista.
DamageType - string descrevendo o tipo de dano que o matou.
DIE - este BOT morreu.
Killer - id único do jogador que o matou, caso exista.
DamageType - string descrevendo o tipo de dano que o matou.
DAM - o BOT sofreu dano.
Damage - quantidade de dano sofrida.
DamageType - string descrevendo o tipo de dano.
HIT - feriu outro jogador.
Id - id único do jogador ferido.
Damage - quantidade de dano provocada.
DamageType - string descrevendo o tipo de dano.
PTH - lista de pathnodes em resposta a uma mensagem GETPATH do cliente.
Id - id da mensagem idêntica a enviada pelo cliente, permitindo que este possa reconhecer
a resposta da sua mensagem.
43
Multiple pathnodes - lista de pathnodes para se chegar no destino desejado na ordem
em que precisam ser percorridos.
RCH - resultado booleano em resposta a um comando do tipo CHECKREACH.
Id - id da mensagem idêntica a enviada pelo cliente, permitindo que este possa reconhecer
a resposta da sua mensagem.
Reachable - True se o personagem pode se movimentar na direção informada, False caso
contrário.
From - localização do personagem no momento do check.
FIN - enviada quando a partida termina.
Commandos:
INIT - mensagem enviada para que seja instanciado um personagem no jogo, deve ser enviado
antes de poder executar qualquer ação e somente após receber uma mensagem do tipo
NFO do servidor.
Name - Nome a ser usado pelo BOT.
Team - Diz o time ao qual o BOT pertencerá.
SETWALK - diz se o personagem irá se movimentar andando ou correndo.
Walk - Se tiver valor True o personagem irá caminhar, caso contrário irá correr.
STOP - para qualquer movimentação que esteja executando.
JUMP - faz o personagem pular.
RUNTO - se movimenta para uma determinada localização ou alvo.
Target - id único do alvo para o qual deseja se movimentar. Só irá funcionar se o alvo
estiver visı́vel, caso contrário o personagem não fará nada.
Location - As três coordenadas da localização para onde o personagem deve se movimentar.
STRAFE - semelhante ao RUNTO, mas o personagem irá se movimentar em uma direção
enquanto está olhando para outro ponto.
Location - As três coordenadas da localização para onde o personagem deve se movimentar.
44
estiver visı́vel.
TURNTO - faz o personagem virar um valor em unidades UT ou para a direção de um alvo ou
uma localização.
estiver visı́vel.
Rotation - Valor de rotação que se deseja usar. Três coordenadas em unidades UT em
valores absolutos, separadas por espaço ou vı́rgula (2pi = 65535 unidades UT). Esse
argumento somente é usado se nenhum alvo for indicado.
Location - As três coordenadas da localização para onde o personagem deve se virar.
Somente usada se não forem passados nem alvo nem valor de rotação.
ROTATE - rotaciona uma determinada quantidade de unidades UT
Amount - quantidade em unidaes UT a ser rotacionada, podendo ser negativa para rotacionar no sentido anti-horário
Axis - eixo sobre o qual será feita a rotação
SHOOT - faz com que o personagem comece a atirar.
Location - As três coordenadas da localização para onde o personagem deve atirar.
Target - id único do alvo no qual o personagem deve atirar. Se o alvo estiver visı́vel
o servidor irá providendicar correção da mira e irá fazer com que o personagem
continue mirando no alvo. Caso não esteja visı́vel o personagem somente irá ficar
atirando na localização informada. Mesmo informando o alvo ainda é necessário
informar a localização.
Alt - Faz com que o personagem use o disparo alternativo da arma.
CHANGEWEAPON - o personagem troca de arma.
Id - id único da arma que o personagem deve usar. Se for usado o valor Best será
escolhida a melhor arma que ainda tenha munição.
STOPSHOOT - faz o personagem parar de atirar.
CHECKREACH - checa se é possı́ve se movimentar diretamente para algum lugar ou algo
sem ser obstruı́do.
45
Target - id único do alvo para o qual se deseja fazer o check. É necessário que ele esteja
visı́vel.
Location - As três coordenadas da localização alvo. Somente usado se nenhum alvo for
informado.
Id - id da mensagem criada pelo BOT para ser retransmitida em resposta pelo servidor,
assim é possı́vel identificar a resposta da mensagem enviada.
From - localização do personagem no momento do check.
GETPATH - obtém um caminho para uma localização especı́fica. É retornada uma lista
ordenada de pathnodes.
Location - As três coordenadas da localização para onde o personagem deve ir.
Id - id da mensagem criada pelo BOT para ser retransmitida em resposta pelo servidor,
assim é possı́vel identificar a resposta da mensagem enviada.
MESSAGE - envia uma mensagem para todos ou somente para os integrantes do time do BOT.
String - string a ser enviada.
Global - Se o valor for True, envia a mensagem para todos, caso contrário somente para
o time.
PING - envia um PING para o servidor que irá responder com um PONG.
46
APÊNDICE B -- PARÂMETROS DE
CONFIGURAÇÃO PARA O
ALGORITMO GENÉTICO
UTILIZADO PELO NEAT4J
PROBABILITY.MUTATION - Controla a mutação das conexões e o fator da função sigmóide
dos neurônios
Faixa de Valores - 0 - 1
Valor usado - 0.45
PROBABILITY.CROSSOVER - Define a taxa em que indivı́duos da mesma espécie realizam
o crossover
Valor usado - 0.35
PROBABILITY.ADDLINK - Define a taxa em que novas conexões são adicionadas.
Não leva em conta o parâmetro que lida com conexões recorrentes.
Valor usado - 0.3
PROBABILITY.ADDNODE - Taxa de adição de num novo neurônio a uma conexão ativa.
Valor usado - 0.5
PROBABILITY.MUTATEBIAS - Taxa em que os bias dos neurônios sofrem mutação.
47
Valor usado - 0.3
PROBABILITY.TOGGLELINK - Define a taxa em que uma conexão entre dois neurônios
pode mudar seu estado de ativada para desativada e vice-versa.
Valor usado - 0
PROBABILITY.WEIGHT.REPLACED - Define com que frequência o peso de uma conexão
é mudado aleatoriamente para outro valor.
Valor usado - 0.1
EXCESS.COEFFICIENT - Coeficiente especı́fico do NEAT. Provê a importância de genes
do tipo excess no cálculo de compatibilidade entre cromossomos.
Faixa de Valores - = 0
Valor usado - 1
DISJOINT.COEFFICIENT - Coeficiente especı́fico do NEAT. Provê a importância de genes
do tipo disjoint no cálculo de compatibilidade entre cromossomos.
Faixa de Valores - >= 0
Valor usado - 1
WEIGHT.COEFFICIENT - Coeficiente especı́fico do NEAT. Provê a importância da diferença de pesos em conexões de genes no cálculo de compatibilidade entre cromossomos.
Valor usado - 0.4
COMPATABILITY.THRESHOLD - Parâmetro que serve para definir se um cromossomo é
compatı́vel com outro.
Valor usado - 0.5
COMPATABILITY.CHANGE - Se esse valor for 0, o parâmetro
COMPATABILITY.THRESHOLD permanecerá inalterável. Se for maior do que 0 este
parâmetro irá modificar o COMPATABILITY.THRESHOLD dinamicamente a fim de
manter o número de espécies da população equivalente ao SPECIE.COUNT.
48
Valor usado - 0.1
SPECIE.COUNT - Quando o COMPATABILITY.CHANGE é diferente de 0, define a quantidade
de espécies que se deseja ter na população.
Valor usado - 3
SURVIVAL.THRESHOLD - Este valor define a fração dos indivı́duos da espécie que irão
realizar o crossover.
Valor usado - 0.4
SPECIE.AGE.THRESHOLD - Indica a partir de que idade uma espécie começa a ser penalizada,
multiplicando-se o seu fitness por SPECIE.OLD.PENALTY.
Valor usado - 80
SPECIE.YOUTH.THRESHOLD - Indica até que idade uma espécie tem seu fitness multiplicado por SPECIE.YOUTH.BOOST.
Valor usado - 10
SPECIE.OLD.PENALTY - Valor multiplicado pelo fitness de espécies que têm idade maior
que o SPECIE.AGE.THRESHOLD.
Valor usado - 0.8
SPECIE.YOUTH.BOOST - Valor multiplicado pelo fitness de espécies que têm idade menor
que o SPECIE.YOUTH.THRESHOLD.
Valor usado - 1.5
SPECIE.FITNESS.MAX - Indica até que idade uma espécie que não apresente melhoras
continua na população.
49
Valor usado - 15
OPERATOR.XOVER - A classe do operador de crossover.
Faixa de Valores Valor usado - org.neat4j.neat.core.xover.NEATCrossover
OPERATOR.FUNCTION - Classe da função de fitness.
Faixa de Valores - classe que realize a operação de crossover
Valor usado - neat.UTFitnessFunction
OPERATOR.PSELECTOR - Classe do operador de seleção de pais.
Faixa de Valores - classe que implementa o método de seleção
Valor usado - org.neat4j.neat.core.pselectors.TournamentSelector
OPERATOR.MUTATOR - Classe do operador de mutação.
Faixa de Valores - classe que implementa a operação de mutação
Valor usado - org.neat4j.neat.core.mutators.NEATMutator
MAX.PERTURB - Módulo do valor que pode ser aplicado como perturbação a uma conexão.
Valor usado - 3.0
MAX.BIAS.PERTURB - Módulo do valor que pode ser aplicado como perturbação a um bias.
Valor usado - 1.0
FEATURE.SELECTION - Define a estrutura inicial das redes. Se for true um nó de entrada é
conectado a um nó de saı́da aleatoriamente até que todas as saı́das tenham uma conexão.
Se for false todos nós de entrada são conectados a todos os nós de saı́da.
Faixa de Valores - true ou false
Valor usado - false
RECURRENCY.ALLOWED - Define se as conexões recorrentes são mantidas após um cromossomo ter sofrido mutação.
50
Valor usado - true
INPUT.NODES - Quantidade de nós de entrada das redes.
Valor usado - 8
OUTPUT.NODES - Quantidade de nós de saı́da das redes.
Valor usado - 1
NN.CONFIG - Localização do arquivo de configuração das redes. Pode ser relativo ou absoluto.
Faixa de Valores - path do arquivo de configuração
Valor usado - /home/cicero/neat4j/ut/ut ga neat.net
ELE.EVENTS - Determina se eventos de extinção de vida ou ELEs (Extinct Life Events)
irão ocorrer ou não. Isso faz com que o limite de compatibilidade inicial seja multiplicado
por 5 e os n% melhores indivı́duos serão mantidos.
Valor usado - false
ELE.SURVIVAL.COUNT - Indica a porcentagem da população que irá sobreviver na ocorrência de um ELEs.
Valor usado - 0.1
ELE.EVENT.TIME - De quanto em quanto tempo um ELE irá ocorrer.
Valor usado - 1000
KEEP.BEST.EVER - Determina se a espécie com o melhor indivı́duo encontrado até agora
será mantida mesmo depois que o valor do SPECIE.FITNESS.MAX seja excedido.
51
Valor usado - false
EXTRA.FEATURE.COUNT - Indica a quantidade extra de genes dentro de um cromossomo
que não nenhum efeito topológico e são usadas para a definição de valores de entrada
evoluı́dos.
Valor usado - 0
POP.SIZE - Indica a quantidade de cromossomos que a população terá.
Valor usado - 60
NUMBER.EPOCHS - Número de épocas que serão executadas durante o processo de evolução.
Valor usado - 100
TERMINATION.VALUE - Valor de fitness que se alcançado fará o algoritmo parar independente de ter sido chegado ao número máximo de épocas.
Valor usado - 100000000
NATURAL.ORDER.STRATEGY Se for true - Quanto menor o fitness, melhor é o indivı́duo.
Se for false quanto maior o fitness melhor será o indivı́duo.
Valor usado - false
SAVE.LOCATION - Local onde deve ser salvo o melhor indivı́duo de cada geração.
Faixa de Valores - String
Valor usado - /home/cicero/neat4j/ut/ut neat ga.ser
52
REFERÊNCIAS
BITTENCOURT, G. Inteligência Computacional. Departamento de Automação
e Sistemas, Universidade Federal de Santa Catarina, 2005. Disponı́vel em:
<http://www.das.ufsc.br/gia/softcomp/>.
GAMEBOTS. University of Southern California, 2002. Disponı́vel em:
<http://gamebots.sourceforge.net/>.
HAYKIN, S. Redes Neurais Principios e Pratica. [S.l.]: Bookman, 2001.
JBP. The Mutators FAQ. Planet Unreal, 2000. Disponı́vel em:
<http://www.planetunreal.com/mutation/FAQ/>.
KISHIMOTO, A. Inteligência Artificial em Jogos Eletrônicos. 2004.
LAIRD, J. E.; LENT, M. van. Human-level AI’s killer application: Interactive
computer games. In: AAAI/IAAI. [s.n.], 2000. p. 1171–1178. Disponı́vel em:
<citeseer.ist.psu.edu/laird00humanlevel.html>.
NERO. 2005. Disponı́vel em: <http://www.nerogame.org/>.
NILSSON, N. J. Artificial Intelligence - A New Synthesis. [S.l.]: Morgan Kaufmann, 1998.
513 p. ISBN 7-111-07438-6.
REZENDE, S. O. Sistemas Inteligentes Fundamentos e Aplicacoes. [S.l.]: Manole, 2003.
RIT. Gamebots. Rochester Institute of Technology - Department of Computer Science, 2005.
Disponı́vel em: <http://www.cs.rit.edu/j̃db/gamebots/>.
ROZICH, R. JavaBot for Unreal Tournament. [S.l.]: Projeto JavaBot, 2002.
SIMMERSON, M. NEAT4J. 2006. Disponı́vel em: <http://utbot.sourceforge.net>.
STANLEY, K. O. Efficient Evolution of Neural Networks through Complexification. Tese
(Doutorado) — The University of Texas at Austin, Agosto 2004.
SWEENEY, T. UnrealScript Language Reference. Epic MegaGames, Inc, 1998. Disponı́vel
em: <http://unreal.epicgames.com/UnrealScript.htm>.

universidade federal da bahia implementac¸˜ao de um agente

Transcrição

Documentos relacionados

Nota de Alta

Bolo do Caco Bimby: 27 min Ingredientes: 1 c. café sal

Fettuccine à Alfredo Ingredientes: 400 g massa fettuccine ou

Sopa de Castanhas Ingredientes: 1 cebola 40 g azeite 50 g linguiça

Jardineira de Carne

comunicarh - ed 10

Trabalho Prático n 3 Conversor BCD-7 Segmentos SSI

autorização do responsável

SHELLAC 78`

Inteligência Artificial

Dinâmica de Populaç˜oes:Um Breve Histórico - IME