Lila: Detect all positions without a legal sequence of moves to checkmate

[Pablo-No]

https://lichess.org/tXLCGzpvIn
the last position, white's time ran out and it was ruled that black won. However, a checkmate can't be reached with a series of legal moves. Therefore, according to FIDE Laws of Chess, this game should've ended in a draw.

Forum post

I know that it's almost impossible to know when it's a draw or not, but we need something at least to have a official way to report these issues when they happen, like an official form on FAQ or contact page.

Also i apologise if there is a legal sequence of moves to win.

[Pablo-No]

Posterior comment by Toadofsky:

Yeah, after Black's 44th move a dead position is reached although Lichess failed to detect this.

I hadn't noticed that, but I think it's true too.

[TBestLittleHelper]

https://lichess.org/faq#timeout

In the event of one player running out of time, that player will usually lose the game. 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 (FIDE handbook §6.9, PDF).

In rare cases this can be difficult to decide automatically (forced lines, fortresses). By default we always side with the player who did not run out of time.

[Pablo-No]

https://lichess.org/faq#timeout

Yeah, I knew it was there.

In the event of one player running out of time, that player will usually lose the game. 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 (FIDE handbook §6.9, PDF).

That's the problem, this possition should have been a draw (well according to Fide chess laws rule 1.5 this should have been a draw previously on move 44).

In rare cases this can be difficult to decide automatically (forced lines, fortresses). By default we always side with the player who did not run out of time.

Yeah, I know, I'm asking about a clever way to check this or an official way to report them, because posting in the forum every time it happens is not practical because you post may not be anwered.

I hope this answers your comment.

[niklasf]

Yet another queue for moderators to process and the necessity to then change game results is not a feasible solution.

So until someone comes up with a novel approach to decide these cases automatically, the FAQ entry will have to do.

[Pablo-No]

If I wanted to program it, what language would I have to use?

[niklasf]

Since the difficulty lies in the algorithm, not the programming, you can use any programming language you like.

[Pablo-No]

Thanks for your help.

[Pablo-No]

Finished adding all possibilities, I still have to add more examples, demostrate that some are impossible, and programming. I hope I'm not missing another possition where one opponent cannot checkmate other. I'm working on https://github.com/Pablo-No/lila-5.2.2-6.9.

[isaacl]

I think you want to run games through stockfish.

[niklasf]

That doesn't really work with vanilla Stockfish, because Stockfish will only find mate if it's possible against best defense. Here we're looking for checkmate against the worst possible defense (helpmate).

[isaacl]

Maybe a special build of stockfish that makes the worst moves for one player and best for the other. It's an infeasible problem and stockfish could prob accomplishe the majority.

[niklasf]

Declaring a position as dead too early is completely unacceptable. That makes this problem so hard. The status quo is better than a helpmate solver that almost always works.

[jakobvarmose]

I thought a bit about this and I came up with an algorithm, that can detect most blocked positions (of course without any false positives). The algorithm might look complicated but it can be implemented quite efficiently with bitboards.

1. Determine which pieces are blocked.
2. Generate all squares that any white piece can move to (not capture), when the blocked pieces are the only other pieces on the board. If any of the pawns can move to the 8th rank, then it is not a draw.
3. Generate all squares that white could capture a hypothetical black piece on, when the blocked pieces are the only other pieces on the board.
4. Do the same for black.
5. If white can put a piece on any of the squares black can capture on, or if black can put a piece on any of the squares white can capture on, then it is not a draw. (Optional: If only the king is attacked and the king always has a safe retreating square, or if only non-blocked pieces can capture non-blocked pieces, then it is still a draw.)
6. Otherwise neither player can capture any of the opponent's pieces or put the opponent's king in check, so obviously it is a draw.

Does anybody know how often these positions happen in practice?

[dlbbld]

The positions are extremely rare. But one should never forget the possibility that such a position could decide an important event.

For an approach, I throw in the helpmate term.

The "theoretical chance to checkmate" is equivalent to having a helpmate (a mate where the opponent cooperates, or more simply one can make the opponents moves to one's favour).

There are helpmate tools, so there must be an algorithm. So one idea would be to first give the result as usual. For such cases are extremely rare, and the result should be indicated immediately, otherwise no fun here.

Then trigger the helpmate algorithm. If it does not find a mate, correct the result to a draw and explain the players.

Maybe someone knows how a helpmate algorithm works, so to build the logic into Lichess. One approach would be to play the worst engine moves for the opponent, the best for oneself. But that must really find the theoretical mate, if one and finish in quick time, not easy at all. The helpmate algorithm must guarantee to find the mate if one exists, otherwise would be useless.

One could also calculate during the game, to have the result at the end. A big overhead, however. This is just brainstorming.

[Pablo-No]

@jacobvarnase could I use your algorithm in my project? It's licensed under MIT license, https://github.com/Pablo-No/lila-5.2.2-6.9

[dlbbld]

Per my understanding, a general solution is not possible. The challenge is, to apply the law, one has to be sure, that if for example, White runs out of time, Black has no possible checkmate. The point is that one needs to determine the "no possible checkmate". Finding a possible checkmate for Black solves this, but when no possible checkmate is found, this does not say, that there is "no possible checkmate", and exactly this statement is needed to apply the rule.

For there is no algorithm to find the possible mate, which is perfect and runs in a reasonable time, correct me if wrong. As with normal mates, finding no mate does not mean there is no mate. A brute force algorithm would be perfect (to calculate each game outcome) so would say if there is a possible mate or none at all. But as well known brute force approaches here are of no practical value, for the required time goes into years and beyond quickly.

The dead position from the Arbiter's manual, https://en.wikipedia.org/wiki/Rules_of_chess#Dead_position, is an example. Here no possible mate for White or Black can be found, for there is none. However, to prove that there is none, which is needed to apply the rule, is extremely difficult. This is an example where a brute force approach would already be impossible for timely reasons (to calculate all possible game outcomes).

For some special positions, the rule could be implemented. For example, for the positions where both sides have only one possible move for each turn until the game ends. So the only possible game outcome can be calculated in a deterministic way, and the rule can be applied. Some examples for such positions are in a duplicate issue, same underlying problem (#7039).

[jakobvarmose]

@Pablo-No Of course - it's just an algorithm, so I don't own it or anything.

I already implemented a simplified version in Go. It only handles bishops and pawns, and there are some corner cases that are not detected, but the general idea is the same. https://github.com/jakobvarmose/deadposition2/blob/master/isdead/isdead.go#L176

I also downloaded all the games from June and did a bit of analysis:

• The algorithm found 4313 games with blocked positions - or about 144 on per day.
• 522 games (12.1%) were won by one of the players (most likely due to timeout or resignation).
• In 193 games (4.5%) one or both players had a bishop (the rest only included pawns).
• In 6 of the games the players continued playing for more! than 50 moves due to pawn pushes.

https://github.com/jakobvarmose/deadposition2/blob/master/june.txt

[ddugovic]

Feel free to also test my helpmate (White to mate) / antihelpmate (Black to mate) solver although I agree that absent a novel approach, it's too computationally expensive to run this on every timeout https://github.com/ddugovic/Stockfish/blob/master/src/types.h#L159