delanceyplace.com 06/01/07 - the complexity of go

• 0 COMMENTS

In today's excerpt - the Asian board game 'Go', regarded as the most complex board game in the world:

"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 seems to be computer science's Achilles' heel: humans can soundly beat the machines. ...

"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 3^N, 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 10³⁸; on the large board, about 10^170. Additionally, more stones do not ensure victory, and players must be able to consider local positions and the board as a whole. ...

"[Recent software developments have led to a new program called] MoGo, [which] demonstrated its abilities this past spring, vanquishing strong amateur players on nine-by-nine boards, and beating weaker ones on large boards.. So, [experts say] ending the reign of professional human Go players could occur in 10 years."