Originally posted by moonbus
The key is this: controlling more territory (and holding more prisoners) is the criterion for determining who has won the game, once they decide to stop playing. But that is not the criterion for deciding when to stop playing. The criterion for deciding when to stop playing is: when both sides believe they can no longer improve their positions. ...[text shortened]... ogram has not already calculated that it does in fact hold more territory (+ prisoners) ?
Regarding the ending of Go vs. chess: that's a good point you have there. The end result in Go is not clear until the score is counted. So when both players pass and end the game, the result is not yet known. However, at the point where both players pass, the end result is already determined, in the sense that the score follows from the final position in a deterministic way using the counting rules. Both players have perfect knowledge of the state of the game and could theoretically keep track of the score along the way. They should stop (pass) when they see no way to improve their score.
So, for a theoretically unlimited computer, there is no bigger challenge to solve Go than to solve chess. But practically, given the current state of hardware and software, this is indeed a challenging task as you mentioned. However, I disagree with the statement that formulating it in a finite approach is more challenging.
About AlphaGo: as far as I understood the way they approached the problem from reading several articles a while back, they have mainly focused on training a neural network with a bunch of master games and playing against itself. This neural network is used as a position evaluation, giving a score for each position. Similar to most chess computers, this is then used in a tree-search with finite depth. In chess, the concept of position evaluation is much simpler, taking e.g. material evaluation, king safety, mobility, pawn structure into account. Such a heuristic model for a position in Go is much harder for the reasons I mentioned in a earlier post, i.e. much larger branching factor meaning much more possible future positions. This increases the uncertainty associated with a limited horizon. In addition, a game of Go has more moves than in chess on average. Instead of a heuristic evaluation function, the developers of AlphaGo have opted for a large neural network, which does not contain any heuristics but is just trained (tuned) by studying many games.
About your questions: since AlphaGo constantly runs its search algorithms in combination with its neural network position evaluation, it has an estimate of the score of the game at any time. It is then relatively straightforward to detect that making a move does not improve its (estimated) score, by just considering "pass" as an additional move option throughout its search.