6 ms·

I wonder if/how that interacts with the new draw rule. (For the uninitiated: the formal rule to adjudicate games as draws automatically or on time is that the g

by qsort 8mo ago

I wonder if/how that interacts with the new draw rule. (For the uninitiated: the formal rule to adjudicate games as draws automatically or on time is that the game is a draw if there exists no sequence of moves that could lead to checkmate. Interestingly, although this has almost no strategic implications, it means that... it's almost impossible to write a program to detect draws that's technically correct. A similar corner case is draws in Magic the Gathering, which is literally undecidable in general.)

Sesse__ 8mo ago
Is that a new rule? I was under the impression that it had been the case for a very long time that if you went out on time but there was no possible sequence of moves leading to checkmating you, it was a draw instead. (Meaning, of course, that having more pieces could be a disadvantage in such situations, which feels a bit unfair. E.g., KvKB is a draw, but KPvKB can lead to a mate if both sides cooperate, and thus would be a time loss for white even if black would never win in practical play.)
- jmount 8mo ago
  I just updated the article. I did use Python's insufficient material detection, in addition to the ability to call for a draw (3-fold repetition, and 50 move rule). I think the "75 move rule" that doesn't require a player to call is one of the more recent rule changes.
- qsort 8mo ago
  That's not new, but how it formally works has changed. There used to be a number of explicitly enumerated cases (i.e. bare king and king with a minor piece,) now the rule instead just says that there must exist a sequence of moves to mate. Some positions, even with pawns (imagine a completely closed position with only pawns and kings) wouldn't have been automatically drawn under the previous system but now would be. I think USCF rules, unlike FIDE, still have the enumerated cases? The difference is extremely minor and has almost no strategic implications, it's just an interesting corner case.
  - TZubiri 8mo ago
    Does it depend on elo as well?
    - lmm 8mo ago
      No. How could it possibly depend on elo?
      - TZubiri 8mo ago
        Well it can depend on Referee discretion, and the referee can evaluate whether a position is obviously a draw or not. Something in high elo may obviously be a draw, like KRPPP vs KRPP, or KRN vs KR but not necessarily in lower elo.
        Sesse__ 8mo ago
        What if the players are both much higher-rated than the arbiter? Basically, once you've lost on time, you're giving up the right to any sort of agency, and thus the Elo doesn't matter. The rules are charitably giving you a rating of minus infinity and allow you to attempt salvaging half a point with that.
  - Sesse__ 8mo ago
    The oldest rules on FIDE's pages are the ones for “before 2014”. They state: 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) And 9.6 just states: The game is drawn when a position is reached from which a checkmate cannot occur by any possible series of legal moves. This immediately ends the game, provided that the move producing this position was legal. And similarly 6.9, which governs loss on time: Except where one of the Articles: 5.1.a, 5.1.b, 5.2.a, 5.2.b, 5.2.c applies, if a player does not complete the prescribed number of moves in the allotted time, the game is lost by the player. However, the game is drawn, if the position is such that the opponent cannot checkmate the player’s king by any possible series of legal moves. So it's at least ten years old, but possibly quite more. I know I have a copy of the 1984 rules (or possibly even older) somewhere on paper, but then I'd have to go into the attic :-)
deleted 8mo ago
[deleted]
Someone 8mo ago
> the game is a draw if there exists no sequence of moves that could lead to checkmate. Interestingly, although this has almost no strategic implications, it means that... it's almost impossible to write a program to detect draws that's technically correct. I don’t see what makes that technically difficult. The number of possible positions is finite, so just enumerate the game tree and check whether it contains a checkmate situation. I also don’t see why it would be almost impossible in practice. Aren’t the only weird situations ones where there are pawns that could be promoted to queens if they weren’t blocked by other pawns, and those pawns prevent all other pieces on the board from taking pawns and from checkmating the king?
- BobaFloutist 8mo ago
  >there are pawns that could be promoted to queens if they weren’t blocked by other pawns, and those pawns prevent all other pieces on the board from taking pawns and from checkmating the king? I'm having a hard time picturing this scenario. Is it that any move to take a pawn places the mover in check?
  - Someone 8mo ago
    I have a hard time envisioning that, too, but I think one can construct boards with rook or two bishops being closed in behind a setup with all 16 pawns still on the board, with the opposing king on the other half of the board.
- program_whiz 8mo ago
  You're approach seems straight-forward in theory -- just check every possible move and make sure that none lead to a checkmate. The only issue is that "checking every possible move" is a huge state space (way above what is computable). Not only that, but there are cycles (so you need to deduplicate). And if the game is a draw, then that means the number of moves is technically unbounded (since there would always be a move that makes the search tree deeper), as by definition, there is no way to end the game. So the question is 'when do you stop searching?'. It could be that checkmate is possible, but you haven't searched the 1 in 1 billion part of the strategy tree. In practice, its probably down to some heuristics and a reasonable depth search, but its not formally verifiable. Its a variant of the halting program -- prove that there is a stopping point for this game.
lxgr 8mo ago
For 7 remaining pieces or less, there are actually tablebases of all possible positions showing whether there's a possible win or loss for either side: https://en.wikipedia.org/wiki/Endgame_tablebase https://en.wikipedia.org/wiki/Endgame_tablebase
- eszed 8mo ago
  Huh! I don't follow chess closely enough to have known the tables go that deep. Do high-level players memorize (enough of) those that their strategy in a losing position shifts to creating a drawing piece combination? Or do the tables only formalize something was that always done intuitively?
  - lxgr 8mo ago
    I don't think human players memorize tables in the same way that they memorize opening lines. The number of possible endgame position values is astronomical; "Syzygy" for 7 pieces is a few TB of data, for example. Heuristics get them very close, but I vaguely remember hearing that sometimes the tables will find an obscure move sequence to turn around a draw to a win 15 or 20 moves in that a human has no chance of spotting. These tablebases do have something eerie to them, as they represent the phase transition from heuristics to the "solved" part of chess. Lichess will automatically swap to them once it's feasible, and instead of a position evaluation, you'll just instantly see whether it's winning, losing, or drawing. Ken Thompson called it "playing chess with God": https://en.wikipedia.org/wiki/Endgame_tablebase#%22Play_chess_with_God%22 https://en.wikipedia.org/wiki/Endgame_tablebase#%22Play_ches... That said, this can happen with chess engines as well; if a position can be exhaustively analyzed, it'll show you "winning/losing/drawing in n moves" just like the tablebases. The tablebases just guarantee that they'll find that solution in constant time.

by qsort 8mo ago

Sesse__ 8mo ago

Is that a new rule? I was under the impression that it had been the case for a very long time that if you went out on time but there was no possible sequence of moves leading to checkmating you, it was a draw instead. (Meaning, of course, that having more pieces could be a disadvantage in such situations, which feels a bit unfair. E.g., KvKB is a draw, but KPvKB can lead to a mate if both sides cooperate, and thus would be a time loss for white even if black would never win in practical play.)

jmount 8mo ago
I just updated the article. I did use Python's insufficient material detection, in addition to the ability to call for a draw (3-fold repetition, and 50 move rule). I think the "75 move rule" that doesn't require a player to call is one of the more recent rule changes.
qsort 8mo ago
That's not new, but how it formally works has changed. There used to be a number of explicitly enumerated cases (i.e. bare king and king with a minor piece,) now the rule instead just says that there must exist a sequence of moves to mate. Some positions, even with pawns (imagine a completely closed position with only pawns and kings) wouldn't have been automatically drawn under the previous system but now would be. I think USCF rules, unlike FIDE, still have the enumerated cases? The difference is extremely minor and has almost no strategic implications, it's just an interesting corner case.
- TZubiri 8mo ago
  Does it depend on elo as well?
  - lmm 8mo ago
    No. How could it possibly depend on elo?
    - TZubiri 8mo ago
      Well it can depend on Referee discretion, and the referee can evaluate whether a position is obviously a draw or not. Something in high elo may obviously be a draw, like KRPPP vs KRPP, or KRN vs KR but not necessarily in lower elo.
      - Sesse__ 8mo ago
        What if the players are both much higher-rated than the arbiter? Basically, once you've lost on time, you're giving up the right to any sort of agency, and thus the Elo doesn't matter. The rules are charitably giving you a rating of minus infinity and allow you to attempt salvaging half a point with that.
- Sesse__ 8mo ago
  The oldest rules on FIDE's pages are the ones for “before 2014”. They state: 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) And 9.6 just states: The game is drawn when a position is reached from which a checkmate cannot occur by any possible series of legal moves. This immediately ends the game, provided that the move producing this position was legal. And similarly 6.9, which governs loss on time: Except where one of the Articles: 5.1.a, 5.1.b, 5.2.a, 5.2.b, 5.2.c applies, if a player does not complete the prescribed number of moves in the allotted time, the game is lost by the player. However, the game is drawn, if the position is such that the opponent cannot checkmate the player’s king by any possible series of legal moves. So it's at least ten years old, but possibly quite more. I know I have a copy of the 1984 rules (or possibly even older) somewhere on paper, but then I'd have to go into the attic :-)

deleted 8mo ago

[deleted]

Someone 8mo ago

> the game is a draw if there exists no sequence of moves that could lead to checkmate. Interestingly, although this has almost no strategic implications, it means that... it's almost impossible to write a program to detect draws that's technically correct. I don’t see what makes that technically difficult. The number of possible positions is finite, so just enumerate the game tree and check whether it contains a checkmate situation. I also don’t see why it would be almost impossible in practice. Aren’t the only weird situations ones where there are pawns that could be promoted to queens if they weren’t blocked by other pawns, and those pawns prevent all other pieces on the board from taking pawns and from checkmating the king?

BobaFloutist 8mo ago
>there are pawns that could be promoted to queens if they weren’t blocked by other pawns, and those pawns prevent all other pieces on the board from taking pawns and from checkmating the king? I'm having a hard time picturing this scenario. Is it that any move to take a pawn places the mover in check?
- Someone 8mo ago
  I have a hard time envisioning that, too, but I think one can construct boards with rook or two bishops being closed in behind a setup with all 16 pawns still on the board, with the opposing king on the other half of the board.
program_whiz 8mo ago
You're approach seems straight-forward in theory -- just check every possible move and make sure that none lead to a checkmate. The only issue is that "checking every possible move" is a huge state space (way above what is computable). Not only that, but there are cycles (so you need to deduplicate). And if the game is a draw, then that means the number of moves is technically unbounded (since there would always be a move that makes the search tree deeper), as by definition, there is no way to end the game. So the question is 'when do you stop searching?'. It could be that checkmate is possible, but you haven't searched the 1 in 1 billion part of the strategy tree. In practice, its probably down to some heuristics and a reasonable depth search, but its not formally verifiable. Its a variant of the halting program -- prove that there is a stopping point for this game.

lxgr 8mo ago

For 7 remaining pieces or less, there are actually tablebases of all possible positions showing whether there's a possible win or loss for either side: https://en.wikipedia.org/wiki/Endgame_tablebase https://en.wikipedia.org/wiki/Endgame_tablebase

eszed 8mo ago
Huh! I don't follow chess closely enough to have known the tables go that deep. Do high-level players memorize (enough of) those that their strategy in a losing position shifts to creating a drawing piece combination? Or do the tables only formalize something was that always done intuitively?
- lxgr 8mo ago
  I don't think human players memorize tables in the same way that they memorize opening lines. The number of possible endgame position values is astronomical; "Syzygy" for 7 pieces is a few TB of data, for example. Heuristics get them very close, but I vaguely remember hearing that sometimes the tables will find an obscure move sequence to turn around a draw to a win 15 or 20 moves in that a human has no chance of spotting. These tablebases do have something eerie to them, as they represent the phase transition from heuristics to the "solved" part of chess. Lichess will automatically swap to them once it's feasible, and instead of a position evaluation, you'll just instantly see whether it's winning, losing, or drawing. Ken Thompson called it "playing chess with God": https://en.wikipedia.org/wiki/Endgame_tablebase#%22Play_chess_with_God%22 https://en.wikipedia.org/wiki/Endgame_tablebase#%22Play_ches... That said, this can happen with chess engines as well; if a position can be exhaustively analyzed, it'll show you "winning/losing/drawing in n moves" just like the tablebases. The tablebases just guarantee that they'll find that solution in constant time.