1
Inteligência Artificial No Jogo Command Bots Daniel C. Tavares
Janderson A. S. Lima
Henrique M. Silva
Renan C. Azevedo
Figura 1: Tabuleiro de jogo.
Centro de Educação Superior de Brasília, Brasil. Resumo O artigo procura estudar os mecanismos de inteligência artificial utilizados no desenvolvimento do jogo Command Bots em busca de entender se é possível a utilização de uma única técnica de em seu desenvolvimento e qual seria. Em caso negativo, será feito esforço de compreensão dos desafios que exigiram a adoção de mais de uma alternativa para a realização dos objetivos de desenvolvimento.
Abstract The article tries to understand the artificial intelligence mechanisms used in the development process of the game Command Bots, in search of answering if it is possible tu use only one technique in its development and which one. If the answer is negative, the development process will be analysed in order to understand the challenges that led to the adoption of more than one alternative to achieve the development goals.
Palavras-chave: Jogos Digitais. Inteligência Artificial. Sistema Especialist. Sistema multi-agentes. Máquina de Estados-Finita. Contato:
[email protected]
1 Introdução O presente trabalho buscará demonstrar a utilização de sistemas de inteligência artificial no desenvolvimento do jogo Command Bots. Será realizado esforço a fim de responder ao questionamento: é possível aplicar uma única metodologia de inteligência artificial no contexto do jogo? No segundo capítulo, após esta introdução, será feito sobrevoo introdutório ao tema inteligência artificial, verificando se existe alguma diferenciação interna no campo da inteligência
artificial que busque melhor alternativa. No terceiro capítulo, será feita contextualização tendo-se o jogo como plano onde serão aplicadas técnicas de inteligência artificial a fim de resolver os desafios encontrados e buscar-se-á a ferramenta de inteligência artificial ideal. Será também descrita a plataforma de desenvolvimento e a linguagem de programação utilizada para o desenvolvimento. No capítulo quatro, será detalhada a aplicação das escolhas feitas a fim de superar os desafios de movimentação, ataque e decisões diversas no jogo. O quinto capítulo apresentará formalmente a resolução para o questionamento inicial e concluirá a pesquisa.
2 Inteligência Artificial e Jogos Digitais As definições de inteligência artificial são amplas e sem consenso. Há aquelas que focam na busca pela ação racional; na ação semelhante à realizada pelos seres humanos; com foco na reprodução do pensamento humano ou no pensamento racional. 1 A área também pode ser dividida entre os dois grandes grupos: a) o da inteligência artificial “forte” 2, relacionada à busca da construção de máquinas capazes de pensamento racional e emoções; e b) da inteligência artificial “fraca” 3, voltada para o desenvolvimento de programas ou robôs que auxiliem a compreensão da inteligência (que Champandard4 entende como “o apanhado de habilidades que permitem aos seres humanos resolver problemas com recursos
1 RUSSEL, Stuart.; NORVIG, Peter. Artificial Intelligence: a modern approach. Estados Unidos : Pearson Education Inc, 1995. 2 Tradução livre para: “Strong”. BRIGHTON, Henry.; SELINA, Howard. Introducing Artificial Intelligence. Reino Unido : Icon Books Ltd, 2012. p. 6. 3 Tradução livre para: “Weak”. Ibidem. p. 7. 4 CHAMPANDARD, ALEX. J. AI Game Development: synthetic creatures with learning and reactive behaviours. Estados Unidos da América : New Riders Publicshing, 2004.
2
limitados (...)” 5 [Tradução livre]), tanto humana, quanto animal, especialmente no campo teórico. 6 Em Norvig e Russel 7, inteligência artificial é entendida como “estudo de agentes que recebem percepções do ambiente a realizam ações.” 8 Tendo como parâmetro a definição onde “agentes computadorizados devem (...) operar autonomamente, perceber o ambiente, persistir em período de tempo prolongado, adaptar-se à mudança, criar e perseguir objetivos. Um agente racional é aquele que age buscando alcançar o melhor resultado ou, quando há incerteza, o melhor resultado esperado.” 9 [Tradução livre]. Para Champandard10, no mesmo sentido, a programação de inteligência artificial com uso de agentes utiliza-se de “um processador que coleta informação, a processa, delibera um pouco mais e executa ações” 11. O uso de técnicas diversas de inteligência artificial visa à resolução de problemas complexos, emulação de pensamento e planejamento, aprendizagem, comunicação, percepção e ação. 12 O tópico de inteligência artificial especificamente para jogos, para Champandard13, traz o desafio de desenvolver comportamentos inteligentes “em criaturas genuínas” 14 [Tradução livre] com foco em cada animat 15 (animal artificial) individual, em processo chamado de embodiment16 (de agora em diante traduzida como personificação), realizado dentro do escopo de uma arquitetura reativa17 [Tradução livre] e indo além do trabalho de um desenvolvedor de inteligência tradicional, que “apenas programa e aperfeiçoa algoritmos acadêmicos” 18 [Tradução Livre]. Tal 5 Tradução livre para: “(...) set of skills that allows humans to solve problems with limited resources (…)”. Ibidem. p. 5. 6 RUSSEL, Stuart.; NORVIG, Peter. Opus Citatum. 7 Ibidem. 8 Ibidem. p. viii. 9 Tradução livre para: “(…) computer agents are expected to (…) operate autonomously, perceive their environment, persist over a prolonged time period, adapt to change, and create and pursue goals. A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.” Ibidem. p. 4. 10 CHAMPANDARD, ALEX. J. Opus Citatum. 11 Tradução livre para: “One central processor acquires information, processes itm deliberates a bit more, and executes some actions”. Ibidem. 12 RUSSEL, Stuart.; NORVIG, Peter. Opus Citatum. 13 CHAMPANDARD, ALEX. J. Opus Citatum. 14 Tradução livre para: “Genuine creatures”. Ibidem. p. xxxviii. 15 Ibidem. p. xxxviii. 16 Ibidem. p. xxxix. 17 Ibidem. 18 Tradução livre para: “just Programming and optimizing academic algortihms”. Ibidem. p. xxxix.
empreendimento, por ele chamado de “nouvelle game AI” 19 (nova inteligência artificial para jogos), em contraposição a “IA normal” 20 [Tradução livre], tem como objetivo “aumentar a credibilidade e simplificar o desenvolvimento” 21 [Tradução livre]. Para Funge e Millington 22 é possível dividir as tarefas de inteligência artificial em três categorias: “movimento” 23 [Tradução livre] (significando decisões que geram movimento), [Tradução livre] “tomada de decisão” 24 (significando escolhas entre as melhores opções para o momento) e “estratégia” 25 [Tradução livre] (significando o trabalho em equipe de diferentes agentes). Neste trabalho, no capítulo quatro, serão expostas as estratégias de movimentação e de tomada de decisões (aqui classificadas como ataque e “estados e decisões”). Contudo, o jogo não apresenta modelos de estratégia mais elaborados do que sistemas especialistas (como, por exemplo, o movimento de fuga de peças com poucos pontos de vida e, ao mesmo tempo, o movimento de peça que recupere pontos de vida em sua difreção), por isso sua explanação encontra-se incorporada em meio às três partes do referido capítulo.
3 O Jogo Command Bots O jogo desenvolvido e que dá base para o presente estudo chama-se Command Bots e tem como plano de fundo uma luta simulada entre dois jogadores, um humano e outro computadorizado, em tabuleiro virtual. O ambiente que abriga o tabuleiro virtual é uma estação espacial futurista, sendo que, da mesma forma, as peças controladas pelos jogadores contém características futuristas em estilo “cyberpunk” 26 em futuro dominado por máquinas e componentes eletrônicos implantados em humanos como visto na figura 1. Em relação à movimentação, como o jogo dá-se dentro de um grid hexagonal, cada peça deve mover-se apenas um espaço por “ação” (o número de ações por turno é igual ao número de peças no tabuleiro) limitando-se aos espaços adjacentes. Os ataques acontecem da mesma forma, havendo exceção no caso da peça de combate à distância,
19
Ibidem. Tradução livre para: “’Standard’ game AI”. Ibidem. 21 Tradução livre para: “Improving believability and simplifying the development”. Ibidem. 22 MILLINGTON, Ian.; FUNGE, John. Artificial Intelligence For Games: second edition. Reino Unido : Morgan Kaufmann Publishers : 2009. 23 Tradução livre para: “movement”. Ibidem. p. 8. 24 Tradução livre para: “decision making”. Ibidem. p. 8. 25 Tradução livre para: “strategy”. Ibidem. p. 8. 26 CSICSERY-RONAY, Istvan. Cyberpunk and neuromanticism. Disponível em: < http://www.jstor.org/stable/20134180>. Acesso em: 22 maio 2014. 20
3
que pode atacar inimigos a até dois espaços de distância.
•
Busca tabu: Onde há a exclusão de pontos específicos, já conhecidos, na lista de locais a pesquisar. 30
•
Máquina de Estado de Moore: também conhecida como “máquina de Moore” 31 [Tradução livre], onde há nova informação a cada alteração de estado. 32 Para Kyaw, Swe e Peters 33 consiste de número de estados limitados com transições entre eles. 34
•
Sistema especialista 35: que é um sistema dotado de conhecimento inteligência para a resolução de desafios delimitados e específicos.
Figura 2. Guerreiro, Paladino e Arqueiro.
Em termos de mecânica, cada jogador possui três tipos de peças: de combate à distância (arqueiro), de combate corpo-a-corpo (guerreiro) e de combate com possibilidade de recuperar pontos de vida (PDV) dos companheiros (paladino) – vide figura 2. Cada uma dessas peças, quando controlada pela inteligência artificial, tem comportamento específico durante o jogo. Os guerreiros sempre correm em direção aos oponentes, fugindo quando fracas. Os paladinos fogem do combate caso encontrem companheiros próximos que precisem de ajuda. Quando sozinhas, eles nunca fogem do combate, confiantes na capacidade que têm de autorregenerar-se em ritmo mais rápido que as demais classes. Por fim, os arqueiros mantém-se longe com combate corpo-a-corpo e foge caso esteja com poucos PDV, igualmente procurando a ajuda de outra peça que possa lhe recuperar dos ferimentos sofridos em combate. Em termos tecnológicos, o jogo foi desenvolvido para dispositivos móveis, por isso deve ser econômico na utilização de recursos de processamento e memória. A plataforma utilizada para desenvolvimento do jogo foi a Unity3D 27, em sua versão 4.3.1f1, sendo C# 28 a linguagem de programação empregada.
4 As Técnicas de Artificial Aplicadas
Inteligência
No contexto do jogo, em seus mais diversos desafios de desenvolvimento foram aplicadas as seguintes técnicas de inteligência artificial: •
Sistema multi-agentes: há mais de um agente quando há o esforço de maximizar o desempenho de um agente, possivelmente em detrimento de outro agente. Cada agente decide o que o que fazer de forma independente. 29
27 UNITY3D. Disponível em: < http://unity3d.com/pt>. Acesso em: 25 maio 2014. 28 C SHARP. In: WIKIPÉDIA, a enciclopédia livre. Flórida: Wikimedia Foundation, 2014. Disponível em: . Acesso em: 25 maio 2014. 29 RUSSEL, Stuart.; NORVIG, Peter. Opus Citatum.
A seguir, serão contextualizadas e explanadas de forma prática todas as técnicas de inteligência artificial utilizas no desenvolvimento do jogo. Ressalte-se que as mensagens enviadas entre os agentes (que comunicam os eventos entre as entidades) 36 não estão no escopo do presente trabalho. A divisão dos tópicos dar-se-á por desafio enfrentado. 4.1 Movimentações em Grid O primeiro desafio da inteligência artificial que atua como adversário do jogador humano encontra-se na movimentação em grid. Como agentes primários de posicionamento, são utilizados os objetos de jogo (GameObjects) colocados para representar o chão (de agora em diante denominado floor) e as peças que se movimentam no tabuleiro. Trata-se de sistema multi-agentes reativo (não baseado em complexos modelos de mundo, mas agindo e acordo com aquilo que é apresentado pela realidade em que está inserido a cada passo) 37. O passo inicial é determinar qual objetivo as peças devem seguir. Para isso, é lançado raycast 30
KAUR, Parmjeet.; KAUR, Usvir.; SINGH, Dheerendra. Optimization Techniques in Association Rule Mining: A Review. Disponível em: < http://inpressco.com/wpcontent/uploads/2014/05/Paper691566-1569.pdf>. Acesso em: 25 maio 2014. p. 3. 31 Tradução livre para: “Moore Machines”. CHAMPANDARD, ALEX. J. Opus Citatum. p. 513. 32 Ibidem. 33 KYAW, Sithu. Aung.; PETERS, Clifford.; SWE, Thet. Naing. Unity 4.x Game AI Programming. Reino Unido : Packt Publishing Ltd, 2013. 34 Ibidem. 35 MENDES, Raquel Dias. Inteligência Artificial: sistemas especialistas no gerenciamento da informação. Ci. Inf., Brasilia , v. 26, n. 1, Jan. 1997 . Desponível em: . Accesso em: 26 Maio 2014. 36 KYAW, Sithu. Aung.; PETERS, Clifford.; SWE, Thet. Naing. Opus Citatum. 37 RUSSEL, Stuart.; NORVIG, Peter. Opus Citatum.
4
(raio que se expande de ponto central até limite estabelecido ou infinito) circular com extensão sobre todo o tabuleiro (foi escolhida dispersão igual ao “infinito” (mathf.infinity38), mas é possível limitar à extensão do tabuleiro) que retorna vetor com informação sobre todos os posicionamentos de todos os objetos encontrados (que devem possuir colisor, ou collider). Desse vetor são desconsideradas as informações não pertencentes a gameObjects classificados como peças, e as peças do mesmo time. Em seguida, é feita comparação entre todas as peças do time inimigo a fim de descobrir qual está mais próxima, tornando-se essa o alvo da movimentação ou ataque futuro.
Figura 3: linhas vermelhas (Debug.DrawRay, não visíveis na versão release) demonstrando ligação entre os floors adjacentes já listados e o agente.
(armazenada na forma de variável estática de acesso publico e hospedada na classe OverSeer.cs), quando há ocupação ou desocupação de floor. 4.2 Ataque O ataque de peças de combate corpo-acorpo e à distância é distinto, organizando da seguinte maneira, em estrutura no estilo sistemaespecialista: •
Ataque de peças de combate corpo-a-corpo: caso a peça adversária esteja dentro de raycast com distância igual àquela de movimento, acima explanada, e se houver movimento possível (restante) para o jogador, será realizado ataque por meio do envio de mensagem informando a outra peça de que deve perder PDV. Há retorno da mensagem informando quantos PDV foram perdidos, tal informação numérica é adicionada aos pontos de experiência (XP) do jogador atacante.
•
Ataque de peças de combate à distância: utiliza-se o mesmo princípio do ataque corpoa-corpo, mas com a distância do raycast duplicada. A troca de mensagens também segue o mesmo padrão.
4.3 Estados e Decisões Em seguida, os floors adjacentes (agregados em vetor formado por raycast com distância limitada – vide figura 3) são questionados sobre qual está mais próximo do objetivo acima estabelecido. Esse floor será o escolhido para receber o novo posicionamento da peça. Após a movimentação outra peça deve realizar o mesmo processo.
Figura 5: Máquina de estados de finita. Cores verdes para PDV altos; cinza para normal; amarelo baixo; e vermelho muito baixo. Figura 4: linhas verdes (Debug.DrawRay, não visíveis na versão release) indicando ponto no espaço ligado às posições poribidas, que não podem recebr movimentação de peças.
Caso haja alguma outra peça sobre um posicionamento disponível ele será excluído da lista, utilizando-se as premissas da busca tabu. Essa lista de exclusão (vide figura 4) é formada a partir de processo de adição ou exclusão em lista tabu
Utilizando sistema de máquina de estados finitas, foram criados estados para todas as peças. Esses estados estão diretamente relacionados aos PDV de cada peça, a saber: excited (100 PDV), agitated (de 99 a 80 PDV), normal (de 79 a 50 PDV), winded (de 49 a 30 PDV) e Dying ( de 29 a 1 ponto de vida) – vide figura 5. Com zero PDV a peça é considerada como morta e desaparece do tabuleiro (é destruída a instância). Os estados influenciam no jogo das seguintes formas:
38
MATH.INFINITY. Disponível em: < http://docs.unity3d.com/ScriptReference/Mathf.Infinity.ht ml >. Acesso em: 27 Maio 2014.
5
1.
2.
Quando são contabilizados os PDV a serem oferecidos como bônus ou desconto ao dano sofrido: a.
aqueles estados acima do estado normal somam até dois pontos: excited = 2 e agitated = 1;
b.
aqueles estados abaixo do estado subtraem até dois pontos: dying = -2 e winded = -1;
c.
o estado normal adiciona 0 pontos (deixa inalterado o resultado).
Caso a peça esteja com o estado dying: a.
b.
3.
Ela foge do combate andando de forma aleatória (em termos técnicos, ela buscará os pontos de referência mais distantes, espalhados em pontos opostos do cenário, o que força a alteração de direção) saindo da situação de combate e andando pelos espaços válidos até recuperar naturalmente os PDV e sair do estado dying ou ser auxiliado por uma peça com capacidade de recuperar seus PDV. Caso seja peça com capacidade de recuperar PDV, ela jamais deixará o combate quando atingir tal estado.
Caso a peça tenha capacidade de recuperar PDV de peças companheiras de time: a.
Ela procurará, por meio de raycast, se há peças amigas com poucos PDV. Caso existam, se dirigirá para seu encontro.
b.
Ao encontrar (ficar em espaço adjacente) peças aliadas com poucos PDV, ela recuperará parte dos pontos da peça enfraquecida.
Em relação ao item 1: essa matemática permite que peças que estejam mais fracas (com menos PDV) recebam menos dano a cada ataque, assim como tenham bônus de defesa. Peças mais fortes (com mais PDV) sofrem mais danos a cada ataque e tem penalidade no bônus de defesa. Em analogia com o comportamento humano isso faz sentido, levandose em consideração que pessoas muito fortes e em pleno vigor (excited) tendem a ter menos cuidado e estarem mais sucetíveis a sofrerem maiores danos, enquanto pessoas mais machucadas (dying) tendem a adotar posição defensiva e serem mais conservadoras, aumentando seunível de defesa.
5 Conclusão O presente trabalho demonstrou a utilização de sistemas de inteligência artificial no desenvolvimento do jogo Command Bots. Foi possível observar no segundo capítulo que há diversas abordagens para o tópico inteligência artificial e que existe o esforço em separar a inteligência artificial dos jogos da chamada inteligência artificial tradicional. No terceiro capítulo, foi feita contextualização tendo-se o jogo como plano onde seriam aplicadas técnicas de inteligência artificial a fim de resolver os desafios encontrados durante o desenvolvimento. No capítulo quatro, foram demonstradas as escolhas feitas a fim de superar os desafios de movimentação, ataque e decisões com base em técnicas como pesquisa tabu, máquina de estados, sistema especialista e sistema multi-agentes. Constatou-se que, no trato com a realidade de desenvolvimento do jogo, foi preciso recorrer a técnicas múltiplas, não sendo praticável a aplicação de apenas uma alternativa no que tange as ferramentas de inteligência artificial.
6 Referências CHAMPANDARD, ALEX. J. AI Game Development: synthetic creatures with learning and reactive behaviours. Estados Unidos da América : New Riders Publicshing, 2004. C SHARP. In: WIKIPÉDIA, a enciclopédia livre. Flórida: Wikimedia Foundation, 2014. Disponível em: . Acesso em: 25 maio 2014. CSICSERY-RONAY, Istvan. Cyberpunk and neuromanticism. Disponível em: < http://www.jstor.org/stable/20134180>. Acesso em: 22 maio 2014. KAUR, Parmjeet.; KAUR, Usvir.; SINGH, Dheerendra. Optimization Techniques in Association Rule Mining: A Review. Disponível em: < http://inpressco.com/wpcontent/uploads/2014/05/Paper691566-1569.pdf>. Acesso em: 25 maio 2014. KYAW, Sithu. Aung.; PETERS, Clifford.; SWE, Thet. Naing. Unity 4.x Game AI Programming. Reino Unido : Packt Publishing Ltd, 2013. MATH.INFINITY. Disponível em: < http://docs.unity3d.com/ScriptReference/Mathf.Infinity.ht ml >. Acesso em: 27 Maio 2014. MENDES, Raquel Dias. Inteligência Artificial: sistemas especialistas no gerenciamento da informação. Ci. Inf., Brasilia , v. 26, n. 1, Jan. 1997 . Desponível em: . Accesso em: 26 Maio 2014.
6
MILLINGTON, Ian.; FUNGE, John. Artificial Intelligence For Games: second edition. Reino Unido : Morgan Kaufmann Publishers : 2009. RUSSEL, Stuart.; NORVIG, Peter. Artificial Inteligence: a modern approach. Estados Unidos : Pearson Education Inc, 1995. UNITY3D. Disponível em: < http://unity3d.com/pt>. Acesso em: 25 maio 2014.
