persistent stalemate threat

[lucasart]

[d]7k/2R3b1/6R1/1r5P/6K1/8/8/8 w - - 0 55
Rxg7 is obviously the blunder that leads to a draw (crazy rook).

I've seen this kind of pattern occur many times, and every time it really pisses me off that my engine doesn't understand this. A brute force search inevitably plays the materialistic Rxg7, and the search keeps shuffling the wood to delay the 3-rep draw, meaning that it may take a lot of depth to solve, if at all!

So I tried a rather radical approach which is to detect such things in the eval directly. Here's how it works:
1/ calculate the eval normally, let's call it e
2/ if the side to move has a persistent stalemate threat, return max(0,e)
3/ if the other side has a persistent stalemate threat, return min(0,e)

A side has a persistent stalemate threat if:
1/ the squares around the king are all attacked
2/ we have a rook or a queen that can deliver check

All this is fortunately quick to compute as there are many early exit cases, and I have some precalculated attacks available (a bitboard by piece type and side).

The position after Rxg7 is now evaluated as a draw, and the search gives credible results

Code: Select all

info score cp 459 depth 1 nodes 205 time 0 pv h5h6
info score cp 422 depth 2 nodes 520 time 0 pv g6d6 h8h7
info score cp 414 depth 3 nodes 2073 time 0 pv g6c6 h8h7 c6f6 b5b4 f6f4
info score cp 400 depth 4 nodes 3027 time 0 pv g6c6 b5b4 c6c4 b4c4 c7c4 g7e5
info score cp 403 depth 5 nodes 4499 time 0 pv g6c6 h8h7 c6f6 b5b4 f6f4 b4b5
info score cp 400 depth 6 nodes 9731 time 10 pv g6c6 h8h7 c6e6 b5b4 g4f3 b4b3 f3f4 b3b5
info score cp 396 depth 7 nodes 33230 time 40 pv g6e6 h8h7 e6e4 h7h6 c7c6 h6h7 e4e6
info score cp 395 depth 8 nodes 43219 time 60 pv g6e6 h8h7 e6e4 h7h6 c7c6 h6h7 e4e6
info score cp 396 depth 9 nodes 91207 time 120 pv c7c8 h8h7 c8c4 g7e5 c4e4 b5c5 g6g5 e5d6 e4e6 c5c4 g4f3
info score cp 408 depth 10 nodes 341693 time 320 pv c7c4 h8h7 c4e4 b5c5 e4e7 h7h8 g6e6 c5c4 e6e4 c4e4 e7e4 h8h7
info score cp 429 depth 11 nodes 670798 time 650 pv g6c6 b5b4 g4f5 b4b1 h5h6 b1f1 f5g4 f1g1
info score cp 469 depth 12 nodes 885881 time 800 pv g6a6 b5b4 g4g5 b4b8 h5h6 g7d4 a6e6 d4b6 c7d7 b8g8 g5f5 b6c5 e6e5 c5b4
info score cp 471 depth 13 nodes 1058588 time 910 pv g6a6 b5b4 g4g5 b4b1 h5h6 b1g1 g5f4 g1f1 f4e4 f1e1 e4f3 g7f8 a6a8 e1f1 f3e4 h8g8 c7d7 f1f2
info score cp 507 depth 14 nodes 2135735 time 1600 pv h5h6
info score cp 499 depth 15 nodes 4060606 time 2680 pv h5h6 g7e5 c7e7 e5b2 g6c6 b5b8 g4h5 b8f8 c6c7 b2f6
info score cp 492 depth 16 nodes 4539747 time 2990 pv h5h6 g7e5 c7e7 e5b2
info score cp 496 depth 17 nodes 5866752 time 3840 pv h5h6 g7e5 c7e7 e5b2
info score cp 504 depth 18 nodes 11502784 time 7320 pv h5h6 g7b2 g6g5 b5b8 g5d5 h8g8 g4h5 b8e8 c7a7
info score cp 504 depth 19 nodes 13247685 time 8420 pv h5h6 g7b2 g6g5 b5b8 g5d5 h8g8 g4h5 b8f8 d5g5 g8h8 g5c5 b2d4 c5d5

Now I need to do some random checks with the debugger, and see if I can find some positions that are incorrectly flagged as persistent stalemate threat. And then I need to do some testing to see if the speed loss and potential errors, are really costly in elo terms.

Has anyone tested other ways to fix this problem ?

[lucasart]

actually I had to revise my conditions to something a little more complex. here's the code anyway:

Code: Select all

static int persistent_stalemate(const Board *B)
{
	unsigned us;
	if (!(KAttacks[B->king_pos[White]] & ~B->st->attacks[Black][NoPiece]))
		us = White;
	else if (!(KAttacks[B->king_pos[Black]] & ~B->st->attacks[White][NoPiece]))
		us = Black;
	else
		return NoColor;
	
	bool mobile_pawns = false;
	uint64_t pawns = B->b[us][Pawn];
	unsigned them = opp_color(us), ksq = B->king_pos[them];
	
	if (pawns) {
		if (shift_bit(pawns, us ? -8 : 8) & ~B->st->occ)
			mobile_pawns = true;
		else if (shift_bit(pawns & ~FileA_bb, us ? -9 : 7) & B->all[them])
			mobile_pawns = true;
		else if (shift_bit(pawns & ~FileH_bb, us ? -7 : 9) & B->all[them])
			mobile_pawns = true;			
	}
	
	if (!mobile_pawns && !several_bits(B->all[us] & ~pawns & ~B->b[us][King]))
	{
		if ((B->st->attacks[us][Rook] | B->st->attacks[us][Queen]) & rook_attack(ksq, B->st->occ))
			return us;
		if (B->st->attacks[us][Queen] & bishop_attack(ksq, B->st->occ))
			return us;
	}
	return NoColor;
}

used as follows

Code: Select all

	int r = (1-phase)*(e->op[us]-e->op[them]) + phase*(e->eg[us]-e->eg[them]);
	int c = persistent_stalemate(B);
	
	if (c == NoColor)
		return r;
	else if (c == B->turn)
		return max(0, r);
	else
		return min(0, r);

[Dan Honeycutt]

Interesting. Thanks.

I'm busy with other stuff right now but I put a todo note with a link to your post in my eval comments.

Another thought I've had about this sort of position, if you have a substantial advantage it should increase iteration by iteration. If it is stagnant something is wrong. Remedy - maybe shorten the half-move clock. Haven't tried any of this.

Best
Dan H.

[Edmund]

Try this position from a rapid game between Felgaer – Malakhov

[d]k7/2KR4/P1N5/3r4/8/8/8/8 w - - 0 1

Felgaer blunders with 118. Rh7 ??; 118. Re7! Rd7+ 119. Kb6!, and White wins.

[Edmund]

by the way
if you talk a little bit of german you should read Heiner Marxens memo on permanent checks. It is included with the chest package.

So far the algorithm described there is for me the only logical approach to conclusively solve the problem for a chess engine with certainty.

It is about constructing a table with 64 x 64 x 2 entries (one checking piece, the king, two colors) and solve either forward or backward for whether the attacker can force the king into any cycle.

[lucasart]

Try this position from a rapid game between Felgaer – Malakhov

[d]k7/2KR4/P1N5/3r4/8/8/8/8 w - - 0 1

Felgaer blunders with 118. Rh7 ??; 118. Re7! Rd7+ 119. Kb6!, and White wins.

Nice one Re7! And it's interesting to note that any other move is a blunder, even Rd8+ forcing the exchange of rooks.

My engine evaluates the root position at 0 already., with the above described method. And the search finds the winning move very quickly:

Code: Select all

info score cp 1852 depth 1 nodes 7 time 0 pv d7d5
info score cp 619 depth 2 nodes 144 time 0 pv c6d4 d5e5
info score cp 630 depth 3 nodes 605 time 0 pv c6d4 d5c5 c7b6 c5c8
info score cp 631 depth 4 nodes 841 time 0 pv c6d4 d5c5 c7b6 c5c8 d7e7
info score cp 613 depth 5 nodes 2513 time 0 pv c6d4 d5h5 c7b6 h5h6 b6b5 h6h5 b5c4
info score cp 607 depth 6 nodes 5905 time 10 pv a6a7 d5d7 c7d7 a8b7 d7d6 b7a8 d6e5 info score cp 1169 depth 7 nodes 7917 time 10 pv a6a7 d5d7 c7d7 a8b7 d7e7 b7c6 a7a8q c6c5 a8e4 c5b6
info score cp 1178 depth 8 nodes 14750 time 20 pv a6a7 d5d7 c7d7 a8b7 d7e7 b7c6 a7a8q c6c5 a8e4 c5b6
info score cp 1374 depth 9 nodes 35282 time 40 pv d7e7 d5d7 c7b6 d7e7 c6e7 a8b8 e7c6 b8a8 c6d8

[lucasart]

Try this position from a rapid game between Felgaer – Malakhov

[d]k7/2KR4/P1N5/3r4/8/8/8/8 w - - 0 1

Felgaer blunders with 118. Rh7 ??; 118. Re7! Rd7+ 119. Kb6!, and White wins.

Nice one Re7! And it's interesting to note that any other move is a blunder, even Rd8+ forcing the exchange of rooks.

My engine evaluates the root position at 0 already., with the above described method. And the search finds the winning move very quickly:

Code: Select all

info score cp 1852 depth 1 nodes 7 time 0 pv d7d5
info score cp 619 depth 2 nodes 144 time 0 pv c6d4 d5e5
info score cp 630 depth 3 nodes 605 time 0 pv c6d4 d5c5 c7b6 c5c8
info score cp 631 depth 4 nodes 841 time 0 pv c6d4 d5c5 c7b6 c5c8 d7e7
info score cp 613 depth 5 nodes 2513 time 0 pv c6d4 d5h5 c7b6 h5h6 b6b5 h6h5 b5c4
info score cp 607 depth 6 nodes 5905 time 10 pv a6a7 d5d7 c7d7 a8b7 d7d6 b7a8 d6e5 info score cp 1169 depth 7 nodes 7917 time 10 pv a6a7 d5d7 c7d7 a8b7 d7e7 b7c6 a7a8q c6c5 a8e4 c5b6
info score cp 1178 depth 8 nodes 14750 time 20 pv a6a7 d5d7 c7d7 a8b7 d7e7 b7c6 a7a8q c6c5 a8e4 c5b6
info score cp 1374 depth 9 nodes 35282 time 40 pv d7e7 d5d7 c7b6 d7e7 c6e7 a8b8 e7c6 b8a8 c6d8

The first choice of DoubleCheck here is a7, before finding the right move at depth 9. It actually makes sense. After a7, forcing Rxd7 and Kxd7:
[d]k7/P2K4/2N5/8/8/8/8/8 b - - 0 1
And this will be a draw by repetion, because the black king will go from a8 bo b7 and back to a8 etc. So it makes sense that DiscoCheck requires a few plies of search to see that (and remember there are null moves, search reduction, razoring and futility pruning etc.)

[Gerd Isenberg]

The desperado pattern is tricky to detect statically, see The King versus Nimzo Guernica game, WMCCC 1993:
https://chessprogramming.wikispaces.com ... #Desperado

[d] r7/8/4p2k/5bR1/3p3r/Np6/1P6/K7 w - - 2 61

For instance, without the e6 pawn the bishop might capture the rook later on d7 leaving the b1-h7 diagonal and escape square b1 ...

Stalemate detection in qsearch seems obligatory for that, and may be to trigger extensions if hanging piece gives check, but capturing leaves stalemate score ...

[Edmund]

And it's interesting to note that any other move is a blunder, even Rd8+ forcing the exchange of rooks.

Knight protecting the pawn also wins, but later.

Re7 Mate in 12
Nb4 Mate in 13
Nb8 Mate in 15

[lucasart]

The desperado pattern is tricky to detect statically, see The King versus Nimzo Guernica game, WMCCC 1993:
https://chessprogramming.wikispaces.com ... #Desperado

[d] r7/8/4p2k/5bR1/3p3r/Np6/1P6/K7 w - - 2 61

For instance, without the e6 pawn the bishop might capture the rook later on d7 leaving the b1-h7 diagonal and escape square b1 ...

Stalemate detection in qsearch seems obligatory for that, and may be to trigger extensions if hanging piece gives check, but capturing leaves stalemate score ...

That's a hard one! Fortunately those cases are rare, much more so than the usual crazy rook theme. But my code doesn't detect that, so it's up to the search to figure it out. DiscoCheck solves it, eventually...

Code: Select all

info score cp 0 depth 27 nodes 45348816 time 24030 pv g5g6 h6h7 g6g7 h7h8 g7h7 h8g8 h7g7 g8f8 g7f7 f8e8 f7e7 e8d8 e7d7 d8e8 d7e7