8 ms·

One additional issue for computers is that humans don't play the game tree out to its conclusion - humans recognise winning and losing positions rather than pla

by ronaldx 12y ago

One additional issue for computers is that humans don't play the game tree out to its conclusion - humans recognise winning and losing positions rather than playing a much longer (perhaps infinite) prove-out game. A naive game theory strategy runs into a disasterous problem - the game tree is extensively longer than the 200 moves that a human will play. So, a computer has to recognise a winning position, in a heuristic way, as well as the best players do. But, even as a total beginner, it's easy to notice Go programs sometimes get the end-of-game scoring totally wrong. Once you've overcome this first problem, you've reduced Go to "just" a 200-move game tree.

hyperpape 12y ago
I don't know what you're trying to say. Monte Carlo based programs play out entire games, and evaluate them by scoring the end of the game--no heuristics needed for the evaluation, only for the playouts. And yes, they can accurately score a completed game.
- ronaldx 12y ago
  I'm trying to express why Go is a difficult problem to solve. I'm saying this (scoring, play-out) has been a difficult problem, which was not solved even a small number of years ago, and is still not considered straightforward. Even if it is solved correctly now, that's only a start. I would also note that Monte Carlo is by definition a heuristic method - it is statistical and not guaranteed to be optimal.
  - rockdoe 12y ago
    I would also note that Monte Carlo is by definition a heuristic method - it is statistical and not guaranteed to be optimal. So is the endpoint evaluation in chess programs. This isn't a difference between Go and the other games. (In fact, pretty much nothing in your original post is)
    - ronaldx 12y ago
      Anyone who has a modest understanding of chess can codify very simple rules for identifying a winning endgame. There are extensive wikipedia articles on what constitutes a winning endgame in chess, as the board simplifies towards the end of the game: https://en.wikipedia.org/wiki/Endgame_tablebase https://en.wikipedia.org/wiki/Endgame_tablebase says "All chess positions with up to 6 pieces have been solved" So, I disagree. Even if you don't count this as a theoretical difference, it is a practical difference.
      - rockdoe 12y ago
        Anyone who has a modest understanding of chess can codify very simple rules for identifying a winning endgame. The exact same thing can be done in go, scoring a finished game is trivial. The strength of the program simply isn't determined much by correctly identifying and scoring terminal positions, but the intermediate ones. And for both chess and go, one very much uses heuristics which are often wrong. If the heuristics were never wrong, you wouldn't have to do the tree search part at all. Endgame databases only have a tiny effect on the strength of chess programs (a common misunderstanding!) just because it's not very common for the game to be still "flippable" by the time they become relevant. In all the other positions, you need the heuristics. The situation for checkers on the other hand, is very different. There the endgame databases were critical for solving the game, but due to mandatory capturing rules the search space reduces much faster. Edit: Not sure why HN won't let me reply. But anyway: the error that you're both making is assuming that the positions in which humans stop and score are "endgame" or "finished" positions. That's not at all the case! A game is finished if there are no more legal moves besides filling one's own eyes. Counting at that point is trivial because all the life & death situations are "resolved". Monte Carlo programs play until those positions, not the ones where a human would stop the game. (if you now bring up seki, you get half a cookie)
        thinkpad20 12y ago
        It seems you've studied this more than me, so perhaps I'm just misunderstanding you, but it sounds like you are equating a finished game with endgame. Scoring a finished game is obviously trivial, but even when a small number of positions remain open on a Go board, the game tree is still combinatorically vast, and I don't think there are any "simple rules" for determining optimal play.
- asolove 12y ago
  I think the above is trying to say that the percentage of total possible trees that a human would bother considering is much lower in Go than most games, like chess. So the computational resources needed to do Monte Carlo and get results competitive with human players are much greater. But the poster is wrong in saying that this means computers need to use heuristics. Indeed, the recent breakthroughs in Go-playing programs come from removing heuristics that previously helped the programs prune the tree space and instead just using Monte Carlo to simulate all possibilities.
  - hyperpape 12y ago
    Actually, computers use relatively knowledge heavy playouts these days. http://lifein19x19.com/forum/viewtopic.php?f=18&t=9371 http://lifein19x19.com/forum/viewtopic.php?f=18&t=9371. There's a tricky balance, because incorporating too much knowledge/heuristic use can make the program miss good but surprising moves. Nonetheless, the trend seems to be heavy playouts.
    - sehugg 12y ago
      Yes, the strategy for rollouts (the rest of the game after you leave the currently explored tree) are still an area of research. The successful programs usually involve some sort of local shape matching or other heuristic, sometimes trained using ML techniques. One of the surprising results is that having stronger play between opponents in the rollout phase does not always equate with a successful search. Having a balanced strategy -- that is, one that does not introduce a bias for either player -- appears more important.
- rdtsc 12y ago
  > Monte Carlo based programs play out entire games Would that be pretty much impossible with Go on current hardware and software?
  - rockdoe 12y ago
    Not sure what you mean? That's exactly how go programs work today. They don't need to play out the games with an optimal strategy. Just an unbiased, sufficiently random one.
  - hyperpape 12y ago
    No, it's just 300 or so moves. It's an entire game, not an entire game-tree (all possible moves).
ama729 12y ago
> humans recognise winning and losing positions rather than playing a much longer (perhaps infinite) prove-out game. If true, does it mean a computer (or an Human) could win by just not conceding?
- DupDetector 12y ago
  No. "Conceding" means passing. If you don't pass, you have to play. If you play when the game is effectively over, you either play in your opponent's territory and get captured, or your own, which reduces your score. If you play in your own territory enough then you can actually end up losing your eyes, and then be captured.
  - rockdoe 12y ago
    I guess the remark comes from the "perhaps infinite" proof game. I don't know why they put "perhaps infinite" there as most Go rulesets have rules against repeating board positions.
    - bbaumgar 12y ago
      A mathematically established lower bound on the longest possible go game is 10^10^48 [1]. While this isn't infinite, it's certainly large enough to be considered infinite in practice. [1] http://en.wikipedia.org/wiki/Go_and_mathematics http://en.wikipedia.org/wiki/Go_and_mathematics
      - shasta 12y ago
        Of course there are situations in mathematics where the tightest proven bound is 10^10^48 and the conjectured value is 7.
        howeman 12y ago
        Sure, but that number is a lower bound, not an upper bound.

by ronaldx 12y ago

hyperpape 12y ago

I don't know what you're trying to say. Monte Carlo based programs play out entire games, and evaluate them by scoring the end of the game--no heuristics needed for the evaluation, only for the playouts. And yes, they can accurately score a completed game.

ronaldx 12y ago
I'm trying to express why Go is a difficult problem to solve. I'm saying this (scoring, play-out) has been a difficult problem, which was not solved even a small number of years ago, and is still not considered straightforward. Even if it is solved correctly now, that's only a start. I would also note that Monte Carlo is by definition a heuristic method - it is statistical and not guaranteed to be optimal.
- rockdoe 12y ago
  I would also note that Monte Carlo is by definition a heuristic method - it is statistical and not guaranteed to be optimal. So is the endpoint evaluation in chess programs. This isn't a difference between Go and the other games. (In fact, pretty much nothing in your original post is)
  - ronaldx 12y ago
    Anyone who has a modest understanding of chess can codify very simple rules for identifying a winning endgame. There are extensive wikipedia articles on what constitutes a winning endgame in chess, as the board simplifies towards the end of the game: https://en.wikipedia.org/wiki/Endgame_tablebase https://en.wikipedia.org/wiki/Endgame_tablebase says "All chess positions with up to 6 pieces have been solved" So, I disagree. Even if you don't count this as a theoretical difference, it is a practical difference.
    - rockdoe 12y ago
      Anyone who has a modest understanding of chess can codify very simple rules for identifying a winning endgame. The exact same thing can be done in go, scoring a finished game is trivial. The strength of the program simply isn't determined much by correctly identifying and scoring terminal positions, but the intermediate ones. And for both chess and go, one very much uses heuristics which are often wrong. If the heuristics were never wrong, you wouldn't have to do the tree search part at all. Endgame databases only have a tiny effect on the strength of chess programs (a common misunderstanding!) just because it's not very common for the game to be still "flippable" by the time they become relevant. In all the other positions, you need the heuristics. The situation for checkers on the other hand, is very different. There the endgame databases were critical for solving the game, but due to mandatory capturing rules the search space reduces much faster. Edit: Not sure why HN won't let me reply. But anyway: the error that you're both making is assuming that the positions in which humans stop and score are "endgame" or "finished" positions. That's not at all the case! A game is finished if there are no more legal moves besides filling one's own eyes. Counting at that point is trivial because all the life & death situations are "resolved". Monte Carlo programs play until those positions, not the ones where a human would stop the game. (if you now bring up seki, you get half a cookie)
      - thinkpad20 12y ago
        It seems you've studied this more than me, so perhaps I'm just misunderstanding you, but it sounds like you are equating a finished game with endgame. Scoring a finished game is obviously trivial, but even when a small number of positions remain open on a Go board, the game tree is still combinatorically vast, and I don't think there are any "simple rules" for determining optimal play.
asolove 12y ago
I think the above is trying to say that the percentage of total possible trees that a human would bother considering is much lower in Go than most games, like chess. So the computational resources needed to do Monte Carlo and get results competitive with human players are much greater. But the poster is wrong in saying that this means computers need to use heuristics. Indeed, the recent breakthroughs in Go-playing programs come from removing heuristics that previously helped the programs prune the tree space and instead just using Monte Carlo to simulate all possibilities.
- hyperpape 12y ago
  Actually, computers use relatively knowledge heavy playouts these days. http://lifein19x19.com/forum/viewtopic.php?f=18&t=9371 http://lifein19x19.com/forum/viewtopic.php?f=18&t=9371. There's a tricky balance, because incorporating too much knowledge/heuristic use can make the program miss good but surprising moves. Nonetheless, the trend seems to be heavy playouts.
  - sehugg 12y ago
    Yes, the strategy for rollouts (the rest of the game after you leave the currently explored tree) are still an area of research. The successful programs usually involve some sort of local shape matching or other heuristic, sometimes trained using ML techniques. One of the surprising results is that having stronger play between opponents in the rollout phase does not always equate with a successful search. Having a balanced strategy -- that is, one that does not introduce a bias for either player -- appears more important.
rdtsc 12y ago
> Monte Carlo based programs play out entire games Would that be pretty much impossible with Go on current hardware and software?
- rockdoe 12y ago
  Not sure what you mean? That's exactly how go programs work today. They don't need to play out the games with an optimal strategy. Just an unbiased, sufficiently random one.
- hyperpape 12y ago
  No, it's just 300 or so moves. It's an entire game, not an entire game-tree (all possible moves).

ama729 12y ago

> humans recognise winning and losing positions rather than playing a much longer (perhaps infinite) prove-out game. If true, does it mean a computer (or an Human) could win by just not conceding?

DupDetector 12y ago
No. "Conceding" means passing. If you don't pass, you have to play. If you play when the game is effectively over, you either play in your opponent's territory and get captured, or your own, which reduces your score. If you play in your own territory enough then you can actually end up losing your eyes, and then be captured.
- rockdoe 12y ago
  I guess the remark comes from the "perhaps infinite" proof game. I don't know why they put "perhaps infinite" there as most Go rulesets have rules against repeating board positions.
  - bbaumgar 12y ago
    A mathematically established lower bound on the longest possible go game is 10^10^48 [1]. While this isn't infinite, it's certainly large enough to be considered infinite in practice. [1] http://en.wikipedia.org/wiki/Go_and_mathematics http://en.wikipedia.org/wiki/Go_and_mathematics
    - shasta 12y ago
      Of course there are situations in mathematics where the tightest proven bound is 10^10^48 and the conjectured value is 7.
      - howeman 12y ago
        Sure, but that number is a lower bound, not an upper bound.