Richard Lorentz (left) discusses abstract game theory with a colleague in Jena, Germany.
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 of Engineering and Computer Science’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. Lorentz and the university’s other six research fellows will be presenting their research at an event in the fall.
“This is an ongoing project I’ve been working on for years and will continue for years,” said Lorentz, who has been teaching at California State University, Northridge for 25 years. He earned a bachelor’s degree in math at Claremont McKenna College and his doctorate in computer science from Washington State University.
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 each possible move, the opponent’s possible responses and the potential damage. 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 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 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 said.
The catch is that no one knows why it performs so well. “Monte Carlo tree search does better than we think it should,” he explained.
Lorentz has been studying variations of the MCTS algorithm, 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 mundane, could eventually prove transformative. “My ultimate goal is solving the mystery of why MCTS is working so well,” he said.
—Sarah Lifton, College of Engineering and Computer Science
