How Videogame Helps the Development of Artificial Intelligence
Wed, 23 Jan 2019 || By Faadillah Fayyadh Aidad

Introduction

Since its inception as a mod in Blizzard’s Warcraft 3, Defense of the Ancients (Dota) has become one of the most popular e-sports in the world. The game was the brainchild of multiple developers in the past, it but reaches its most significant popularity on the hands of IceFrog. Dota reaches a global audience since the game was acquired by the game developer Valve (with IceFrog hired as Valve employee), and rebranded as Dota 2. The game is very complex, requiring strategic thinking, real-time decision making, as well as high-level technical skill to master the game.

In its simplest form, Dota is a five versus five team game. Players control a hero unit, with a specific ability and roles against the opposing team. The game is played on a map and is split by a river in the middle and is divided into three lanes, with three towers to each lane and two to guard the Ancients. In order to win the game, the player’s hero unit need to accumulate gold and experience from killing enemy heroes and various creatures on the battlefield, buy items to empower their heroes, push and destroy the towers, and ultimately the opponent's Ancient (hence the name "Defense of the Ancients"). With more than 100 heroes and items, Dota has a vast number of variable any players or AI need to calculate, with hero selections (called drafting) often determine the outcome of a match before it even began. The non-profit organisation used this complex game OpenAI to develop new kinds of general purpose AI with learning capabilities.

Dota 2 Map version 7.15

According to their website, OpenAI is a "non-profit artificial intelligence research company" with a goal to "advance digital intelligence in the way to benefit humanity as a whole, unconstrained by a need to generate a financial return." Their research output includes Dactyl, a robot hand who can perform the complex dexterous motion, as well as a learning algorithm called Proximal Policy Optimization, which is utilised to develop the OpenAI Five. Meanwhile, the Dota bot team is developed by OpenAI.

 

AI in Video Games

Artificial intelligence on video games is not a new concept, as some games require good AI to enhance the gameplay experience. The complexity of the existing AI behaviour is differentiated by the type of game played by the players. For instance, within a First Person Shooter (FPS) game, where for most games the objective for the player is to eliminate the opposing team, the AI uses the Finite State Machine (FSM) algorithm. FSM algorithm derives all possible actions of the human actors, then programmed the AI to do a specific action depending on the action of the players. In First Person Shooter game, the AI is programmed to shoot the player when they are visible, retreat when their health gets low, and find a way to restore their health before engaging the players again. The FSM algorithm's biggest weakness is the predictability of the AI action, as they are hardwired to a specific action, players may find their behaviour repetitive and quickly become bored. Another form of AI algorithm is the Monte Carlo Search Tree (MCST). MCST analyses all possible moves the AI can make, the human response to their moves, and their predicted responses, ad infinitum. The ever-expanding options create branches of decisions, which makes them perfect to be utilised on complex strategy games such as Chess and Total War Rome. AI developers have created intelligent AIs since its inception. However, the most significant achievement for any AI developer is the creation of AIs who can learn. Algorithms like FSM and MCST can only do so much; the AI behaviour still relies on the programs that govern them, they cannot evolve or change their behaviour based on the player's input. Dota’s complexity and ever-evolving nature mean that it requires a dynamic AI as well as serve as the perfect training ground for the AI.

Breakthrough

OpenAI first promotes their breakthrough in video game AI through a one versus one Dota match with Dendi, a top player in Dota professional scene during The International 7, the annual world championship for Dota 2. In a game of one versus one, Dota is much simpler than the ordinary one, yet the AI is capable of defeating Dendi. The bot achieved this with little to no human intervention, and the AI developer assigns a value to the bot's action to incentivise them to improve (killing enemy heroes are right, taking damage is terrible). The bots learn by reinforcement learning with self-play, playing against themselves (and their past selves), within an accelerated environment. This scheme allows them to take years of Dota experience in a matter of several months. After the one versus one, the OpenAI develops OpenAI Five, a bot who can learn and improve on five versus five Dota. To that end, OpenAI identifies several required skills the bot need to master Dota:

  1. Long time horizons ()

Small decisions in Dota can cost the game. As OpenAI observes every fourth frame (Dota runs at 30 frames per second), it predicts that there are around 20,000 movements within a Dota match for victory, and most of them are strategic. As a comparison, in the Chess game, the movement mostly ends after 40 moves.

  1. Partially observed state

Units and structures in Dota cannot see the whole map, but they can only see areas around them. The "fog of war" conceals the position of opposing teams, which hinder the ability to gather reliable information. The AI needs to be able to predict what the opponent's move based on limited information. 

  1. High-dimensional, continuous action space

OpenAI calculates that there are around 170,000 possible moves a hero can make on each tick. The AI needs to be able to choose the one who can ensure victory.

  1. High-dimensional, continuous observation space

Unlike Chess, the Dota battlefield is very dynamic, with Non-Player Characters (NPC) units, towers, trees, and runes occupying the space. The AI needs to be creative to use the game’s environment to their advantage.

Source: OpenAI’s mission is to ensure that artificial general intelligence benefits all of humanity,  https://openai.com/five/

 

With this knowledge in mind, OpenAI has been capable of developing OpenAI Five into a team that can defeat progressively better enemies. Throughout several months, they have been capable of defeating higher MMR (matchmaking rating, a numerical value representing player's abilities) players. The Five plays in a modified Dota game (mirror hero matchups, no wards, and five invulnerable couriers), although they manage to improve the Five to play with real Dota rules prior to The International 8 (although with limited hero pool). OpenAI Five was finally defeated in the International 8 by a team of professional players, representing the top 0.1% percentile of Dota players. OpenAI aims to develop better AI for the next International, with the goal of defeating a professional team with the full hero pool, drafting, and professional rules.

 

Conclusion

Video games provide a good environment to develop AI. Just like for humans, it demands creative problem solving with the available tools at their disposal, within a non-realistic environment. As demands for competitive gaming start to grow, the development of video games more complex for Dota 2 would, in turn, incentivise the creation of smarter AI in the future. This virtuous cycle would hopefully help organisations like OpenAI to achieve their goal of developing digital intelligence for the good of humanity.

Editor: Anisa Pratita Mantovani

Read another article written by Faadillah Fayyadh Aidad


Reference

David Silver. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm.. [online].Available at: arXiv:1712.01815v1.

OpenAI.(2018).OpenAI Five. [online]. Available at: https://blog.openai.com/openai-five/

OpenAI.(2017).Proximal Policy Optimization. [online]. Available at: https://blog.openai.com/openai-baselines-ppo/#ppo.

Harbing Lou. (2017).AI in Video Games: Towards a More Intelligent Game, [online]. Available at: http://sitn.hms.harvard.edu/flash/2017/ai-video-games-toward-intelligent-game/