ADVERTISEMENT
See Inside June 2007

Silicon Smackdown

New Go algorithm aims to depose humans

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.

This is only a preview. Get the rest of this article now!

Select an option below:

Customer Sign In

*You must have purchased this issue or have a qualifying subscription to access this content


It has been identified that the institution you are trying to access this article from has institutional site license access to Scientific American on nature.com.
Click here to access this article in its entirety through site license access.

Rights & Permissions
Share this Article:

Comments

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Scientific American Special Universe

Get the latest Special Collector's edition

Secrets of the Universe: Past, Present, Future

Order Now >

X

Email this Article

X