persistent stalemate threat

[Michel]

Less than a second for GNUChess!

Code: Select all

	0.00	217290	0:00.69	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rg7+ Kf8 Rf7+ Ke8 Re7+ Kd8 Rd7+ Kc8 Rc7+ Kb8 Rb7+ Kc8 Rc7+ 
 19	0.00	153238	0:00.54	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rg7+ Kf8 Rf7+ Ke8 Re7+ Kd8 Rd7+ Kc8 Rc7+ Kb8 Rb7+ Kc8 Rc7+ 
 18	0.00	114397	0:00.45	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rg7+ Kf8 Rf7+ Ke8 Re7+ Kd8 Rd7+ Kc8 Rc7+ Kb8 Rb7+ Kc8 Rc7+ 
 17	0.00	85894	0:00.38	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rg7+ Kf8 Rf7+ Ke8 Re7+ Kd8 Rd7+ Kc8 Rc7+ Kb8 Rb7+ Kc8 Rc7+ 
 16	0.00	71748	0:00.34	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rg7+ Kf8 Rf7+ Ke8 Re7+ Kd8 Rd7+ Kc8 Rc7+ Kb8 Rb7+ Kc8 Rc7+ 
 15	0.00	61601	0:00.31	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rg7+ Kf8 Rf7+ Ke8 Re7+ Kd8 Rd7+ Kc8 Rc7+ Kb8 Rb7+ Kc8 Rc7+ 
 14	0.00	54915	0:00.29	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rg7+ Kf8 Rf7+ Ke8 Re7+ Kd8 Rd7+ Kc8 Rc7+ Kb8 Rb7+ Kc8 Rc7+ 
 13	0.00	50205	0:00.26	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rg7+ Kf8 Rf7+ Ke8 Re7+ Kd8 Rd7+ Kc8 Rc7+ Kb8 Rb7+ Kc8 Rc7+ 
 12	0.00	47482	0:00.26	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rg7+ Kf8 Rf7+ Ke8 Re7+ Kd8 Rd7+ Kc8 Rc7+ Kb8 Rb7+ Kc8 Rc7+ 
 12	0.00	46610	0:00.25	Rg6+ 
 11	-3.68	40778	0:00.23	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rxh4 d3 Rd4 Rc8 Rc4 e5 Kb1 
 11	-3.81	36797	0:00.21	Rg6+ 
 10	-3.56	27885	0:00.18	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rxh4 Rc8 Rh1 d3 Rg1+ Kf7 Nb5 
 10	-3.96	22299	0:00.14	Rg6+ 
  9	-3.71	12297	0:00.08	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rxh4 d3 Rb4 Kg7 Rb7+ Kg6 Rxb3 d2 
  8	-3.71	10907	0:00.08	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rxh4 d3 Rb4 Kg7 Rb7+ Kg6 Rxb3 d2 
  8	-3.92	4099	0:00.04	Rg6+ 
  8	-4.17	5490	0:00.04	Rg6+ 
  7	-3.65	1929	0:00.01	Rg6+ Kh7 Rg7+ Kh8 Rh7+ Kg8 Rxh4 d3 Kb1 
  6	-3.87	1188	0:00.01	Rg6+ Kh7 Rh6+ Kg7 Rxh4 d3 Kb1 
  6	-3.87	1065	0:00.01	Rg6+ 
  5	-4.20	865	0:00.01	Rg6+ Kh7 Rh6+ Kg7 Rxh4 e5 
  5	-4.38	386	0:00.00	Rh5+ 
  5	-5.54	435	0:00.00	Rh5+ 
  5	-6.00	605	0:00.00	Rh5+ 
  4	-4.10	206	0:00.00	Rh5+ Kg6 Rh6+ Kg5 Rxh4 
  3	-4.02	95	0:00.00	Rh5+ Kg6 Rxh4 
  2	-4.02	50	0:00.00	Rh5+ Kg6 
  1	-4.02	34	0:00.00	Rh5+ 

  1	-9.96	17	0:00.00	Rg1 

[Volker Annuss]

Try this one:
[d]2r4k/5Pp1/6P1/8/8/RP5K/2PPPPP1/8 b - - 0 1

It looks like a persistant stalemate threat but it is mated in 18.

[Michel]

15 seconds for GNUChess (on an old P4).

Code: Select all

21 -9964 1568 5939872  Rc3+ d3 Rxd3+ f3 Rxf3+ Kh2 Rh3+ Kg1 Rh1+ Kf2 Rf1+ Ke3 Rf3+ Kd2 Rd3+ Kc1 Rd8 b4 Rd1+ Kb2 Rb1+ Kc3 Rb3+ Kd2 Rd3+ Ke1 Rd1+ Kf2 Rf1+ Kg3 Rf3+ Kh2 Rxf7 Ra8+ Rf8 Rxf8#

[lucasart]

Try this one:
[d]2r4k/5Pp1/6P1/8/8/RP5K/2PPPPP1/8 b - - 0 1

It looks like a persistant stalemate threat but it is mated in 18.

By chance my program doesn't recognize this as a persistent stalemate threat. This is because it doesn't see the blackjking as trapped, as squares around aren't all attacked (one is occupied by a blocked pawn).

[lucasart]

15 seconds for GNUChess (on an old P4).

Code: Select all

21 -9964 1568 5939872  Rc3+ d3 Rxd3+ f3 Rxf3+ Kh2 Rh3+ Kg1 Rh1+ Kf2 Rf1+ Ke3 Rf3+ Kd2 Rd3+ Kc1 Rd8 b4 Rd1+ Kb2 Rb1+ Kc3 Rb3+ Kd2 Rd3+ Ke1 Rd1+ Kf2 Rf1+ Kg3 Rf3+ Kh2 Rxf7 Ra8+ Rf8 Rxf8#

There's something I don't understand with this position. After playing: Rc3+ d3 Rxd3+ f3 Rxf3+ Kh2 Rh3+ Kg1 Rh1+ Kf2 Rf1+ Ke3 Rf3+ Kd2 Rd3+ Kc1 (where my engine agrees with GNU Chess), we reach this position:
[d]7k/5Pp1/6P1/8/8/RP1r4/2P1P1P1/2K5 b - - 0 1
Now, why would black be forced to play Rd8 here ? I don't see what stops him from continuing this game of rook contact checks to the white king. I would naively play Rd1+ here.

But the mate is there, and DiscoCheck agrees with GNU Chess from here (mate in a max of 10 moves), and plays Rd8. I just want to understand it from a human point of view, because I just don;'t see how black rook runs out of contact checks.

[Daniel Shawul]

Black can continue contact checks but he has to capture Pb3 to continue the threat. Then the whole rank 3 will be clear with no pawns. After the king zig-zags through the openings back to h2, black has no choice but to contact check at h3 at which point the white rook suddenly awakens and gives a checkmate by capturing the rook. I am sure there is a PV to it but thats how humans understand it.

[lucasart]

Black can continue contact checks but he has to capture Pb3 to continue the threat. Then the whole rank 3 will be clear with no pawns. After the king zig-zags through the openings back to h2, black has no choice but to contact check at h3 at which point the white rook suddenly awakens and gives a checkmate by capturing the rook. I am sure there is a PV to it but thats how humans understand it.

Nice!!!

[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);

Better with comments, and also slightly optimized the early exit conditions

Code: Select all

static int persistent_stalemate(const Board *B)
/* This code detects persistent stalemate threats (crazy rook/queen patterns). The return value is
 * the color that has a persistent stalemate (ie. the side that "threatens to be stalemated"). When
 * there is no such threat (most often), the early exit routes are hopefully fast, and the return
 * value is logically NoColor. */
{
	/* Rule 1: King is busted (squares around are all attacked) */
	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;
	
	const uint64_t pawns = B->b[us][Pawn];
	
	/* Rule 2: We have at most one piece, and this piece is a Rook or a Queen */
	if (several_bits(B->all[us] & ~pawns & ~B->b[us][King]) || !get_RQ(B, us))
		return NoColor;

	/* Rule 3: we have no mobile pawn */
	bool mobile_pawns = false;
	unsigned them = opp_color(us);
	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) {
		/* At this point:
		 * 1. our King is busted
		 * 2. we have at most one piece, which is a Roomk or a Queen
		 * 3. we have no mobile pawn
		 * If this Rook or Queen can deliver check, then it's a persistent stalemate threat */
		unsigned ksq = B->king_pos[them];
		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;
}

I'm now going to experiment with stalemate detection in the qsearch.

[lucasart]

Just so you know, the above didn't work: elo-wise it was equal at 100,000 nodes/move, but at longer time control 6sec+0.15sec it was proven to be a regression (score was about 2 stdev below 50% after 1000 games).

There are 3 factors to consider
1/ the extra computation slows down a little: negative effect
2/ some nodes are correctly flagged: positive effect
3/ some nodes are incorrectly flagged (the rule is not 100% correct): negative effect

1/ was negligible, as I made sure the code is fast and has early exit routes
2/ looks nice in certain test positions, but their occurrence in real games, or more precisely in searched nodes (not just the moves played but all the nodes searched), is infinitesimal.
3/ is more important than 2/. Overlooking 2/ at certain nodes is not as severe as incorrectly flagging as a draw nodes where the apparently persistent stalemate threat is actually refuted.

So, it's probably safer to use the QS for that and detect stalemate in the QS. However such detection has to be performed at the beginning of the QS, before the stand pat, and before the move loop, both of which often trigger a fail high. So my guess is that it's going to be relatively costly in speed, and it's unikely to be compensated by the benefit of understanding certain rare draws. Also writing a function that determines whether a position is stalemate without doing move generation, and thinking about all possible cases is complex and therefore slow (+risk of bugs). As pointed out in 3/ we don't want to incorrectly flag positions as stalemates when they're not, while overlooking certain ones is not as severe.

IOW 3/ has to be totally eradicated, as if it occurs, even if relatively much less often than 2/, it can be disastrous. I can think of ways to do a stalemate check that is a sufficient but not necessary condition: king can't move & no mobile pawns & no pieces. Tht should be fast to compute, and could make sense to put at the beginning of the QS.

Anyway, it's no my to do list now, and I'll do some testing with the QS method.

[ZirconiumX]

More stupid thoughts. Do you have a routine for detecting stalemate, or is it done in the search? If the former then you could recycle the code, if the latter you could bring the score closer to zero.

Also, could you *please* be uci compatible and use 'score mate x' rather than 'score cp (hugenumber-x)'?

Matthew:out