The following article is a reproduction, and has been modified for this site. The original article, and many more, can be found at RemptonGames.com

In May 1997,World Chess Champion Garry Kasparov went face to face against his greatest challenger. That challenger’s name was Deep Blue, and it was a chess playing computer developed by IBM. Kasparov had already defeated Deep Blue in a best-of 6 match the previous year, but now it was back and better than ever. While it was a close match, Deep Blue ended up defeating the grandmaster 3.5 to 2.5, and forever cemented computers as the true masters of chess.

Who knew a machine could look so smug?

While this may have been shocking at the time, looking back this is not too surprising. Chess, at its core, is a highly regimented and deterministic game. Every game begins with the exact same layout of pieces on the board, white always goes first, and pieces move in very predictable ways. In addition, highly knowledgeable players tend to draw from a pool of established moves, particularly in the early and late game. This level of structure and predictability makes it a perfect candidate for a computer to conquer.

Since 1997, the computers’ hold on Chess has only gotten stronger. Processing speeds and memory capacity continue to increase each year, while the human hardware has remained pretty stable for thousands, if not millions, of years. These days computers are capable of looking much further ahead and analyzing future moves far more effectively than any human player could ever hope to.

Chess isn’t the only game we have lost to the machines either. Each year computers seem to become better and better at our favorite games, and are gaining ground one game at a time. At this pace it might seem inevitable that all games will eventually be conquered by computers, but is this really the case? Or are there some games that a computer could never master? Lets find out!

To answer this question I am going to be dividing computers into 5 levels, based on how “computable” they are. The lower the level, the easier a computer could conquer the game.

Regarding Digital Games

This discussion is mostly going to be focused on physical, tabletop games. While I may return to this topic at a later point and discuss digital games, I find that this question is hard to even define in a satisfying way when it comes to digital games. Digital games, by definition, are already running on a computer, and any AI that would play a digital game inherently needs access to some of the data in order to even act.

Deciding how much access the agent should have is very messy. If you limit their access to information you could be unnecessarily handicapping the AI, but too much access (such as allowing them to read their opponent’s keypresses) would be an unfair advantage. In general, I would say that computers have a major advantage in any sort of reflex based games (such as fighting games) because they can react much more quickly than a human opponent. As for strategy games, in many ways these can be treated similarly to a tabletop game of similar complexity.

Also, sometimes the computer cheats

Level 1 – Solved Games

Computers have level 1 games in the bag. These games are considered to be “solved”, which means that all of the possible moves have already been analyzed and computers have already determined strategies which guarantee that they will win (usually if they go first) or possibly draw.

For an example of a solved game, think of tic-tac-toe. Tic-tac-toe is a very simple game, with a very limited number of moves. There are only 9 squares, and each turn the number of possible squares decreases by 1. This means that there are a total of 9! (9 factorial) possible games of tic-tac-toe. If we count each of these games as being unique, that means that there are 362, 880 possible games of tic-tac-toe.

However, the real number is actually much lower, because this includes duplicate states such as reflections and rotations. For example – while your first move might seem like it has 9 possibilities, there are really only 3 – you can play in a corner, on a side, or in the middle. Which corner or which side you choose doesn’t really matter, so we can assume the real number is much lower.

Tic-tac-toe is such a simple game that most human players have solved it, and if you don’t make a mistake you should always end in a draw or “cat game”. Computers, however, have solved much more complicated games than this.

tic-tac-toe love

tic-tac-toe-mens-organic-t-shirt

tic-tac-toe-romantic

The only people who can’t seem to figure out this game are t-shirt manufacturers.

The most complicated game that has been truly solved so far is Checkers. Checkers was first solved back in 2007 by a team led by Jonathan Schaeffer, a computer scientist at the University of Alberta. While very effective Checker playing computers had been around for decades before this point, this team was the first to exhaustively analyze all possible playing positions in Checkers, and determine the outcome assuming optimal play.

This was no easy feat however. At its peak this project had around 200 desktop computers performing calculations, and the entire proof took 18 years to complete. While improvements in computing technology will certainly expand the horizon of what is solvable, it is likely that Checkers will hold the position of most complex solved games for a while.

Level 2 – Solvable Games

This category includes games that, while not currently solved, seem like they have all of the necessary criteria to be solved at some point in the future. At the moment this is where Chess stands. While computers have mastered Chess they have not yet solved it. However, it is unlikely to stay this way forever.

On the one hand, the complexity of Chess is far higher than any other game that have been solved up to this point. While estimates vary (and finding an exact measure for the computational complexity of a game is extremely difficult), the low end speculates that Chess is around 1,000 times as computationally complex as Checkers, and it could be far higher. This means that if it were to be solved it would likely take quite a long time, and need an immense amount of computing power.

That being said, it is still entirely possible. There is nothing about Chess that prevent it from being solved, given enough time and computing power. The rules are extremely precise and fixed, and while the number of possible moves is extremely high it is still finite. Given how prestigious such an accomplishment would be, I find it quite likely that Chess will be solved at some point in the future.

At which point we will invent new forms of Chess that make absolutely no sense out of spite

Level 3 – Theoretically Solvable Games

At this level I would place games that are theoretically solvable, but could never actually be solved given the constraints of a finite universe. These are games that you could design a computer program to start solving and try to figure it out, but the universe would explode before it ever finished.

It actually takes surprisingly little for a game to reach this point. As a perfect example, take the game Go. Go is a very old board game from ancient China, and has a very simple rule-set. The game is played on a 19 * 19 grid, and players take turns placing stones on the intersections of that grid. One player places white stones, the other places black stones. If you completely surround your opponents stones those stones are removed from the board, and the game ends when both players choose to pass their turn without taking an  action.

psshht….it doesn’t look THAT complicated…

Despite these simple rules this game has an incredibly high computational complexity, and an almost limitless amount of possibilities. Consider this – when White makes the first move in Chess they have 20 different possible moves – 8 pawns which can move either 1 or 2 spaces, and 2 knights that can each move 2 different ways. The first player in Go, on the other hand, has 361 possible moves, and the possibilities hardly decrease over time.

An average game of Go can take well over 100 moves, but I will use 100 as a conservative measurement for ease of calculation. If you consider that the average move has ~100 potential spots for a player to put their piece (once again, a conservative estimate) this puts the number of possible moves over a 100 move game at 10 to the 200, or 1 Googol squared. This is an absurd number of possibilities (for comparison, the number of particles in the universe is on the order or 10^86), and the true number is likely to be far, far larger than this.

Because of this enormous number of possibilities it is not simply unlikely that Go will be solved – it is absolutely impossible. There is simply not enough time or computational power in the universe to ever be able to calculate all of the outcomes.

For this reason, it was considered unlikely that computers would ever even be able to play Go at a professional level. However, this was proven to be incorrect with the invention of AlphaGo, which became the first computer to defeat a professional Go player in 2015. Since then, even more advanced Go playing computers have been designed. While this game may never be solved, it seems like that is not a strong enough criteria for a game to be unable to master it.

Level 4 – Unsolvable Games

In this category we look at games that do not meet the criteria to ever be solved by a computer. This includes games with random elements, hidden information, or social aspects that make it impossible to create an exhaustive database of outcomes (no matter how much computing power or time you had).

A great example of a game in this category is Poker, specifically Texas Hold’em (although much of this discussion will apply to other variants as well). There are numerous features about Poker that make it impossible to solve, and that also make it very difficult for a computer to play at a high level.

First, Texas Hold’em is not a deterministic game. It has elements of luck and randomness, so even if you make the choice that gives you the best chance of winning you will still end up losing a large portion of the time.

In addition, Poker has hidden information – you can see your own hand, but you cannot see everybody else’s. This forces you to make predictions about what you think they might have based on their behavior, and make the decision that will work best in the long run.

Finally, Poker is a game that is largely based on trying to read your opponent while preventing your opponent from reading you. The cards you actually have are often far less important than the cards your opponents think you have, and bluffing and intimidation are a large part of Poker strategy.

All of these aspects make this game quite difficult for a computer to play at a high level. While humans are extremely good at reading each other’s actions and expressions, this is a very difficult skill to teach to an AI. In addition, while computers can calculate the moves that have the highest probability of being successful on a purely mathematical level, in a game with real people the mathematically optimal move is not always the most effective.

All of these aspects make this game quite difficult for a computer to play at a high level. While humans are extremely good at reading each other’s actions and expressions, this is a very difficult skill to teach to an AI. In addition, while computers can calculate the moves that have the highest probability of being successful on a purely mathematical level, in a game with real people the mathematically optimal move is not always the most effective.

On the other hand, robots do have great Poker faces

All of these factors make it impossible to truly “solve” Poker, since there are an infinite number of variables that must be taken into account, and there is no such thing as the “best move” for any given situation.

While these games can never be solved by a computer, this still doesn’t mean that they cannot be played. There are a few AI programs, such as Libratus and DeepStack, that have successfully competed against professional Poker players in laboratory environments. However, despite this success I still think that computers have a long way to go before they can actually match the level of human players.

Without going into too much detail, in these tests the AI would usually face off against a fixed group of players over a long period of time (usually a few weeks) and play thousands of hands. This allowed the AI to specifically adapt itself to the strategies of the particular players it was playing against, while potentially leading to mental fatigue for the human players. These conditions give the computer a significant advantage, and do not match standard tournament conditions.

In professional Poker tournaments player must be able to adapt to a constantly changing environment as the number of opponents and types of opponents change over time. You will not have weeks to adapt to the strategies of particular players, and you will not be in fixed, laboratory conditions. We have yet to see a Poker playing AI that can truly succeed in these conditions.

Level 5 – Unplayable Games

If there are any games that robots will never be able to play at the same level as a human, it is probably games that rely on social interaction, cooperation, and creativity. While computers may be far better than people at calculating possibilities quickly, they are likely to never be as good at interacting with other people as we are.

Take a game such as Apples to Apples. This game requires players to think about the person who is currently judging, and determine which type of answer they would choose. Do they want funny answers? Ironic answers? Very serious and accurate answers? Answering these questions, and choosing an answer that fits, would be extremely difficult for a computer.

A robot playing Cards Against Humanity might be a little too on the nose

However, the ultimate unplayable category of games would probably be Role-playing games. These games rely on not only social interaction and storytelling, but on working together and using your abilities in interesting and creative ways. This is an area that people are fantastic in, but one that I cannot see computers matching for a very long time, if ever.

Until Next Time!

That is all I have for this week. If you enjoyed this article, check out the rest of the blog and subscribe on Twitter, Youtube, or here on WordPress so you will always know when I post a new article. If you didn’t, let me know what I can do better in the comments down below. And join me next week, where I will share a project I have been working on!