Games, an engine for Artificial Intelligence

Today, designing a machine capable of beating a human champion at a game is an important lever in the development of artificial intelligence. Resounding victories have been achieved, but certain frontiers, such as multiplayer mode, seem almost impassable.     

Key highlights:

Since the dawn of time, the formalization of games has always been a profound driving force for scientific research. Artificial intelligence has, very early in its history, used games as levers for its development. In 1979, a computer using a neural network dethroned a backgammon champion. Then it was the turn of chess, the TV game Jeopardy!, poker, and more recently the game of go. However, some games - such as bridge or the video game StarCraft - are still resistant to machines. Indeed, they contain too many parameters and uncertainties that the machine still cannot manage. Hidden information or a multiplayer mode, in which the computer doesn't know whether its actions are helping its teammates or its enemies, pose many difficulties. Many organizations, such as DeepMind or Facebook, have taken up the challenge of crossing this new, now impassable, frontier.

Since the dawn of time, the formalization of games has always been a profound driving force for scientific research. One thinks here naturally of the way in which games of chance, such as the throwing of dice or the observation of certain cards in a complete game, have served as a basis for the construction of probability theory, which finds its formalism thanks to the work of the Russian mathematician Andrei Kolmogorov. But we can also mention game theory, a theoretical discipline that allows us to understand (formally) situations in which the players, the decision-makers, interact. A game is then defined as a universe in which each decision maker has a set of possible actions, determined by the rules of the game. The outcome of the game depends then on the actions taken by each decision maker. We owe this theory to the brilliant mathematician John Nash. Artificial intelligence, very early in its history, used games as levers for its development. In 1979, a computer dethroned a backgammon champion, then it was the turn of chess, the American television game Jeopardy!, poker, and more recently the game of go. However, some games, such as bridge or the video game StarCraft, are still resistant to machines. Indeed, they contain too many parameters and uncertainties that the machine still cannot manage. But, of course, it's only a matter of time before the machine is able to handle them.           

The first successes

The first success of a machine against a player (success a little forgotten) dates back to 1979. The scene takes place in Monte-Carlo, during a backgammon championship. That year, a robot nicknamed Gammonoid had to face the winner of the world backgammon championship at the end of the competition held in the principality. The software is located thousands of miles away, at Carnegie-Mellon University in the United States. Calculations are therefore carried out remotely and transmitted via a satellite link, a real technological debauchery for the time. Gammonoid simply gives the results. The machine finally won 7-1 against Luigi Villa, winner of the Monte-Carlo championship. It is the first victory of an algorithm against a human champion, and the program already relies on a neural network, a tool which will allow, years later, a computer to beat a go player. But history did not remember this first victory. The first victory of a computer which marks the spirits is that of Deep Blue in 1997. Deep Blue, designed by IBM, defeated the then world chess champion Garry Kasparov. It is worth noting that, since then, computers have become more powerful. In 2006, it is a PC powered by a commercial software, Deep Fritz, which beats the Russian world champion Vladimir Kramnik. In 2011, another victory makes a little more noise, probably because of the notoriety of the game concerned. It is indeed a game of general knowledge that Watson, an artificial intelligence also created by IBM, will win. This game, called Jeopardy! is very popular in the United States. Created by Merv Griffin, Jeopardy! has been on American television since March 30, 1964. The principle is simple. Based on answers, contestants must guess the questions. The real change from past experience is that Watson does not know the answer to the presenter's questions. It's not enough to simply search or calculate quickly. He has to deduce it himself. Like his opponents, Watson does not have access to the Internet, but he does have an advantage: IBM admits that it has a cheat sheet equivalent to 200 million pages. This is no small feat, however. The questions, asked in natural language, must be analyzed by a myriad of algorithms, which extract the meaning and keywords. To the question "Wanted for the theft of a loaf of bread in Les Misérables", the answer had to be "Jean Valjean". Watson can then, as the rules of the game dictate, ask further questions for clarification, and all he has to do is explore his gigantic database. By winning 2 out of 3 rounds, Watson wins $1 million in Jeopardy! and achieves an unprecedented feat.

DeepMind and the game of go  

The artificial intelligence system that allowed Gammonoid to win at backgammon will be used again in 2016 for another game, that of go. Developed by Demis Hassabis and his company DeepMind, owned by the American giant Alphabet, the AlphaGo software clearly beats the European champion 5-0 that year and leaves only one victory to the Korean champion (4-1), Lee Sedol. To appreciate the size of the feat, the number of atoms in the universe is estimated at 10^80. The possibilities of moves in the game of go are 10^600, so we can understand the extent of AlphaGo's feat. The victory of an artificial intelligence in the game of go marks an important date, because it is a very complex strategy game. Experts, such as Elon Musk, thought that this result would not be obtained before 10 years. Another important victory takes place the following year. In January 2017, for 20 days, the artificial intelligence program Libratus, developed by Carnegie-Mellon University, plays poker in its most complex version, No-Limit Texas Hold'em, against 4 of the world's best players. After 120,000 games, the 4 champions are all beaten and lose $1.7 million against Libratus. As the players explain very well, what impressed them the most was Libratus' ability to learn very quickly, to change strategy in order to adapt to the attempts of its opponents, who are looking for flaws in its approach. In 2015, Claudico, the predecessor of Libratus, lost to 4 professional players, one of whom will also face Libratus. Within two years, artificial intelligence was catching up, taking power in poker and making a major leap forward. Artificial intelligence is not developed to play poker, but to be able to think strategically. It can therefore be used to solve many of the problems of the real world. Libratus was not developed for a single activity. For some, it marks the birth of what may very soon look like a strong artificial intelligence. In reality, we're not there yet. For example, some games are very resistant to machines, such as bridge, which is very difficult to play. There is some uncertainty, because the game of others is hidden. You have to explain your choices, the games are played as a team and, finally, it is difficult to know if our actions help our partners or our opponents more. Today it is scientifically impossible to manage all this data at the same time for a computer program. We find the same type of problem in the case of the video game StarCraft, where the parts of the territory that are not explored remain hidden from the players.

The new frontier           

Again, having to play as a team adds to the complexity. StarCraft is now on DeepMind's list, but also on Facebook’s. It symbolizes the new frontier for artificial intelligence, that of multiplayer video games. Several organizations have already launched themselves into the race, and OpenAI, a non-profit artificial intelligence research association, has recently distinguished itself. At the beginning of August 2018, a "team" of 5 neural networks knocked down professional players, in the flesh, to a simplified version of Dota 2, one of the most popular e-sports in the world. Yet Dota 2 is a nightmare for programmers. Each player controls a particular "hero" and must work with 4 teammates to destroy the opposing team. Only a small area around each hero is visible (incomplete information), with the rest of the battlefield to be explored. Each hero can decide to target an enemy or pursue a side quest. Every fraction of a second, thousands of actions can be chosen. The heroes encounter various objects (trees, buildings, etc.) or players (teammates or enemies), more than 20,000 observations to be analyzed in a fraction of a second. Finally, having a long-term strategy is crucial to winning, as an individual action has only a minor impact on the final victory. This new frontier seems almost impassable.