The global online gaming industry is no game, as it is estimated that in 2019 it gained $33.6 billion in revenue. Every day, thousands and thousands of people around the world play for hours complex team strategy games, whether in friendly games, or in tournaments that pay big cash prizes. In fact, the esports industry generates $1.2 billion a year in revenue and distributes more than $120 million in prizes, so there are many professional teams and leagues.
One of the games that gives the most prizes each year ($35 million in 2019) is Dota 2. This videogame, belonging to the multiplayer online battle arena genre, brings together daily more than 40 million players who, in teams of 5 members, face off in a fantasy world for the control of their fortress. Players can choose from nearly 120 characters, each with special and unique abilities. Because Dota 2 is team-oriented, players must coordinate and plan their actions with their teammates to achieve victory.
On April 13, 2019, a team controlled with Artificial Intelligence (IA) defeated the 2018 world champion team of DOTA 2 in two of three games. Then the program, called OpenAI Five, faced for 4 days every team that wanted to play with it, winning 7,215 times and losing only 42 (Read the article describing the project here).
Although systems like OpenAI Five have a complex architecture and use very advanced tools, the working principle is the same as any game: in the current situation, look for the actions you can take and evaluate which one gets you closer to your goal. The techniques for doing this search fall into the field of AI called problem solving, which studies how to find the sequence of actions that leads to a desired state of affairs. In addition to mastering games, problem solving is used to find the best route to get to a place, accommodate millions of components and connections in an integrated circuit, plan robot navigation, or find the sequence for the automatic assembly of a product.
To understand the principles and algorithms of problem solving we will use a classic problem: to find the path between two points. In the figure below we show seven cities (from A to G), joined by the paths represented by the arrows and separated by the distance shown. For simplicity, each path is one way only. The problem is to find a way from city A to City G.
The central element of problem solving is the state of things in which we are in. In our example, the state is represented by the city in which we are located. In other cases it is represented by the position of the pieces on the board, by the set of components and connections in a circuit or, in the case of Dota 2, by the location of the 10 players, the inventory of items they have, as well as the location of structures, enemies, trees and all kinds of objects (OpenAI Five represents a state with 16,000 values).
Solving a problem is to find the sequence of possible actions that, from the initial state, allow us to transit between different states until we reach the goal state. As we will see later, if we incorporate a criterion to evaluate how close we are to the goal, this information helps us to decide what action to take in the current state.
Now, how to navigate between possible states? Over time many ingenious search algorithms have been invented that, with the power of today's computers, allow for systems like Dota 2 or navigation assistants. Next, we show some of the best known, each suitable to different circumstances.
- Breadth first search. If we represent our problem as a tree, this technique goes through each level in order, as the animation shows. It gets to the goal without evaluating whether it followed the best route.
- Depth first search. This algorithm explores completely each branch of the tree it opens. In some cases, it reaches the goal faster, but depends on the order of the nodes. It neither evaluates if it used the best route.
- Uniform Cost Search. It's like a depth first search, but it traverses first the branches with the lowest accumulated travel cost. It gets to the goal through the lowest cost route, although not in the fastest way.
- A* search algorithm. It works just like the uniform cost search, but to decide which branch to continue exploring it adds to the accumulated cost an estimate of how close we are to the goal (In our example the straight-line distance to the G city). It rapidly finds the best route to the goal, so it is one of the most used algorithms.
The search method is essential to avoid reviewing states that do not bring us closer to the goal, a critical issue in problems with millions and millions of possible states, whose exploration can take a long time even with the most powerful computers. That is why the development of search methods and criteria to evaluate proximity to the goal is a very active area of research of AI, which has produced interesting techniques. These include genetic algorithms, which generate new states (children) from the combination of two other states (parents) with a small change (mutation), or those that emulate the collective behavior of animals or insects.
Did you enjoy this post? Read another of our posts here.
