The Googol Game
There’s a game I came up with a year ago to demonstrate some of the current failures of Artificial Intelligence (AI) systems. I call it the Googol Game.
The Googol Game
The Googol Game is as follows: You pick any number between one and one googol. (One googol is 10¹⁰⁰ and can be written as a 1 followed by 100 zeros.) We repeat this process three times. If you pick the number 5 every single time, you win.
Now to you, a human, this game probably seems really simple. Just pick 5 three times in a row, and you win. But for many of the AI algorithms today, this game is too complex for the computer to figure out how to win.
Why? Because most games are represented inside the computer as a “tree”. For example, let’s take a look at the game Tic Tac Toe.
How AIs Work
As we can see, each move the AI could make creates a new “branch” of the tree. The image only shows the part of the tree for 3 of the 9 possible first moves that could be made, and also doesn’t show many of the second moves, that could be made, but hopefully you get the idea.
To play through a game, the AI follows a branch all the way down to the bottom, where either one of the players has won, or the game is a tie. At this point, the AI is given a number, describing how “good” that game was for it. For example, if the AI was playing as X, and X lost, it might receive the number -1. But if the AI was playing as O and O won, it might receive a positive 1. I say “might” because it’s up to the programmer what numbers are assigned to the “value” of that game, but the idea is that winning should have a higher value than losing.
This is how many of the current AIs understand games. They see them as a tree with options they can follow, and at the end is some value. They’re trying to play the game in order to maximize the value at the end.
For example, simple algorithms such as Minimax solve the game by looking at every single branch and ensuring that the move the computer makes is the worst for its opponent (and therefore, the best for itself). More complex algorithms such as AlphaZero (which can play Chess, Go, and Shogi) play through many many games (over 10 million) and then learn to predict the value that each move will lead to. They then pick the move they think will lead to the best value.
Why is this bad?
If AIs represent games as trees and they always start at the top of the tree, they’re going to have a hard time playing games where there are lots of options and very few ways to win. This is known as the Sparse Rewards Problem.
Imagine the computer trying to play the Googol Game. For the first move, there are a googol different options! Which one should it take? It doesn’t know, and it won’t know how well it did until it plays out a full game. What are the chances that it picks the one correct option and actually learns how to win the game? Well, there are 10¹⁰⁰ options for each move, 3 moves, and only 1 way to win, so the answer is 1/(10¹⁰⁰)³. (Note that (10¹⁰⁰)³ is 1 followed by 300 zeros.)
So, as you can see, it would be nearly impossible for Minimax or AlphaZero to learn to play a game like this. In fact, even newer AIs such as Agent57 (which plays better than humans on every single Atari game) which try to explore different moves in order to solve the Sparse Rewards Problem, would likely not be able to win at the Googol Game. Internally, the computer still sees the game as a tree and starts at the beginning, having no idea what moves are good or bad.
It can get worse.
Imagine the Googol Game, but instead of picking a number between 1 and 10¹⁰⁰, you instead picked a number between 1 and 2^(8 billion). Again, if you pick the number 5 three times in a row, you win. The way we currently program many AIs, most of them would not be able to even play this game, much less win. Why? Because most computers run their entire system on at most 8 GB of RAM. (RAM is the quickly accessible storage that computers use while running programs.) 8 GB is 8 billion bits. So, to even store the number 2^(8 billion) would take up all the memory of the system.
For example, note that if you type 2^(8 million) into WolframAlpha, it gives you some cool stats. But as soon as you type 2^(8 billion) into WolframAlpha, it says it doesn’t understand your query, because the number is so big, the computers running the site don’t know what to do, so it displays that message instead.
However, once again, humans can both understand and play this game just fine. AIs can’t even simulate a single move.
What can we do?
I’m not sure, which is the main reason I’m writing this.
I think the issue is not necessarily that the AI algorithms that we’ve created are bad, but that the tree representation of games can be really bad for AIs learning how to play them.
In other words, I think that representing every game as a tree is the problem, and that we should look into other ways of getting computers to understand the rules of a game.
I’m currently inspired by IBM’s Neuro-Symbolic Concept Learner that would represent games as a modifiable database, rather than as a tree. (Explanatory video here.) But I still think there’s lots of work to be done in this area.
Another problem may be that we’re not communicating human-known information about the game to the AI effectively. For example, when playing a game like Super Mario Bros, humans are told what buttons to press in order to make Mario move and jump, and generally know that angry-looking enemies are bad, etc. However, AIs have to discover this all from scratch.
Along these lines, I’m optimistic about algorithms like this one that use English to guide the computer towards actions that may help it win. I also am curious about research like this that’s about how well humans can guess how to play a game based on how the game looks and works. (Explanatory video here.)
Finally, even if we do use the tree representation of the game, it might be good to come up with algorithms that don’t start at the top of the tree — instead somehow starting at the bottom of the tree and working their way up. I noticed that when I was trying to figure out how I think about playing the Googol Game, I usually start off thinking something like “I know I need to end up picking 5 three times by the end of the game. So in order to do that I should pick 5 for the first move.” That is, I plan my moves based on the specific end state I want to be in. This is unlike many AIs that are unaware of what end states are even possible until they play through the entire game.
What You Can Do
Help us programmers and researchers solve this problem! Leave a comment about how you approach playing games — maybe it will help someone figure out how to build a better AI.
As always, I want to hear from you.
[1] By Traced by User:Stannered, original by en:User:Gdr — Traced from en:Image:Tic-tac-toe-game-tree.png, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1877696
