Is the board game “Go” NP complete?

Question

There are plenty of Chess AI's around, and evidently, some are good enough to beat some of the world's greatest players.

I've heard that many attempts have been made to write successful AI's for the board game Go, but so far nothing has been conceived beyond the average amateur level.

Could it be that the task of mathematically calculating the optimal move at any given time in Go is an NP-complete problem?

Answer 1

It's a common misconception that chess, GO is NP-hard. Generalized chess may be NP-hard. Chess has an 8x8 board, generalized chess has an nxn board with many pieces. The question is, given a certain position on an nxn board, will white win if both players play perfectly? There may be a "yes" answer and the certificate for NP might be a list of perfect moves for both players, but it's intractable to check if those moves by black are actually perfect. Maybe black has better moves so that white doesn't win. You can't check such a certificate in polynomial time.

Chess and Go are both EXPTIME complete. IIRC, Go has more possible moves, so I think it a higher multiple of that complexity class than chess. Wikipedia has a good article on the complexity of Go.