4 ms·

Perhaps they meant that only certain "stalemates" are computationally infeasible with their ethereum platform? There are stalemates where it is impossible to ch

Perhaps they meant that only certain "stalemates" are computationally infeasible with their ethereum platform? There are stalemates where it is impossible to checkmate the King, but where the players can just keep making moves indefinitely.

mikeash 10y ago
Those aren't stalemates, technically speaking. Such a game would end either when the players both realized it's pointless and agreed to a draw, or when it's gone on long enough for the same position to repeat three times, and one player claims a draw. The second case may well be computationally infeasible too, since it would involve keeping and searching the entire history of the game.
- oli5679 10y ago
  Edit - I suppose it is a draw rather than a stalemate Fide Rules 5.2 (B) The game is drawn when a position has arisen in which neither player can checkmate the opponent’s king with any series of legal moves. The game is said to end in a ‘dead position’. This immediately ends the game, provided that the move producing the position was legal. (See Article 9.6)
  - mikeash 10y ago
    Oh yes, I was thinking of a case where checkmate is theoretically possible, but where your opponent can thwart it indefinitely with good play. But as you say, that's a draw rather than a stalemate. Which is not a particularly important distinction, I will admit!
    - oli5679 10y ago
      No worries.. Programming all the draw scenarios in chess wouldn't be completely trivial. If you add clocks to the game then you also need to account for when you flag but your opponent cannot win the game with legal moves. There are some strange edge-cases here for pawns vs minor pieces. Example: https://www.chess.com/forum/view/livechess/draw-by-insufficient-material2 https://www.chess.com/forum/view/livechess/draw-by-insuffici...
    - Scarblac 10y ago
      The starting position is probably "a case where checkmate is theoretically possible, but where your opponent can thwart it indefinitely with good play".
      - mikeash 10y ago
        Heh, indeed. I think what I meant was that your opponent can thwart it, in practice, given the actual abilities of both players. Things like the 50 move rule and the repetition rule are ways to detect this condition without actually having to figure out a way to analyze their abilities to decide whether a position is practically unwinnable.
  - Scarblac 10y ago
    Yes, that one is quite hard to get right for normal chess engines too, and it usually isn't done. E.g. if both sides have only a bishop left, then if the two bishops are on squares of the same color checkmate isn't possible, but if they are on different colors then checkmate is possible in a corner. Or pawn formations in the middle of the board that prevent breakthroughs. Most online chess sites only consider the obvious case of king + bishop or knight vs king to be a draw under that rule (and king v king, obviously).
- aweinstock 10y ago
  Searching the history to enforce the threefold repetition rule[1] wouldn't be efficient, but the fifty-move rule[2] could be pretty cheaply implemented (one cell of state for a counter, an increment-and-check per move, and resetting the counter to 0 on the relevant moves). [1]: https://en.wikipedia.org/wiki/Threefold_repetition https://en.wikipedia.org/wiki/Threefold_repetition [2]: https://en.wikipedia.org/wiki/Fifty-move_rule https://en.wikipedia.org/wiki/Fifty-move_rule

mikeash 10y ago

Those aren't stalemates, technically speaking. Such a game would end either when the players both realized it's pointless and agreed to a draw, or when it's gone on long enough for the same position to repeat three times, and one player claims a draw. The second case may well be computationally infeasible too, since it would involve keeping and searching the entire history of the game.

oli5679 10y ago
Edit - I suppose it is a draw rather than a stalemate Fide Rules 5.2 (B) The game is drawn when a position has arisen in which neither player can checkmate the opponent’s king with any series of legal moves. The game is said to end in a ‘dead position’. This immediately ends the game, provided that the move producing the position was legal. (See Article 9.6)
- mikeash 10y ago
  Oh yes, I was thinking of a case where checkmate is theoretically possible, but where your opponent can thwart it indefinitely with good play. But as you say, that's a draw rather than a stalemate. Which is not a particularly important distinction, I will admit!
  - oli5679 10y ago
    No worries.. Programming all the draw scenarios in chess wouldn't be completely trivial. If you add clocks to the game then you also need to account for when you flag but your opponent cannot win the game with legal moves. There are some strange edge-cases here for pawns vs minor pieces. Example: https://www.chess.com/forum/view/livechess/draw-by-insufficient-material2 https://www.chess.com/forum/view/livechess/draw-by-insuffici...
  - Scarblac 10y ago
    The starting position is probably "a case where checkmate is theoretically possible, but where your opponent can thwart it indefinitely with good play".
    - mikeash 10y ago
      Heh, indeed. I think what I meant was that your opponent can thwart it, in practice, given the actual abilities of both players. Things like the 50 move rule and the repetition rule are ways to detect this condition without actually having to figure out a way to analyze their abilities to decide whether a position is practically unwinnable.
- Scarblac 10y ago
  Yes, that one is quite hard to get right for normal chess engines too, and it usually isn't done. E.g. if both sides have only a bishop left, then if the two bishops are on squares of the same color checkmate isn't possible, but if they are on different colors then checkmate is possible in a corner. Or pawn formations in the middle of the board that prevent breakthroughs. Most online chess sites only consider the obvious case of king + bishop or knight vs king to be a draw under that rule (and king v king, obviously).
aweinstock 10y ago
Searching the history to enforce the threefold repetition rule[1] wouldn't be efficient, but the fifty-move rule[2] could be pretty cheaply implemented (one cell of state for a counter, an increment-and-check per move, and resetting the counter to 0 on the relevant moves). [1]: https://en.wikipedia.org/wiki/Threefold_repetition https://en.wikipedia.org/wiki/Threefold_repetition [2]: https://en.wikipedia.org/wiki/Fifty-move_rule https://en.wikipedia.org/wiki/Fifty-move_rule