Hacker News Reader

Comment by arcanus | Hacker News Reader

Remarkable achievement, much more impressive than Chess, imo.

Not just in your opinion. The search space is exponentially larger in go because you can place a piece on any unoccupied square.

"The search space for Go's game tree is both wider and deeper than that of chess. It has been estimated to be as big as 10^170 compared to 10^50 for chess, making the normal brute-force game tree search algorithms much less effective. "

http://ai-depot.com/LogicGames/Go-Complexity.html

To provide a little more perspective. The estimated number of atoms in the observable universe is about 4*10^80. So we have no hope of ever being capable of "solving" go by mapping out every possible game state AKA "brute forcing" the game.

https://en.m.wikipedia.org/wiki/Shannon_number

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.

Not just in your opinion, Go is objectively much more difficult for computers than Chess.

I think being difficult "for computers" is a misleading concept. Go is more difficult for our current algorithms than chess, at least in part because we've focused on chess for much longer.

Sooner or later we may discover some new algorithm (this deep-neural-net-based approach may be it) which will reduce Go to be as tractable as chess, or even more so.

It was more difficult for computer programmers to program an ai which reach a human top level, and for this level you have to throw much more hardware in it.

Until it isn't. Once humans are handily beaten in both games, it's kinda hard to tell which game is harder (I guess you could compare the amount of computations needed to beat the top human player, but that does not let you distinguish if it's harder for computers or conversely easier for humans.)

Reply on news.ycombinator.com