Menu
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 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?
907
1 Answer. 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.
It only makes sense to talk about an infinite family of problems as being NP-complete. For this reason games like chess cannot themselves be NP-complete, as they only have a finite (albeit unthinkably large) number of possible positions.
Both Chess and Go are strategy games. Both are worthwhile to learn and play. Go is simpler than Chess and yet more complex. Simpler because all pieces are the same, just black and white, and in Go the pieces do not move around the board.
“So Go is probably the most complex game ever devised by man. It has 10^170 possible board configurations, which is more than the numbers of atoms in the universe,” said study author and AlphaGo co-developer Demis Hassabis of Google DeepMind. The team's goal was to beat the best human players, not just mimic them.
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.
187
Even if Go is merely in P it could still be something horrendous like O(n^m) where n is the number of spaces and m is some (large) fixed number. Even being in P doesn't make something reasonable to compute.
22
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
