Inteligência Artificial nos Games # 1
Um tema que cada vez mais chama a atenção do público em geral é de uma inteligência artificial que pode fazer coisas que na prática são complicadas para humanos.
Quando algo que humanos têm jogados à milhares de anos, como Go, ou a centenas, como xadrez, é destruído de forma brutal por um sistema computacional, vemos claramente o potencial desses sistemas em áreas que só víamos em filmes no passado.
O objetivo deste post, é dar uma visão de IA em games, através de artigos acadêmicos e notícias na mídia, além de propor uma formulação futura para o assunto.
Algumas notícias sobre o assunto:
Um exemplo recente é o Alpha Star, um sistema baseado em Reinforcement Learning, LSTM( Long Short Term memory) e outros parâmetros que ganhou de jogadores do mais alto nível no Starcraft.
Neste vídeo da Nature, o autor dele explica o funcionamento do sistema. Starcraft é um jogo extremamente complexo, eu por exemplo jogo o game (mesmo sendo noob ainda), e posso dizer que profissionais nesse game são máquinas sobre humanas.
Ganhar de jogadores que jogaram esse jogo por anos é algo difícil de processar inicialmente.
A DeepMind (Subsidiária da Google) também criou o Alphago, um sistema que também abusava de Reinforcement learning, LSTM e Monte Carlo Search Tree para jogar um jogo que até então não tinha sido resolvido por algoritmos convencionais, pela sua complexidade.
Isso mostra que sistemas de IA têm capacidade de serem melhores que Bots em games atuais.
O Blog acima mostra resultados de uma competição de IA no minecraft, o artigo mostra que Reinforcement Learning não é o suficiente em sistemas que necessitam exploração como o Minecraft, isso é óbvio de certa forma.
O uso de Imitation Learning por exemplo mostrou eficaz para permitir que o sistema aprendesse de forma eficiente.
Imitation Learning se baseia normalmente em clips, vídeos focando em uma tarefa especifica em um game, o objetivo é reconhecer os padrões representados e replicar eles artificialmente.
O uso de Imitation Learning + Reinforcemente Learning já foi usado extensivamente, recentemente em: CARL: Controllable Agent with Reinforcement Learning for Quadruped Locomotion.
A combinação destes dois modelos é apresentado no blog como uma forma bem interassante para jogos de exploração como o Minecraft, Tibia, World Of Warcraft, entre outros.
Esse método é interessante, mas obviamente outros parâmetros devem ser usados em sistemas de navegação em games. Os mais comuns são os Algoritmo “A Star”( Pentikäinen e Sahlbom, 2019.), BFS (Breadth-first search) [Monteiro,2018] e Hierarchical path finding(HPA) [Noori, 2015].
Papers também exploram Soft Q Learning como (Tang, 2019), outros usam algoritmos com A3C (Song, 2020) para servir como um adicional à modelos de Reinforcement Learning.
Eu gostei muito do Algoritmo A Star com o uso de campos potenciais para detectar inimigos no starcraft (Hagelbäck, 2008 ;Hagelbäck, 2015).
Nesses dois papers os autores exploram o uso de A Star para achar o melhor caminho no sistema do game, além do uso de boids flocking algorithm para agrupamentos de unidades no starcraft.
Essa imagem mostram o uso de campos potenciais para detectar a localização de inimigos (bolinha vermelha) e de aliados (bolinhas verdes). Esses campos gerados no sistema permitem tanto planejar o ataque ao inimigo ou recuar unidades caso haja perigo nesse embate.
O modelo também permite gerar campos potenciais em estruturas como torres aliadas e inimigas, no terreno, para uma movimentação mais efetiva.
Esses campos são bem práticos, e dão uma noção visual da percepção do sistema de IA do game com relação a terrenos e oponentes.
Essa imagem mostra uma perspectiva mais aérea, a geração dos campos potenciais de terrenos e localização de inimigos.
Esse estilo de navegação em IA’s funciona bem no starcraft e em jogos 2D Arcade como Bomberman. Pesquisa relacionada ao uso desses modelos em jogos como Tibia, World Of Warcraft (WOW) ou Tera seriam interessantes para a questão da exploração do game.
Em (Cui, 2011), eles analisam o uso de Pathfinding em jogos como WOW nessa imagem. O artigo trata sobre a diferença de Dijkstra’s pathfinding e o A Star, mostrando na prática o por que de A star ser prevalente hoje.
Um exemplo citado foi o Civilization IV, um jogo de estratégia com reinos bem conhecido por jogadores com esse gosto. A complexidade do sistema desse jogo poderia ser aproveitada usando A Star.
A representação acima mostra um pathfinding de A até B usando formas poligonais como forma de estrutura espacial.
Nós vamos ter nestas mesh, arestas e vértices compondo essa representação que pode agora ser representada matematicamente. Ao longo de usar isso, eles propõe um método chamado DOP(Direction Oriented Pathfinding).
O Objetivo é gerar:
- Uma rede de polígonos que representam o mapa do game.
- Achar o melhor caminho entre esses polígonos (Talvez usando A Star)
- Mostrar o melhor caminho dentro do mapa.
Embora seja uma boa idéia, eles não fizeram experimentos práticos mostrando o DOP.
Em [Noori, 2015] os autores dão uma lista bem completa sobre o uso de algoritmos de pathfinding em games, os mais recentes são o GHPA*, JPS,Phi* e BIDDFS.
Alguns deles são optimizações do A star.
Esses foram os resultados comparatidos, sendo que eles separam os algoritmos em Uninformed Search e Informed Search. O HPA* foi o que se saiu melhor nesse caso.
Reinforcement Learning e Imitation Learning são bons métodos para treinar jogos complexos como Minecraft, Tibia ou WOW para jogar o jogo de forma coesiva.
Mas técnicas de navegação ainda devem ser aplicadas, nesse caso a HPA* talvez seja o algoritmo mais eficiente para pathfinding no momento.
O mercado de games gerou uma receita de $ 60 Bilhões de 2020–2021 (Statista, 2021), é algo em expansão e com cada vez mais consumidores de longo termo. Usar melhores algoritmos para exploração de IA’s em game talvez seja o próximo passo da IA nesse tema.
Se você quiser saber mais sobre Reinforcement Learning e outras técnicas de IA em games, recomendo o nosso canal no youtube que explica com detalhes esse tema no qual já analisamos vários dos artigos citados nesse post.
By Mike R.
Referências:
- Google AI beats top human players at strategy game StarCraft II, 30 October 2019, Nature.
- The computer that mastered Go, 26 January 2016, Nature.
- AI takes on popular Minecraft game in machine-learning contest, 26 November 2019, Nature.
- Tang,Towards Informed Exploration for Deep Reinforcement Learning, UC Berkeley,2019.
- Song, Spellcaster Control Agent in StarCraft II Using DeepReinforcement Learning, MDPI Eletronics, 2020.
- Pentikäinen e Sahlbom, Combining Influence Maps andPotential Fields for AI Pathfinding, Master of Science in Engineering: Game and Software Engineering, 2019.
- Monteiro, Beating Bomberman with Artificial Intelligence, PUC, 2019.
- Noori, Simulation and Comparison of Efficency in Pathfinding algorithms in Games, Ciência e Natura, 2015, 37:230DOI: 10.5902/2179460X20778.
- Hagelback, The Rise of Potential Fields in Real Time Strategy Bots, Blekinge Institute of Technology, 2008.
- Hagelback, Hybrid Pathfinding in StarCraft, January 2015, IEEE Transactions on Computational Intelligence and AI in Games 8(99):1–1DOI: 10.1109/TCIAIG.2015.2414447.
- Hagelbäck, Using Multi-agent Potential Fields in Real-time StrategyGames, Conference: 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), Estoril, Portugal, May 12–16, 2008, Volume 2.
- Cui, Directions oriented pathfinding in Video Games, International Journal of Artificial Intelligence & Applications (IJAIA), Vol.2, №4, October 2011.
- Noori,Simulation and Comparison of Efficency in Pathfinding algorithms in Games, Ciência eNatura, v. 37Part 2 jun. 2015, p. 230−238, 2015.
- Video Game Industry — Statistics & Facts, Statista Research Department, Jan 18, 2021.
- Canal no Youtube: https://www.youtube.com/channel/UCN5HGjBHvzjhNLtQwZe4L0A/videos
