It’s all just a game for CECS research fellow

Richard Lorentz

Computer science professor Richard Lorentz takes his games seriously. But you won’t find him glued to a PlayStation or engrossed in the latest version of The Sims. In Lorentz’s world, games are an outstanding vehicle for testing computer algorithms, and as the college’s 2011-12 research fellow, he’ll be spending the spring semester studying the merits of different algorithms in computerized versions of three lesser-known board games: Amazons, Havannah and EinStein würfelt nicht.

“This is an ongoing project I’ve been working on for years and will continue for years,” he says.

His project focuses on algorithms called minimax and Monte Carlo tree search (MCTS). In the past, most computer board games relied on minimax, which arrives at the best move by considering the player’s possible options, the opponent’s possible responses, the player’s responses to these responses, and so on, eventually accessing the potential advantage each move will provide the player. While it worked well in games like chess, for complex games like the classic Japanese game Go, it created a hopeless bottleneck. MCTS, by contrast, plays many random games, and the move that does best across the random games is the one the player—in this case a computer—is “happiest” with.

The difference between the two algorithms is striking. Before the discovery of MCTS about six years ago, someone who had been playing Go for four or five months could beat the best computer games. Using MCTS, however, a computer can play Go at the level of the top club players. “MCTS has revolutionized a lot of games,” Lorentz says.

Richard and Nohannes Waldmann discussing abstract game programming in Ingo Althofer’s apartment, Jena, Germany.

The catch is that no one knows why it performs so well. “Monte Carlo tree search does better than we think it should,” he explains.

Lorentz has been studying variations of the MCTS algorithm for some time, and his Amazons program, a blend of minimax and MCTS, is the current world champion. For his research project, he will expand his investigation to additional games, in collaboration with students, who will learn the algorithms, how to implement them efficiently and modify them for the task at hand—skills they can adapt to the workplace whenever they need to implement an algorithm they are unfamiliar with.

Lorentz’s own aim, while less pragmatic, could eventually prove transformative. “My ultimate goal is solving the mystery of why MCTS is working so well,” he says.