persistent stalemate threat

[lucasart]

Here's the position reached in a game between my engine DoubleCheck 2.5 and Bikjump 2.1
[d]8/1p4p1/2k2R1p/8/8/8/1r5r/K7 b - - 0 1
This is typically where computers are stupid and humans understand immediately that it's a draw due to the persistent stalemate threat. The white rook can check the black king wherever it goes, and can never be taken due to the resulting stalemate...

Of course DoubleCheck playing black was happy with a score of +10.5 or so. In fact, tournament testers will generally report an incorrect win for black here, because they use a resign feature like: if score is above 700 for 5 moves in a row according to both parties, adjudicate as a win.

I just can't figure out how to make the search understand that kind of problem

any ideas ?

[Vinvin]

It's the "crazy rook" theme ... this theme appears when only one rook can move. Is possible to extend search until you see repetition when this condition is valid ?

[Gerd Isenberg]

Here's the position reached in a game between my engine DoubleCheck 2.5 and Bikjump 2.1
[d]8/1p4p1/2k2R1p/8/8/8/1r5r/K7 b - - 0 1
This is typically where computers are stupid and humans understand immediately that it's a draw due to the persistent stalemate threat. The white rook can check the black king wherever it goes, and can never be taken due to the resulting stalemate...

Of course DoubleCheck playing black was happy with a score of +10.5 or so. In fact, tournament testers will generally report an incorrect win for black here, because they use a resign feature like: if score is above 700 for 5 moves in a row according to both parties, adjudicate as a win.

I just can't figure out how to make the search understand that kind of problem

any ideas ?

Stalemate detection (at least with lonesome king) and some checks in qsearch and/or check extensions should help here.

[lucasart]

Here's the position reached in a game between my engine DoubleCheck 2.5 and Bikjump 2.1
[d]8/1p4p1/2k2R1p/8/8/8/1r5r/K7 b - - 0 1
This is typically where computers are stupid and humans understand immediately that it's a draw due to the persistent stalemate threat. The white rook can check the black king wherever it goes, and can never be taken due to the resulting stalemate...

Of course DoubleCheck playing black was happy with a score of +10.5 or so. In fact, tournament testers will generally report an incorrect win for black here, because they use a resign feature like: if score is above 700 for 5 moves in a row according to both parties, adjudicate as a win.

I just can't figure out how to make the search understand that kind of problem

any ideas ?

Stalemate detection (at least with lonesome king) and some checks in qsearch and/or check extensions should help here.

stalemate detection in the qsearch ? that would be a horrible solution, as it would make the program significantly slower. Unless I can figure out some good precondition to do it... the "only one rook can move" mentionned by Vincent but somewhat more generalized

[Gerd Isenberg]

Stalemate detection in the qsearch ? that would be a horrible solution, as it would make the program significantly slower. Unless I can figure out some good precondition to do it... the "only one rook can move" mentionned by Vincent but somewhat more generalized

Sure with the precondition of either a lonesome king, may be with some rammed pawn(s) or pinned pieces like in the Desperado sample from the WMCCC 1999 game The King vs. Nimzo. If you don't have the attack-table infrastructure to determine it quickly, it sucks of course.

[d] r7/8/4p3/5b1k/3p3r/Np6/1P4R1/K5R1 w - - 0 58

[Volker Annuss]

Maybe you can lower the evaluation, when there is a huge material advantage and the 50 move conter becomes big (but still much smaller than 50 moves).

Here is another crazy rook theme, that is not a draw:
[d]2r4k/5Pp1/6P1/8/8/RP5K/2PPPPP1/8 b - - 0 1

Black is mated in 18 moves. The idea is to move d3 and f3, have the b-pawn captured and when the black rook gets to h3 again, the white rook can give mate there.

This one is easily solved, if you extend checks, test checks in qsearch and not reduce moves out of check, that do not capture.

[Don]

Here's the position reached in a game between my engine DoubleCheck 2.5 and Bikjump 2.1
[d]8/1p4p1/2k2R1p/8/8/8/1r5r/K7 b - - 0 1
This is typically where computers are stupid and humans understand immediately that it's a draw due to the persistent stalemate threat. The white rook can check the black king wherever it goes, and can never be taken due to the resulting stalemate...

Of course DoubleCheck playing black was happy with a score of +10.5 or so. In fact, tournament testers will generally report an incorrect win for black here, because they use a resign feature like: if score is above 700 for 5 moves in a row according to both parties, adjudicate as a win.

I just can't figure out how to make the search understand that kind of problem

any ideas ?

First of all, never use the resign feature if you want completely accurate results. If you "fix" this particular issue there will just be another one such as persistent mate threat, major piece completely out of play, or something else you haven't thought of. These rules are all broken in some sense since the user interface can never know if the chess programs themselves can handle it. We have all seen programs not be able to mate with BNvsK, and I have even seen programs screw up RvsK due to some bug so a resign rule can give a free half point or full point to a program that has not earned it.

An improvement to the resign rule which would handle this specific case and is good common sense anyway is to never adjudicate in the presence of checking moves. If one color is getting "checked to death" does it make sense to give the other side a win? Any user interface or test harness that supports resign rules should have that in some form. Even if it were as simple as never adjudicate when one side is in check. It's very common for the losing side to find a sequence of checks that could morph into a repetition draw or force the winning side to compromise in order to avoid the draw.

As for trying to handle this in a chess program, the problem is that there are other special case situations that a program could have trouble dealing with, this is just one of many. You COULD make a program understand this position with some work, but you would surely weaken it more than you would help it. I guarantee that this particular theme is so rare that it will affect (the outcome) of only 1 game out of thousands.

There may come in a time in the future when programs are hundreds of ELO stronger than they are today. The programs will play so well that issues such as this will stand out as real glitches, one of the few imperfections they have. but that is not today. There are bigger issues than this such as trapped pieces which can NEVER be freed. This goes to the bigger issue of an evaluation function that doesn't reason, it just evaluates. However the search DOES reason and with ever increasing depth issues such as this are resolved - even if it takes a ridiculously high depth for that to happen.

[lucasart]

Maybe you can lower the evaluation, when there is a huge material advantage and the 50 move conter becomes big (but still much smaller than 50 moves).

Not sure it solves anything. So what ? After 20 moves it will report +5 i/o +10.5 or whatever. The point is that it's too late and the result of the game will not change. Black should not have allowed this position to occur in the first place. So I think the correct solution is what Gerd suggests. I'll have a look at how to implement it in a way that doesn't do more harm than good (lone king seems to make sense)

[Don]

Maybe you can lower the evaluation, when there is a huge material advantage and the 50 move conter becomes big (but still much smaller than 50 moves).

Not sure it solves anything. So what ? After 20 moves it will report +5 i/o +10.5 or whatever. The point is that it's too late and the result of the game will not change. Black should not have allowed this position to occur in the first place. So I think the correct solution is what Gerd suggests. I'll have a look at how to implement it in a way that doesn't do more harm than good (lone king seems to make sense)

Keep in mind that any program can solve this eventually - it will either be a 50 move draw or a repetition check. 100 ply will get this by 50 move draw rule and I'm pretty sure that it will be solved much more quickly by repetition although white will be motivated to try every possible pattern of avoidance.

There are themes that cannot be solves "so easily" that I believe deserve more attention. Trapped pieces are hard to analyse for instance. They require some sort of reasoning about the position or really good database of common patterns.

[Evert]

I can think of two possible approaches: detect that the position is stalemate apart from the one moving piece and evaluate the position as draw-ish if it can deliver check (you can't score it as a draw). Even if not entirely correct, it can help the engine avoid such positions if it is ahead through the drop in score.
The second approach is for white: in a position like this, actively try to get a repetition.

I think the first may be worth something (if it's the difference between a win and a draw every now and then), not so sure about the second. It won't be much though.

It might mainly make the program appear a bit smarter, which is in itself not a bad goal.