3 ms·

> 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 me

by Someone 9mo 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 9mo 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 9mo 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 9mo 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.
qsort 9mo ago
In the overwhelming majority of situations including almost the totality of those you care about in practice, it's trivial to say "draw" or "no draw". I mean "technically correct" in this sense: imagine you're a programmer writing a chess game. At some point, you have to write a function "isPositionDrawn()" that takes as input a board position and says "true" if the game is over as a draw, false otherwise. What do you do? - Trivial material checks don't work: even if you're sophisticated (light color vs. dark color bishops) there exist positions, even with pawns, that are drawn as per the rule as stated. - Enumerating the game tree is obviously correct but it's too large to do in practice, we want an answer before the heat death of the universe. So, what code do you put inside that function? If I'm not mistaken there is an "official" algorithm to do it, but it's very complicated, and in practice in computer chess a simplified version of the rule (a list of cases with "insufficient material") is used. Again, it's mostly nerdy navel gazing, the consequences on actual play are minuscule, but it's interesting that many games have nontrivial termination if we follow the letter of the rules.

by Someone 9mo ago

BobaFloutist 9mo 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 9mo 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 9mo 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.

qsort 9mo ago

In the overwhelming majority of situations including almost the totality of those you care about in practice, it's trivial to say "draw" or "no draw". I mean "technically correct" in this sense: imagine you're a programmer writing a chess game. At some point, you have to write a function "isPositionDrawn()" that takes as input a board position and says "true" if the game is over as a draw, false otherwise. What do you do? - Trivial material checks don't work: even if you're sophisticated (light color vs. dark color bishops) there exist positions, even with pawns, that are drawn as per the rule as stated. - Enumerating the game tree is obviously correct but it's too large to do in practice, we want an answer before the heat death of the universe. So, what code do you put inside that function? If I'm not mistaken there is an "official" algorithm to do it, but it's very complicated, and in practice in computer chess a simplified version of the rule (a list of cases with "insufficient material") is used. Again, it's mostly nerdy navel gazing, the consequences on actual play are minuscule, but it's interesting that many games have nontrivial termination if we follow the letter of the rules.