Silicon Smackdown

New Go algorithm aims to depose humans
or subscribe to access the full article.

A decade ago IBM's chess program, Deep Blue, beat world champion Garry Kasparov in a six-game match. The event marked a milestone, forcing humans to yield dominance of yet another strategic diversion. Only the Asian board game Go seemed to be computer science's Achilles' heel: humans could soundly beat the machines. A new algorithm can now take on strong human players--and win.

Go has proved enormously difficult for computer programmers because of the game's deceptive complexity. The objective of Go is to stake out territory and surround an opponent by placing black or white stones on the intersections of a nine-by-nine or 19-by-19 line grid. Especially on the large board, the number of possible moves per turn is huge--200 on average for each midgame position compared with the several dozen possible in chess. There are also enormous branching factors. Given N positions on the board, the total number of possible game positions is 3N, because every position can be occupied by a black or white piece, or it can be empty. The total number of legal positions on the small board is about 1038; on the large board, about 10170. Additionally, more stones do not ensure victory, and players must be able to consider local positions and the board as a whole.

or subscribe to access the full article.
Buy Digital Issue $7.99
Print + Digital
All Access
$99.99 Subscribe
Rights & Permissions
Share this Article:


You must sign in or register as a member to submit a comment.

Email this Article