After 2,500 Years, a Chinese Gaming Mystery is Solved
Source: Hilbert
Go is an old game where, broadly speaking, players take turns placing white and black pieces on a board in an attempt to surround the most empty territory on the playing field. The earliest known reference to it dates back to China in the 5th century B.C., which means people were playing it along the shores of the Yangtze before the Parthenon cast its shadow over Athens. At once simple and complex, it's known for the high degree of versatility its gridded playing surface offers, and for years—centuries, even—some players assumed the number of legal positions must be infinite on the game's standard 19x19 boards. But that's not exactly true, as computer scientist John Tromp revealed last week. There's just a friggin' lot of them.
Specifically, Tromp discovered this is the number of legal ways you can use the board's 361 points with the black and white playing pieces and empty spaces:
2081681993819799846
9947863334486277028
6522453884530548425
6394568209274196127
3801537852564845169
8519643907259916015
6281285460898883144
2712971531931755773
6620397247064840935
That's hardly the kind of thing you can figure out with pen and paper. As one Reddit user pointed out in reference to Tromp's earlier work, that's bigger than the total number of observable atoms in the universe.
Tromp started the calculations back in March 6 of last year, with the help of staff and big servers at both the Institute for Advanced Study's School of Natural Sciences and the IDA's Center for Communications Research in Princeton, New Jersey, along with some help from Hewlett-Packard's Helion Cloud.
"The software was developed mostly in 2005, so from then we had the ability to attempt it, but not the required hardware resources," Tromp tells me in an e-mail. "By 2007, we (me and Michal Koucký) were just able to compute the number of legal 17x17 positions, and that exhausted the resources available at the Dutch Centre for Mathematics and Computer Science where I worked."
Want to double-check his work? Tromp provides the software he used on his github repository, but he cautions that you'll need "a beefy server with 15 TB of fast scratch diskspace, 8 to 16 cores, and 192 GB of RAM."
Indeed, for years the available technology held him back, limiting him to calculating boards beneath 19x19 grid standard. The leap from 17x17 to 19x19 may not seem like much, but Tromp emphasizes that each increase in the board's dimensions demands a fivefold increase in the memory, time, and diskspace required.
Tromp unsuccessfully tried to get "dozens" of companies, people, and institutions like Amazon and Google to sponsor his quest to borrow the hardware to calculate the results for a 19x19 board, but the winning ticket dropped in 2014 when fellow Dutchman Piet Hut, an astronomer at the Institute for Advanced Study, came through with an offer. After Tromp and friends achieved some notoriety for figuring out the number of legal positions on an 18x18 board, the right folks jumped on board for the final push.
So after solving a mystery that's been unsolved for 2,500 years, what's next? Tromp tells me he plans to continue work on his "Cuckoo Cycle" proof-of-work system and solve large-scale Connect Four problems, but he's especially interested in improving his similar work on chess. Chess, though, is a different beast.
"The situation is very different with chess, in that we'll never know the exact number," he says. "Right now we don't even know the order of magnitude. I want to get to the point where we can at least say: the number is between 10^44 and 10^45."
Which leaves the question of why?
"Having the ability to determine the state complexity of the greatest abstract board game, and not doing it, that just doesn't sit right with me," Tromp says. "Or, as the great mathematician Hilbert proclaimed, 'We must know — we will know!"
| }
|