Um Algoritmo Evolutivo para a adaptação de NPCs em um jogo de ação Kleber O. Andrade1, Ana Estela A. Silva2, Marcio K. Crocomo2 1
Escola de Engenharia de São Carlos – Universidade de São Paulo (USP) Caixa Postal 13566-590 – São Carlos, SP – Brasil. 2
Departamento de Ciência da Computação Escola de Engenharia de Piracicaba (EEP) – Piracicaba, SP – Brasil. {pdjkleber, marciokc}@gmail.com,
[email protected]
Abstract. An Evolutionary Algorithm was developed to support a game in which the non-player character strategies are adapted, during each battle, accordingly to the human player strategies. Thus, the Evolutionary Algorithm tends to increase the software attraction to the players. In order to develop the game, the C# language and the XNA framework (by Microsoft) were employed. The present work tries to contribute to the state of the art in which there are few publications using Evolutionary Algorithm applied to games in real time execution. Therefore, this work contributes to one more case study. Thanks to the Evolutionary Algorithm implemented in this work, the related game was very successfully adapted to the player´s actions. Resumo. Durante este trabalho foi desenvolvido um Algoritmo Evolutivo (AE) e elaborado um jogo em que as estratégias adotadas pelos personagens não controlados pelo jogador se adaptam de acordo com as estratégias utilizadas pelo jogador a cada batalha. Desta forma o AE tende a aumentar a atratividade do software. Para a elaboração deste jogo, foi utilizada a linguagem C# e o framework XNA desenvolvido pela Microsoft. O presente trabalho vem a contribuir com o estado da arte, onde são poucas as publicações de aprendizagem utilizando AEs aplicados a jogos em tempo real, sendo assim, o mesmo contribui com mais um estudo de caso. Graças ao AE implementado, o jogo produzido mostrou adaptar-se às ações do jogador.
1. Introdução As primeiras tentativas de se criar um jogo segundo Kent (2001), foi em 1958 no Brookhaven National Laboratories em Nova Iorque, pelo físico Willy Higinbotham. O “Tennis for Two” era exibido em um osciloscópio e processado por um computador analógico. Willy morreu no dia 10 de Novembro de 1995, porém ele não é lembrado por inventar o primeiro jogo eletrônico, e sim por ter contribuído com a criação da primeira bomba atômica que destruiu as cidades de Hiroshima e Nagasaki durante a segunda guerra mundial. Para muitos adoradores de jogos clássicos, o primeiro jogo eletrônico chama-se Spacewar!, desenvolvido por Steve Russel em 1961 durante a sua graduação no MIT (Massachussets Institute of Technology) [Demaria 2004]. Spacewar é um jogo no qual
dois jogadores se envolvem em uma batalha espacial e tentam derrotar o oponente com torpedos e, ao mesmo tempo, evitar uma representação do sol que fica no centro da tela. Uma das pessoas que tinha contato com o jogo era o engenheiro Ralph H. Bear que em 1971 fecha contrato com a Magnavox e lança em 1972 o primeiro console doméstico, o Magnavox Odyssey. A indústria de jogos procurou tornar os jogos mais realistas, para atrair novos jogadores e aumentar o faturamento. Desde então, a criação de jogos evoluiu, e os jogos eletrônicos começaram a chegar a um nível impensável de realidade nos últimos 20 anos. Desenvolver jogos é uma atividade multidisciplinar na área da computação. Dentre as matérias envolvidas estão: projeto, programação, desenho, música, efeitos sonoros, hardware, redes, inteligência artificial (IA), matemática e física. Em função da diversidade de disciplinas envolvidas, os jogos se mostram um bom ambiente para a pesquisa de novas tecnologias para estas áreas da computação. Inicialmente os fabricantes de jogos têm concentrado grandes esforços ao realismo da ambientação gráfica. No entanto, autores como Sweetser (2002) dizem que o próximo foco a ser explorado no mercado de jogos será com personagens que se comportam de forma realista e podem aprender a se adaptar, ao invés de personagens mais visivelmente reais [Crocomo 2006]. Tais informações estão sendo reforçadas devido ao aumento do investimento das empresas em jogos com qualidade em sua inteligência artificial. Dentre as diversas técnicas envolvidas em IA, os Algoritmos Evolutivos (AE) [Yannakakis 2005] têm sido bastante utilizados para evoluir comportamentos e estratégias de jogos desde os anos 80. Porém, a técnica encontra resistência em ser utilizada pelos desenvolvedores de jogos. Autores como Spronck, Sprinkhuizen-Kuyper e Postma (2004) afirmam que esta técnica (assim como a técnica de Redes Neurais Artificiais [Haykin 2001]) permite a obtenção de comportamentos não aceitáveis durante o processo de aprendizado dos personagens se aplicada de maneira errada [Crocomo 2006]. Alguns trabalhos realizados por: Crocomo (2006), Crocomo (2008) e Cruz e Demasi (2003) já conseguiram, com sucesso, utilizar AEs para gerar estratégias pelos personagens não controlados pelo jogador (NPCs – Non-Player Characters). O presente trabalho procura contribuir com a aplicação dos AEs no aprendizado dos NPCs de um jogo, onde existem poucos trabalhos encontrados até o momento.
2. Trabalhos Relacionados Em um trabalho de graduação desenvolvido no Instituto de Ciências e Matemática Computacional (ICMC-USP), AEs são utilizados para criar um jogo adaptativo, no qual o comportamento dos agentes controlados pelo computador tende a se adaptar de acordo com as estratégias utilizadas pelo jogador. Neste trabalho, vários AEs são testados, com o objetivo de encontrar uma configuração capaz de alcançar seu objetivo [Crocomo 2006]. Em [Crocomo, 2006] é dito que alguns autores chegam a afirmar que AEs não são alternativas viáveis pra esse tipo de aplicação por não cumprirem o requisito de
eficiência. Contrariando essas informações, o software produzido resultou num jogo em que os personagens controlados pelo computador oferecem um grau de adaptabilidade às ações do jogador devido ao AE implementado. Além disso, foi possível observar o surgimento de estratégias originais muito eficientes utilizadas pelo computador que superaram as expectativas dos desenvolvedores. Em outro trabalho de Crocomo (2008), o autor tenta verificar a possibilidade de aplicar AEs no aprendizado on-line de jogos. Para isso, é contestada a veracidade da afirmação de alguns autores que afirmam que os AEs não são aplicáveis na prática para atingir o objetivo em questão. Um jogo de computador é desenvolvido, no qual o algoritmo de aprendizagem gera estratégias inteligentes para os NPCs através de um AE. Desta forma, a função do AE é fazer com que a estratégia adotada pelo computador se adapte a estratégia utilizada pelo usuário a cada vez que joga. No final do trabalho, é realizada uma comparação entre a técnica Dynamic Scripting desenvolvida por Spronck, Sprinkhuizen-Kuyper e Postma (2004), e o AE desenvolvido, onde se concluí que o AE é no mínimo tão eficiente quanto à técnica anterior. Cruz e Demasi (2003) apresentam um método de evolução em tempo real de agentes em jogos eletrônicos de ação, baseado em algoritmos genéticos. A idéia de seu trabalho é de fazer os agentes dentro de um jogo evoluírem de acordo com determinados objetivos até atingirem um certo patamar, a partir do qual evoluem livremente de acordo com o adversário. O objetivo do método proposto é de permitir que haja uma evolução suave da capacidade dos agentes de acordo com o adversário, fazendo assim, com que o nível de dificuldade do jogo cresça na mesma proporção em que o jogador humano melhora seu desempenho. Para ainda Cruz e Demasi (2003) testarem o método, foi desenvolvido um jogo chamado “Olhos Assassinos”, no qual, o jogador controla um aventureiro que dispõe de uma arma com tiros limitados, mas recarregáveis que deve se proteger contra os olhos que tentam matá-lo. Os resultados do projeto foram bastante animadores. Baseado em tempos de perda de vida do jogador e diferença entre esses tempos, pode-se notar um tendência ao longo do tempo de ter uma evolução bem suave entre os agentes. O método apresentado apesar de ter resultados animadores e de ampla gama de possibilidades de uso, apresentou algumas desvantagens, como o risco da evolução dos agentes sair completamente do previsto em relação à próxima geração.
3. O Projeto Desenvolvido O projeto foi construído utilizando a linguagem C#, o Ambiente Integrado de Desenvolvimento Microsoft Visual C# Express Edition 2005 (Integrated Development Environment – IDE) , XNA Game Studio Express 2.0 que é um framework desenvolvido pela Microsoft. Ferramentas como GIMP e Inkscape para computação gráfica e na edição do som o software Audacity. Todos os softwares utilizados são gratuitos. O jogo desenvolvido (O Último Sobrevivente) para este projeto tem como objetivo servir de ambiente de teste para o AE implementado. Neste jogo o usuário é responsável pelo controle de um único personagem, contra quatro NPCs. O Último Sobrevivente segue o gênero ação, onde o jogador deve responder com velocidade ao que está acontecendo na batalha para não ser surpreendido pelos NPCs e perder.
3.1. O Jogo O jogo se passa em uma arena de batalha, no qual existem quatro NPCs (cavaleiros vermelhos) e um jogador (cavaleiro negro). Cada NPC possui uma energia e um único equipamento que é composto por uma espada. A espada possui um dano padrão, retirando somente um quarto de vida do personagem que recebe o ataque. O jogador controla o cavaleiro negro que dispõe também de uma energia e uma espada. O cavaleiro negro deve se proteger contra os cavaleiros vermelhos que tentam matá-lo. Os personagens podem andar em oito direções, estando limitados somente à dimensão da arena (570x600 pixels). O objetivo é tentar permanecer vivo e exterminar os NPCs. A Figura 1 mostra uma tela do jogo desenvolvido.
Figura 1. Tela do jogo “O Último Sobrevivente” – Sprites utilizados no jogo extraídos de http://reinertileset.4players.de/. Acessado em abril de 2008.
Cada um dos NPCs pode se encontrar em situações determinadas pelas duas primeiras colunas da Tabela 1. A terceira coluna apresenta as ações a serem tomadas em cada uma destas situações. Na primeira coluna é representado o nível de energia que pode variar de 0 a 2, sendo 0 um nível baixo de energia, 1 o nível intermediário e 2 o nível mais alto. A segunda coluna representa a quantidade de amigos que está dentro do campo de percepção daquele NPC (limitada a um raio de 150 pixels ao seu redor). Para cada situação, existe uma única saída (coluna 3) que representa a ação a ser executada pelo NPC. Os possíveis valores para a terceira coluna são explicados abaixo: (0) Algoritmo para fugir do jogador quando o ver. (1) Algoritmo para caminhar em direção ao amigo mais próximo. (2) Algoritmo para procurar e perseguir o jogador para atacá-lo. De acordo com os dados da Tabela 1, os NPCs com base na energia e quantidade de amigos que pode ver, assumem assim uma determinada ação, definida pela coluna 3.
Como essa coluna define o comportamento para um personagem do computador, a mesma pode ser vista como uma possível abstração de um NPC. Tabela 1. Entrada (colunas 1 e 2) e suas respectivas saídas (coluna 3).
3.2. O Algoritmo Evolutivo do Jogo O AE proposto para o jogo tem como cromossomos as estratégias de uma população composta por quatro guerreiros. Um cromossomo é uma configuração para a coluna 3 da Tabela 1 acima. O funcionamento do AE consiste em 5 etapas básicas: geração da população aleatoriamente, testes dos indivíduos no ambiente, seleção do indivíduo mais bem adaptado, aplicação dos operadores genéticos (crossover e mutação), geração de uma nova população. Este funcionamento pode ser visto no fluxograma da Figura 2. Geração da população aleatoriamente
Testes dos indivíduos no ambiente
Seleção do indivíduo mais bem adaptado
Geração da nova população
Aplicação dos operadores genéticos
Figura 2. Fluxograma de funcionamento do AE.
Os parâmetros dos cromossomos dos indivíduos são iniciados aleatoriamente após começar o jogo. A população então é testada no ambiente do jogo, e o membro mais bem adaptado ao final da batalha é então selecionado para se tornar o pai da próxima geração. São aplicadas em seguida, as funções de crossover e mutação para produzir a próxima geração que será então testada na próxima batalha. 3.2.1. Cromossomos O cromossomo é uma estrutura de dados que representa uma possível solução para um problema. Os cromossomos dos NPCs do jogo a serem evoluídos serão representados
como um vetor numérico, sendo que cada célula pode ser composta de valores variando de 0 a 2. Essa estrutura tem 3¹² (531.441) possibilidades de estratégia para cada NPC. Um exemplo de cromossomo é representado na Figura 3.
Figura 3. Exemplo de cromossomo.
3.2.2. População O conceito de população aplica-se a um grupo de indivíduos. Cada indivíduo dentro da população é representado por um cromossomo, e cada cromossomo é detentor de uma possível solução para o mesmo problema, sendo na maioria das vezes diferentes entre si. Pode-se chamar de geração cada nova população produzida nas iterações do algoritmo. Cada nova iteração representa uma nova batalha. Um exemplo de uma possível população é representado na Tabela 2 abaixo. Tabela 2. Exemplo de população onde cada indivíduo é um NPC
3.2.3. Função de Pontuação Cada solução é avaliada por uma função de pontuação no decorrer do jogo, recebendo uma nota que indica o quão eficaz é a solução [Tomassini, 1995]. Os NPCs do jogo são recompensados com 5 pontos para cada ataque realizado com sucesso e 2 pontos a cada 10 segundos que permaneça vivo na partida. Porém, para encontrar uma boa solução é necessário punir certas ações, e para cada ataque que o NPC receber do jogador ele é punido com 3 pontos de sua nota. Essas pontuações foram reguladas empiricamente após alguns jogos, para deixar o jogo mais dinâmico. 3.2.4. Método de Seleção O método de seleção é responsável por selecionar os indivíduos mais aptos para o cruzamento. No jogo proposto foi utilizado o método de elitismo, já que este pode aumentar rapidamente o desempenho do AE, porque previne a perda da melhor solução já encontrada. Sendo assim o AE pode convergir mais rapidamente, o que é ideal para o jogo, já que o mesmo possui um grande número de soluções e uma pequena população. A idéia do elitismo é copiar os melhores cromossomos (neste jogo, é copiado apenas o melhor cromossomo) para a nova população. O resto da população é submetido aos operadores genéticos (crossover e mutação). A partir disso, a melhor solução é escolhida para gerar descendentes.
3.2.5. Crossover O operador crossover permite combinar dois ou mais cromossomos de uma mesma população para formar descendentes similares. Esse operador pode ser aplicado de diversas maneiras e com certa probabilidade de ocorrência, denominada probabilidade de recombinação. O crossover no jogo, assim como em qualquer outro problema é aplicado logo após o indivíduo mais bem adaptado ser escolhido. Esse indivíduo torna-se o “pai” da população e terá chances de ter seus genes na próxima população. Cada valor dos cromossomos dos indivíduos tem 50% de probabilidade de recombinação. Um exemplo pode ser visto na Figura 4.
Figura 4. Exemplo de crossover.
3.2.6. Mutação O operador de mutação é necessário para a introdução e manutenção da diversidade genética da população, alterando arbitrariamente um ou mais componentes de um indivíduo. Por exemplo, quando o operador é aplicado, cada alelo possui 5% (valor definido empiricamente após vários testes) de chance de ser substituído por um novo valor. No caso do valor original ser 0 ou 1, o novo valor será 2. Se o valor original for 2, o novo valor terá 50% de probabilidade de ser 1, caso contrário, será 0. Outro exemplo de mutação pode ser visto na Figura 5.
Figura 5. Exemplo de mutação.
4. Resultados Obtidos Neste trabalho foi desenvolvido um AE para a adaptação das estratégias dos NPCs do jogo “O Último Sobrevivente”, construído também neste projeto. O AE utilizado apresentou uma adaptação bem interessante, tendendo a ter uma evolução de forma bem distribuída ao longo do tempo e de acordo com o próprio desempenho do jogador. Foram realizados testes em 80 batalhas. Após cada partida, seus dados foram armazenados para análises futuras. A partir desses dados foram obtidos gráficos que apresentam a adaptação dos NPCs. Cada linha do gráfico da Figura 6 abaixo é referente
a um indivíduo daquela população. Maiores valores de aptidão indicam melhor desempenho do NPC durante aquela partida em particular.
Figura 6. Gráfico de evolução do experimento 1 com coordenadas Média Móvel Aptidão / Geração
Com o primeiro experimento demonstrado no gráfico da Figura 6, é possível notar que naquele jogo a população começou aleatoriamente muito boa conseguindo garantir desafios ao jogador. Com o passar dos jogos o usuário começou a perceber como os NPCs agiam, passando a ganhar dos mesmos. Porém, uma adaptação dos NPCs à nova estratégia adotada pelo usuário fez com que os mesmos voltassem a dar dificuldades ao jogador. Um segundo experimento, obteve um jogo mais desafiador. Os NPCs aprendiam de maneira rápida a estratégia do jogador, que também se adaptava às estratégias dos NPCs. Sendo assim o jogo permaneceu em equilíbrio, aumentando a atratividade do mesmo. O gráfico que representa este experimento pode ser visto na Figura 7.
Figura 7. Gráfico de evolução do experimento 2 com coordenadas Média Móvel Aptidão / Geração.
Embora o primeiro experimento tenha resultado em um maior número de vitórias para o jogador (30 derrotas e 50 vitórias), essas vitórias foram consecutivas. Já o segundo experimento, o jogador teve uma quantidade menor de vitórias (54 derrotas e 26 vitórias), porém elas foram distribuídas de maneira uniforme, sendo assim o jogo obteve um maior nível de disputa entre o jogador e os NPCs. O desafio ao jogador surgiu da adaptatividade das estratégias dos NPCs proporcionada pelo AE.
O objetivo do trabalho era adaptar as estratégias dos NPCs, de maneira a tornar o jogo mais desafiador ao usuário. Além das estratégias básicas de procurar amigos, fuga e perseguição do jogador, os NPCs apresentaram em algumas ocasiões estratégias muito eficientes, como a formação de grupo para um ataque mais concentrado. Essa estratégia pode ser vista na Figura 8.
Figura 8. Agrupamento formado pelos NPCs.
5. Conclusão O Algoritmo Evolutivo desenvolvido durante este projeto foi capaz de adaptar as estratégias dos NPCs frente ao desempenho apresentado pelo usuário. Essas adaptações podem ser constatadas nos experimentos realizados, pois apresentam evidências da adaptação das populações evoluídas pelo AE em resposta ao ambiente em que se encontram. Aplicações como esta, podem ser possíveis em uma variedade de jogos, como os de ação, estratégia, MMORPGs e outros. Dessa forma, não é necessário que o programador codifique todas as estratégias que serão utilizadas e sim esperar que a capacidade de gerar estratégias novas a cada jogo diferente renove o interesse despertado pelo mesmo em seus usuários. Ao utilizar o AE proposto neste projeto, busca-se aumentar o entretenimento, pois o mesmo adiciona novos desafios ao jogador e apresenta comportamentos diferentes para cada personagem evoluído com o objetivo de aumentar o interesse do usuário no jogo. Foi constatado que os níveis de dificuldade oferecidos pelas adaptações das estratégias adotadas pelo computador foram bem equilibrados, tendendo a oferecer entretenimento. Como são poucos os trabalhos existentes que utilizam um AE para aprendizado em tempo real em um jogo, este trabalho colabora com o estado da arte ao produzir um caso de uso para esta situação. O jogo de ação obtido permitiu que estratégias eficientes fossem obtidas pelo computador durante a interação com o jogador. Tais resultados incentivam a aplicação desta técnica pelos desenvolvedores de jogos que tenham como interesse oferecer novos desafios a cada partida.
Referências Crocomo, M. K. (2006) “Desenvolvimento de um Jogo Adaptativo Utilizando um Algoritmo Evolutivo”. 2006. 39 f. Dissertação (Graduação) – Universidade de São
Paulo – Instituto de Ciências Matemática e Computação (USP-ICMC), São Carlos, SP. Crocomo, M. K. (2008) “Um Algoritmo Evolutivo para Aprendizado On-line em Jogos Eletrônicos”. 2008. 95 f. Dissertação (Mestrado) – Universidade de São Paulo – Instituto de Ciências Matemática e Computação (USP-ICMC), São Carlos, SP. Demaria, R. Wilson, J. L. (2004) “Hign Score! The Illustrated History of Electronic Games”. 2nd edition. Emeryville: McGraw-Hill/Osborne, 2004. Demasi, P. e Cruz, A. (2003) “Evolução de Agentes em Tempo Real para Jogos Eletrônicos de Ação”. II Workshop Brasileiro de Jogos e Entretenimento Digital, 2003. Haykin, S. (2001) “Redes Neurais: Princípios e Prática”. 2. Ed. Porto Alegre: Brookman 2001. 898 p. Kent, S. L. (2001) “The Ultimate History of Video Game: From Pong to Pokemon, the Story Behind the Craze That Touched Our Lives and Changed the World”, New York: Three Rivers Press. Spronck, P., Sprinkhuizen-kuyper, I. e Postma, E. (2003) “Online Adaptation of Game Opponent AI in Simulation and in Practice”. Proceedings of the 4th International Conference on Intelligent Games and Simulation (GAME-ON 2003), pp. 93-100. EUROSIS, Belgium, 2003 Sweetser, P. (2002) “Current AI in games: A review”. Australian Journal of Intelligent Information Processing Systems. Scool of ITEE, University of Queensland. Tomassini, M. (1995) “Survey of genetic algorithms”. In: Annua reviews of Computational Physics, World Scietific, 3, 87-118, 1995. Yannakakis, G. N. (2005) “AI in Compute Games: Generating Interesting Interactive opponents by the use of Evolutionary Computation”. 257 f. Tese (Doutorado) – University Of Edinburgh, Edinburgh 2005.
