10

1 INTRODUÇÃO

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

ligada ao processo evolutivo humano, com sua história contada, desde uma

base alicerçada nos estudos de Aristóteles, e caminhando sem respostas

definitivas, através do tempo, permeando-se por várias teorias relacionadas

com o ser humano (NILSSON, 1998).

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

permanente, solidificando a estrutura de aprendizado, contando com a adesão,

mesmo que lenta, de cientistas capazes de promover sua divulgação. O

movimento passa a contar com uma estrutura de conceitos devidamente

formalizados que permitem uma robustez maior e que começam a melhorar

aptidões que se tornariam marcos e abririam as portas para o início das

pesquisas e estudos, sendo um deles, os Algoritmos Genéticos (RUSSELL e

NORVIG, 2004).

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, além de se entranhar no meio industrial, 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.

Este trabalho está organizado da seguinte maneira: o Capítulo 2

relaciona a evolução da Inteligência Artificial com seu uso em jogos eletrônicos.

O Capítulo 3 mostra a evolução, desde seu surgimento até os dias atuais, e a

conceituação de Algoritmos Genéticos. O Capítulo 4 engloba dois estudos de

caso relacionados aos Algoritmos Genéticos, um aplicando-o em navegação

11

autônoma e outro para controle de comportamento de personagens. Por fim,

são apresentadas as considerações finais do trabalho.

12

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

Este capítulo desenvolve um histórico da Inteligência Artificial e também

do seu uso em jogos eletrônicos.

2.1 Introdução

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

p.23), "... 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

I.A. é 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 I.A., 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

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 e deu devido a grande parte dos estudos realizados anteriormente,

13

por outros autores e por ele próprio, tratavam 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.

2.2 Histórico

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

inteligentes se encontravam distantes dos que é conhecido 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 sim 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

(Ilustração 1), 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, palavra do inglês que representa a ação de um jogador contra outro

apenas, ou seja, relação de um para um, não havendo necessidade da

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

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

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

utilização da IA.”

14

Ilustração 1: Spacewar!Fonte: (BATISTA et al., 2007)

Na década de 70, apesar de seu início conturbado, foram quebradas

muitas das expectativas em relação à Inteligência Artificial, 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, mostrado

na Ilustração 2. 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.

15

Ilustração 2: Odyssey 100Fonte: (BATISTA et al., 2007)

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

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

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

empresas a terem seu próprio grupo de pesquisa em I.A., e a utilizar sistemas

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

redes neurais, 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 I.A., 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).

Nesse mesmo período, o grande avanço relacionado à I.A. 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 qual circunstância ela deve ser executada. O jogo Pac-Man,

de 1980 (Ilustração 3), 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.

16

Ilustração 3: Pac-ManFonte: (GALLAGHER E RYAN, 2009)

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

(Ilustração 4), 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).

Ilustração 4: Sim CityFonte: (PERALTY, 2007)

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

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

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

17

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-finding1, 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 utilizar a redes neurais2 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 (Ilustração 5), que

aperfeiçoou muito os processos das máquinas de estados, o que tornou o jogo

mais realista 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).

Ilustração 5: Half-LifeFonte: (GAMESPOT, 2009)

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

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

18

Atualmente, os campos de aplicabilidade da IA são muito extensos e

possuem muitos sub-campos (RUSSELL e NORVIG, 2004), mas algumas

áreas despertam maior interesse da comunidade científica e, com isso,

adquirindo um maior espaço para desenvolvimento de novas tecnologias e

aplicações.

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

O sistema ALVINN foi responsável por controlar um carro, mantendo-o

na pista, através de um percurso desconhecido, por 98% do tempo, numa

distancia de 4600 km (RUSSELL e NORVIG, 2004). Ele recebe informações de

câmeras de vídeo, analisa essas informações e gera respostas compatíveis

com a situação, guiando o carro a partir delas e também de um histórico de

outros treinamentos.

A I.A. também vem sendo aplicada na área médica, sendo que

programas de diagnóstico foram responsáveis por executar tarefas no nível de

um médico especialista em várias áreas da medicina (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 (Ilustração 6), 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

19

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, e

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.

Ilustração 6: Black & WhiteFonte: (MOLYNEUX, 2001)

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 (Ilustração 7),

utilizou técnicas de I.A. 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).

20

Ilustração 7: Left 4 DeadFonte: (POSEY, 2008)

A Tabela 1 mostra um resumo da evolução da Inteligência Artificial em

jogos eletrônicos numa linha do tempo.

Tipo de I.A. Jogo que a utiliza Ano do jogo

Sem IA

Tênis para Dois – Primeiro jogo eletrônico a ser desenvolvido

1958

Spacewar – Desenvolvido como demonstração de capacidade de hardware

1961

Padrões de Movimento

Pursuit e Qwak – Atirar em alvos móveis 1974

Gun Fight 1975Space Invaders – Clássico dos primeiros consoles

1978

Finite State Machines

(FSM)

Pac-Man – Primeiro jogo a utilizar FSM 1980

Sim City – Primeiro simulador de cidades 1989

Herzog Zwei – Primeiro jogo de Tiro em Primeira Pessoa – Utiliza algoritmo de Path-finding

1990

Doom – Máquinas de Estados mais Complexas

1993

Battlecruiser 3000AD – Utiliza Redes Neurais

1996

Half-Life – Jogo do ano – Melhor Game 1998

21

Várias Técnicas AI do ano – Aperfeiçoou consideravelmente as técnicas de máquinas de estadoTotal War – Controle de centenas de unidades ao mesmo tempo em tempo real

2000

The Sims – Simulação de personalidade realizada por IA

2000

Black and White – Utilização de várias técnicas de IA para controle realista de comportamento e aprendizado de personagens

2001

F.E.A.R. – IA responsável por controle de comandos para ações em esquadrão

2005

Left 4 Dead – IA utilizada para gerar desafios em tempo real baseados no desempenho do jogador

2008

Tabela 1: Linha do tempo da Inteligência Artificial em Jogos

2.3 Conclusão

Este capítulo abordou, de forma simplificada, a evolução da Inteligência

Artificial com o passar do tempo, além da evolução de sua utilização em jogos

eletrônicos. O próximo capítulo tratará especificamente dos Algoritmos

Genéticos, fazendo um breve histórico e, em seguida, descrevendo seu

funcionamento.

22

3 ALGORITMOS GENÉTICOS

Neste capítulo é abordado um breve histórico dos Algoritmos Genéticos,

assim como uma descrição de seus principais conceitos.

3.1 Histórico

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

inicio, 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 três áreas diferentes de

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

Genéticos (GROSKO et al., 2009). Todas estas áreas possuem uma 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, que o processo de

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

23

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, como 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 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

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, como problemas matemáticos

24

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 apoiando 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 os 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).

Tendo estas características em vista, seu objetivo era emular estes

processos da melhor maneira possível, fazendo com que este fosse realizado

através de computadores de forma consistente, o que facilitaria

consideravelmente a solução de problemas, e sua aplicação a qualquer tipo de

problema, independentemente de sua complexidade (HOLLAND, 2009).

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

Algoritmos Genéticos passaram também a serem 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).

25

3.2 Conceitos

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

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 8, 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 8: 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, conseqüentemente, 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, 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

baseado 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 a qual o

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

26

indivíduos da população 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 9:

Ilustração 9: 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 que 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,

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

Ilustração 10. A freqüê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 10: Processo de mutação

27

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

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, onde 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.”

função ALGORITMO-GENÉTICO(população, FN-FITNESS) retorna um indivíduoentradas: população, um conjunto de indivíduos

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

nova_população ← conjunto vaziopara i ← 1 até TAMANHO(população) faça

x ← SELEÇÃO-ALEATORIA(população, FN_FITNESS) y ← SELEÇÃO-ALEATORIA(população, FN_FITNESS) filho ← REPRODUZ(x,y) se (pequena probabilidade aleatória) então filho ← MUTAÇÃO(filho) adiciona filho a nova_geração

população ← nova_população até algum indivíduo estar adaptado o suficiente ou até ter decorrido tempo suficienteretornar 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 paisn ← 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éticoFonte: (RUSSEL e NORVIG, 2004)

28

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 seqüê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.

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.

Com os conceitos sobre o funcionamento dos Algoritmos Genéticos

abordados neste capítulo, serão feitos em seguida dois estudos de caso,

descrevendo a utilização dos Algoritmos Genéticos em navegação autônoma

de personagens e controle de comportamento dos mesmos.

29

4 TRABALHOS RELACIONADOS

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. Existem algumas aplicações dos Algoritmos

Genéticos em jogos, das quais navegação autônoma e controle de

comportamento de personagens são os temas destes trabalhos. São

demonstrados o funcionamento do processo de navegação autônoma de

personagens, tendo um algoritmo genético como responsável pelo controle dos

mesmos, e uma comparação com um método de navegação padrão, no caso,

a busca em árvore de decisão, que será descrito a seguir. Em seguida é feita

a descrição do uso de Algoritmos Genéticos atuando no controle de

personagens em batalhas.

O primeiro jogo foi realizado por Appolinario e Pereira (2007) para

exemplificar o uso de Algoritmos Genéticos em jogos e, ao mesmo tempo,

compará-lo a um método de busca mais comum, no caso, a busca em árvore

de decisão.

O segundo jogo foi um jogo de ação desenvolvido por Silva et al. (2008)

cujo objetivo era apresentar os Algoritmos Genéticos como possibilidade para

controle de comportamento em personagens de jogos como uma nova opção

no desenvolvimento de jogos.

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.

30

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

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. A Ilustração 11 mostra a representação gráfica de

uma árvore. 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 para melhoria do processo que foi utilizada 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.

Ilustração 11: Representação de uma árvore de decisãoFonte: (COMPUTAÇÂO, 2009)

4.1.2 Descrição do problema

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

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

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

31

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

aleatória (APPOLINARIO e PEREIRA, 2007).

Ilustração 12: Visual gráfico do mapaFonte: (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 mostra a Ilustração 13. 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

32

partida e o valor 9 para o ponto de chegada (APPOLINARIO e PEREIRA,

2007).

Ilustração 13: Matriz do mapaFonte: (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

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 atravéssou uma posição

ocupada por uma 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, tambem é

levado 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

33

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 a

taxa 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 base para a quantidade de obstáculos variou 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 ambos as técnicas

(APPOLINARIO e PEREIRA, 2007).

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

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

blocos e obstáculos no mapa, como mostra a Tabela 2:

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 292Tabela 2: Tabela de dados comparativa

Fonte: (APPOLINARIO e PEREIRA, 2007)

34

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 a 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 14.

Ilustração 14: Gráficos comparativos de desempenhoFonte: (APPOLINARIO e PEREIRA, 2007)

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, mostrou-se necessária a mudança desse valor para

flexibilizar os resultados, definindo que um cromossomo precisaria conter entre

30% e 35% da quantidade total de movimentos possíveis de serem realizados

no mapa, como mostra a Ilustração 14. Outra mudança importante realizada

por Appolinario & Pereira (2007) foi a de fixar a quantidade de cromossomos

35

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 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 cromossomo10 x 10 7030 x 30 54050 x 50 1500

Tabela 3: Relação Tamanho do Mapa x Tamanho do CromossomoFonte: (APPOLINARIO E PEREIRA, 2007)

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

em certos momentos, apresentava 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

15.

Ilustração 15: Solução encontrada com movimento desnecessárioFonte: (APPOLINARIO e PEREIRA, 2007)

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

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

36

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 (Ilustração 16), 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 et al., 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 et al., 2008).

37

Ilustração 16: Tela do jogo O Ultimo SobreviventeFonte: (SILVA et al., 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

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,

onde 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 4.

Vida Amigos Cromossomo (Saída)0 0 20 1 10 2 20 3 21 0 01 1 01 2 11 3 02 0 22 1 12 2 22 3 1

Tabela 4: Relação Dados x ComportamentosFonte: (SILVA et al., 2008)

38

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 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:

População Cromossomo AptidãoIndivíduo 1 0 2 1 0 0 2 0 1 0 0 0 1 20Indivíduo 2 0 1 0 2 0 2 2 1 0 1 0 1 12Indivíduo 3 0 0 0 0 0 0 0 0 0 0 0 0 5Indivíduo 4 1 1 2 1 1 0 1 1 1 1 1 1 11

Tabela 5: 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, pois há um grande número de

possibilidades e uma população pequena (SILVA et al., 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

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

39

Ilustração 17: Crossover MultipontoFonte: (SILVA et al., 2008)

4.2.3 Resultados

O comportamento dos NPCs evoluiu de acordo que novas partidas

foram sendo realizadas, e também de acordo que 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 de acordo 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 seqüência. A

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

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

40

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 19 mostra o equilíbrio que se deu

durante o experimento.

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

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

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

dois, neste caso.

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, como

mostra a Ilustração 20.

41

Ilustração 20: Ataque em grupoFonte: (SILVA et al., 2008)

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.

4.3 Conclusão

Este capítulo abordou dois trabalhos relacionados ao uso de algoritmos

genéticos em jogos, o primeiro, sobre navegação autônoma e o segundo, sobre

controle de comportamento em personagens.

No próximo capítulo será feito um estudo de caso, propondo uma

aplicação de algoritmos genéticos em um jogo que não o utiliza.

42

5 ESTUDO DE CASO

Neste capítulo é proposta a utilização de um algoritmo genético a um

jogo que não o utiliza originalmente, para melhorar o desempenho dos NPCs

do jogo. São definidos apenas os parâmetros iniciais necessários para o

funcionamento do algoritmo.

5.1 Aplicação proposta

O jogo utilizado como base para esta proposta 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, sendo esta destruição considerada apenas pelo toque

do fantasma no personagem e vice-versa, caso o jogador possua 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.

Ilustração 21: Pac-Man

43

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 fantasmaSem Power-up 0Com 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 6.

População Composição do cromossomoIndiví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 1Indivíduo 4 0 1 0 1 1 0 1 0

Tabela 7: 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.

5.2 Conclusão

Após ter sido analisado cuidadosamente o jogo Pac-Man, este estudo

teve a intenção de propor a utilização do Algoritmo Genético, definido e

44

demonstrado anteriormente, neste jogo. São propostos valores dos parâmetros

necessários para o funcionamento do algoritmo.

Espera-se que, com a utilização dos Algoritmos Genéticos, onde os

resultados obtidos não são totalmente controláveis, possa-se obter um grau de

dificuldade maior em relação ao comportamento dos NPCs, assim como uma

adaptação maior às estratégias utilizadas pelo jogador, aumentando o realismo

do jogo, tentando obter resultados satisfatórios, como no trabalho de

Appolinario e Pereira (2007) relatado no item 4.2.

Também espera-se que este estudo de caso possa ser utilizado

posteriormente em outros trabalhos, e possivelmente ser desenvolvido, para

que seja melhor adaptado de forma que possa ter sua aplicabilidade testada e

comprovada.

45

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, onde 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.

Alicerçando um estudo de caso no sucesso obtido pelo uso dos

Algoritmos Genéticos para controle de comportamento de personagens em

jogos, conforme descrito anteriormente, foi proposta uma aplicação do

algoritmo em um contexto onde 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.

46

6 REFERENCIAS BILBIOGRÁ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.

47

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.

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

48

http://200.169.53.89/scgames/artigos/08980100008.pdf. Acesso em 20 de Novembro de 2009.