On Wednesday the news broke that an artificial intelligence has finally cracked one of the most complex board games out there, Go. The announcement and subsequent paper from Google’s DeepMind showcases their brainchild, nicknamed AlphaGo. This computer program is not only capable of playing Go, but also defeated the European Go champion, Fan Hui back in October 2015. It is currently scheduled for a match against Lee Sedol in March, arguably the reigning world champion in the game.

If this story feels familiar, it’s because it is – IBM’s Deep Blue famously beat chess grandmaster Garry Kasparov back in 1997, launching artificial intelligence (AI) into the public consciousness and starting a great pursuit of computer programs that could beat humans at every conceivable game of skill. The team at DeepMind announced early last year they had develop another AI which could beat humans at a whole swathe of classic arcade video games, from pong to space invaders.

The game of Go itself has a deep appeal to the mathematically minded, from baseball-like in-depth player statistics, to convoluted mathematical models for player rankings, so it is no surprise that it would appeal as a challenge for designers of artificial intelligence. But what caught my attention amongst the media flurry, was this statement by Demis Hassabis, CEO of Google DeepMind in interview with Nature:

“Go is a very ancient game, it is probably the most complex game humans play, it has more configurations on the board that there atoms in the universe […]”.

These kinds of statements are often hard to wrap your head around. From intuition, it does not make any sense: I can sit at my desk with a standard 19×19 Go board and the 361 stones it takes to fill it, and very laboriously make every possible combination on the board. This way I haven’t used up all the atoms in the universe, only those for a single set of Go that I have in front of me.

Dealing with very large sums such as the number of atoms in the universe is a notoriously difficult thing to grasp intuitively. Let us begin by looking at the actual numbers. What is the number of possible configurations on a Go board? For the standard 19×19 board, there are 361 positions where the two players can place their stones. In Go, any given position can be either empty, a black stone or a white stone, meaning any of the 361 positions can be in one of 3 states. Thus, the number of possible board configurations is 3361, or to put it in more standard notation, 1×10172. Of those, only about 1×10170 are legal positions, in other words not violating the rules of Go. Surprisingly, the exact number of legal positions has been calculated as:

208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935

Which, I am sure you will agree, a rather large number indeed. Now, onto the universe. The usual number banded about is of 1×1082 atoms in the universe. In truth, any such estimate is made with some very strong assumptions. The typical approach an astrophysicist might take when thinking about this problem is to start with the number of stars in the universe. Computer simulations put that number at around 1×1023. Next we need to know how much stuff is in a star – based on the universe observable from Earth, each star weighs an average of 1×1035 grams. Next, a perhaps the most precise estimate in this equation, is that each gram of matter contains about 1×1024 protons. Finally, we can put all those numbers together:

1023 × 1035 ×1024 = 1082

Planets and other planetary bodies don’t make it into the calculation since stars are substantially more massive. So ultimately it is a very rough, back of an envelope estimate, which is probably in the correct region, give or take a few orders of magnitude.

Going back to the number of Go board positions, we can see that there is a massive difference between the two estimates. How can this be? The first way to conceptualise this is to think of not using a single Go board to make every combination, but to have many Go boards sitting side by side, each with a different combination of stones laid on top. As we established before, we would need 1×10172 individual boards to make every possible combination. How much room would that take? Laying them side-by-side in single file, the line of Go boards would measure 4×10168 km. For comparison, the diameter of the observable universe is about 1×1033 km.

Another helpful way to think about the problem is to consider how long it would take a person to set a single board to display every possible combination of stones. Let us assume a reasonable competent person can shift the stones to any new configuration in 20 seconds. Even better, let us assume we have a robot that can do the same, with the added advantage that it does not eat, sleep, or make mistakes. Starting with a blank board, how long would it take to complete every possible board combination? Using the values above, it would take 1×10163 years, on expressed fully:

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

That is not only a very long time; it is many times longer than the age of the universe, which is 13.8 billion (109) years old.

This astounding number of board combinations is often cited as one of the reasons Go is particularly fiendish game; while it is true that Go is very complex, we as humans constantly engage in games that have fantastical numbers of possibilities from poker (106 possible hands) to chess (1010^50 possible games). Even humble Connect Four has 1013 legal playing positions, and most 10-year-olds seems to manage just fine. We are certainly capable of dealing with exponential complexity, just not very good at thinking about it.

—————————————————————————————————

The AlphaGo story was widely reported across the general press, and more extensively in science reporting.

Advertisements