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.

> 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.

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.

I understand that the search space is larger, but how have you determined that it is exponentially larger than in chess?

The exponent is larger. That's what that means. It's not a simple doubling (quadratic) or linear increase in search space.

From the linked article above

"Some of the factors responsible for the game tree's enormity are shown below. (A comparison to chess is shown in brackets)

the size of the board : 19x19 (8x8)

the average number of moves per game is around 300 (80)

the average branching factor at each turn is around 235 (35)

players can pass"

It's been 10 years since I did the math for this in my AI class but a simplified example would be to compare the start of each game. a go player has 19^2 or 361 possible moves. then on the second turn there are 360 possible moves (since one space has been taken up by the first move) so after two moves there are 361*360 or 129,960 possible go board configurations.

a chess player is more restricted by the smaller size of the board and the way pieces are permitted to move. so there are a total of 16 possible pawn moves on the first turn plus 4 possible knight moves leaving 20 total moves available. On the second turn the second player is similarly resticted to 20 possible moves causing the total number of chess board configurations after two moves to be 400. Once more room opens up on the chess board the branching factor does increase a bit but it never comes close to the hundreds of potential moves at any step during a go game.

this "branching factor" is the key to the size of a search space. in chess it gets messy to calculate due to the variety of piece types and their allowable movements but it's easy to see that at any given board configuration there are fewer possible moves. to calculate the search space you multiply the number of potential moves at each step until every board configuration has been accounted for.

https://en.wikipedia.org/wiki/Branching_factor

You are forgetting KOs and super-KOs, as well as newly created spaces from captures.

I left out a metric ton of shit for the sake of making it easier to convey the concept.