News for hackers. Stuff that matters.
Re:Google achieves AI 'breakthrough' by beating Go champion by hackinthebochs on Wednesday January 27, 2016 @02:43PM (#10982507)
Personally I think its not nearly as impressive as state-space comparisons would have you believe. The initial difficulty in cracking Go was because we were using standard game AI techniques that works on games with a much smaller state space. Once we developed methods specifically for Go, we started making progress in leaps and bounds. But this doesn't represent fundamental progress in the AI of games, but rather a recognition of using the wrong tool for the job.

The difference between Chess and Go is critical here. I don't know if there's any formal analysis of this sort, but the difference seems to be that in Go multiple paths to the same board state are very similar in evaluation. And so sets of moves can be evaluated as a batch or stochastically. I think it was an algorithm that exploited this property that saw one of the first significant jumps in computer Go strength. Contrast this with chess where different paths to a given board state vary so widely in evaluation that you must evaluate them all. I suspect it is this property that allows Google's technique to be effective in evaluation positions. But I don't see it extending to games that aren't similar to Go in this regard, like chess.

Re:Google achieves AI 'breakthrough' by beating Go champion by mjmaher on Wednesday January 27, 2016 @04:02PM (#10983318)
> in Go multiple paths to the same board state are very similar in evaluation

Not at all, different paths to a board state also have widely varying evaluations in Go. Joseki is a great example of this, especially since these sequences have been thoroughly analyzed. In most joseki playing any move out of order will leave weakness and a skilled opponent will not just continue to play the pattern out of sequence.

Re:Google achieves AI 'breakthrough' by beating Go champion by gnarbarian on Wednesday January 27, 2016 @03:54PM (#10983229)
You're right of course. the branching factor of Go really only shows how much more difficult it is to blindly brute force than Chess. It's worth saying that neither game is close to being solved completely (as in mapping every possible game state). Creative techniques must be used in both games to cull out large chunks of the search space.

I definitely see how the more simplistic movement rules (and lack of variety of piece types) in Go would make it easier to cull off large swathes of the search space. Despite this my gut tells me that the branching factor is still the best benchmark we have (and easiest to convey) for comparing the computational difficulty of solving a board game with an adversarial search algorithm.