FUNDAO UNIVERSIDADE FEDERAL DE RONDNIANUCLEO DE CINCIA E TECNOLOGIADEPARTAMENTO DE INFORMATICAALISSON DINI GOMESA INTELIGNCIA ARTIFICIAL EM JOGOS ELETRNICOS DE ESTRATEGIA EM TEMPO REAL: UM ESTUDO DA IMPLEMENTAO DE AGENTES COGNITIVOS COM A CAPACIDADE DE APRENDIZAGEMPORTO VELHO2010FUNDAO UNIVERSIDADE FEDERAL DE RONDNIANUCLEO DE CINCIA E TECNOLOGIADEPARTAMENTO DE INFORMATICAA INTELIGNCIA ARTIFICIAL EM JOGOS ELETRNICOS DE ESTRATEGIA EM TEMPO REAL: UM ESTUDO DA IMPLEMENTAO DE AGENTES COGNITIVOS COM A CAPACIDADE DE APRENDIZAGEMALISSON DINI GOMESOrientadora: Darlene Figueiredo Borges Coelho, D. Sc.MonograIiasubmetidaaFundaoUniversidade Federal de Rondnia como requisito parcial a obtenodotitulodeLicenciatura/Bacharel em InIormatica.PORTO VELHO2010FICHA CATALOGRFICABIBLIOTECA PROF. ROBERTO DUARTE PIRESBibliotecria Responsvel: Ozelina Saldanha CRB11/947 Gomes, lisson Dini G6331iA inteligncia artificial em jogos eletrnicos de estratgia em tempo real: um estudo da implementao de agentes cognitivos com a capacidade de aprendizagem / lisson Dini Gomes. Porto Velho, Rondnia, 2010. 178f.: il.Trabalho de Concluso de Curso (Graduao em nformtica) Fundao Universidade Federal de Rondnia / UNR. Orientadora: Prof. Dr. Darlene Figueiredo Borges Coelho. 1. nteligncia artificial 2. Estratgia em tempo real 3. Aprendizagem 4. Agentes cognitivos e evolutivos . Coelho, Darlene Figueiredo Borges . Ttulo. CDU: 004.8iiiLISSON DINI GOMESA INTELIGNCIA ARTIFICIAL EM JOGOS ELETRNICOS DE ESTRATEGIA EM TEMPO REAL: UM ESTUDO DA IMPLEMENTAO DE AGENTES COGNITIVOS COM A CAPACIDADE DE APRENDIZAGEMMONOGRAFIA SUBMETIDA AO CORPO DOCENTE DO CURSO DE BACHARELADO E LICENCIATURA EM INFORMATICADAFUNDAO UNIVERSIDADE FEDERAL DE RONDNIA COMO PARTE DOS REQUISITOS NECESSARIOS PARA OBTENO DO GRAU DE LICENCIATURA/BACHARELADO EM INFORMATICAAprovada porProI. Darlene Figueiredo Borges Coelho, D. Sc. (orientadora)ProI. Liliane da Silva Jacon, M. Sc.ProI. Silvia Rissino, D. Sc.PORTO VELHO2010ivDedicatriaA concluso deste trabalho representa um marco no processo de superao pelo qual tenho passado nos ultimos dois anos, superao essa que tem se dadodesdeoaspectoacadmico-proIissionalde minhavidaatoaspectoemocional, sendoque neste em especiIico tenho ha um ano empenhado uma das mais duras lutas de minha vida, da qual estou saindo vitorioso. Assim, dedico este trabalho a todos aqueles que acreditaramem minhaIoraquandoelaIoi postaaprovaea todos aqueles que souberamreconhecer meus mritos quando movi as montanhas que me propus a mover.vAgradecimentosPrimeiramente, agradeoaoGrande Pai, comoqualmereconcilieirecentemente, embora me mantenha avesso as religies e igrejas, por considerar estas enquanto vendas para aConscinciaPopular, issoquandonoseconIiguramcomoocorreemalgunscasos enquanto Iormas de extorquir o suado dinheiro do povo trabalhador.Agradeo a minha Iamilia, por todo o apoio prestado nos momentos necessarios. Em especial ao meu irmo Mauro, por sempre ter se mantido ao meu lado, me ajudando sempre que precisei. Meu irmo, sem sua constante ajuda e disposio, eu diIicilmente teria trilhado metade do caminho que trilhei at hoje. Obrigado.A orientadora deste trabalho, proI. Darlene, por sempre ter se mostrado disposta a me prover as luzes que guiaram este trabalho, se comportando com pleno compromisso com sua misso de proIessora.Aos amigos e companheiros de luta Filipe, Ricardo, Mara, Vinicius, Daniel, Marcio, Marilsa, Valdeci, Valderi, Uilian, Renan, Keitty e Jota, pela compreenso que tm tido com a situao que encaro atualmente. Em especial a Filipepelos 6 anos de amizade e por ter sido parte importante no processo que Iormou o que sou hojea Marilsa e Marciopor sempre terem acreditado em meus esIoros e pelas constantes palavras de apoio a Marapor estar ao meu lado, apesar da distncia que nos separa, nos momentos mais diIiceis que passei nestes ultimos tempos, a Danielcompanheiro de luta, companheiro de estrada e companheiro de heavy metal, pela grande pessoa que tem se mostrado a Ricardoque apesar das inumeras discusses que tivemos nestes ultimos trs anos, um grande amigo, que estimo muito e a Viniciusque apesar da relativa distncia que temos um do outro, uma pessoa que admiro e respeito muito, e que acreditou em meus esIoros nos momentos de diIiculdade.Aos colegas de trabalhoIvan, WalIrido, Jorge, Emerson, Lourdes e Alexandrepela compreenso que tm tido com a minha condio de estudante.Aos amigos Giovanni, Paula e Ariane, pelos momentos alegres que passamos juntos nestes ultimos 3 anos. A Giovanni em especial, geograIo, amigo de haracore e Iuturo colega de trabalho, pelas diversas vezes em que se prestou a dispor uma parte do seu tempo para me aconselhar em relao a este trabalho nas questes relacionadas a sua Iormatao, alm de me prover umacopiadesuatesedemestradoparameservir dereIerncia. A Arianepela disposio em me prover uma copia de sua monograIia para tambm me servir de orientao vina elaborao deste trabalhoAgradeo, por Iim, a todos aqueles que, direta ou indiretamente, contribuiram para a realizao deste trabalho.vii'Eaivino quemobtemuma vitoria alteranao suas taticas em conformiaaae com a situao ao inimigo` (Sun T:u, A Arte aa Guerra)viiiResumoEste trabalho tem como objetivo demonstrar a possibilidade de se construir agentes inteligentes com a capacidade de adquirir esquemas de aprendizagem eIetiva em relao aos seusoponentes, sendoinspiradopor experinciasdoautor comojogobrasileiroOutlive, produzidopelaempresaContinuumEntertainment, ondepuderamser observadasatitudes adaptativas por partes dos seus agentes cognitivos. No entanto, estas atitudes se mantinham apenas no mbito de uma unica partida, no se estendendo para as partidas posteriores aquela. A partir disso, Ioi levantada a hipotese da possibilidade de construo dos agentes inteligentes inicialmente propostos, sendo que nesta Iase da realizao deste trabalho os mesmos Ioram denominados agentes cognitivos evolutivos. Com vistas a cumprir com o objetivo proposto, Ioirealizada pesquisa bibliograIica a respeito do gnero de estratgia emtempo real, buscando-se caracteriza-los e compara-los a gneros proximos; pesquisa bibliograIica a respeito dos agentes inteligentes e da implementao das Iunes cognitivas de planejamento eaprendizagem, buscando-seassociar estasIunesaocontextodosjogoseletrnicosde estratgia emtempo real; experimentos como jogoOutlivecomvistas a observar o comportamento de seus agentes cognitivos de Iorma mais sistematica; e, por Iim, pesquisa bibliograIica com vistas a veriIicar a existncia da possibilidade de construo dos agentes cognitivos evolutivos. Ao Iim da pesquisa, pde-se observar que, de Iato, esta possibilidade existe, sendoquejaexistemtcnicasemdiscussocomvistasaimplementarosreIeridos agentes. Almdisso, pde-se observar que o aproIundamento das pesquisas na area conveniente, umavezqueaindanoIoi demonstradoseumadas tcnicas discutidas, o algoritmo gentico, aplicavel ou no ao aprendizadoonlineemjogos eletrnicos de estratgia em tempo real.Palavras-chave:Inteligncia ArtiIicial; estratgia emtempo real; agentes inteligentes; planejamento; aprendizagem; Outlive; agente evolutivos;Dynamic Scripting; algoritmo gentico.ixAbstractThis work has the objective oI demonstrating the possibility oI constructing intelligent agents with the capability oI acquiring eIIective learning schemes to deal with their opponents, being inspiredbyexperiences oI theauthor withtheBraziliangameOutlive, producedbythe soItware enterprise Continuum Entertainment, where could be observed adaptive attitudes in its cognitive agents. However, these attitudes were kept only in the range oI one game, and weren't kept to other games. Then was taken the hypothesis oI the possibility oI constructing the intelligent agents initially proposed, and in this phase oI the realization oI this work they were called the evolutionary cognitive agents. To IulIill the proposed objective, a bibliographic research was realized about the game genre oI the real time strategy, trying to describethemecomparethem toclosegenres;the Iollowingactivitieswerealsorealized: bibliographic researchabout theintelligentagentsandthe implementation oIthecognitive Iunctions oI planning and learning, trying to associate these Iunctions to the context oI the real time strategy games; experiments with the game Outliveto observe the behavior oI its cognitive agents more systematically; and, Iinally, bibliographic research to veriIy the possibility oI construction oI the evolutionary cognitive agents. At the end oI the research, could be observed that this possibility exists, and already exist techniques in discussion about their implementation. Furthermore, could be observed that continuing this research is interesting, because wasn't still demonstrated iI one oI the discussed techniques, the genetics algorithm, is applicable or not to the online learning in real time strategy games.Keywords:ArtiIicial Intelligence; real timestrategy;intelligentagents;planning;learning; Outlive; evolutionary agents; Dynamic Scripting; genetics algorithm.xLISTA DE ILUSTRAESIlustrao 1: Imagens de Her:og Zwei. Fonte: GERYK, s.d...................................................5Ilustrao 2: Imagens de Dune II. Fonte: GERYK, s.d...........................................................6Ilustrao 3: Imagens de Warcraft. Fonte: GERYK, s.d.........................................................7Ilustrao 4: Imagem de Total Annihilation. Fonte: GERYK, s.d...........................................9Ilustrao 5: Imagens de Starcraft. Fonte: GERYK, s.d.......................................................10Ilustrao 6: Imagens de War:one 2100. Fonte: GERYK, s.d...............................................10Ilustrao 7: Imagens do jogo Homeworla. Fonte: GERYK, s.d..........................................12Ilustrao 8: Imagens de Age of Empires II. Fonte: GERYK, s.d.........................................12Ilustrao 9: Esquema de representao da diviso dos agentes inteligentes emtipos especiIicos........................................................................................................30Ilustrao 10: Representao esquematica de umagente reativo simples. Adaptado de (RUSSEL & NORVIG, 2004: p. 47)................................................................31Ilustrao 11: Diagrama esquematico de umagente baseado emmodelos. Adaptado de (RUSSEL & NORVIG, 2004: p. 49)................................................................32Ilustrao 12: Diagrama esquematica de umagente baseadoemobjetivos. Adaptadode (RUSSEL & NORVIG, 2004: p. 50)................................................................33Ilustrao 13: Diagrama esquematico de umagente baseado na utilidade. Adaptado de (RUSSEL & NORVIG, 2004: p. 51)................................................................34Ilustrao 14: Esquema geral de um planejamento de ordem parcial que envolve a necessidade de destruio de multiplos inimigos por parte de um agente.......46Ilustrao 15: Logotipo da Continuum Entertainment. Imagem extraida do jogo Outlive.....51Ilustrao 16: Unidade robotica a esquerda e ser modiIicado geneticamente a direita. Imagem extraida do jogo Outlive...................................................................................53Ilustrao 17: A esquerda, Maxwell. A direita, Kaminski. Imagem extraida do jogo Outlive..............................................................................................................53Ilustrao 18: A esquerda, Morales. A direita, Mackenzie. Imagem extraida do jogo Outlive..............................................................................................................54Ilustrao 19: Carl Eberhardt. Imagem extraida do jogo Outlive...........................................55Ilustrao 20: Acima, o aspecto de uma jazida de urnio. Abaixo, o aspecto de uma jazida de Ierro. Imagem extraida do jogo Outlive........................................................56Ilustrao 21: Exposiodaestratgiautilizadapeloagente.Aaglomeraodestacadano retngulo 1 consiste na aglomerao de cerca de 50unidades areas do jogador, enquantoqueaaglomeraodestacadanoretngulo2indicauma aglomeraode9incineradores e9tempestades. Pode-seobservar queo caminho esta completamente bloqueado. Desta Iorma, o agente utiliza a rota indicada pela trajetoria vermelha a esquerda da imagem em :oom..................67xiLISTA DE QUADROSQuadro 1:Trapaas possiveis no jogo Outlive.......................................................................61Quadro 2:Distribuio dos agentes entre as raas no experimento VI..................................69Quadro 3:Relao dos indices de Ireqncia de vitorias de cada tcnica implementada nos experimentos realizados. Adaptado de (CROCOMO, 2008: p. 79)......................83Quadro 4:VeriIicaoda superioridade doDynamic Scriptingemrelaoaoalgoritmo gentico. Extraido de (CROCOMO, 2008: p. 81).................................................85Quadro 5:VeriIicao da superioridade doalgoritmo gentico emrelaoaoDynamic Scripting. Adaptado de (CROCOMO, 2008: p. 81)..............................................86xiiLISTA DE EQUAESEquao 1:Comparao do numero de vitorias obtidas por um determinado algoritmo com o numero total de partidas disputadas por este contra algum outro algoritmo. Adaptada de CROCOMO (2008: p 76).............................................................82Equao 2:Comparaodonumerodevitorias obtidas peloalgoritmogenticocomo numerototal departidasdisputadascontraporestecontraalgumoponente. Extraida de CROCOMO (p. 76)........................................................................82Equao 3: Erro amostral para a Ireqncia de vitorias de uma tcnica de implementao de um agente cognitivo evolutivo em relao a outra.......................................83Equao 4: Varinciaamostralutilizadaparaocalculodoerroamostralapresentadona equao 3...........................................................................................................84Equao 5:Validao da superioridade de uma tcnica de implementao de agentes cognitivos evolutivos em relao a outra..........................................................84Equao 6:Relao alfa........................................................................................................90Equao 7:Funode aptido geral de umagente evolutivo quando este perde uma partida................................................................................................................91Equao 8:Funodeaptidogeral deumagenteevolutivoquandoestevenceuma partida................................................................................................................91Equao 9:Funo de aptido por estado de um agente evolutivo no estado 1...................91Equao 10:Relao alfa para o estado i...............................................................................92Equao 11:Funodeaptidoporestado de umagenteevolutivonoestadoi, dadoque i ~ 1}................................................................................................................92Equao 12:DeIinio do valor de h......................................................................................92Equao 13:Relao alfa para o estado h..............................................................................93Equao 14:Funo de pontuao do agente.........................................................................93Equao 15:Relao beta geral..............................................................................................94Equao 16:Relao beta para o estado i..............................................................................94Equao 17:Relao gama geral............................................................................................95Equao 18:Relao gama para o estado i............................................................................95Equao 19:Funo de atualizao do peso de uma regra para um agente evolutivo quando este no alcana o ponto de equilibrio...............................................................96Equao 20:Funo de atualizao do peso de uma regra para um agente evolutivo quando este alcana ou sobrepuja o ponto de equilibrio................................................97Equao 21:Relao aelta....................................................................................................101Equao 22:Funo de aptido de um agente evolutivo quando este perde uma partida....102Equao 23:Funo de aptido de um agente evolutivo quando este vence uma partida...103xiiiLISTA DE SIGLAS E ABREVIATURAS3D3 dimensesAPIApplication Programming InterfaceATPAbsolute Turning PointCRPGComputer Role Playing GameEBLExplanation-basea learningIAInteligncia ArtiIicialICBMInter Continental Ballistic MissileRPGRole Playing GameRTPRanaomi:ation Turning PointRTSReal Time StrategyxivLISTA DE SIMBOLOSA(0)Nivel de ao 0 no planejamento em graIoA(i)Nivel de ao i no planejamento em graIoS(0)Nivel de estado 0 no planejamento em graIoS(1)Nivel de estado 1 no planejamento em graIoS(i)Nivel de estado i no planejamento em graIoxvSUMRIOIntroduo..................................................................................................................................1Captulo 1.OS 1OGOS ELETRNICOS DE ESTRATGIA EM TEMPO REAL.........41.1. Introduo...............................................................................................................41.2. A histria dos jogos eletrnicos de estratgia em tempo real.............................41.3. Conceitos bsicos dos jogos eletrnicos de estratgia em tempo real..............141.4. Asdiferenasentreosjogos de estratgiaemtemporealejogosde estilos semelhantes...........................................................................................................191.4.1. Estratgia em tempo real x estratgia baseada em turnos......................201.4.2. Estratgia em tempo real x ttica em tempo real.....................................221.5. Consideraes finais.............................................................................................23Captulo 2.OS AGENTES INTELIGENTES NOS 1OGOS ELETRNICOS DE ESTRATGIA EM TEMPO ERAL..........................................................................252.1. Introduo - A Inteligncia Artificial.................................................................252.2. Os agentes inteligentes.........................................................................................272.2.1. Os agentes reativos simples........................................................................312.2.2. Os agentes baseados em modelos...............................................................312.2.3. Os agentes baseados em objetivos..............................................................322.2.4. Os agentes baseados na utilidade...............................................................332.3. Funes cognitivas nos agentes...........................................................................342.3.1. O planejamento nos agentes.......................................................................352.3.1.1. Caracterizao geral.........................................................................352.3.1.2. Aaplicaodoplanejamentoaosjogoseletrnicosdeestratgia em tempo real....................................................................................442.3.2. A aprendizagem nos agentes......................................................................472.3.2.1. Caracterizao geral.........................................................................472.3.2.2. Aaplicaodaaprendizagemnos jogos eletrnicos de estratgia em tempo real.....................................................................................492.4. Consideraes Finais............................................................................................50Captulo 3.OS AGENTES COGNITIVOS NO 1OGO OU1LIJE....................................513.1. Introduo.............................................................................................................513.2. Outlive....................................................................................................................513.3. Os agentes cognitivos no jogo Outlive.................................................................623.3.1. Introduo....................................................................................................623.3.2. Os experimentos..........................................................................................633.3.2.1. Caracterizao geral.........................................................................63xvi3.3.2.2. Caracterizao dos experimentos....................................................663.3.2.2.1. Experimento I..........................................................................663.3.2.2.2. Experimento II........................................................................673.3.2.2.3. Experimento III.......................................................................683.3.2.2.4. Experimento IV........................................................................703.3.2.2.5. Experimento V.........................................................................713.3.2.2.6. Experimento VI.......................................................................723.3.2.3. Consideraes finais a respeito dos experimentos..........................743.4. Consideraes finais.............................................................................................75Captulo 4.OS AGENTES COGNITIVOS EVOLUTIVOS..............................................764.1. Introduo.............................................................................................................764.2. Os agentes cognitivos evolutivos.........................................................................764.2.1. Introduo....................................................................................................764.2.2. A literatura a respeito dos agentes cognitivos evolutivos........................764.2.2.1. O Dynamic Scripting..........................................................................794.2.2.2. O algoritmo gentico.........................................................................794.2.3. O trabalho de CROCOMO........................................................................814.2.4. O trabalho de PONSEN..............................................................................894.2.5. Consideraes gerais acerca dos trabalhos consultados........................1104.3. Consideraes finais...........................................................................................112Consideraes finais e recomendaes para trabalhos futuros.........................................113REFERNCIAS BIBLIOGRFICAS................................................................................115APNDICE A-ESQUEMADEPLANE1AMENTOEMGRAFOPARA AGENTES INTELIGENTES EM 1OGOS DE ESTRATGIA EM TEMPO REAL........................118APNDICE B -ESTRUTURASDO 1OGOOU1LIJEE RESPECTIVAS IMAGENS..............................................................................................................................120APNDICE C - UNIDADES DO 1OGO OU1LIJE.........................................................125APNDICE D - UNIDADES DO 1OGO OU1LIJE E RESPECTIVAS IMAGENS.....136APNDICEE-TABULAODASINFORMAESOBTIDASNOS EXPERIMENTOS................................................................................................................139APNDICEF-COMBINAESPOSSIVEISDE AGENTESPARAOCASODE UTILIZAO DE 7 AGENTES NUMA MESMA PARTIDA.........................................1631IntroduoA Inteligncia ArtiIicial uma area do conhecimento relativamente recente, possuindo uma historia de aproximadamente 60 anos de desenvolvimento. Busca reproduzir, em maquinas, os processos de raciocinio humano, sendo que, dado o alto grau de complexidade do mesmo,acaba sendo sub-dividida emuma sriede campos, quecompreendemdesde o planejamento e aprendizagem at o processamento de linguagem natural.Em termos de aplicabilidade, utilizada, dentre outras atividades, para 'demonstrao de teoremas matematicas, criao de poesias e diagnostico de doenas (RUSSEL& NORVIG, 2004: p. 1). Uma outra area de aplicabilidade da disciplina so os jogos eletrnicos. Este trabalho se Iocara neste mbito.Nos jogos eletrnicos, at recentemente, havia, por parte das empresas deste ramo, a preocupao com a criao de poderosos sons e graIicos, com vistas a tornar os jogos o mais realistas possivel (BITTENCOURT & OSORIO apua CROCOMO, 2008: p. 12). No entanto, as ultimas tendncias nestes jogos tem demonstrado o grau de importncia que se pode auIerir a produo de oponentes que representem um real desaIio ao jogador, o que pode Iazer com que o mesmo aproveite melhor os jogos que adquire.Nos jogos eletrnicos de estratgia em tempo real em especiIicoque sero o Ioco deste trabalhouma IA bem projetada um quesito de suma importncia, uma vez que, caso no seja implementada uma IA no minimo razoavel, a experincia de jogo perde o sentido. Desta Iorma, neste gnero de jogo, no basta que o jogo possua bons graIicos e sons se a IA utilizada no prover um grau de desaIio interessante ao jogador.Este trabalho se Iocara na questo da Inteligncia ArtiIicial aplicada aos jogos eletrnicos de estratgia em tempo real. Sua inspirao veio da experincia do autor com o jogo Outlive, produzido pela empresa brasileiraContinuum Entertainment, sendo que nesta experincia o mesmo pde detectar umcerto grau de aprendizagememseus agentes cognitivos, que, entretanto se mantinha apenas no mbito de uma partida. Em suma, no se 2pode dizer que neste jogo exista um esquema de aprendizagem eIetivo, uma vez que o que apreendido pelo agente no decorrer de uma partida perdido a partir do momento em que esta encerrada.A partir disso, Iormulou-se a seguinte questo: E possivel a criao de um modelo de agente cognitivo que possua um esquema de aprendizagem eIetivo em sua estrutura?Partiu-se da hipotese de que tal Ieito era possivel, sendo que a este agente cognitivo Ioi, inicialmente, atribuidaadenominaodeagentecognitivoevolutivo. Apartir disso, realizou-se a pesquisa que deu origem a este trabalho, sendo que tal pesquisa cumpriu com as seguintes etapas:1. Pesquisa bibliograIica a respeito dos jogos eletrnicos de estratgia em tempo real;2. PesquisabibliograIicaarespeitodosagentesinteligentes, buscando, emespeciIico, compreenderdequeIormaelespodemser implementadosemjogoseletrnicosde estratgiaemtemporeal. Almdisso,Ioirealizadapesquisa arespeitodasIunes cognitivas do planejamento e da aprendizagem, Iunes essas que, dentro do que pde ser observado, so as mais aplicadas a esta categoria de jogos;3. Realizao de um conjunto de experimentos no jogo Outlive para avaliar a capacidade de adaptao dos agentes cognitivos aplicados ao mesmo;4. Pesquisa bibliograIica emtrabalhos anteriores que tratamdos agente cognitivos levantados para este trabalho.A partir desta pesquisa, surgiu este trabalho, que conta com a seguinte estrutura: O capitulo I trata dos jogos eletrnicos de estratgia em tempo real. Neste capitulo, realizado um relato da historia desta categoria de jogos, alm de serem expostos os conceitosbasicosaplicadosamesmaerealizadaumacomparaodognerocom alguns gneros proximos; O capitulo II trata dos agentes inteligentes, sendo que no mesmo so Ieitas algumas consideraes gerais arespeitodaIntelignciaArtiIicial paraentoproceder-sea 3analise dos agentes inteligentes, para posteriormente realizar-se uma analise das Iunes cognitivas aplicaveis aos agentes cognitivos dos jogos de estratgia em tempo real, mais especiIicamenteas Iunes deplanejamentoeaprendizagem, buscando associar a utilizao destas Iunes na categoria de jogos que objeto deste trabalho; O capituloIIItrata da aplicao dosagentescognitivosao jogo Outlive,sendoque aqui realizada uma analise do reIerido jogo, sendo expostos a sua historia e alguns conceitosutilizadosnoseuambientedejogo, almdeserIeitaacaracterizaoe discusso a respeito dos experimentos realizados no reIerido jogo; O capitulo IV discute os agentes cognitivos evolutivos, realizando, inicialmente, uma caracterizao geral dos mesmos para apos isso discutir os dois trabalhos que serviram de base para a analise realizada no reIerido capitulo.4CAPITULO 1 - OS 1OGOS ELETRNICOS DE ESTRATGIA EM TEMPO REAL1.1. IntroduoOs jogos eletrnicos de estratgia em tempo real possuem uma historia de aproximadamente 20 anos de desenvolvimento, periodo no qual diversas inovaes tm sido produzidas para o gnero, sendo que, mesmo na atualidade, estas inovaes continuam a ser agregadas ao mesmo.OprimeirocapitulodestetrabalhotemaIunobasicadeapresentarosconceitos basicos reIerentes aos jogos eletrnicos de estratgia emtempo real e apresentar uma retrospectiva historica de seu desenvolvimento.A abordagem tera como ponto de partida a apresentao de uma retrospectiva historica acerca do gnero, produzida com base no trabalho deGERYK(s.d.) publicadonositewww.gamespot.com; seguiracomaapresentaodos conceitos basicos relativos aomesmo, seguindo-se a issouma comparao comalguns gneros proximos, a seremespeciIicados nomomento da abordagem. Apos isso, sero realizadas as consideraes Iinais do capitulo.1.2. A Histria dos 1ogos Eletrnicos de Estratgia em Tempo RealOs jogos de estratgia em tempo real possuem uma historia de aproximadamente 20 anos de desenvolvimento, sendo que a cada dia novos recursos so acrescentados aos jogos, dado o constante desenvolvimento do poder de processamento dos computadores ao longo do tempo.Os primordios dos jogos de estratgia em tempo real remontam ao ano de 1982. Os jogoslanadosnestapocacomcaracteristicasdosjogosconsideradosnestetrabalhono podemser considerados como tais. Noentanto, carregamseus mritos por seremseus precursores.No inicio desta historia, desenvolveram-se duas linhas de desenvolvimento paralelas, sendo uma localizada no Reino Unido e outra nos Estados Unidos. Apenas mais tarde veio surgir uma cultura de desenvolvimento mais uniIicada globalmente.No Reino Unido, o gnero inicia-se com o jogo Stronkers, de John Gibson, lanado em 1983 pela empresa Imagine Software. Ja nos Estados Unidos, a caminhada inicia-se com o 5lanamento do jogo The Ancient Art of War, lanado em 1984 por Dave e Barry Murry, da empresa Evryware (WIKIPEDIA, 2009).Mais a Irente, em 1989, lanado o jogo Her:og Zwei, pela Sega Entrerprises Lta., parao Sega Genesis.Ojogo, desenvolvidoparaser jogadopordoisjogadores,temcomo aspecto basico o Iato de a cada jogador ser designada uma base principal e um conjunto de bases menores. Almdestas, ojogodisponibilizava umconjuntodebases neutras, que poderiam ser tomadas pelos jogadores com Iins de Iortalecimento destes. O objetivo Iinal de cadaagentecontrolador destruir abasedoagentecontrolador inimigo. Acadaagente controlador era dado o comando de um veiculo que pode se locomover tanto em terra quanto em ar, dependendo da convenincia do agente controlador. Ou seja, a qualquer momento do jogo o agente controlador pode converter seu veiculo de terrestre para areo ou vice-versa. O agente controlador possui controle apenas sobre esta unidade.Este jogo ainda no pode ser considerado como um jogo de estratgia em tempo real, uma vez que ao agente controlador dado apenas a possibilidade de controlar uma unidade, sendo que as bases no eram postas sob seu controle.O primeiro jogo que pode ser considerado eIetivamente como um jogo de estratgia em tempo real o jogo Dune II, desenvolvido pela Westwooa Stuaios. Este jogo prov um conjunto de 3 naes, que representam 3 casas reais que lutam pelo controle do recurso spice, o unico existente no jogo (GERYK, s.d.).Ilustrao 1. Imagens ae Her:og Zwei. Fonte. GERYK, s.a.6Dune II uma verdadeira evoluo em relao a Her:og Zwei em muitos aspectos que mais a Irente passam a parecer triviais. No entanto, importante observar que estas evolues basicamente estabeleceram as convenes do gnero dos jogos de estratgia em tempo real (GERYK, s.d.). MaisespeciIicamente, asinovaesdojogoseapresentamnosseguintes aspectos:1. No jogo, permitido ao jogador construir bases em qualquer lugar do mapa;2. Ojogoestabelece oconceitodas dependncias para aconstruode estruturas. Ou seja, para que se possa construir determinadas estruturas, deve-se primeiramente construir outras estruturas, que so predecessoras daquelas;3. E introduzida a idia de que as diIerentes naes do jogo possuem diIerentes estruturas eunidades, poisemHer:ogZweiambososjogadorescontrolavambasicamentea mesma unidade.Noentanto, importante destacar alimitaoexistente nojogoquepermitia ao jogador construir no maximo 25 unidades. No entanto, tomando-se em conta a capacidade de processamento das maquinas da poca, plenamente compreensivel isso, no implicando esta caracteristica em uma questo problematica.De Dune II at os dias atuais, uma srie de jogos tem surgido no mercado. No entanto, sero abordados neste trabalho apenas aos jogos que tenham introduzido novos conceitos ao gnero.O primeiro jogo apos Dune IIsurgido 2 anos apos o lanamento deste, depois de um verdadeiro hiato para o emergente gnero da estratgia em tempo realIoiWarcraft. Orcs ana Humans, lanado pela Bli::ara Entertainment. DiIerente do jogo anterior, que se baseava Ilustrao 2. Imagens ae Dune II. Fonte. Fonte. GERYK, s.a.7em temas de Iico cientiIica,Warcraftse baseia num mundo de Iantasia marcado pela luta desenIreadaentrearaadoshumanosearaados ogros. Ojogoestabeleceumasriede inovaes para o gnero, a saber:1. Insero das unidades de combate direto1;2. Existncia de mais de um recurso a ser extraidomadeira e ourodiIerentemente da estrutura mono-recursal2existente em Dune II. E importante destacar que determinadas unidades eestruturas, paraseremconstruidas, requeremaaplicao combinada destes dois recursos.3. Insero do modo multiplayer, o que torna Warcraft o primeiro jogo de estratgia em tempo real para o PC com este modo de jogo.Noentanto, importantedestacar ograndeproblemadeWarcraft: ainteligncia artiIicial muito limitada. Um dos problemas que podem ser encontrados nela se reIerem ao Iato de as unidades atacaremIerozmente qualquer inimigo que vempela Irente, sem qualquer critriomaissistematicoarespeitodoquedeveser atacadoedoquenodeve (GERYK, s.d.).Esta limitao vem a ser superada com o lanamento, em 1995, do jogo Warcraft II.Tiaes of Darkness, onde o jogo permite coisas como rotas de patrulha. A inteligncia artiIicial deste jogo um Iator importante que o torna um jogo mais soIisticado e desaIiante que seu predecessor (GERYK, s.d.).Outras inovaes trazidas pelo jogo so as seguintes:1 Unidades tais como espadachins, cavaleiros, etc.2 Utiliza-se, aqui, este termo para se reIerir a existncia de apenas um recurso no jogo considerado.Ilustrao 3. Imagens ae Warcraft. Fonte. GERYK, s.a.81. A insero da nvoa de guerra3 nos jogos de estratgia em tempo real.2. A insero das unidades navais nos jogos de estratgia em tempo real;3. A insero de um terceiro recurso a ser utilizadoo oleo, sendo que at o momento trabalhava-se nos jogos de estratgia em tempo real com um maximo de 2recursos, caracteristica essa existente em Warcraft.E importante registrar que a srie Warcraft, nestes primeiros momentos, nunca esteve so no mercadodosjogosdeestratgiaemtemporeal.Estapoca IoidominadapelaIorte concorrncia entre esta srie e a srieCommanaanaConquer, daWestwooa, empresa desenvolvedoradojogoDuneII. Noquepeseosucessocomercial dasrieeatradio desenvolvida pela empresa ao lanar o primeiro jogo do gnero,Commana ana Conquer extremamente Iraco nombito da criatividade e por issono lhe sera reputada muita importncia neste trabalho. Enquanto Warcraftsempre traz novos conceitos a cada jogo que lanaatem Warcraft II,CommanaanaConquerselimitaareutilizar-sedeconceitosja utilizadosemoutrosjogos, eemtermosdeinovaestrazapenasalgumasdiIerenciaes entre uma verso e outra, inovaes essas que no podem ser consideradas, concretamente, enquanto contribuies eIetivas ao gnero dos jogos de estratgia em tempo real.NovosrecursossotrazidospelojogoTotal Annihilation, lanadoem1997eque disputa Iortemente o mercado com o jogo Starcraft, lanado em 1998 pela Bli::ara. Neste momento, pode-se observar uma mudana no espectro da concorrncia comercial dos jogos de estratgia em tempo real,uma vez que, se antes encontram-se em disputa pelo mercado as empresasWestwooa, com CommanaanaConquer, eBli::ara, comWarcraft, nestenovo momento o Ioco muda para a disputa entreActivision,com Total Annihilation, eBli::ara, com Starcraft.3A nvoa de guerra um recurso dos jogos de estratgia em tempo real que Iaz com que sejam visiveis ao jogador apenas as areas que este ja tenha explorado durante a partida da qual participa.9No entanto, digno de nota que Total Annihilation, diIerentemente de Commana ana Conquer, no se limita a reutilizao de conceitos utilizados em outros jogos. As principais inovaes dojogo, que trazemcontribuies signiIicativas para ognerodos jogos de estratgia em tempo real, so duas:1. A utilizao de unidades e mapas em 3 dimenses, o que o Iaz um dos primeiros jogos a se utilizarem deste recurso;2. AintroduodoconceitodasIilasdecomandos, quepermitequeojogadorlance varias ordens a uma determinada unidade, sendo que estas ordens sero executadas na seqncia em que Iorem dadas. Este conceito vem a resolver um problema existente nosjogosdeestratgiaemtemporeal deatento, queoIatodeojogadorser obrigadoaconstantementeretornar aunidadesasquaisIoramdadasdeterminadas ordens para dar as novas ordens que devero ser executadas pelas mesmas. O grande rival de Total Annihilation, Starcraft, Ioi lanado um ano depois, em 1998. Como de praxe para a Bli::ara, o jogo trouxe consigo novidades signiIicativas, a saber:1. A historia do jogo, no modo de campanha, esta sempre sendo reIerenciada atravs dos dialogos dos personagens;2. As 3 raas existentes no jogo possuem diIerenas marcantes entre si, diIerenas essas que inIluenciam Iortemente o mtodo de jogo com cada uma.Ilustrao 4. Imagem ae Total Annihilation.Fonte. GERYK, s.a.10Apos Starcraft, lanado no mercado o jogo Close Combat, que traz inovaes como oIatormoraldas unidades, que varia conIorme as condies as quais as mesmas so submetidas. Noentanto, este jogoseencaixa mais nognerodatatica emtemporeal. Portanto, no sero realizadas consideraes adicionais a respeito do mesmo.O proximo jogo a trazer inovaes para o gnero War:one 2100, desenvolvido pela Pumpkin Stuaiose lanada pela Eiaos Interactive. E mais um jogo digno de nota e de bons elogios, umavezqueinsereumasriedeelementosqueseconstituemcomoverdadeiras contribuies para o gnero dos jogos de estratgia em tempo real. InIelizmente o jogo no logrou grande xito comercial, o que no tira seus mritos pela questo da criatividade.Quanto as inovaes, so as seguintes:Ilustrao 5. Imagens ae Starcraft. Fonte. GERYK, s.a.Ilustrao 6. Imagens ae War:one 2100. Fonte. GERYK, s.a.111. A pesquisa tecnologica e a produo de unidades aqui muda totalmente em relao aos outrosjogosdeestratgiaemtemporeal. Aoinvsdepesquisar ouconstruir um determinado tipo de unidade, pesquisa-se componentes das unidades, tais como rodas, esteiras, canhes, etc., conIorme o desenvolvimento da campanha e constroi-se novas unidades atravs da combinao destes diversos componentes. Ou seja, ao invs de se pesquisar um tanque por exemplo, o jogador pesquisa as suas componentes e quando tivertecnologiadisponivelparaisso,poderaentoconstruir otanque, mas tambm podera construir lana-misseis com quase a mesma estrutura, com a diIerena apenas de que, ao invs do canho caracteristico de um tanque, ele sera equipado com um canho caracteristico de um lana-misseis. Como pode-se observar, o jogo prov ao agente controlador uma grande liberdade de ao.2. Quando se joga no modo de campanha para um jogador, a condio da base que este construiu durante um determinado estagio da campanha transIerida para o proximo estagio, o que torna desnecessario ao jogador construir sua base desde o inicio no novo estagioemqueentrar. Almdisso, estemodelodejogabilidadeinduzojogadora utilizar de Iorma mais racional as unidades em um determinado momento,uma vez que a preservao destas unidades Iara com que o jogador comece o proximo estagio desuacampanhaIortalecido. EstacaracteristicadojogoimplicatambmumIoco menor no aspecto da micro-administrao das bases.Em 1999 tambm lanado o jogo Homeworla, desenvolvido pela empresaRelice lanada pela empresa Sierra. No mbito da campanha, o jogo basicamente reutiliza a Iormula utilizada por War:one 2100. Entretanto, grande inovao trazida pelo jogo se reIere a questo graIica, pois o mesmo se utiliza de graIicos totalmente em 3D, alm do Iato de no se utilizar deterrenosterrestresouaquaticos, seIocandoapenasemambientesareosounoespao sideral, o que implica a utilizao apenas de naves pelo jogo.12Ainda em 1999, lanado Age of Empires II. The Age of Kings, desenvolvido pela Ensemble Stuaiose lanado pela Microsoft Corporation. O jogo pode ser considerado uma dadivados jogos deestratgiaemtemporeal, sendoemalgumas discusses atmesmo considerado, em conjunto com sua expanso, The Conquerors, o melhor jogo de estratgia em tempo real ja desenvolvido.No mbito das inovaes, se colocam as seguintes:1. UmaintelignciaartiIicial altamentedesenvolvida, oqueIazcomqueasunidades componentes de umconjunto se auto-arranjemquando recebemuma ordemdo Ilustrao 7. Imagens ao fogo Homeworla. Fonte. GERYK, s.a.Ilustrao 8. Imagens ae Age of Empires II. Fonte. GERYK, s.a.13jogador, de Iorma que as unidades de combate direto Iicam mais a Irente do grupo e as unidades especializadas emataque adistncia sealoquemnapartetraseiras dos grupos. Alm disso, as unidades, quando incumbidas de atacar os inimigos, buscam atacar os alvos mais apropriados, aoinvs de atacar qualquer alvoinimigoque encontrem pela Irente.2. O jogo se Ioca na historia real de diversos povos existentes na historia da humanidade, sendo que os jogos anteriores se Iocam basicamente em historias Iicticias;3. O jogo cria o recurso que permite ao agente controlador ordenar, atravs de um sino, que os aldeesunidades construtoras do jogose escondam no centro da cidadequartel-general da baseou dele saiam, conIorme o critrio do agente controlador.Em julho de 2000, lanado o jogo Warloras Battlecry. O jogo uma adaptao da srie Warlorasdo gnero da estratgia baseada em turnospara o gnero da estratgia em tempo real. Sua inovao basica se coloca no sentido de inserir ao gnero o conceito, utilizado nos jogos de RPG4, do heroi que evolui ao passo que adquire experincia.Ainda em 2000, no ms de novembro, lanado o jogo Sacrifice, desenvolvido pela ShinyEntertainmentelanadopelaInterplay. Agrandenovidadetrazidapelojogoa possibilidadedeseressuscitar aunidadeheroi, conceitoesteque, juntocomaidiado desenvolvimento do heroi, sera utilizada em Warcraft III.OutrasinovaestrazidasmaisaIrentesecolocamnosentido decriarmapascom terrenos multiplos. O jogo Earth 2150, por exemplo, permitia as unidades a possibilidade de movimento por debaixo da terra, e Dragonshara, lanado em 2005, utiliza esta propriedade na questo da coleta de recursos, uma vez que os dois recursos existentes no jogo so alocados, cada um, em um dos terrenos nos quais os mapas do jogo so divididos (WIKIPEDIA, 2009). Os jogos Warhammer 40,000. Dawn of War, de 2004; Star Wars. Empire at War, de 2006 e Company of Heroes, tambm de 2006, trazemuma outra inovao, que consiste na substituiodoantigomodelodecoletaderecursos, ondeumaunidadeespeciIicaIicava responsavel porestaatividade, porumsistemadecontroledepontosestratgicos, ondea ocupao destes pontos implica na progressiva produo de pontos que possibilitama construo de novas estruturas e unidades.4Modalidadedejogo, ondenormalmenteahistoriaselocalizaemummundodeIantasia, ondeojogador controlaum oumais personagensqueno decorrer dojogotomam determinadasmissesparasi,ditadas por personagens no-jogaveis e adquirem experincia conIorme enIrentam as criaturas existentes no jogo. A sigla signiIica Role Playing Game.14Para o Iim de 2009, esta ainda previsto o lanamento do jogo Starcraft II,jogo que tem trazido grande expectativa para o universo dos jogos de estratgia em tempo real. O jogo, pelas demonstraes dadas at o momento pela Bli::ara, possui uma parte graIica bastante semelhante a Warcraft III. Ainda assim, o jogo traz uma outra inovao para o gnero, que o Iato de ser possibilitado a determinadas unidades terrestres a propriedade de se locomoverem entre diIerentes niveis de terreno5.1.3.Conceitos Bsicos dos 1ogos Eletrnicos de Estratgia em Tempo RealOsjogoseletrnicosdeestratgiaemtemporeal podemserdeIinidoscomosendo jogos onde diversos agentessejam eles humanos ou agentes inteligentes controlados pelo computadorso colocados eminterao emumdeterminado terreno, onde lhes so designadasumconjuntodeestruturaseunidadesmilitares, estascaracterizandoabasede atuao de cada agente, e a estes agentes so dados os objetivos de:1. Expandir as bases que lhes so dadas, atravs de coleta de recursos que esto espalhados pelo terreno, construo de novas estruturas e unidades e pesquisa tecnologica;2. Destruir as bases dos agentes inimigos.Alm destes Iatores relacionados logo atras, a principal caracteristica que deIine um jogo eletrnico de estratgia em tempo real o Iato de que as aes dos diversos agentes so dadas simultaneamente no ambiente de jogo. Aqui a estratgia em tempo real se diIere de um outro gnerodejogos eletrnicos,os jogosde estratgiabaseados em turnos. Esteassunto sera tratado mais a Irente.Os principais conceitos que precisamser delineados para que se possa ter uma abordagemsatisIatoria da questo so os conceitos de agentes controladores, naes, economia, recursos, estruturas, unidades e seus tipos e as esIeras de administrao.Os agentes controladores so os sujeitos que administram as bases. Podem ser tanto jogadores humanos quanto agentes inteligentes controlador por computador. No mbito deste 5 Este conceito se reIere as diIerenas geograIicas de terreno, mais especiIicamente a existncia de pontos mais altos e pontos mais baixos do mesmo.15trabalho, a reIerncia fogaaor sera utilizada com Iins de reIerncia aos agentes controladores humanos.As naes consistemnoconjuntodos diIerentes agrupamentos existentes emum determinadojogoeletrnicodeestratgia emtemporeal. SoreIerenciados dediversas Iormas nos jogos, dependendo da tematica dos mesmos, sendo considerados como raas em algunscomo por exemplo Warcraft II, com os ogros e humanos, e Starcraft, com os terrans, os :ergs e os protossou naes e povos propriamente ditos em outroscomo por exemplo nas diversas naes existentes na srieAge of Empires. Cada nao nos jogos possui estruturas e unidades proprias. Em alguns jogos, possivel ainda que uma determinada nao controle unidades e estruturas de outras raas. EmStarcraft. Brooawar, expanso do Starcraftoriginal, aunidadeDarkArchon, pertencentearaadosprotoss, podecontrolar unidades deoutras raas. Assim, apartir destahabilidadedaunidade, pode-secontrolar unidades construtoras de outras raas e assim criar bases com diversas raas controladas por apenas um jogador ou agente inteligente.O conceito de economia se reIere a administrao da base como um todo, e tem como base a realizao da coleta dos recursos existentes no terreno e sua aplicao na construo de estruturas e unidades com vistas a expanso da base e deIesa no caso de ataques inimigos.Os recursos se reIeremao conjunto de elementos dispostos no terreno que so utilizados para expanso da base. A diversidade e a tipologia dos recursos variam de acordo com o jogo que se leva em considerao, sendo que ha jogos onde se deve administrar apenas um recurso e outros onde se deve administrar 3 ou mais recursos, como por exemplo no jogo Warcraft II, da Blizzard Entertainment, que possui 3 tipos de recursos: o ouro, a maaeira, e o oleo.As estruturas consistem no conjunto de construes inseridas na base. Assim como os recursos, os tipos e a diversidade das construes variam de acordo com o jogo considerado. Normalmente, os Iins agregados as estruturas so:1. Estabelecimento do local da base principal, sendo que normalmente este Iim alocado aumaestruturaespeciIica, queseradenominada, aqui, genericamentepelotermo quartel general. O nome dado a tal estrutura varia conIorme o jogo. No entanto, este Iato no altera a Iuno da unidade dentro do jogo, que a de basicamente delimitar o ponto de partida de um determinado agente numa dada partida;162. Expanso da capacidade populacional da base, que consiste no numero de unidades que podem ser produzidas num determinado momento;3. Aconstruo de novas unidades, sendoque normalmente ha estruturas que so responsaveis pela construo de algumas unidades, enquanto outros tipos de unidades so designadas para ser construidas por outras estruturas;4. Arealizaode pesquisas objetivandoa melhoria tecnologicada base, aspecto esse essencial paraaexpansoeaumentodaprobabilidadedeumdeterminadoagente vencer uma partida.5. O comrcio com outros agentes.As unidades se reIerem ao conjunto de entidades as quais so atribuidas as Iunes de construo dabaseou ataqueaos inimigosedeIesa dabase.Ostipos deunidadesvariam conIorme o jogo e os temas que estes utilizam em suas historias. Normalmente, as unidades so divididas nas seguintes categorias:1. Unidades construtoras;2. Unidades terrestres;3. Unidades aquaticas;4. Unidades areas.As unidadesconstrutoras so as unidades responsaveisdiretamentepelaexpanso e manuteno da base. A elas so alocadas as Iunes de construir novas estruturas para a base e a de reparar as estruturas existentes que porventura tenham soIrido dano em decorrncia de condies adversas, como por exemplo a ocorrncia de ataques inimigos.No necessario ir muito longe para conceituar as outras modalidades de unidades. Basta apenas levar em conta as suas nomenclaturas, sendo que as unidades terrestres so as unidades as quais so possibilitadas apenas a movimentao emterra, as aquaticas as unidades capacitadas apenas a movimentao na agua e as areas as unidades capacitadas a movimentao emespao areo. No entanto, importante destacar que o mbito de movimentaodeumadeterminadacategoriadeunidadesnoimplicanecessariamenteo mbito de ataque desta categoria. Ou seja, unidades terrestres no atacam somente unidades terrestres, assim como unidades areas no atacam somente unidades terrestres. Dependendo 17do tipo de unidade que se leva em conta, elas podem ter campos de ataques diversos. Ou seja, ha unidades terrestresquepodematacartantounidades terrestreseunidadesareas, assim como ha jogos em que unidades areas so impossibilitadas de atacar unidades terrestres at quesejamIeitasasmelhoriastecnologicasnecessariasaisso, comoporexemplo, ojogo Outlive, onde a unidade Jingaaorpossui esta caracteristica, ou seja, at que seja realizada a pesquisasobreodispositivotorpeaoaefotons, estaunidadepodeapenasatacar unidades areas. No entanto, ha de se destacar tambm que ha jogos onde determinadas categorias de unidades so impossibilitadas de atacar outros tipos em determinadas circunstncias, independentemente do grau de desenvolvimento tecnologico alcanado por uma determinada base. Como exemplo disso, pode-se tomar o jogo Warcraft II, onde unidades terrestres no podem atacar unidades aquaticas em alto mar, assim como estas no podem atingir unidades terrestres ou estruturas inimigas Iora de seu alcance quando esto posicionadas junto a costa da base inimiga em operaes de ataque.Os tipos de unidades se reIerem aos conjuntos de unidades idnticas entre si em um determinado jogo. Os tipos das unidades dispostas nos jogos dependem muito da tematica que o jogo adota. O jogo Warcraft II, por exemplo, tem como tematica a guerra entre humanos e ogros. A cada uma das duas raas so alocadas unidades de tipos diIerentes que, no entanto, possuem Iunes semelhantes. Ou seja, a cada unidade dos ogros equivale uma unidade de Iuno semelhante aos humanos. O jogo Starcraft, desenvolvido pela Bli::ara Entertainment, assim como Warcraft II, tem como tematica guerras envolvendo 3 raas: os terrans, humanos normais, os :ergs, uma raa alienigena com o aspecto semelhante ao de insetos, e os protoss, uma raa alienigena com poderes psiquicos altamente desenvolvidos. Da mesma Iorma como em Warcraft II, a cada raa so designadas unidades diIerentes, mas que, dentro de cada nivel, possuem Iunes semelhantes. Aqui, entretanto, importante observar que este jogo possui algumas diIerenas mais notaveis no que tange a este ponto, como por exemplo as unidades mais poderosas de cada raa, que so os Battlecruisers, para os terrans; os Guaraians, para os :ergs e os Carriers, para os protoss. Antes desta analise, entretanto, conveniente deIinir de Iorma mais rigorosa estas unidades.Os Battlecruisersso grandes naves de batalha cujos ataques inIligem danos signiIicativos as estruturas ou unidades inimigas e, apos realizada a pesquisa pertinente, so equipadas com um dispositivo denominado Yamato Gun, que carrega e lana um poderoso raio em direo ao alvo especiIicado pelo agente que o comanda. Os Battlecruisers, exceto no 18caso de se utilizarem do Yamato Gun, Iicam ao alcance das estruturas de deIesa6inimigas, podendo ser atacados pelas mesmas enquanto realizam seu ataque.OsGuaraianssounidades derivadasda unidadeMutalisk,surgindo atravs de um processo de incubao que este soIre sob o comando do agente controlador, desde que este tenha construido a estrutura Great Spire,derivada da estrutura Spire. Estas unidades podem atacar as estruturas de deIesa da base inimiga sem darem a possibilidade de estas revidarem o ataque.Por sua vez, os carriers so grandes naves que, em operaes de ataque, lanam naves menores, denominadasinterceptors, alocadas emseuinterior. Estas soos responsaveis diretospeloataqueaosinimigos, cabendoaoscarriersapenaslana-las. Assimcomoos Guaraiansdos:ergs, podem atacar as estruturas de deIesa inimigas sem a possibilidade de revide do ataque. No entanto, importante destacar que, embora os carriersno possam ser atacados, os interceptors o podem, uma vez que so unidades designadas para a realizao de combate a curta distncia.ApenasnestasdeIiniespode-severdiIerenassubstanciaisnoIuncionamentodas unidades de cada raa, principalmente no que tange ao aspecto da possibilidade de revide por parte das estruturas de deIesa da base que esta sendo atacada, pois enquanto osGuaraians podem atacar tranqilamente sem a necessidade de se preocupar com as estruturas de deIesa inimigas, os carriers precisam ter um nivel de ateno maior com os interceptors,uma vez que estes podem ser destruidos durante a batalha, e a construo de novos requer a aplicao de recursos, o que pode se tornar uma situao problematica quando o agente controlador se encontrarcom recursosescassos. QuantoaosBattlecruisers, apreocupaoaindamaior, umavezqueaIaltadoscuidados necessariospor partedoagentecontrolador comsuas unidadespoderaimplicar naperdadasmesmas, eaconstruodeumnovoBattlecruiser requer a aplicao de uma quantidade de tempo e recursos consideravel. Observe-se que estas diIerenas no muito signiIicantes implicam mudanas estratgicas relevantes de acordo com a raa que se utiliza em uma determinada partida.Para Iins de comparao, tome-seas unidades mais poderosas de cada raa no jogo Warcraft II: osaragons, paraos ogros, eosGriphonRiaers, dos humanos. Estas duas 6 Pode-se reIerenciar estas estruturas, em termos gerais, atravs do termo torres, apenas para Iins metodologicos. No entanto, dentro do jogo, cada raa possui suas proprias estruturas de deIesa, que, embora cumpram com o mesmo objetivo, possuem diIerentes Iormas e Iuncionalidades.19unidades possuem enquanto caracteristica signiIicativa apenas seu aspecto externo, sendo que as caracteristicas essenciais so as mesmas: unidades areas com alto poder destrutivo.Determinadas unidades so equipadas comhabilidades especiais que podemser utilizadas no decorrer do jogo e cuja utilizao consome umoutro recurso, que sera denominado aqui, de Iorma genrica, energia.7Adiscussoacerca da administrao das unidades nodecorrer dos jogos leva, necessariamente, a discusso sobre as esIeras de administrao de bases.Este conceito pode ser deIinido como o conjunto de condies internas da base do agente controlador, que este deve manejar durante uma partida.CHUNG et. al.as classiIica em 3:1. A micro-administrao de unidades: se reIere ao controle de unidades individuais;2. O planejamento ttico: Se reIere a administrao de tropas engajadas em algum tipo de atividade.3. O planejamento estratgico:se reIere as grandes linhas do planejamento durante a partida, comoporexemploadeIiniodomomentonoqualserarealizadaalguma atividade, comopor exemploaconstruodoexrcitoaser utilizadopeloagente controlador ou o lanamento de um ataque a alguma base inimiga.1.4. As diferenas entre os jogos de estratgia emtempo real e jogos de estilos semelhantesOs jogos de estratgia em tempo real so um gnero especiIico dos jogos eletrnicos, composto pelas caracteristicas expostas anteriormente.No entanto, ha gneros de jogos que lhe assemelham, e interessante distingui-los dos RTS8. Tais gnerosso os jogos de estratgia baseados emturnoseos jogos detaticaem tempo real.7 Esta denominao tem Iins apenas metodologicos. Assim como varias das caracteristicas dos jogos eletrnicos de estratgia em tempo real, a denominao deste recurso varia conIorme a tematica do jogo. Por exemplo, no jogo Warcraft II, so denominados por mana, em Iuno da tematica deste jogo se voltar mais para um mundo de Iantasia. Ja no jogo Starcraft, este recurso denominado como energia, em Iuno de este se posicionar num mundo Iuturistico.8Sigla em ingls utilizada com Iins de reIerncia aos jogos de estratgia em tempo real.SigniIicareal-time strategy.201.4.1. Estratgia em tempo real x estratgia baseada em turnosOs jogos de estratgia baseados em turnos assemelham-se aos jogos de estratgia em temporeal. Noentanto, comooproprionomeindica, diIeredestesnosentidodequeos jogadores no planejam e executam suas estratgias simultaneamente, e sim alternadamente ou de outras Iormas relativamente semelhantes, conIorme sera exposto adiante.O modelo mais normal de jogo de estratgia baseado em turno o modelo onde os jogadores planejam e aplicam suas estratgias alternadamente, ou seja, um lana suas jogadas de cada vez. O exemplo mais classico deste modelo de jogo o xadrez.No entanto, como Iica implicito no que esta sendo argumentado at o momento, este no o unico modelo. Os jogos de estratgia baseados em turnos e os jogos de estratgia em tempo real podem ser considerados como dois extremos de uma reta, onde entre os dois existe uma srie de modalidades de jogos de estilos diIerentes entre si, mas que possuem, em sua grandeparte, elementos dosdoistiposdejogos. Emseuconjunto, estesestilosdejogos Iiguram entre os sistemas de organizao do tempo em jogos (WIKIPEDIA, 2009).Dentro deste conjunto de estilos de jogos, podem ser encontrados os jogos de turnos cronometrados, os ticks, os jogos com compresso do tempo, os jogos de turnos executados simultaneamente, os jogos baseados em relogio, os jogos baseados na iniciativa das unidades, os jogos onde so permitidos a interveno de um jogador num turno que no lhe pertence, os jogos com turnos ou Iases especiais,os jogos parcialmente ou opcionalmente baseados em turnos ou emtempo real e os jogos emtempo real compausa. No so necessarias consideraes acerca destes jogos, uma vez que este no o objeto deste estudo.A existncia de diIerenas entre os jogos de estratgia em tempo real e os jogos de estratgia baseados em turnos tem suscitado, ao longo do tempo, uma srie de discusses que as tomamcomopontodereIerncia, realizandocomparaes entreas mesmas. Como Iacilmente observavel, estas discusses dividem o espectro de jogadores em dois grupos: os que deIendem os jogos de estratgia em tempo real e os que deIendem os jogos baseados em turnos.A argumentao do primeiro grupo se encontra nos seguintes pontos (WIKIPEDIA, 2009):211. Os jogos de estratgia em temporeal oIerecemum grau decorrespondncia com a realidade imensamente maior que os jogos baseados em turnos, pois no mundo real a ocorrnciadeguerrasimplicanecessariamenteaelaboraoeaplicaosimultnea das estratgias pelos atores envolvidos;2. A espera pela realizao da jogada pelo outro jogador pode tornar a experincia do jogo entediante;3. Os jogos baseados em turnos tm muitas regras e so diIiceis de dominar em Iuno do numero de minucias que simulam.Ja os deIensores dos jogos baseados emturnos se Iundamentamnos seguintes argumentos (idem):1. Os jogadores so capazes de planejar melhor seus movimentos em Iuno do tempo extra que lhe disponibilizado e os desenvolvedores so capazes de suprir os jogadores com um espectro maior de opes taticas;2. Os jogossomais limpos emIunodeavitorianosebasear nosreIlexos do jogador, e os jogos, teoricamente, so providos de uma melhor inteligncia artiIicial, dado a quantidade de poder de processamento que lhes disponibilizada;3. Emais realisticocontrolar multiplas unidadesdeIormainteligenteutilizandoeste sistema, pois o jogador no obrigado a dividir sua ateno com diversos grupos de unidades;4. Emais Iacil manter vigilncia sobre as aes do inimigo quando o jogador inIormado a respeito de todas as aes daquele.Analisando-se objetivamenteaquesto, conclui-seIacilmenteque,dentreestesdois modelos, os jogos em tempo real terminam por possuir uma srie de vantagens em relao ao outro modelo, conIorme sera exposto adiante.AargumentaoquedeIendeos jogos baseados emturnos sebaseiam, deIorma sinttica, no seguintes pontos:1. Facilidade de planejamento para o jogador;222. Melhor inteligncia artiIicial nos jogos, em Iuno do menor consumo dos recursos computacionais existentes;3. Maior conIormidade com a realidade;4. Facilidade de vigilncia Irente ao inimigo.Quantoaoponto2, importantedestacar queodesenvolvimentodoharawareao longo do tempo pode suprir esta necessidade tranqilamente, tornando, assim, as diIerenas no mbito das sobras de poder de processamento dos computadores insigniIicantes.Quanto aos outros pontos da argumentao que se coloca a Iavor da estratgia baseada em turnos, trata-se, na perspectiva aqui apresentada, de grandes equivocos. Veja-se:1. As Iacilidades para o planejamento do jogador quanto as suas jogadas no existem no mundo real, pois todas as aes dos atores envolvidos em questes que requerem a aplicao de conhecimentos estratgicos se do simultaneamente;2. A vigilncia em relao aos inimigos, quando se coloca a questo dentro do mbito da realidade, sedaatravs deservios deinteligncia, enemsempreestes servios conseguem manter estrita vigilncia sobre os inimigos.Por esta argumentao, pode-se observar Iacilmente que os jogos baseados em turnos no correspondem a realidade dos Iatos quando se Iala em aplicao de estratgias, uma vez queosatoresenvolvidosnorealizamsuasaese, aposisso, esperamasaesdeseus inimigos para ento lanarem suas aes. Os mesmos agem conIorme a situao lhes permite, o que necessariamente implica que as estratgias so elaboradas e aplicadas simultaneamente pelos atores envolvidos nestes processos.1.4.2. Estratgia em tempo real x ttica em tempo realA diIerena basica entre os jogos de estratgia em tempo real e os jogos de tatica em tempo real se reIere ao Ioco de cada um, pois os jogos de estratgia se Iocam num mbito mais geral das questes militares, pois atribuidaaojogador aresponsabilidadedeno apenas vencer os inimigos, mas tambmde gerenciar suas proprias bases no mbito econmico. Ou seja, alm do jogador ter de se preocupar com os inimigos, deve tambm se 23Iocar em ter um numero de unidades e estruturas suIiciente para ter uma base Iorte, alm de produzir recursos em quantidade suIiciente para poder manter esta base.Ja os jogos de tatica em tempo real se Iocam mais no aspecto do combate direto com o inimigo. Normalmente, os jogos detaticaemtemporeal nopossuememsuaestrutura questes relacionadas agerenciamento debases ecoleta derecursos. Normalmente sua estrutura consisteemdispor paraojogador umconjuntodeunidades inseridas emum determinado campo de batalha, onde o jogador devera pensar em Iormas de derrotar as Ioras inimigas utilizando as unidades que lhes so disponibilizadas.Outro aspecto notavel de diIerenciao entre os jogos de estratgia em tempo real e os jogos de tatica em tempo real o maior Ioco que este da as unidades individuais. Nos jogos de estratgia em tempo real todas as unidades pertencentes a um determinado tipo possuem as mesmas caracteristicas, tendo-se como unica exceo para esta situao as unidades herois. Ja dentre os jogos de tatica em tempo real, ha jogos onde cada unidade possui um nome proprio, o que implica uma identidade para cada unidade. Ja outros, como por exemplo o jogo Close Combat,, produzidoem1995pelaempresaAtomicGames, bastanteconhecidopeloalto grauderealismocolocadoemsuaestrutura, pois oagentecontrolador obrigadoase preocupar com a munio limitada que lhe alocada, com a gravidade das Ieridas recebidas por seussoldadoseatmesmoascondiesmentais epsicologicasdestesduranteojogo (WIKIPEDIA, 2009).Realizando uma comparao mais sistematica entre os jogos de estratgia em tempo real e os jogos de tatica em tempo real, pode-se ver que os dois gneros se complementam, principalmente no que tange a sua aplicabilidade em programas de treinamento de pessoal, por exemplo. A diIerena basica entre os dois gneros o Iato de os jogos de tatica em tempo real se Iocarem num aspecto mais especiIico das questes estratgicas. Em Iuno disso, ha discusses que at mesmo consideram os jogos de tatica em tempo real como um sub-gnero dos jogos de estratgia em tempo real.1.5. Consideraes finaisNeste capitulo Ioi apresentada a historia dos jogos eletrnicos de estratgia em tempo real,almdosconceitosbasicosdestesjogoseumacomparaodestegnerocomalguns proximos.24Pela historia dos jogos de estratgia em tempo real, pode-se observar que o gnero tem agregadoasi umsriedeevolues, evolues essasquecontinuamaser incorporadas mesmo na atualidade, sendo que as evolues vo desde a parte graIica, com a transio da arquiteturaem2dimensesparaade3dimensesatajogabilidade, comotambmpela agregao ao gnero de caracteristicas pertencentes a outros gneros de jogos.25CAPITULO 2 - OSAGENTESINTELIGENTESNOS1OGOSELETRNICOSDE ESTRATGIA EM TEMPO REAL2.1. Introduo - A Inteligncia ArtificialA Inteligncia ArtiIicial (IA) uma area do conhecimento que vem sendo desenvolvida desde o Iimda Segunda Guerra Mundial, sendo, portanto, uma area do conhecimentobastanterecente(RUSSEL&NORVIG, 2004: p. 3). OproprionomeIoi cunhado apenas em 1956 (idem). O autor (idem) relata que atualmente, a IA abrange uma enorme variedade de subcampos, desde areas de uso geral, comoaprendizadoepercepo, attareIasmaisespeciIicascomojogosde xadrez, demonstrao de teoremas matematicas, criao de poesia e diagnostico de doenas.Continuando (idem), argumenta que 'a IA sistematiza e automatiza tareIas intelectuais e, portanto, potencialmente relevante para qualquer esIera de atividade intelectual humana. Nesse sentido, ela verdadeiramente um campo universal.No ha umconsenso na parcela da comunidade cientiIica ligada a Inteligncia ArtiIicial sobre uma conceitualizao sistematica exata desta area. Neste mbito,existem 4 Iocos, a saber;1. A IA vista como a construo de sistemas que agem como seres humanos;2. A IA vista como a construo de sistemas que pensam como seres humanos;3. A IA vista como a construo de sistemas que agem racionalmente;4. A IA vista como a construo de sistemas que pensam racionalmente.Nesteponto, pode-seobservarquetaisIocosconceituaislevamemconsideraoa combinao de dois Iatores binarios:1. Operaes realizadas pelos sistemas a serem construidos: pensamento x ao;2. Forma de ao dos sistemas a serem construidos: humaniaaae x racionaliaaae.26A primeira abordagem da IA tem como ponto basilar de analise a questo do teste de Turing. Estetestepermitedeterminar seumamaquinatemacapacidadedereproduzir o pensamento humano de Iorma que qualquer pessoa que interaja com esta maquina no saiba se esta interagindo com uma outra pessoa ou com uma maquina. RUSSEL & NORVIG (idem: p. 4)adetalhanosseguintestermos: 'Ocomputador passaranotesteseuminterrogador humano, depois depropor algumas perguntas por escrito, noconseguir descobrir seas respostas escritas vm de uma pessoa ou no.A segunda abordagem, Iocada na questo da construo de sistemas que pensam da mesma Iorma que os seres humanos, esta ligada a questo da modelagem cognitiva. Busca entender os processos que regema cognio humana para entomodelar sistemas que reproduzam estes processos. RUSSEL & NORVIG (idem: p. 5) relata a existncia de duas Iormas de se entender os processos cognitivos humanos: a primeira a introspeco, ou seja, a busca de captar os pensamentos humanos a medida que eles se desenvolvem, e a segunda atravs deexperimentos psicologicos. Continuando, oautor argumenta que 'depois que tivermos uma teoria da mente suIicientemente precisa, sera possivel expressar a teoria como umprograma de computador (idem). Estes conhecimentos so do mbito do campo interdisciplinardacinciacognitiva, que'reunemodeloscomputacionaisdaIAetcnicas experimentais da psicologia para tentar construir teorias precisas e veriIicaveis a respeito dos processos de Iuncionamento da mente humana (idem).A terceira abordagem cai no mbito da logica, sendo, em Iuno disso, denominada de tradiologicista(idem: p. 6), sendo que'por volta de1965, existiam programas que,em principio, podiamresolverqualquerproblema solucionavel descrito emnotao logica (idem). O principal objetivo desta escola o de desenvolver programas nestes moldes para criar sistemas inteligentes (idem).Entretanto, o autor (idem) relata que essa abordagem enIrenta dois obstaculos principais. Primeiro, no Iacil enunciar o conhecimento inIormal nos termos Iormais exigidos pela notao logica, em particular quando o conhecimento menos de 100 certo. Em segundo lugar,ha umagrandediIerenaentreser capazderesolver umproblemaemprincipioe resolv-lo na pratica. At mesmo problemas com apenas algumas dezenas de Iatos podem esgotar os recursos computacionais de qualquer computador, a menos que ele tenhaalgumaorientaosobreasetapasderaciocinioquedevetentarprimeiro. Embora ambos os obstaculos se apliquem a qualquer tentativa de construir sistemas de raciocinio computacional, eles surgiram primeiro na tradio logicista27Ja a quarta abordagem se Ioca na questo do agente racional. RUSSEL & NORVIG (idem) deIine um agente racional como um agente que 'age para alcanar o melhor resultado ou, quando ha incerteza, o melhor resultado esperado.Normalmente, a Inteligncia ArtiIicial costuma se preocupar coma questo da construo de agentes racionais. O Ioco deste trabalho dar-se-a tambm neste sentido, tendo emvista que, quandose Iala emagentes inteligentes aplicados a jogos eletrnicos de estratgia em tempo real, Iala-se, necessariamente, de agentes racionais.Este capitulo tera como ponto especiIico de abordagem estes agentes. Iniciar-se-a com a exposio acerca dos tipos de agentes existentes, a saber: os agentes reativos, subdivididos entre dois grupos: os agentes reativos simples e os agentes reativos baseados em modelos. E os agentes cognitivos, sub-divididos em outros dois grupos: os agentes baseados em objetivos e os agentes baseados na utilidade; prosseguir-se-a com uma abordagem acerca do planejamento nos agentes e uma abordagem acerca da aprendizagem nos agentes. Cada um destes topicos tera dois pontos de abordagem: uma caracterizao geral de cada operao e uma analise mais pratica de cada uma, ou seja, como estes conceitos so aplicados aos agentes cognitivos dos jogos eletrnicos de estratgia emtempo real. Apos isso, seguir-se-a as consideraes Iinais do capitulo.As partes deste capitulo que tratamdos agentes inteligentes e das tcnicas de planejamentobasear-se-onotrabalhodeRUSSELL&NORVIG(idem), eaabordagem acerca da aprendizagem basear-se-a no trabalho de RICH & KNIGHT (1993).2.2. Os agentes inteligentesOs agentes inteligentes podem ser deIinidos basicamente como agentes compostos por um conjunto de sensores, um conjunto de atuadores e um conjunto de regras de raciocinio, inseridos em um dado ambiente, sendo que, atravs de seus sensores, recebem inIormaes deste ambiente, as processa de acordo com suas regras de raciocinio e retornam uma resposta a este ambiente atravs de seus atuadores.Os sensores podem ser deIinidos como qualquer dispositivo de recepo de inIormaes acoplados aoagente. Comoexemplos, podemser citadossensorestrmicos, microIones e cmeras.28Os atuadores podem ser entendidos como o conjunto de dispositivos atravs do qual o agenteintervemnoambienteondeestainserido. Estaintervenopodesedar atravsda emisso de sinais de voz, que podem ser lanados ao ambiente atravs de sintetizadores de voz, ou tambm atravs de intervenes diretas, como por exemplo o ato de se locomover at um determinado local.O ambiente consiste no conjunto de estruturas, reais ou virtuais, no qual o agente esta inserido e com o qual interage. Este ambiente pode ser tanto o mundo real, com o qual um rob, por exemplo, interage, ou mesmo uma estrutura de um jogo de computador, no qual o agente interage com outros agentes inteligentes e com jogadores humanos.Os ambientes so deIinidos de acordo com os seguintes parmetros:1. Observabilidade:Consiste noespectrodoambiente quepodeser captadopelos sensores do agente. Neste sentido, o ambiente pode ser completamente observvel ou parcialmente observvel, sendo que o ambiente completamente observavel pode ser captadocompletamentepelossensoresdoagente, oupelomenosemseusaspectos mais relevantes; eparcialmenteobservavel quandoseusaspectosrelevantesno podem ser captados em sua plenitude pelos sensores do agente.2. Estocasticidade:Pode-se dizer que consistena possibilidade de o desenvolvimento interno do ambiente a partir de um determinado estado conjugado com as aes do agente ser deIinido ou no em um campo de probabilidade. Aqui, o ambiente pode ser determinstico, estocsticoouestratgico. Os dois primeiros casos reIerem-sea interaodoagentecomoambiente, quandonohaoutros agentes inseridos no mesmo, e o terceiro se reIere a existncia desses outros agentes no ambiente, quando apenas esta existncia, e mais nenhum outro Iator, conIere ao ambiente um determinado grau de estocasticidade. O ambiente deterministico quando 'o proximo estadodoambiente completamente determinado peloestado atual e pela ao executada pelo agente (p. 41), sendo estocastico quando esta condio no satisIeita.3. Seqencialidade:Este parmetro baseia-se na relao entre os diversos estados que um determinado ambiente pode assumir no decorrer do tempo, em Iuno das aes doagente. Desta Iorma, umambiente pode serseqencialouepisdico, sendo episodicoquandoaaodoagentenumdeterminadoestadonopossui qualquer 29relao comos estados posteriores do ambiente, e seqencial quando existe a possibilidade de inIluncia de aes executadas pelo agente num determinado estado do ambiente em estados posteriores do mesmo.4. Dinamicidade: a dinamicidade se reIere a possibilidade de existncia de mudanas no ambiente que se do independentemente da ao do agente e e ocorrem enquanto este deliberaumaao. Nestesentido, umambientepodeserestticoquandoesta possibilidade inexistenteou dinmicono caso contrario.5. Continuidade:Consistenapossibilidadedeoambienteserdescritoemtermosde estados ou dimenses Iisicas Iinitos, sendo discreto quando descrito de acordo com estes parmetros e contnuo no caso contrario.6. Quantidade de agentes inseridos no ambiente: O agente inteligente pode no estar agindo solitariamente no ambiente. Outros agentes tambm o podem ao mesmo tempo. Com relao a esse parmetro, um ambiente pode ser um ambiente de agente nico ou um ambiente multiagente.Cadaagentecompostopelaconjunodeduasestruturas: umaarquiteturaeum programa de agente (p. 44). A arquitetura pode ser deIinida como o conjunto de estruturas Iisicas que compem o agente. Pode ser tanto o corpo de um rob como tambm o conjunto de circuitos logicos de um computador que do vida a um agente inteligente inserido em um jogo de computador.Ja o programa de agente consiste no conjunto de estruturas logicas que compem o agente.Guardadas as devidas propores, pode-se dizer que a arquitetura consiste no haraware do agente inteligente. E o programa de agente, o seu software.Tal estrutura pode ser deIinida de acordo com a seguinte sentena:Agente Arquitetura + Programa de AgenteOautor (idem) relataque'otrabalhodaIAprojetar oprogramadeagenteque implementa a Iuno do agente que mapeia percepes em aes. E importante salientar que o programa de agente deve ser apropriado para a arquitetura (idem). Isto signiIica dizer, em termos praticos que, se oagente no possui uma estrutura adequada,torna-se impossivela 30execuodoseuprogramadeagente. Ouseja, nosepodeprogramar umagentepara caminhar quando este no tem pernas, da mesma Iorma que impossivel a uma pessoa voar por conta propria, dado que a natureza no lhe proveu as asas que lhe permitiriam o vo.Outroconceitoqueimportantesalientar arespeitodos agentes inteligentes o conceito da funo ae agente. Este conceito esta relacionado com o conceito do programa de agente. Noentanto, diIeredestenoaspectoqueestetemumcarater deimplementao, enquantoqueaIunodeagentetemumcarater mais matematico, mapeando'qualquer seqncia de percepes especiIica para uma ao (p. 34)Os agentes inteligentes dividem-se num total de 4 categorias,conIorme a ilustrao abaixo:OquediIerenciaostiposdeagentesinteligentesentresibasicamenteonivelde complexidade atribuido a cada tipo de agente, sendo que os agentes reativos simples so os modelos mais simples dentre todos, seguindo-se, ento, uma ordemde complexidade crescente at os agentes baseados emutilidade, que so os modelos mais complexos, passando-se pelos agentes baseados em modelos e pelos agentes baseados em objetivos.Este topico abordara cada modelo de agente de Iorma separada, de acordo com o nivel de complexidade,iniciando-secom os agentes reativos simplesat os agentes baseados na utilidade.Ilustrao 9. Esquema ae representao aa aiviso aos agentes inteligentes em tipos especificos.312.2.1. Os agentes reativos simplesOs agentes reativos simples so implementados com uma estrutura basica de estimulo-resposta. Ou seja, a cada estimulo que recebem do ambiente onde esto inseridos, retornam uma resposta pr-determinada, ignorando todo o historico de percepes recebidas do ambiente at o momento em que recebeu o estimulo imediato.2.2.2. Os agentes baseados em modelosOs agentes baseados em modelos, como o proprio nome indica, so dotados, alm da estrutura basica contida em um agente reativo simples, de uma estrutura interna denominada moaelo ae munao.Esta estrutura consiste num conjunto de inIormaes contidas no agente que registram a situao do ambiente onde o agente esta inserido de acordo com duas condies, a saber:1. A condio do ambiente desconsiderando a ao do agente;2. A condio do ambiente em Iuno da ao do agente.Ilustrao 10. Representao esquematica ae um agente reativo simples.Aaaptaao ae (RUSSEL & NORJIG, 2004. p. 47)32Este modelo de mundo utilizado pelo agente para guiar a sua ao. Assim, o agente noutilizaapenas asuapercepoimediatadoambienteparapoder entoagir sobreo mesmo. Ao passo que recebe a inIormao do ambiente, o agente baseado em modelos possui a capacidade de calcular a sua ao antes de executa-la.2.2.3. Os agentes baseados em objetivosO agente baseado em objetivos um modelo de agente dotado, alm das estruturas existentes nos agentes reativos baseados em modelos, de um conjunto de objetivos que guia sua ao.EstesobjetivospodemserdeIinidoscomoumconjuntodecondiesdesejaveisao agente (p.49). Num jogoeletrnicodeestratgiaemtemporeal, por exemplo, podemser deIinidos como objetivos do agente a destruio das bases inimigas e a preservao da propria base.Ilustrao 11. Diagrama esquematico ae um agente baseaao em moaelos.Aaaptaao ae (RUSSEL & NORJIG, 2004. p. 49)33Os objetivos de um agente tm complexidade variavel, sendo que alguns podem ser atingidos diretamente e outros devem seguir passos muito mais complicados para que possam ser atingidos. Neste sentido, so deIinidos algoritmos de busca e planejamento. Destes dois conceitos, apenas o planejamento sera Ioco deste trabalho, sendo analisado mais adiante.Embora os agentes baseados em objetivos paream menos eIicientes, eles so muito mais Ilexiveis que os agentes reativos, dado que 'o conhecimento que apoia suas decises representado de maneira explicita e pode ser modiIicado (p. 50). Alternncias de condies ambientais nosagentesreativosimplicamnareescritadeumasriedepontosnasregras condio-ao9para que estes agentes possam ter uma interao adequada com o ambiente onde esto inseridos. Num agente baseado em objetivos, basta que se atualize o conceito de aoeIicientenas novas condies ambientais paraqueoagentepossaemitir respostas adequadas as mesmas.2.2.4. Os agentes baseados na utilidadeOs agentes baseados na utilidade so um modelo de agente que, alm da estrutura de objetivos existente, so dotados de um conjunto de regras de utilidade.A um agente podem ser dados um conjunto de objetivos que, no entanto, podem ser contraditorios ou ter graus de eIicincia distintos. Neste sentido que surge a importncia do 9 Regras que relacionam as respostas do agentes aos estimulos externos.Ilustrao 12. Diagrama esquematico ae um agente baseaao em obfetivos.Aaaptaao ae (RUSSELL & NORJIG, 2004. p. 50)34mecanismo da utilidade. Este mecanismo permite que o agente possa deliberar qual ao mais conveniente em relao a seus objetivos.Neste sentido, deIinida na estrutura do agente uma funo ae utiliaaae, que mapeia um estado (ou uma seqncia de estados) em um numero real, que descreve o grau de Ielicidade associado. Uma especiIicao completa da Iuno de utilidade permite decises racionais emdois tipos de casos nos quais os objetivos so inadequados. Primeiro, quandoexistemobjetivoscontraditorios, dosquaisapenas algunspodem seratingidos (.), a IunodeutilidadeespeciIicaocompromisso apropriado. Em segundo lugar, quando existem varios objetivos que o agente deseja alcanar e nenhum deles pode ser atingido com certeza, a utilidade Iornece um meio pelo qual a probabilidade de sucesso pode ser ponderada em relao a importncia dos objetivos (p. 50)O conceito de feliciaaae, colocado pelo autor na passagem acima exposta, pode ser entendida como a convenincia de uma ao em relao aos objetivos do agente.2.3. Funes cognitivas nos agentesPode-sedizer queosagentesinteligentessosistemasmodelados parareproduzir, juntoaoambienteondesoinseridos, grausdeintelignciainerentesaoser humano, em niveis variados de aproximao.Ilustrao 13. Diagrama esquematico ae um agente baseaao na utiliaaae.Aaaptaao ae (RUSSEL & NORJIG, 2004. p. 51)35A inteligncia humana, entretanto, possui em sua estrutura um conjunto de diversas Iunes. Dentreelas, pode-secitar oplanejamento, aaprendizagem, oprocessamentode linguagemnatural eoraciocinioprobabilisticoe/ouestatistico, sendoqueaoestudoda modelagem de cada uma destas Iunes correspondem sub-areas da Inteligncia ArtiIicial.Nos jogos eletrnicos de estratgia em tempo real, e mais especiIicamente no estudo dosagentescognitivos evolutivos, pode-sedizerqueas Iunescognitivasmais utilizadas pelos agentes programados para estas aplicaes so o planejamento e a aprendizagem. Neste sentido, este trabalhoIocar-se-a essencialmente nestas Iunes, abstraindoas outras em Iunodenoteremaplicabilidadenosjogoseletrnicosdeestratgiaemtemporeal to evidente quanto as que sero tratadas adiante.2.3.1. O planejamento nos agentes2.3.1.1. Caracterizao geralOplanejamentopodeserdeIinidocomosendoaIunocognitivadeseconceber, dentrodeumdeterminadoambienteedadoumoumaisobjetivos, umconjuntodeaes seqncias ouparalelas quepermitiroaoagente queoconcebeuatingir oobjetivoou conjunto de objetivos que lhe Ioi dado.RUSSELL& NORVIG(pp. 363-446) Iaza abordagem do planejamento atravs da caracterizao geral do conceito e da especiIicao de sua aplicao a problemas do mundo real.Todaaopressupeaexistnciadedeterminadas condies quepermitamasua execuo. O autor(idem) as denomina como pr-condiesda ao. Alm disso, toda ao esta dotada de efeitos sobre o ambiente, que consistem basicamente nas conseqncias diretas da execuo de uma ao por um agente em um dado ambiente.Os conceitos de ao, pr-condies e eIeitos so essenciais para que se possa caracterizar oplanejamentonecessarioaconsecuodeumdeterminadoobjetivoporum agente racional.Continuando sua discusso, o autor(idem) deIine os seguintes modelos de planejamento:1. Planejamento com busca no espao de estados;362. Planejamento de ordem parcial;3. Planejamento atravs de graIos;4. Planejamento com logica proposicional.Nestetrabalho,sero consideradasapenas as metodologiasda busca emespaosde estados,oplanejamentodeordemparcial eoplanejamentoatravsdegraIos, dadoqueo planejamento com logica proposicional no possui uma aplicabilidade nos jogos eletrnicos de estratgia em tempo real to clara como as outras metodologias.Oplanejamento atravs de busca emespaos de estados tambmnotemuma aplicabilidade muito clara na caracterizao do planejamento em agentes de jogos eletrnicos de estratgia em tempo real. No entanto, ela sera abordada em Iuno de possuir relaes com o planejamento de ordem parcial.Oplanejamentocombusca noespaode estados deIinido peloautor como a abordagem mais objetiva para a questo do planejamento.Umespaodeestadosconsistenoconjuntodeestadosqueoambienteeoagente podem assumir entre o estado atual em que se encontram e o estado que esta deIinido como objetivo do agente. Cada estado deIinido por um conjunto de literais que dizem quais so as suas caracteristicas.A busca no espao de estados pode ser Ieita em dois sentidos:1. Para frente: Aqui o planejamento Ieito a partir do estado inicial do problema, que geralmentedeIinidoatravs deumconjuntodeliterais positivos, sendoqueos literaisquenoaparecemnadescriodoestadosoconsideradosIalsos. Apartir deste estado, o agente calcula o conjunto das aes que vo modiIicar o ambiente at que se atinja oobjetivoespeciIicado, utilizando aque melhor lhe convier. Esta abordagem tambm pode ser denominada como planejamento porprogresso. Dado que os estados que no so descritos soconsiderados Ialsos, diz-se que nesta modalidade de planejamento o agente utiliza-se de uma hiptese de mundo fechado.2. Para trs: Neste caso, diIerentemente da busca para Irente, o planejamento se da a partir doestadodeIinidocomoobjetivoparaoagente, sendoquecabeaoagente detectar as aesrelevantespara que possa atingir o objetivo que lhe Ioi proposto. Almdisso, deve-selevar emconsideraoqueas aes aseremrealizadas pelo 37agente devem ser consistentes, ou seja, uma ao no pode desIazer qualquer literal quesejadesejavel aconsecuodoobjetivoproposto. Estaabordagemtambm conhecida como planejamento por regresso.As modalidades de planejamento baseadas na busca em estados de espao consistem em modalidades de planejamento de ordem total, ou seja, modalidades de planejamento onde todo o plano seguidoestritamentede acordo com uma determinadaordem,inexistindoo paralelismo de aes no plano.Determinadas aes so mais importantes ou obvias que outras. No entanto, o ordenamento estritamente cronologico das aes pode Iazer com que as aes importantes ou obvias no sejam tratadas com o devido grau de prioridade.Esta questo vem a ser resolvida atravs do planejamento de ordem parcial, que passa a tratar em seu bojo a questo do paralelismo entre determinadas aes, permitindo que estas aes paralelas possam ser executadas sem uma ordem estrita.O planejamento de ordem parcial trabalha com o reIinamento do plano, aspecto esse inexistentenasabordagensbaseadasembuscaemespaosdeestados. DestaIorma, esta abordagem toma o plano como pronto assim que detecta o conjunto de aes que levara ao cumprimento eIetivo do objetivo proposto ao agente.Umplanoinicial podenosereIiciente. Nestesentidosecolocaaimportnciado reIinamento de um plano, sendo que este processo traz a possibilidade da modelagem de um planoquevenhaautilizarmenosrecursosou mesmotrataraspartesmaisimportantesou obvias do plano com a devida prioridade.Cada plano dentro de um planejamento de ordem parcial possui 4 componentes, que so:1. Um conjunto de aes, que consistem nas intervenes do agente junto ao ambiente;2. Um conjunto de restries de ordenao, que consistem nas regras de precedncias entredeterminadasaes. Aqui importanteassinalar anoodeciclos, quea condio onde uma ao uma precondio e ao mesmo tempo eIeito de outra ao. 3. Um conjunto de vnculos causais, que consistem em aes que devem ser executadas entre outrasduasaes e quenopodemser canceladasnointervalo entre as duas aes consideradas. Vale ressaltar que, das aes onde o vinculo causal esta inserido, a 38primeira ao precondio do vinculo causal e este precondio para a segunda ao.4. Um conjunto de precondies abertas, que consistem em precondies que no esto sendo alcanadas por nenhuma ao no plano em um determinado momento.Quando no ha nenhum ciclo nas restries de ordenao e nenhum conIlito com os vinculos causais do plano, diz-se que encontrou-se um plano consistente. E quando encontra-se umplano consistente que no possua nenhuma precondio aberta, diz-se que Ioi encontrada uma soluo para o problema colocado (p. 379).O planejamento de ordem parcial trabalha atravs da criao de um plano inicial, que consiste em duas aesIniciar e Terminara restrio de ordenao que indica que Iniciar vem antes de Terminar,nenhum vinculo causal e todas as precondies em Terminarcomo precondies abertas. E importante destacar que as aes Iniciar e Terminar no representam nenhuma ao concreta. So apenas indicadores do inicio e do Iim do plano. So consideradas, por isso, como 'aes Iicticias (p. 378).A partir da condio colocada, o algoritmo de planejamento cria, para cada uma das precondies existentes, vinculos entre estas e a ao Iniciar, estabelecendo as restries de ordenao e vinculos causais apropriados, alm de criar novas aes conIorme a necessidade. Apos a realizao destas operaes, o algoritmo realiza um teste de objetivo, que consiste em veriIicar se o plano encontrado representa uma soluo para o problema colocado (idem: p. 380). Apos encontrada a soluo, dada por encerrada a execuo do algoritmo.As heuristicas de planejamento de ordem parcial e total podem soIrer