Distinguishing between humans and computers in the game of go

(Phys.org)—By analyzing the statistical features of thousands of go games played by humans and computers, researchers have found that it's surprisingly easy to tell whether a game is being played by a human or by a computer. The results point to fundamental differences in the ways that humans and computers solve problems and may lead to a new kind of Turing test designed to distinguish between the two.

The researchers, C. Coquidé and B. Georgeot at the University of Toulouse, and O. Giraud at the University of Paris-Saclay, have published a paper on their statistical analysis of go games played by humans and computers in a recent issue of EPL.

"We think our work indicates a path towards a better characterization and understanding of the differences between human and computer decision-making processes, which could be applied in many different areas," Giraud told Phys.org.

As the researchers explain, go is a particularly good platform to investigate how computers solve complex problems due to the vast number of possible moves a player can make at any turn. On a 19x19 go board, there are 10¹⁷¹ possible legal positions (compared to "just" 10⁵⁰ in chess). In addition, the number of possible games of go was recently estimated to be at least 10^{10^108}. Such numbers are gigantic even for a computer, making it impossible for any program to simply use brute-force methods to analyze all possible moves and games. Instead, computers must use more sophisticated approaches.

In the new study, the researchers constructed databases of 8000 games played by amateur humans; 8000 games played by the software Gnugo, which uses a deterministic approach; 8000 games played by the software Fuego, which uses a Monte Carlo approach; and 50 games played by the software AlphaGo, which has become famous in the past couple years for beating world champion human go players. The researchers then built networks for each database that capture information about the patterns of moves on the go board.

One of the most interesting results is that the networks based on software—especially Gnugo—have large numbers of "communities," which are parts of a network that are strongly linked within themselves but weakly linked to the rest of the network. As the researchers explain, the presence of these communities indicates that the software programs are creating many different types of strategies that are different from other types of strategies; that is, their strategies are varied and diverse. By comparison, the networks based on human games have fewer communities and more large hubs with lots of direct links, indicating that human strategies were more related to each other and less diverse.

While enlightening, these results are not unexpected, as they correspond to some previous observations of computers playing go. For instance, in 2016 and 2017, human analysts watching AlphaGo compete against world champions were often surprised and puzzled by the strategies that the computer used.

Overall, the researchers found that the statistical differences between the computer- and human-generated networks are much larger than the variability within each network, indicating that the differences are statistically significant and could potentially be used to distinguish between groups of human-played games and computer-played games. Further, the results show that it's not necessary to analyze thousands of games, as the differences could be significant even for the relatively small 50-game database from AlphaGo.

As a consequence, the researchers propose that the statistical differences could be used to design a new kind of Turing test, similar to the original test in which a person tries to tell whether they are interacting with a human or a computer by asking questions. The new version of the Turing test would involve playing go games instead of asking questions, and then performing statistical tests to identify characteristic features of human and computer players.

The researchers also expect that it would be interesting to use similar statistical methods to investigate the differences in how humans and computers approach other complex problems besides go. From this data, it may be possible to gain a better understanding of how computers "think."

"We would like to study in more detail the origin of the differences between the human-generated and computer-generated networks, to see how they reflect in terms of differences in strategies used in the game," Giraud said. "We are also planning to apply these techniques to other areas where computers and humans are present, starting with other board games such as chess."