Game over: program developed by SEAS alumnus wins human-versus-computer strategy competition
Score one more for the computers.
In 1997, Deep Blue outmaneuvered Garry Kasparov in a legendary game of chess. Fourteen years later, Watson clobbered Ken Jennings and Brad Rutter in a historic “Jeopardy!” match. And now, Bot_Sharp has been crowned the first computer-program champion in an annual human-versus-machine strategy game competition.
The victorious program, designed by David Wu, A.B. ’11, defeated three human opponents in the Arimaa Challenge, an annual online tournament that pits the best human players against computer programs in a series of head-to-head matchups.
Arimaa (pronounced Ah-REE-ma), a strategy board game that is played with a standard chess set, was invented in 2003 by computer engineer Omar Syed, who sought to create a game that would be simple for humans to master, but much more difficult for computers to play well. Players maneuver six different kinds of pieces around the board, while pushing, pulling, freezing, or capturing the pieces of their opponent. The first player to move one of his or her weakest pieces (called rabbits) across the entire board wins.
“It turns out that Arimaa has been fairly computer-resistant since it was developed – a lot more so than chess,” Wu said.
Wu discovered Arimaa while he was a Harvard student. Designing computer games had been a longtime hobby for the computer science concentrator, who learned the basics of programming while he was in high school. Fueled by his competitive spirit, he set out to design a program that could defeat the best human Arimaa players.
To make his program play well, Wu employed many of the same efficient search algorithms developed years earlier for games like chess. These algorithms explore the outcomes of all possible sequences of moves to choose one likely to lead to the best result. Wu developed a variety of enhancements to hone the search, guiding his program to focus on the most promising possibilities and discard those less likely to be successful, in the same way that human players concentrate on the most important tactics for a specific game situation, while paying little attention to other moves.
He initially entered his program in the Arimaa Challenge in 2008. Over the next seven years, he continued to tweak the program, refining the algorithms and testing Bot_Sharp against computerized opponents.
“I had a lot of fun thinking about the algorithms and the technical details that actually contributed to the strength of my program,” Wu said. “Plus, like with any good game, winning does take a little bit of luck. By luck, one of the experiments I tried this year led to a huge improvement.”
He entered the 2015 competition feeling confident, but never expected to win so decisively. Wu’s program soundly defeated three top human opponents in best-of-three matches (the program finished 7-2 overall). In addition to taking home the Arimaa Challenge title, he received a $12,000 prize and submitted a paper to the journal of the International Computer Games Association.
Despite his program’s victory, Wu doesn’t think the popularity of Arimaa will wane.
“Players are still learning and refining their strategy, so there is a substantial chance that a human player could reach the top again,” he said. “Five years from now, the set of things people know about Arimaa will have expanded greatly.”
Now, Wu is working to increase the game’s popularity. He and several other Arimaa players are designing a more robust website for the game and its annual tournament. Wu hopes that his success will inspire more players to take an interest in Arimaa.
For Wu, who works as a software programmer in New York City, developing the program was an entertaining outlet for his creativity. Fresh off his triumph in the Arimaa Challenge, he is still contemplating whether he’ll set his sights on mastering a new strategy game or focus on a different creative project.
“With programming, I enjoy seeing the variety of things I can create,” he said. “That’s what attracted me to the field in the first place—I can immediately use what I learn to create something entirely new.”