6 ms·

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

by 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.
  - thesteamboat 12y ago
    As it turns out, Go endgames are surprisingly tractable with clever mathematics. See for example http://senseis.xmp.net/?MathematicalGo http://senseis.xmp.net/?MathematicalGo
- sehugg 12y ago
  I wouldn't say scoring is trivial -- it depends on both players agreeing which stones are alive or dead. Experienced Go players "just get it" but computers don't: http://www.andromeda.com/people/ddyer/go/scoring-games.html http://www.andromeda.com/people/ddyer/go/scoring-games.html
  - rockdoe 12y ago
    Scoring is trivial - if the game is actually finished. No human wants to play go games to the finish so essentially all human games are scored by agreement. But a Monte Carlo program just simulates the game vs itself. See the addenum to my post above.
    - howeman 12y ago
      I don't know what you mean by "the game is actually finished". AGA Rules: 9) Ending the Game: Two consecutive passes signal the end of the game. New Zealand rules: The game is finished when both players agree that there are no more worthwhile moves.
      - rockdoe 12y ago
        Those rulesets weren't written by mathematicians. What do they say about life & death disputes while scoring "after the game has ended"? I'm going to guess: Resume the game. Humans agreeing on a score and outcome has little to do with what a program has to do to calculate this score.
        howeman 12y ago
        It's complicated. Most rulesets (AGA, New Zealand, I believe chinese) say "resume the game". The Japanese ruleset is a lot more complicated. I still don't see your argument. Humans and humans are capable of agreeing on a score with those rulesets. Computers are also capable of following the ruleset and agreeing on the score. Computer vs. human games are not playing by a different ruleset. By that ruleset, the game is over when both sides pass.
  - deleted 12y ago
- stcredzero 12y ago
  Edit: Not sure why HN won't let me reply I've also encountered this bug. Please bring it up with dang.
  - DanBC 12y ago
    It's not a bug. It is a delay on replying to nested comments. Click the [link] link to get a reply box quicker.

by ronaldx 12y ago

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.
- thesteamboat 12y ago
  As it turns out, Go endgames are surprisingly tractable with clever mathematics. See for example http://senseis.xmp.net/?MathematicalGo http://senseis.xmp.net/?MathematicalGo
sehugg 12y ago
I wouldn't say scoring is trivial -- it depends on both players agreeing which stones are alive or dead. Experienced Go players "just get it" but computers don't: http://www.andromeda.com/people/ddyer/go/scoring-games.html http://www.andromeda.com/people/ddyer/go/scoring-games.html
- rockdoe 12y ago
  Scoring is trivial - if the game is actually finished. No human wants to play go games to the finish so essentially all human games are scored by agreement. But a Monte Carlo program just simulates the game vs itself. See the addenum to my post above.
  - howeman 12y ago
    I don't know what you mean by "the game is actually finished". AGA Rules: 9) Ending the Game: Two consecutive passes signal the end of the game. New Zealand rules: The game is finished when both players agree that there are no more worthwhile moves.
    - rockdoe 12y ago
      Those rulesets weren't written by mathematicians. What do they say about life & death disputes while scoring "after the game has ended"? I'm going to guess: Resume the game. Humans agreeing on a score and outcome has little to do with what a program has to do to calculate this score.
      - howeman 12y ago
        It's complicated. Most rulesets (AGA, New Zealand, I believe chinese) say "resume the game". The Japanese ruleset is a lot more complicated. I still don't see your argument. Humans and humans are capable of agreeing on a score with those rulesets. Computers are also capable of following the ruleset and agreeing on the score. Computer vs. human games are not playing by a different ruleset. By that ruleset, the game is over when both sides pass.
- deleted 12y ago
stcredzero 12y ago
Edit: Not sure why HN won't let me reply I've also encountered this bug. Please bring it up with dang.
- DanBC 12y ago
  It's not a bug. It is a delay on replying to nested comments. Click the [link] link to get a reply box quicker.