How many possible positions are there in Go?
The number of legal positions on a 19×19 Go board was computed exactly in 2016: 208,168,199,381,979,984,699,478,633,344,862,770,286,522,453,884,530,548,425,639,456,820,927,419,612,738,015,378,525,648,451,698,519,643,907,259,916,015,628,128,546,089,888,314,427,129,715,319,317,557,736,620,397,247,064,840,935 — a 171-digit number. That is why Go resisted computer play for twenty years after chess fell: the search tree is too large for brute force by an unbridgeable margin, so a program has to evaluate positions by pattern rather than by calculation. AlphaGo beat Lee Sedol in 2016, the same year the count was finished.
How the figure is arrived at
Not brute-force enumeration, which is impossible, but dynamic programming: count the legal configurations row by row, tracking only the information about the partial board that affects whether later rows can be legal. The computation took months of CPU time and several terabytes of storage, and its result was verified independently by computing modulo several large primes.
Other numbers and possibilities counts
- How many combinations does a Rubik's Cube have? 43,252,003,274,489,856,000 — about 43 quintillion
- How many ways can you shuffle a deck of cards? about 8 × 10^67
- How many possible chess games are there? about 10^120 games; about 4.8 × 10^44 legal positions
- How many combinations are there in the lottery? 292,201,338 for Powerball
- How many digits of pi have been calculated? about 202 trillion
- How many possible passwords are there? 6.6 quadrillion for eight characters — 540 sextillion for twelve
- How many Sudoku puzzles are there? 6,670,903,752,021,072,936,960 completed grids
- How many prime numbers are there under a million? exactly 78,498
Common questions
- How many possible positions are there in Go?
- about 2.08 × 10^170
- How is that estimated?
- Not brute-force enumeration, which is impossible, but dynamic programming: count the legal configurations row by row, tracking only the information about the partial board that affects whether later rows can be legal. The computation took months of CPU time and several terabytes of storage, and its result was verified independently by computing modulo several large primes.
Related pages
- How many combinations does a Rubik's Cube have? 43,252,003,274,489,856,000 — about 43 quintillion
- How many ways can you shuffle a deck of cards? about 8 × 10^67
- How many possible chess games are there? about 10^120 games; about 4.8 × 10^44 legal positions
- How many combinations are there in the lottery? 292,201,338 for Powerball
- How many digits of pi have been calculated? about 202 trillion
- How many possible passwords are there? 6.6 quadrillion for eight characters — 540 sextillion for twelve
- How many Sudoku puzzles are there? 6,670,903,752,021,072,936,960 completed grids
- How many prime numbers are there under a million? exactly 78,498
- How many people are there in the world? Living things and the natural world
- How many stars are there in the universe? Space and the universe
- How many countries are there in the world? Things people built
- How many bones are in the human body? The human body
- How many grains of sand are there on Earth? Living things and the natural world
- How many ants are there in the world? Living things and the natural world
Sources
- Calculated on this page — At One Place