Photo courtesy of Owen Travis.
Owen Travis, ’24, began playing Go in middle school after a friend took him to the Evanston Go Club in Illinois. In 2016, the AlphaGo computer program beat top player Lee Sedol at the strategy board game and Travis, who remembers reading about the defeat, found himself interested in the intersection of Go and machine learning.
As a junior in the Computer Science Department at Princeton University pursuing a minor in statistics and machine learning, that interest in artificial intelligence and Go resurfaced when Travis began exploring topics for his independent work research paper. He reached out to Princeton’s Henry R. Luce Professor of Information Technology, Consciousness, and Culture of Psychology and Computer Science Tom Griffiths for ideas. Griffiths told Travis about how researchers in his lab were studying whether chess players make rational decisions about when to spend more time thinking through moves during a game. Travis teamed up with Griffith’s post-doctoral researchers Evan Russek and Bas van Opheusden (who now is an AI research scientist at Imbue) to dive into his project. “We proposed taking some of that work and looking into Go,” said Travis.
Go with your gut
Go originated over two millennia ago in China and is one of the oldest board games in the world. The game is played on a 19 by 19 square board, with one player using a set of black stones and the other, white stones. The goal is to surround territory on the board while preventing your opponent from doing the same. “There's some situations where the best move is really obvious from the beginning,” said Travis. Other situations may be tricky and require the player to spend some time thinking over a creative solution. “In that case, the move that you eventually play might be very different from the move you originally conceived, and you gain a lot of value from spending that time thinking.”
In order to measure the value of computation for different Go moves, Travis used an open source AI platform called KataGo. He established the value of added computation in differing Go positions by asking KataGo to generate a move after not doing much computation and then having the AI do extra computation and generate another move. Then he compared the strengths of the competing moves to see how much value the additional computation had added.
As the value of computation increases, Go players tend to spend more time on their moves. This chart shows the correlation of move time versus the value of computation. Courtesy of Owen Travis.
Next, Travis and his collaborators analyzed a huge dataset of human Go moves from the KGS Go Server, where people play timed games against opponents online. He evaluated how long players took to make moves in various positions and whether they spent more time thinking about their moves in positions where the value of computation was higher. Ultimately, Travis and his team found evidence that humans do spend more time making moves in positions where additional thought is valuable. “Human Go players aren't just good at finding the best moves,” said Travis. “They rationally allocate their resources.”
The resulting paper, Go with your gut? Determining the value of computation in the game of Go, earned Travis recognition as one of the Center for Statistics and Machine Learning’s 2024 Independent Work winners.
It’s a requirement for all students in the SML minor, but Travis said he’d recommend that undergraduates across campus take time to complete independent work. As a computer science student, Travis said it was sometimes challenging to form connections with faculty in such a large department. “Doing one-on-one independent work with Professor Griffiths allowed me to make a more personal connection with a professor, get more involved with the research, and meet other people in the lab doing really cool work.”