Revista Eletrônica da Faculdade Metodista Granbery

http://re.granbery.edu.br - ISSN 1981 0377

Curso de Sistemas de Informação - N. 8, JAN/JUN 2010

Algoritmos Genéticos Aplicados a Jogos Eletrônicos

Gilberto Timótheo Júnior1, Sérgio Muinhos Barroso Lima

1

1Faculdade Metodista Granbery

CEP: 36010-532 – Juiz de Fora – MG – Brazil

llonill@hotmail.com, smblima@granbery.edu.br

Resumo

A inteligência artificial vem sendo utilizada no desenvolvimento de jogos

eletrônicos como ferramenta essencial para trazer maior grau de realismo aos

jogos. Este artigo estuda a aplicação dos algoritmos genéticos no

desenvolvimento de jogos, explorando sua aplicabilidade, vantagens e

desvantagens.

Palavras-chave: jogos eletrônicos, desenvolvimento de jogos, ferramentas

para jogos, máquinas de jogos.

Abstract.

The artificial intelligence has been used in the development of video games as

an essential tool to bring greater realism to games. This paper studies the

application of genetic algorithms in game development, exploring their

applicability, advantages and disadvantages.

Key-words: eletronic games, game development, game tools, genetic

algorithms.

1 INTRODUÇÃO

A Inteligência Artificial (IA) desde os seus primórdios está diretamente

ligada ao processo cognitivo humano, evoluindo desde as bases alicerçadas

nos estudos de Aristóteles, e caminhando sem respostas definitivas, através do

tempo, permeando-se por várias teorias relacionadas à inteligência humana

(NILSSON, 1998).

O desenvolvimento da Inteligência Artificial assume um caráter

permanente, contando com a adesão, mesmo que lenta, de cientistas capazes

2

de promover sua divulgação. Nesse contexto, John Holland inicia um processo

de desenvolvimento dos estudos sobre os Algoritmos Genéticos, influenciando

outros pesquisadores a tomarem o mesmo caminho. Com o passar dos anos, e

com sua consolidação, eles começaram a ser utilizados em inúmeras áreas de

pesquisa, sendo uma dessas áreas os jogos eletrônicos (RUSSELL e NORVIG,

2004).

Como uma das muitas aplicações dos Algoritmos Genéticos, os jogos

eletrônicos despertam especial atenção, pois envolvem um número grande e

entusiasmado de usuários e um mercado em rápido crescimento, tão próspero

quanto a indústria do cinema (BATISTA et al, 2009).

Este trabalho trata, então, da confluência entre essas duas áreas, a

Inteligência Artificial e os jogos eletrônicos, especificamente na aplicação de

Algoritmos Genéticos no comportamento de personagens de jogos eletrônicos.

2 HISTÓRICO DA INTELIGÊNCIA ARTIFICIAL EM JOGOS ELETRÔNICOS

A Inteligência Artificial foi definida por muitos, como cita Luger (2004), "...

a ciência da computação que se ocupa da automação do comportamento

inteligente.". Com esta frase ele reafirma a posição de que a IA é um fragmento

da Ciência da Computação que deve, por sua vez, ser baseada em profundos

estudos e princípios teóricos concretos. Neste processo, pode-se incluir como

base toda a estrutura computacional como algoritmo e linguagem apropriados.

Neste processo de entendimento da IA, o próprio Luger (2004) expõe uma

fragilidade nesta definição quando diz:

Entretanto, esta definição padece do fato de que a inteligência em si não é muito bem definida ou entendida. Embora muitos de nós estejam certos de que reconhecemos o que é comportamento inteligente, quando o vemos, é muito improvável que alguém seja capaz de definir inteligência de uma maneira que seja específica o suficiente para auxiliar na avaliação de um programa de computador supostamente inteligente[...]. (LUGER, 2004, p. 23).

A inteligência, segundo Luger (2004), é uma faculdade única, ou apenas

um nome dado a uma coleção de habilidades humanas distintas e não

3

correlacionadas. A inteligência pode ser visualizada através de um

comportamento observável ou inegável evidência de um dispositivo interno

individual.

O primeiro de muitos estudos relacionados à Inteligência Artificial pode

ser atribuído a Aristóteles (NILSSON, 1998), em seu esforço para explicar e

codificar a inteligência humana. Porém, o termo Inteligência Artificial foi

utilizado pela primeira vez por John McCarthy, como nome da conferência em

Dartmouth, em 1956.

Isto se deu devido a grande parte dos estudos realizados anteriormente

tratarem apenas do âmbito matemático dos autômatos, que pode ser

considerado como um modelo matemático de uma máquina de estados finita, a

qual modela o comportamento através de estados e das transições de um

estado para o outro.

No período anterior aos anos 70, os processos classificados como

inteligentes se encontravam distantes dos que são conhecidos hoje. Viviam

ainda um estágio inicial, básico, com uma divulgação restrita, não havendo

portanto nenhum interesse real que justificasse um foco de mercado, isto é,

que recursos financeiros e tecnológicos pudessem ser alocados em um projeto

significativo de pesquisa com o propósito de desenvolvimento. Estas pesquisas

estavam cercadas por grandes expectativas, pois vários testes realizados

obtiveram resultados positivos. Porém, este otimismo excessivo era

acompanhado de controvérsias, já que os testes realizados eram muito

restritos, não verificando problemas mais amplos e complexos (RUSSELL e

NORVIG, 2004).

Devido à inexistência de um mercado para jogos na época, estes não

passavam de testes em laboratórios, como Tênis para Dois, de 1958, que era

um jogo simples, jogado através de um osciloscópio (BATISTA et al., 2007), ou

demonstrações de capacidade de hardware, como no jogo Spacewar!, de 1961,

no qual o jogador controlava uma nave espacial enfrentando naves inimigas e

utilizava algoritmos complexos para cálculos físicos.

Em ambos os casos, os jogos permitiam apenas jogabilidade Versus

Mode, a ação de um jogador contra outro apenas, não havendo necessidade

da aplicação de nenhuma técnica de Inteligência Artificial, conforme menciona

4

(NERF US PLEASE, 2008): “Até as décadas de 60 e início de 70, os jogos

eletrônicos possuíam apenas VERSUS MODE, não havendo a necessidade da

utilização da IA.”

Na década de 70, apesar de seu início conturbado, as pesquisas na área

de Inteligência Artificial começam a gerar resultados mais sólidos. Foi o início

da utilização de métodos para solução de problemas relativamente pequenos,

pois estes não suportavam problemas de maior porte. Exemplos de utilização

desses métodos são: o programa DENDRAL, da Universidade de Stanford,

para inferir a estrutura molecular a partir de dados de um espectrômetro de

massa, e o MYCIN, também da Universidade de Stanford, que tinha como

objetivo diagnosticar infecções sanguíneas.

Na área de entretenimento, os primeiros consoles começaram a ser

lançados no mercado, abrindo uma janela de oportunidades para

desenvolvimento de jogos, sendo o primeiro deles, o Odyssey 100. Foi nesse

período que os primeiros jogos que utilizavam conceitos de Inteligência Artificial

surgiram. As primeiras entidades inteligentes apareceram nos jogos Pursuit e

Qwak, de 1974, onde o jogador deveria atirar em alvos móveis (NERF US

PLEASE, 2008), os quais utilizavam padrões de movimento. O mesmo

processo foi utilizado no jogo Gun Fight, de 1975, e também no jogo Space

Invaders, de 1978.

Já na década de 80, a Inteligência Artificial começa a ser tratada, ao

mesmo tempo, como produto industrial das grandes empresas e como tópico

para estudos científicos. Investimentos pesados na área levaram as grandes

empresas a terem seu próprio grupo de pesquisa em IA e a utilizar sistemas

baseados nela. Também ocorreu uma retomada das pesquisas em relação às

redes neurais1, que haviam sido deixadas de lado até então. Esta retomada,

que aperfeiçoou os processos de reconhecimento de padrões e aprendizado,

levou à mineração de dados, amplamente utilizada atualmente. Em todos os

aspectos da IA, a pesquisa passou a ser tratada rigorosamente como pesquisa

científica, sujeita a todos os métodos de verificação de processos para

assegurar os resultados apresentados (RUSSELL e NORVIG, 2004).

1 Redes neurais são sistemas computacionais estruturados numa aproximação à computação

baseada em ligações. Nós simples são interligados para formar uma rede de nós.

5

Nesse mesmo período, o grande avanço relacionado à IA nos jogos foi a

utilização de uma FSM (Finite State Machine, ou Máquina de Estados Finitos).

Ela descreve uma série de ações passíveis de serem realizadas pelo

personagem e em quais circunstâncias. O jogo Pac-Man, de 1980, ao se

utilizar de uma máquina de estados para cada inimigo, permitiu sua ação

autônoma baseada na atual situação do jogador e dos outros inimigos (NERF

US PLEASE, 2008). No Pac-Man, os estados possíveis da máquina de estados

dos fantasmas são: procurando o jogador, perseguindo o jogador e fugindo do

jogador.

Outro jogo que influenciou seus predecessores foi Sim City, de 1989,

que introduziu um novo sistema de jogo, simulando sistemas complexos e

utilizando técnicas de IA para gerar respostas em tempo real às ações do

jogador (CHAMPANDARD, 2007).

Na década de 1990, surgiu o conceito de Agentes Inteligentes, que se

utilizavam de várias técnicas de IA para resolução de problemas, percepção

constante de determinado ambiente, entre outras aplicações (Russell e Norvig,

2004). Foi nesse período que foi lançado o primeiro jogo do estilo RTS (Real

Time Strategy, ou Estratégia em Tempo Real), Herzog Zwei, de 1990, que já

apresenta algoritmos de path-finding2, porém de baixa qualidade (NERF US

PLEASE, 2008).

Também foi lançado o primeiro jogo do estilo FPS (First Person Shooter,

ou Tiro em Primeira Pessoa), Doom, de 1993, que utilizava, de uma forma mais

complexa, as máquinas de estados para o comportamento dos inimigos.

Em 1996 é lançado o jogo Battlecruiser: 3000AD, cujos desenvolvedores

alegaram serem os primeiros a utilizar redes neurais em um jogo, apesar de

este fato ter causado muitas controvérsias, pois muitos não acreditavam nessa

possibilidade, ou que o processo que se utilizava da técnica seria muito simples

e com pouco impacto nos jogos (NERF US PLEASE, 2008).

A Inteligência Artificial em jogos de tiro em primeira pessoa tomou um

novo rumo após o lançamento do jogo Half-Life, de 1998, que aperfeiçoou

muito os processos das máquinas de estados, o que tornou o jogo mais realista

2 São algoritmos específicos que buscam um caminho entre dois pontos de um cenário.

6

que os seus concorrentes, fazendo com ele fosse aclamado pela crítica como

melhor jogo do ano e também melhor Game AI (jogo com técnicas robustas de

IA) até então (NERF US PLEASE, 2008).

O Remote Agent da NASA foi o primeiro programa de planejamento

autônomo a ser responsável pelo controle das operações de uma nave

espacial, realizando a detecção de problemas, diagnósticos e recuperação

desses problemas na medida em que ocorriam (RUSSELL e NORVIG, 2004).

No campo dos jogos, em 1997, o Deep Blue da IBM se tornou o primeiro

sistema computacional a derrotar o campeão mundial de xadrez, o enxadrista

Garry Kasparov, numa partida de exibição (RUSSELL e NORVIG, 2004).

Em 2000, foi lançado o jogo Total War, que, apesar de não apresentar

avanços em relação a técnicas de IA, introduziu uma nova forma de utilização,

controlando o comportamento e as respostas de centenas de unidades ao

mesmo tempo (CHAMPANDARD, 2007), o que não havia acontecido até então.

Também neste ano, foi lançado The Sims, um jogo de simulação da vida

cotidiana, que deu um grande passo, desenvolvendo a IA nos personagens,

que apresentavam comportamentos mais realistas, desejos e escolhas no

decorrer do jogo (CHAMPANDARD, 2007).

O jogo Black and White, de 2001, deu mais um passo no avanço da

Inteligência Artificial nos jogos. Além de usar máquinas de estados e processos

puramente matemáticos para controle das vilas no jogo, a parte com maior

impacto foi a criatura, que o jogador pode, através de suas ações, moldar sua

personalidade, tornando-a uma criatura pacífica ou num monstro maléfico,

destruindo tudo a sua frente. Este processo é o conjunto de várias técnicas,

como, por exemplo, um sistema de valores simbólicos atribuídos a cada objeto,

aliado a um processo baseado em regras, dão a criatura informações sobre o

objeto. Uma árvore de decisão foi usada para representar a opinião da criatura

sobre algum objeto. Para os desejos da criatura, foram utilizadas redes neurais.

Mas seu uso não se restringiu apenas à criatura, e está presente em cada

personagem do jogo (Molyneux, 2001). Essas técnicas, aplicadas onde são

mais relevantes, tornam o processo mais realista. O jogo provou que o

aprendizado em jogos é uma tecnologia legítima para os jogos de mercado.

7

Em 2005, foi lançado o jogo F.E.A.R., que melhorou consistentemente

os processos de resposta a eventos em tempo real utilizados pelos jogos até

então. A partir desses melhoramentos, movimentos em esquadrão se tornaram

mais intuitivos e realistas (CHAMPANDARD, 2007).

O jogo de Tiro em Primeira Pessoa Left 4 Dead, de 2008, utilizou

técnicas de IA de uma maneira nova, gerando inimigos e desafios, baseando-

se na atual situação do jogador, tornando-o mais fácil, ou mais difícil,

dependendo do desempenho do jogador (CHAMPANDARD, 2007).

Neste contexto da evolução histórica da tecnologia da IA, recentemente

começaram as pesquisas e a utilização dos algoritmos genéticos aplicados a

jogos eletrônicos, especialmente sobre o comportamento dos personagens dos

jogos.

3 ALGORITMOS GENÉTICOS

O desenvolvimento dos estudos de Charles Darwin sobre a evolução

das espécies, apresentados em 1859, no qual o indivíduo mais bem adaptado

ao meio tem maiores possibilidades de sobrevivência, resultaram no conceito

de que as diferentes formas de vida são passíveis de adaptações, através de

mudanças genéticas gradativas. Estas mudanças ocorrem devido à influência

do ambiente em que vive o indivíduo.

Tendo como referência estes conceitos apresentados por Darwin, no

início, as pesquisas relacionadas aos algoritmos evolutivos foram realizadas

por biólogos evolucionistas que criaram representações programadas em

computadores para a modelagem de aspectos evolucionários dos animais

(MARCZYK, 2004). Baseando-se na observação dos organismos vivos, que

são grandes solucionadores de problemas, possuindo uma incrível capacidade

de adaptação ao ambiente imposto a eles, houve um grande aprofundamento

das pesquisas de sistemas de aprendizado.

O estudo dos algoritmos evolutivos baseou-se em três áreas diferentes

de pesquisa: a programação evolucionária, a estratégia evolucionária e os

Algoritmos Genéticos (GROSKO et al., 2009). Todas estas áreas possuem uma

8

mesma base de conhecimento. Porém, se diferenciam em detalhes nos

processos e em seu escopo.

Os primeiros estudos na área de sistemas adaptativos complexos foram

realizados por Nils Aall Barricelli na década de 50. Porém, seu trabalho foi

pouco conhecido. O mesmo aconteceu com o trabalho do australiano Alex

Fraser, também na década de 50. A partir destes primeiros estudos, pesquisas

sobre simulações do processo evolutivo se tornaram mais populares, mas

apenas no final da década de 60 e início da década de 70, o processo de

evolução artificial se tornou amplamente reconhecido, através dos estudos de

Ingo Rechenberg e Hans-Paul Schwefel, os quais conseguiram resolver

problemas complexos através de processos de simulação evolutiva. Porém,

estes processos que foram utilizados pouco se assemelhavam aos Algoritmos

Genéticos (MARCZYK, 2004).

Todos os estudos supracitados se utilizavam de máquinas de estados

finitos, que eram adaptadas durante o processo para melhor adequação ao

problema. Somente na década de 70, com o trabalho de John Holland,

considerado o criador dos Algoritmos Genéticos, foi criada a base para futuras

pesquisas na área. Estes estudos foram focados na adaptação dos seres vivos,

no processo evolutivo, que diz que uma característica que melhor se adapta ao

ambiente é passada adiante. Holland foi o primeiro a introduzir os processos de

crossover, que cria um novo indivíduo com partes definidas dos seus geradores,

e de mutação, que altera um valor aleatório dentro do indivíduo.

Contrastando com o padrão de pesquisa utilizado, que definia o uso de

algoritmos para resolução de problemas específicos, Holland queria estudar os

processos de adaptação na natureza e adaptar estes processos à realidade

computacional (MITCHELL, 1998). O primeiro framework que realizava estes

processos foi nomeado Holland’s Schema Theorem.

Utilizando como base suas pesquisas anteriores, John Holland e

companheiros da Universidade de Michigan publicaram o livro Adaptation in

Natural and Artificial Systems, em 1975, que efetivamente introduziu o conceito

de sistemas digitais adaptativos utilizando mutação, crossover e seleção

natural, os quais serão descritos em detalhe posteriormente, para simular

processos biológicos e utilizá-los para resolução de problemas, sendo esta

9

uma grande inovação para o período. Holland também foi o primeiro a buscar o

desenvolvimento de uma base teórica mais firme para as futuras pesquisas na

área de Algoritmos Genéticos.

Neste mesmo ano, o trabalho de Kenneth De Jong estabeleceu o

potencial dos Algoritmos Genéticos na resolução de testes, introduzindo ruídos

e descontinuidades aos parâmetros das buscas (MARCZYK, 2004).

Em meados da década de 80, os Algoritmos Genéticos já eram

utilizados em vários tipos de aplicações, desdedesde problemas matemáticos

abstratos até problemas de Engenharia mais tangíveis, como controle de fluxo,

detecção de padrões e classificação (MARCZYK, 2004).

No final da década de 80, David E. Goldberg, outro precursor dos

Algoritmos Genéticos atuais, descreve o mesmo como “uma pesquisa baseada

no mecanismo de seleção e genética natural objetivando a otimização”.

Segundo ele, os Algoritmos Genéticos são superiores aos métodos clássicos

de otimização descritos na literatura, pois se apoiaram no fato de que eles

utilizam codificação dos parâmetros e não dados reais; que fazem busca numa

população e não num único ponto; que usam a informação de aptidão e não

outro conhecimento auxiliar; e também que usam regras de transição

probabilísticas e não determinísticas.

O processo de evolução acontece por dois métodos: pela seleção

natural, que faz com que as melhores qualidades dos indivíduos, as quais são

selecionadas em relação ao problema em mãos, sejam repassadas aos seus

descendentes, e a reprodução em si, que garante a mistura dos genes dos

indivíduos envolvidos, resultando num indivíduo diferente e possivelmente

melhor que seus ancestrais (HOLLAND, 2009).

Atualmente, computação evolutiva é um campo muito amplo, e os

Algoritmos Genéticos passaram também a ser aplicados para resolução de

problemas mais comuns, como previsões de bolsas, planejamento de vôos em

aeroportos, design de microchips, entre várias outras aplicações, não havendo

praticamente nenhuma área que não se utilize desses processos (MARCZYK,

2004).

O processo de um algoritmo genético começa com uma população

formada por uma lista aleatória de possibilidades, chamadas de indivíduos ou

10

cromossomos. Estes indivíduos podem ser convertidos de sua notação original,

que é uma representação de uma possível solução do problema, seja ela boa

ou ruim, para notação binária, que é utilizada pelo algoritmo, como mostrado na

Ilustração 1, podendo também ser utilizados em sua notação original. O

número de bits dos indivíduos deve ser o suficiente para que as possíveis

soluções possam ser convertidas novamente à notação inicial, como afirma

(BUCKLAND, 2002): “Uma coisa importante é que cada cromossomo seja

codificado de forma que o conjunto de bits possa ser decodificado para

representar uma solução do problema em questão”.

Ilustração 1: Representação de um indivíduo na notação binária.

Após a geração da população inicial, uma parte dela é selecionada para

reprodução e, consequentemente, para a criação de uma nova geração. Esta

seleção se dá através de uma função de aptidão, ou função de fitness, que

verifica o quão próximo do resultado desejado está aquele indivíduo e atribui

um valor, ou nota, ao indivíduo, baseada nesse fator. O grupo que participará

da reprodução é chamado de grupo gerador, cujos indivíduos são selecionados

com base na nota resultante da função de fitness. Notas melhores aumentam a

probabilidade de um indivíduo participar do grupo gerador (RUSSELL e

NORVIG, 2004).

Depois de selecionado o grupo gerador, os indivíduos são divididos em

pares, e, para cada par, é realizada uma troca de parte dos bits de cada

indivíduo. Esta troca é denominada crossover (BUCKLAND, 2002). O crossover

é realizado seguindo uma taxa de crossover, que é uma porcentagem na qual o

crossover será executado, definida pelo usuário. Ela define a porcentagem de

indivíduos da população que sofrerão crossover. Seguindo uma posição

aleatória, todos os bits à direita daquele ponto serão trocados. Considerando-

se a posição do crossover igual a 3, a reprodução se dá como mostra a

Ilustração 2.

11

Ilustração 2: Processo de crossover.

O resultado da operação de crossover são dois indivíduos novos, que

carregam características dos indivíduos geradores, e farão parte da nova

geração. Quando os indivíduos geradores são muito diferentes, os

descendentes resultantes da operação de crossover podem ser totalmente

diferentes dos pais, o que demonstra que, no início do processo, as primeiras

execuções de crossover darão saltos maiores, enquanto, mais adiante no

processo, devido à seqüência de reproduções, os descendentes tendem a ser

mais parecidos com seus geradores, como afirma (RUSSELL e NORVIG,

2004):

Em geral, a população é bastante diversa no inicio do processo, e assim o crossover (como a têmpera simulada) freqüentemente executa grandes passos no espaço de estados bem no inicio do processo de busca e passos menores adiante, quando a maioria dos indivíduos é bastante semelhante. (RUSSELL e NORVIG, 2004, p.116)

Após o crossover, pode ocorrer o processo de mutação dos indivíduos,

em que um bit do indivíduo é invertido (BUCKLAND, 2002), como mostra a

Ilustração 3. A frequência na qual as mutações são realizadas é baseada na

taxa de mutação, esta sendo uma porcentagem da população que sofrerá a

mutação, também definida pelo usuário.

Ilustração 3: Processo de mutação.

Após a geração dos descendentes, é feita uma avaliação para verificar

se algum dos novos indivíduos faz parte da solução desejada. Caso ocorra, o

processo é finalizado, retornando este indivíduo como solução. O processo

12

também pode ser encerrado caso o tempo limite definido tenha decorrido. Caso

não haja solução, os indivíduos da população inicial menos propensos a ser a

solução do problema são substituídos pela nova geração. Esta nova geração

passa pela função de fitness, em que são atribuídas suas notas, e o processo

de reprodução recomeça (BUCKLAND, 2002).

O fragmento de pseudocódigo na listagem 1 representa um algoritmo

genético. Apesar de ser uma representação relativamente simples de um

algoritmo genético, ela demonstra com objetividade a organização e execução

dos passos descritos anteriormente. Porém, neste caso, ele é apresentado com

uma pequena diferença, a reprodução gera apenas um descendente, como

afirma (RUSSEL e NORVIG, 2004): “[...] em sua versão mais popular, cada

união de dois pais produz apenas um descendente, e não dois.”

O algoritmo recebe como parâmetros a população inicial, gerada a partir

de possíveis soluções do problema, e a função de fitness FN-FITNESS, que irá

definir, através de um valor, a proximidade do indivíduo em relação à solução.

Inicialmente ele cria uma população vazia, nomeada nova_população, que irá

receber os indivíduos gerados pela reprodução. Em seguida, são selecionados

dois indivíduos, x e y, aleatoriamente, usando como base a função de fitness,

que farão parte da reprodução e gerarão um novo indivíduo, denominado filho.

Na função de reprodução, o tamanho do indivíduo x é armazenado na variável

n, e, logo após, é gerado um valor aleatório entre 1 e n, definido como c. O filho

é gerado concatenando os valores do indivíduo x, das posições 1 até c e os

valores do indivíduo y das posições c+1 até n, gerando uma sequência de

valores totalmente nova. Além da reprodução, dependendo da taxa predefinida,

é realizada a mutação no filho, sendo, em seguida, adicionado à

nova_população. Isto é feito até que o limite da população inicial seja atingido.

função ALGORITMO-GENÉTICO(população, FN-FITNESS) retorna um indivíduo

entradas: população, um conjunto de indivíduos

FN-FITNESS, uma função que mede a adaptação de um indivíduo

repita

nova_população ← conjunto vazio

para i ← 1 até TAMANHO(população) faça

x ← SELEÇÃO-ALEATÓRIA(população, FN_FITNESS)

y ← SELEÇÃO-ALEATÓRIA(população, FN_FITNESS)

filho ← REPRODUZ(x,y)

se (pequena probabilidade aleatória) então

filho ← MUTAÇÃO(filho)

13

adiciona filho a nova_geração

população ← nova_população

até algum indivíduo estar adaptado o suficiente ou até ter

decorrido tempo suficiente

retornar o melhor indivíduo de população, de acordo com FN-FITNESS

----------------------------------------------------------------

função REPRODUZ(x,y) retorna um indivíduo

entradas: x,y, indivíduos pais

n ← COMPRIMENTO(x)

c ← número aleatório de 1 a n

retornar CONCATENA(SUBCADEIA(x,1,c),SUBCADEIA(y,c+1,n))

Listagem 1: Representação em pseudocódigo de um algoritmo genético

Fonte: (RUSSEL e NORVIG, 2004)

Os passos descritos anteriormente são repetidos até que algum

indivíduo da população esteja suficientemente próximo da solução proposta,

até que um tempo definido tenha decorrido ou até que o número limite de

iterações definido ocorra. O algoritmo então retorna o indivíduo mais próximo

da solução, baseando-se na função de fitness FN-FITNESS.

4 Aplicações em Jogos

Para exemplificar os conceitos apresentados anteriormente, se faz

necessária a demonstração de possíveis aplicabilidades dos Algoritmos

Genéticos em jogos eletrônicos, tais como a navegação autônoma e controle

de comportamento de personagens.

4.1 Navegação Autônoma

Navegação autônoma se dá quando um agente, utilizando como base

informações como o local pelo qual transitará, a extensão deste local e

possíveis obstáculos, consegue, sem interferência humana, partir de um local

qualquer e atingir um outro local definido como objetivo.

4.1.1 Busca em Árvores de Decisão

Uma busca em árvore de decisão busca o resultado, expandindo, a

partir de um ponto inicial, que é denominado nó raiz da árvore, todas as

14

possibilidades do problema, gerando novos nós, que expandem todas as

possibilidades em novos nós, sendo cada nó uma possibilidade do problema,

fazendo assim até que sejam cobertas todas as possibilidades do problema e o

resultado seja alcançado. Neste modelo, a busca se torna custosa, pois ela

expande sempre todos os nós possíveis, fazendo com que o tempo de busca

seja maior. A solução utilizada para melhoria do processo foi a busca pela

melhor escolha (SHI, 2006).

Na busca por melhor escolha (Best-First Search) são expandidos os nós

e, em seguida, é escolhido o nó que está mais próximo do objetivo final,

baseando-se numa função heurística que estima a distancia do nó até o

objetivo. Com a expansão de menos nós, há um ganho de desempenho no

algoritmo.

4.1.2 Exemplo de aplicação em navegação autônoma

O objetivo principal deste exemplo é que o personagem, no caso, um

tanque, partindo de qualquer ponto de um mapa (ilustração 6), possa, através

do uso de Algoritmos Genéticos, encontrar o ponto de chegada desviando-se

de obstáculos que se apresentam pelo mapa, os quais são posicionados de

forma aleatória (APPOLINARIO e PEREIRA, 2007).

4.1.3 Representação do problema

Inicialmente é considerado um mapa representado através de uma

matriz 10x10 posições. Como ponto de partida será considerada a coordenada

(0,0), no canto esquerdo superior do mapa, e o ponto de chegada se situará na

coordenada (9,9), no canto direito inferior do mapa. Para uso nos processos,

valores são atribuídos às posições do mapa para definir sua característica,

sendo atribuído o valor 0 às posições livres, o valor -1 aos obstáculos

posicionados no mapa, o valor -9 para o ponto de partida e o valor 9 para o

ponto de chegada (APPOLINARIO e PEREIRA, 2007).

Nesta aplicação, conforme Appolinario e Pereira (2007), foram usados

cromossomos que continham entre 60 e 80 alelos, sendo estes subdivisões de

15

um cromossomo, os quais definem uma característica do mesmo, e variando,

neste caso com o tamanho de 2 bits, sendo 00 para movimento para cima; 01

para a esquerda; 10, para baixo; e 11, para a direita. Uma verificação é

realizada durante o processo para analisar se o objeto realizou um movimento

válido, ou seja, se ele se movimentou para fora do mapa, ou se atravessou

uma posição ocupada por um obstáculo, e realizar o cálculo do fitness. Caso o

cromossomo possua algum movimento inválido dentro de sua estrutura, o valor

de seu fitness é reduzido de acordo com essa falha. Além desse fator, também

são levados em consideração, para atribuição do fitness, quantos movimentos

válidos estão presentes naquele cromossomo, através de um contador, e

também a proximidade da última posição do cromossomo em relação ao ponto

de chegada (APPOLINARIO e PEREIRA, 2007).

Após testes preliminares, Appolinario e Pereira (2007) verificaram que as

taxas de acertos do algoritmo, atuando no mapa com 10x10 unidades foram

mais altas quando o número de indivíduos da população foi 80, o número de

gerações a ser criadas foi de 100 e o tamanho do cromossomo foi estabelecido

com 70 bits. Os números que froam base para a quantidade de obstáculos

variaram entre 10, 18 e 34 obstáculos no mapa. Os resultados tiveram valores

médios para tempo de execução e número de movimentos iguais a 0,21

segundos e 22 passos, respectivamente.

4.1.4 Resultados e Comparação

Os testes usados para comparação entre o uso de Algoritmos Genéticos

e busca em árvore tomaram como base 3 mapas, representados por matrizes

10x10, 30x30 e 50x50 (APPOLINARIO e PEREIRA, 2007).

Para análise posterior dos resultados, foram usados como base os

dados de tempo de execução dos processos, tanto do algoritmo genético

quando da busca em árvore, assim como o custo da solução, sendo este custo

o número de passos contidos na solução encontrada por ambas as técnicas

(APPOLINARIO e PEREIRA, 2007).

16

O algoritmo genético teve resultados piores do que a busca em árvore,

tendo a diferença de desempenho aumentado de acordo com o aumento de

blocos e obstáculos no mapa, como mostra a tabela 1.

Tamanho do cenário

Tempo do AG

Tempo da árvore

Custo do AG

Custo da árvore

10x10 0,21 0,1 20 15

30x30 0,35 0,1 151 103

50x50 0,59 0,3 428 292 Tabela 1: Tabela de dados comparativa

Fonte: (APPOLINARIO e PEREIRA, 2007)

Tanto nos cenários de 10x10 unidades, quanto no de 30x30 unidades, o

desempenho da busca em árvore se manteve em 0,1 segundos, enquanto o

algoritmo genético levou 0,21 no primeiro caso, e ainda mais no segundo, com

0,35 segundos. No cenário com 50x50 unidades, a vantagem da busca em

árvore se mantém à frente, realizando o processo em 0,3 segundos, contra

0,59 do algoritmo genético. Em relação ao custo, ou número de passos total da

solução, o algoritmo genético tambem teve desempenho pior, com custos

relativamente grandes em relação a busca em árvore, aumentando ainda mais

com o crescimento do cenário, como mostrado na tabela 2.

As diferenças em relação aos dois métodos fica mais evidente nos

gráficos apresentados na Ilustração 4.

Comparativo por tempo

0

0,2

0,4

0,6

0,8

10x10 30x30 50x50

AG

Árvore

Comparativo por custo

0

100

200

300

400

500

10x10 30x30 50x50

AG

Árvore

Ilustração 4: Gráficos comparativos de desempenho Fonte: (APPOLINARIO e PEREIRA, 2007)

17

Apesar de ter seu desempenho inferior ao da busca em árvore, o

algoritmo genético conseguiu encontrar possíveis resultados, atingindo valores

máximos de 36, 270 e 750 passos para os mapas de 10x10 unidades, 30x30

unidades e 50x50 unidades, respectivamente, enquanto a busca em árvore

atingiu máximos de 44, 287 e 766 passos (APPOLINARIO E PEREIRA, 2007).

Para melhor se adaptar às mudançar de terreno, o número de alelos do

cromossomo, antes fixo, tornou-se variável, definindo-se que um cromossomo

precisaria conter entre 30% e 35% da quantidade total de movimentos

possíveis de serem realizados no mapa, como mostra a tabela 2. Outra

mudança importante realizada por Appolinario & Pereira (2007) foi a de fixar a

quantidade de cromossomos utilizada pelo algoritmo, já que a mudança desse

valor não trouxe variações significativas para os resultados dos testes.

Também foi implementado o elitismo, com seu valor definido em 3%, para

garantir que possíveis soluções ótimas não sejam eliminadas de uma geração

para outra.

Tamanho do Mapa Tamanho do cromossomo

10 x 10 70

30 x 30 540

50 x 50 1500 Tabela 2: Relação Tamanho do Mapa x Tamanho do Cromossomo

Fonte: (APPOLINARIO E PEREIRA, 2007)

Outro problema encontrado foi que as soluções do algoritmo genético,

em certos momentos, apresentavam falhas e movimentos desnecessários.

Porém, estas soluções foram passadas adiante pois seu valor de fitness

sugeria que esta poderia ser uma solução cabível, como mostra a Ilustração 5.

Ilustração 5: Solução encontrada com movimento desnecessário Fonte: (APPOLINARIO e PEREIRA, 2007)

Os Algoritmos Genéticos se mostraram como uma possível solução para

o problema de navegação em jogos eletrônicos, apresentando resultados

18

satisfatórios, além de tempos de resposta rápidos. Porém, em comparação

com o método de busca em árvore, seu desempenho foi consideravelmente

pior, tanto no tamanho das soluções, quanto no tempo de execução. Uma

possível resposta para agilização dos Algoritmos Genéticos pode estar na

hibridização, como afirma (APPOLINARIO e PEREIRA, 2007):

[...] pretende-se implementar um algoritmo híbrido, utilizando o método de busca em árvore para a geração da população inicial em vez de ela ser gerada aleatóriamente. (APPOLINARIO e PEREIRA, 2007, p. 91)

4.2 Controle de Comportamento de Personagens

Neste tópico é abordado o uso de Algoritmos Genéticos no controle do

comportamento de personagens autônomos, explorando o jogo Último

Sobrevivente, descrito em Silva, Crocomo, e Andrade (2008).

4.2.1 Descrição do problema

O jogo analisado possui como cenário uma arena, onde o jogador

controla um cavaleiro e, usando sua espada, deve se defender contra o ataque

de 4 outros cavaleiros controlados pelo algoritmo, denominados NPCs (Non-

Playable Characters ou Personagens Não Jogáveis), e ao final, eliminá-los

(Silva, Crocomo, e Andrade, 2008).

4.2.2 Representação do Problema

A arena adotada como cenário para o jogo, possui proporções de

570x600 pixels. A movimentação, tanto do jogador quando dos NPCs, se dá

em 8 direções, vertical para cima e para baixo, horizontal para a esquerda e a

direita e para as 4 diagonais. Cada cavaleiro possui uma quantidade fixa de

vidas e cada ataque realizado remove de maneira fixa um quarto do valor atual

da vida do outro cavaleiro (Silva, Crocomo, e Andrade, 2008).

Os comportamentos são adotados pelos NPCs de acordo com a

situação atual do jogo. São três possíveis valores para o comportamento: o

19

valor 0 faz com que o NPC fuja do jogador, o valor 1 faz com que o NPC vá em

direção a um aliado e o valor 2 faz com que o NPC persiga e ataque o jogador.

Duas informações servem de base para definir o comportamento do

personagem: o número de aliados presentes atualmente no mapa e a

quantidade de energia restante. Os níveis de vida podem variar de 0 até 2, em

que 0 representa o nível mais baixo de vida, 1 representa um nível

intermediário e 2 representa o nível mais alto de vida do NPC ou Jogador. A

relação entre estas informações é mostrada na tabela 3.

Vida Amigos Cromossomo (Saída)

0 0 2

0 1 1

0 2 2

0 3 2

1 0 0

1 1 0

1 2 1

1 3 0

2 0 2

2 1 1

2 2 2

2 3 1 Tabela 3: Relação Dados x Comportamentos

Fonte: (SILVA et al., 2008)

Se um NPC, por exemplo, tiver seu valor de vida com valor 0 e não

houver mais nenhum aliado, a ação que será realizada por esse NPC será a de

perseguir e atacar o jogador.

Neste caso, para formação dos cromossomos, foi utilizado um vetor

numérico de 12 posições, variando entre 0 e 2, chegando a um total de

531.441 possíveis cromossomos. O cromossomo representa as possíveis

ações dos NPCs, sendo assim, cada cromossomo pode ser considerado como

um personagem nesta situação. Para a função de fitness, o padrão utilizado

para definir as notas dos indivíduos foi de 5 pontos a mais para cada ataque

realizado, e de 2 pontos a cada 10 segundos nos quais o NPC esteja vivo. Em

contrapartida, 3 pontos são removidos da nota do indivíduo caso ele seja

atingido pelo jogador. A tabela a seguir mostra os dados relativos a uma

população qualquer:

20

População Cromossomo Aptidão

Indivíduo 1 0 2 1 0 0 2 0 1 0 0 0 1 20

Indivíduo 2 0 1 0 2 0 2 2 1 0 1 0 1 12

Indivíduo 3 0 0 0 0 0 0 0 0 0 0 0 0 5

Indivíduo 4 1 1 2 1 1 0 1 1 1 1 1 1 11 Tabela 4: Informações de uma possível população

Fonte: (SILVA et al., 2008)

Este jogo, assim como o estudo anterior, utiliza o elitismo para

resguardar, neste caso, apenas a melhor solução obtida em uma geração e

acelerar a convergência do algoritmo (Silva, Crocomo, e Andrade, 2008).

O jogo utiliza um processo de crossover um pouco diferente, chamado

crossover multiponto, o qual define não só um, mas vários pontos de corte ao

longo dos cromossomos selecionados, ocorrendo uma troca maior de

informações para geração do novo indivíduo, como é mostrado na ilustração 6.

A taxa de mutação foi fixada em 5% (SILVA et al., 2008).

Ilustração 6: Crossover Multiponto

Fonte: (SILVA et al., 2008)

4.2.3 Resultados

O comportamento dos NPCs evoluiu à medida que novas partidas foram

sendo realizadas, e também conforme o jogador assimilava suas estratégias.

Dois experimentos foram realizados, cada um contendo 80 partidas. No

primeiro, as notas atribuídas aos indivíduos da geração inicial foram muito boas,

porém à medida que o jogador assimilava as estratégias utilizadas, as notas

sofreram uma queda. Em seguida, já se adaptando às novas técnicas do

jogador, as notas voltaram a subir. O saldo final do jogador foi de 30 derrotas

contra 50 vitórias, sendo muitas delas em sequência. A Ilustração 7 demonstra

esta variação nas notas a cada geração do algoritmo.

21

Ilustração 7: Gráfico Aptidão x Geração do primeiro experimento Fonte: (SILVA et al., 2008)

No gráfico, cada linha representa um personagem, apontando a variação

dos valores de aptidão a cada geração do algoritmo, esta sendo baseada nos

resultados do primeiro experimento.

O segundo experimento teve resultados mais balanceados, com o

algoritmo se adaptando ao comportamento do jogador com maior velocidade,

assim como as repostas do jogador, o que manteve as notas numa variação

menor. O saldo do jogador no segundo experimento foi de 54 derrotas e 26

vitórias que, diferentemente do primeiro experimento, foram distribuídas

uniformemente entre as partidas. A Ilustração 8 mostra o equilíbrio que se deu

durante o experimento.

Ilustração 8: Gráfico Aptidão x Geração do segundo experimento Fonte: (SILVA et al., 2008)

22

Assim como no primeiro, o gráfico possui quatro linhas, uma para cada

NPC, mostrando o desempenho dos mesmos em cada geração do experimento

dois.

Além dos 3 comportamentos básicos definidos anteriormente, os NPCs

em alguns momentos, definiam estratégias inesperadas, pois não faziam parte

da programação inicial. Uma estratégia muito eficaz utilizada pelos NPCs foi a

de se agruparem para realizar um ataque concentrado ao jogador.

Ao adaptar a dificuldade nos jogos, alterando seu comportamento de

acordo com a habilidade do jogador, é mantido o interesse no jogo, pois o

adversário sempre apresenta um novo desafio, uma nova estratégia, que faz

com que o jogador tenha de se esforçar mais para derrotar seu oponente.

5 Aplicação proposta

O jogo utilizado como base para uma nova proposta de aplicação será o

jogo Pac-Man, aplicando o algoritmo genético nos fantasmas, controlando seu

comportamento. O objetivo do jogo é recolher todas as moedas, que dão

pontos ao jogador, presentes no mapa, sem que os quatro fantasmas, que são

os inimigos, o destrua através do toque do fantasma no personagem, exceto

se o jogador possuir o Power-up, que permite ao jogador destruir os fantasmas

por um curto período de tempo.

Será considerado um mapa 17x24 unidades, composto por paredes, que

são os obstáculos, moedas e Power-ups. Os valores atribuídos no mapa para

cada objeto são: -1 para obstáculos, 0 para espaços vazios, 2 para espaços

vazios com moedas, 3 para espaços vazios com Power-ups e 1 para a posição

inicial do Pac-Man.

A movimentação de todos os personagens se dá apenas nos sentidos

vertical e horizontal, sem movimentos diagonais. Para o comportamento dos

fantasmas foram definidos dois possíveis valores: 0 faz com que o fantasma

persiga o jogador em situação normal e o valor 1 faz com que o fantasma fuja

do jogador quando este tiver adquirido um Power-up, como mostra a Tabela 6.

Situação do jogador Resposta do fantasma

23

Sem Power-up 0

Com Power-up 1 Tabela 6: Saída de comportamento dos fantasmas

A população, neste caso, será composta de apenas 4 indivíduos, um

para cada fantasma do jogo. Cada cromossomo será representado inicialmente

por um vetor de 8 posições, sendo que cada posição do mesmo pode variar

entre 0 e 1, conforme definido anteriormente e demonstrado na Tabela 5.

População Composição do cromossomo

Indivíduo 1 0 1 0 0 1 0 1 1

Indivíduo 2 0 1 0 1 1 1 0 0

Indivíduo 3 1 1 0 1 0 0 1 1

Indivíduo 4 0 1 0 1 1 0 1 0 Tabela 5: Tabela de composição de indivíduos

A estratégia de fitness adotada, neste caso, atribui mais 5 pontos à

função de avaliação do cromossomo caso o fantasma consiga destruir o

jogador, e menos 3 pontos caso o jogador, possuindo o Power-up, consiga

destruir o fantasma. A taxa de mutação, inicialmente, será definida em 3%.

Também será aplicado o elitismo, neste caso, repassando apenas um indivíduo,

devido à pequena quantidade de indivíduos da população. O processo de

crossover utilizado será o padrão, gerando apenas um indivíduo.

24

6 Considerações Finais

Com base numa pesquisa bibliográfica, explorou-se um histórico da

Inteligência Artificial com seu foco direcionado para jogos eletrônicos. Também

foi possível desenvolver uma descrição do surgimento e os avanços realizados

na área dos Algoritmos Genéticos, principalmente baseados na teoria

darwiniana da evolução das espécies, em que o indivíduo mais bem adaptado

tem mais possibilidade de sobrevivência, assim como o desenvolvimento de

seus conceitos e processos.

As duas aplicações descritas neste trabalho mostram que os Algoritmos

Genéticos, no contexto de jogos eletrônicos, ainda têm seu uso restrito, pois

como ilustra o primeiro estudo, eles não obtiveram boa performance, o que

muitas vezes é necessário. Já no contexto de controle de comportamento, os

algoritmos se mostraram uma boa solução, pois se adaptam bem ao ambiente

de forma dinâmica e também encontram soluções inesperadas, o que se

assemelha em muitas vezes ao próprio comportamento humano, mantendo

assim o nível de diversão e adicionando um grau a mais de realismo aos jogos.

Como base para futuros trabalhos, foi proposta uma aplicação do

algoritmo em um contexto em que este não foi utilizado originalmente, no caso,

o jogo Pac-Man, fazendo o controle de comportamento dos personagens

considerados inimigos dentro jogo. Tendo sido definidos os parâmetros básicos

e as características necessárias para o desenvolvimento e funcionamento do

algoritmo, espera-se que possa ser obtido um resultado semelhante ao citado

anteriormente, aumentando a dificuldade do jogo e aumentando o realismo do

comportamento dos personagens. Este trabalho traz então, como contribuição, uma aproximação inicial à

utilização dos Algoritmos Genéticos em jogos eletrônicos, abrindo caminho

para futuros trabalhos nessa área, seja na exploração teórica aprofundada,

seja na continuação da exploração de estudos de caso ou até mesmo na

implementação de personagens inteligentes.

25

7 Referências Bibliográficas

BATISTA, M. S., LIMA, S, M B, QUINTAO, P. L., DIAS, L., BATISTA, T. S. Um Estudo Sobre a História dos Jogos Eletrônicos. Juiz de Fora: Faculdade Metodista Granbery, 2007. BUCKLAND, M. AI Techniques for Game Programming. Cincinnati, Ohio: Premier Press, 2002. CHAMPANDARD, A. J. Top 10 Most Influential AI Games. Disponível em AiGameDev.com: http://aigamedev.com/reviews/top-ai-games/. Acesso em 22 de Julho de 2009. GALLAGHER, M., E RYAN, A. Learning to Play Pac-Man: An Evolutionary, Rule-based Approach. Disponível em http://www.itee.uq.edu.au/~marcusg/papers/CEC2003-1432.pdf. Acesso em 23 de Setembro de 2009.

GAMESPOT. Disponível em Half-Life 1 HEV Suit Upgrade: http://www.gamespot.com/users/hl20302/view_image?id=a9II4Bsi7hqY4R3knA. Acesso em 23 de Setembro de 2009.

GROSKO, A. P., GORSKI, J. R., E DIAS, J. D. Algoritmo Genético: Revisão Histórica e Exemplificação. Pontifícia Universidade Católica do Paraná, 2009.

HOLLAND, J. H. Genetic Algorithms. Disponível em Genetic Algorithms: http://www.econ.iastaté.edu/tesfatsi/holland.GAIntro.htm. Acesso em julho de 2009.

LUGER, G. F. Inteligência Artificial: Estruturas e Estratégias para a Solução de Problemas Complexos. São Paulo: ARTMED, 2004.

MARCZYK, A. Genetic Algorithms and Evolutionary Computation. Disponível em The TalkOrigins Archive: http://www.talkorigins.org/faqs/genalg/genalg.html#intro. Acesso em 19 de Agosto de 2009.

MITCHELL, M. An Introduction to Genetic Algorithms. Cambrige: MIT Press, 1998.

MOLYNEUX, P. Postmortem: Lionhead Studios' Black & White. Disponível em Gamasutra: http://www.jnoodle.com/careertech/files/postMortems/BlacknWhite.pdf. Acesso em 23 de Setembro de 2009.

26

NERF US PLEASE, E. Inteligência Artificial em Jogos Eletrônicos. Disponível em http://www.cin.ufpe.br/~ldsp/Semin%E1rio%20Agentes%20Aut%F4nomos/Semin%25E1rio%20Agentes.ppt. Acesso em 31 de Maio de 2009.

NILSSON, N. J. Artificial Intelligence: A New Synthesis. San Francisco: Morgan Kaufmann Publishers, 1998.

PERALTY, D. EA Donates Original SimCity to OLPC Program. Disponível em Geeks are Sexy: http://www.geeksaresexy.net/2007/11/09/ea-donatés-original-simcity-to-olpc-program/. Acesso em 23 de Setembro de 2009. POSEY, S. Left 4 Dead DLC coming soon?. Disponível em The Videogame Blog: http://www.thatvideogameblog.com/2008/12/30/left-4-dead-dlc-coming-soon/. Acesso em 23 de Setembro de 2009.

RABIN, S. AI Game Programming Wisdom. Hingham: Charles River Media, 2002. RUSSELL, S., E NORVIG, P. Inteligência Artificial - Tradução da Segunda Edição. Rio de Janeiro: Editora Campus, 2004

SILVA, C. R. Uso de Algoritmos Genéticos como redutor de dimensionalidade na classificação de imagens hiperspectrais. Disponível em http://dspace.c3sl.ufpr.br/dspace/bitstream/1884/4654/1/disserta_claudionor.pdf. Acesso em 23 de Setembro de 2009.

APPOLINARIO, V. B., PEREIRA, T. L. Navegação autônoma em jogos eletrônicos utilizando Algoritmos Genéticos. Disponível em http://redalyc.uaemex.mx/redalyc/pdf/810/81050108.pdf. Acesso em 23 de Novembro de 2009. SHI, H. Best-First Decision Tree Learning. Disponível em http://adt.waikato.ac.nz/uploads/approved/adt-uow20070112.105857/public/01front.pdf. Acesso em 19 de Novembro 2009. COMPUTAÇÃO, G. M. Busca em Árvores ou Grafos. Disponível em http://www.computacao.gigamundo.com/2009/03/10/busca-em-arvores-ou-grafos/. Acesso em 19 de Novembro de 2009. SILVA, A. E., CROCOMO, M. K., E ANDRADE, K. O. Um Algoritmo Evolutivo para a adaptação de NPCs em um jogo de ação. Disponível em http://200.169.53.89/scgames/artigos/08980100008.pdf. Acesso em 20 de Novembro de 2009.