Sign In

Communications of the ACM

ACM TechNews

After 2,500 Years, a Chinese Gaming Mystery Is Solved

View as: Print Mobile App Share:
A Go gameboard mid-game.

Computer scientist John Tromp used servers to calculate the total number of legal positions on Go's 19x19 game board.

Credit: Jaro Larnos/Flickr

Computer scientist John Tromp discovered the total number of legal positions on Go's standard 19x19 board using servers at the Institute for Advanced Study's School of Natural Sciences, the IDA's Center for Communications Research, and Hewlett-Packard's Helion Cloud.

The software Tromp used was developed in 2005. By 2007, the researchers were able to compute the number of legal positions on a 17x17 board, which exhausted the hardware resources available at the time. Tromp provides the software he used on his GitHub repository, but it requires a server with 15 terabytes of fast scratch diskspace, eight to 16 cores, and 192 GB of RAM.

Although the leap from calculating the legal moves on a 17x17 board to a 19x19 board may seem small, each increase in the board's dimensions demands a fivefold increase in the memory, time, and disk space required, according to Tromp.

He plans to continue work on his "Cuckoo Cycle" proof-of-work system and solve large-scale Connect Four problems, and he is especially interested in improving similar work on chess. "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.

From Motherboard
View Full Article


Abstracts Copyright © 2016 Information Inc., Bethesda, Maryland, USA


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account