Evolving dota 2 shadow fiend bots using genetic programming with external memory

ABSTRACT

The capacity of genetic programming (GP) to evolve a 'hero' character in the Dota 2 video game is investigated. A reinforcement learning context is assumed in which the only input is a 320-dimensional state vector and performance is expressed in terms of kills and net worth. Minimal assumptions are made to initialize the GP game playing agents - evolution from a tabula rasa starting point - implying that: 1) the instruction set is not task specific; 2) end of game performance feedback reflects quantitive properties a player experiences; 3) no attempt is made to impart game specific knowledge into GP, such as heuristics for improving navigation, minimizing partial observability, improving team work or prioritizing the protection of specific strategically important structures. In short, GP has to actively develop its own strategies for all aspects of the game. We are able to demonstrate competitive play with the built in game opponents assuming 1-on-1 competitions using the 'Shadow Fiend' hero. The single most important contributing factor to this result is the provision of external memory to GP. Without this, the resulting Dota 2 bots are not able to identify strategies that match those of the built-in game bot.

References

1. B. Andersson, P. Nordin, and M. Nordahl. 1999. Reactive and memory-based genetic programming for robot control. In European Conference on Genetic Programming (LNCS), Vol. 1598. 161--172.
2. M. Brameier and W. Banzhaf. 2007. Linear Genetic Programming. Springer.
3. S. Brave. 1996. The evolution of memory and mental models using genetic programming. In Proceedings of the Annual Conference on Genetic Programming.
4. J. Cartlidge and S. Bullock. 2004. Combating coevolutionary disengagement by reducing parasite virulence. Evolutionary Computation 12, 2 (2004), 193--222.
5. J. M. Font and T. Mahlmann. 2019. The Dota 2 Bot Competiton. IEEE Transactions on Games (2019). to appear.
6. P. García-Sánchez, A. Tonda, A. M. Mora, G. Squillero, and J. J. Merelo. 2015. Towards automatic StarCraft strategy generation using genetic programming. In IEEE Conference on Computational Intelligence and Games. 284--231.
7. F. Haddadi, H. Günes Kayacik, A. N. Zincir-Heywood, and M. I. Heywood. 2013. Malicious Automatically Generated Domain Name Detection Using Stateful-SBB. In EvoApplications (LNCS), Vol. 7835. 529--539.
8. Max Jaderberg, W. M. Czarnecki, I. Dunning, L. Marris, G. Lever, A. García Castañeda, C. Beattie, N. C. Rabinowitz, A. S. Morcos, A. Ruderman, N. Sonnerat, T. Green, L. Deason, J. Z. Leibo, D. Silver, D. Hassabis, K. Kavukcuoglu, and T. Graepel. 2018. Human-level performance in first-person multiplayer games with population-based deep reinforcement learning. CoRR abs/1807.01281 (2018).
9. S. Kelly and M. I. Heywood. 2017. Emergent Tangled Graph Representations for Atari Game Playing Agents. In European Conference on Genetic Programming (LNCS), Vol. 10196. 64--79.
10. S. Kelly and M. I. Heywood. 2018. Emergent Solutions to High-Dimensional Multitask Reinforcement Learning. Evolutionary Computation 26, 3 (2018), 347--380.
11. S. Kelly, Robert J. Smith, and M. I. Heywood. 2019. Emergent policy discovery for visual reinforcement learning through tangled program graphs: A tutorial. In Genetic Programming Theory and Practice, Wolfgang Banzhaf, Lee Spector, and Leigh Sheneman (Eds.). Vol. XVI. Chapter 3, 37--57.
12. W. B. Langdon. 1998. Genetic Programming and Data Structures. Kluwer Academic.
13. P. Lichodzijewski and M. I. Heywood. 2010. Symbiosis, complexification and simplicity under GP. In Proceedings of the ACM Genetic and Evolutionary Computation Conference. 853--860.
14. S. Ontanón, G. Synnaeve, A. Uriarte, F. Richoux, D. Churchill, and M. Preuss. 2013. A survey of real-time strategy game AI research and competition in StarCraft. IEEE Transactions on Computational Intelligence and AI in Games 5, 4 (2013), 293--311.
15. A. Sapienza, H. Peng, and E. Ferrara. 2017. Performance dynamics and success in online games. In IEEE International Conference on Data Mining Workshops. 902--909.
16. R. J. Smith and M. I. Heywood. 2018. Scaling Tangled Program Graphs to Visual Reinforcement Learning in ViZDoom. In European Conference on Genetic Programming (LNCS), Vol. 10781. 135--150.
17. R. J. Smith and M. I. Heywood. 2019. A Model of External Memory for Navigation in Partially Observable Visual Reinforcement Learning Tasks. In European Conference on Genetic Programming (LNCS), Vol. 11451.
18. L. Spector and S. Luke. 1996. Cultural Transmission of Information in Genetic Programming. In Annual Conference on Genetic Programming. 209--214.
19. G. Synnaeve and P. Bessière. 2016. Multiscale Bayesian modeling for RTS games: An application to StarCraft AI. IEEE Transactions on Computational Intelligence and AI in Games 8, 4 (2016), 338--350.
20. A. Teller. 1994. The evolution of mental models. In Advances in Genetic Programming, K. E. Kinnear (Ed.). MIT Press, 199--220.
21. M. Čertický and D. Churchill. 2017. The current state of StarCraft AI competitions and bots. In AIIDE Workshop on Artificial Intelligence for Strategy Games. 1--7.
22. S. Whiteson, N. Kohl, R. Miikkulainen, and P. Stone. 2005. Evolving soccer keepaway players through task decomposition. Machine Learning 59, 1 (2005), 5--30.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Reinforcement learning

    • Machine learning approaches

      • Bio-inspired approaches

        • Genetic programming