Smith School Formula Helps Computer Triumph in 'Go'

SMITH BRAIN TRUST — A computer created by Google engineers knocked off one of the world's greatest human players of the Chinese game Go this week — a landmark in the development of artificial intelligence. In doing so, it made use of an approach to the computerized analysis of decision-making first developed at the Smith School and Maryland's engineering school.

It's been 19 years since Deep Blue showed that computers could beat a top grandmaster in chess. But Go, a 2,500-year old game in which white and black pieces are placed on a 19-by-19 board, is exponentially more complex even than chess. An average 150-move game contains 10¹⁷⁰ possible board configurations —far too many for even the most powerful computer to definitively examine before each move. So a Go-playing computer has to be fairly selective about which options to study, resorting to a more artful, even "human" approach to game play. (Deep Blue also used a degree of selectivity, but the approach becomes even more important in Go.)

Basically, AlphaGo makes a quick estimate of the likelihood that multiple moves will lead to victory, as well as the variability of those estimates. It then allocates its computational efforts to the moves with high levels of uncertainty (in tandem with high probability of victory). It explores those moves further down the "decision tree" into the future, in order to maximize the tradeoff between uncertainty and likelihood of victory. 

"From a big-picture view, this is the way humans think," says Michael Fu, Ralph J. Tyser Professor of Management Science at the Smith School. "We can't go down those decision trees in the same way a computer can— with brute computational force — so we make rough estimates and go a few moves ahead for several options."  (Unlike humans, AlphaGo can store millions of games that it has played against itself, drawing on that experience to hone its ability to identify winning moves.)

Fu, along with the engineering professor Steven I. Marcus, plus an engineering PhD student (Jiaquiao Hu) and an Institute for Systems Research Postdoctoral Researcher (Hyeong Soo Chang), published "An adaptive sampling algorithm for solving Markov decision processes" in the January-February 2005 issue of Operations Research. The algorithm was designed to be used in any situation involving complexity and uncertainty — for instance, when a company faces the choice of whether to increase the capacity of a semiconductor plant in response to a certain level of sales.   Other scholars later applied it to the world of games and A.I.

AlphaGo beat the Korean master Lee Se-Dol in a five-game series, 4-1.

See also: The engineering school's coverage.