stalemate detection in quiescence search

[jan.klima]

Hi,
I have an endgame-specific question: my engine was misevaluating certain KBK endgames with both sides having one pawn. A typical example of such position:

8/5K1k/8/5Bp1/8/7P/8/8 b - - 0 81

Even with my limited chess knowledge, this seems to be a draw, however, my engine (and others too, including fruit, glaurung, ruffian,...) evaluate it as a win for white. I was wondering why exactly this happens and after some search tree investigation, it's probably really simple: for example, with 7 ply search, the game can go like this: Kh8 Kg6 Kg8(forced) Be6 Kh8(forced) Kh6.

7k/8/4B2K/6p1/8/7P/8/8 b - - 0 84

Now, black must push his pawn and the engine enters quiescence search. The trick is that:
1)Bxg4 is a draw which is simply detected by evaluation
...and...
2)hxg4 is a stalemate

Every reasonable engine detects 1) but most seem to ignore 2).

This happens in searches to almost any depth, white pushes his bishop around first, then maneuvers black into a stalemate position and the quiescence search returns a win for white.

How would you handle this in quiescence search, effectively?

[Onno Garms]

You are right, the position is a draw. Even without any chess knowledge you can check this at
http://www.shredderchess.de/online-scha ... nbank.html

I don't think that a stalemate detection in qs solves the problem. I don't get any stalemate lines reported by the engines I tried.

The problem is simply that there is no simple rule from which follows that the position is a draw. The engine sees that it has a minor more and returns an according value. In PV it moves around forever, like in any other blockade position.

Note that the following similar position is a win for white:
8/5K1k/6p1/6p1/6B1/7P/8/8 w - -

[Gerd Isenberg]

Hi,
How would you handle this in quiescence search, effectively?

Some programs like Ed Schroeder's Rebel generate all moves at every node. What I actually do - see hiding hash-probe
http://64.68.157.89/forum/viewtopic.php ... 19&t=20370
is to generate attack maps and 16 direction-wise target-sets of all legal moves at the beginning of each node. Of course if all target sets are empty, it is either mate or stalemate. It definitely helps in positions like this from the King-Nimzo game WCCC 1993:
[D] r7/8/4p3/5b1k/3p3r/Np6/1P4R1/K5R1 w - - 0 1
Instead of generating all moves it is of course sufficient to generate only one legal move. But if you rely on a different program design detecting stalemates in qsearch might be too expensive compared to the possible gain with rare stalemates.

Gerd

[jan.klima]

You are right, the position is a draw. Even without any chess knowledge you can check this at
http://www.shredderchess.de/online-scha ... nbank.html

I don't think that a stalemate detection in qs solves the problem. I don't get any stalemate lines reported by the engines I tried.

I think it does solve it. And why should the engines you tried report stalemate lines? An engine may either completely misevaluate this(as a win) or say that it's a draw.

The problem is simply that there is no simple rule from which follows that the position is a draw. The engine sees that it has a minor more and returns an according value. In PV it moves around forever, like in any other blockade position.

Note that the following similar position is a win for white:
8/5K1k/6p1/6p1/6B1/7P/8/8 w - -

I disagree. There is a very simple rule which just checks whether the stronger side has its pawn on a good or bad file. In this position, such simple evaluation will say it's a draw. BUT... search will easily see that it's possible to move white pawn to g file. And that's a win. What I'm trying to say is that this is a different scenario from what i have posted...

[hgm]

Why do you think they evaluate it as a win? Are they giving a mate score? Or are they giving +1? Usually +1 is a draw, a single Pawn advantage is not a winning advantage.

[Graham Banks]

Hi Jan,

does this mean that a new version of Pseudo is likely at some stage?

Regards, Graham.

[jan.klima]

The score varies between engines...usually it's somewhere between 4 and 7 pawns, which is clear winning score imho. What I said is valid for Fruit 2.1, Glaurung 2(.0.1?) and Ruffian 1.0.5.

[jan.klima]

Hi Graham,

yes, I have been working on a new version recently. However, my progress is rather slow and with all those new very strong engines around, I see no point in releasing it before I make significant strength improvements. Which can mean two months, half a year or never, who knows...

[Graham Banks]

Hi Graham,

yes, I have been working on a new version recently. However, my progress is rather slow and with all those new very strong engines around, I see no point in releasing it before I make significant strength improvements. Which can mean two months, half a year or never, who knows...

Thanks for answering Jan.
Don't let anybody hurry you or pressure you. Computer chess should be fun, not work.
Looking forward to the new version, whenever it may be.

Regards, Graham.

[tvrzsky]

Hi Jan,
you are right as usually. I have tried it and got following results:
original search:

Code: Select all

FEN: 8/5K1k/8/5Bp1/8/7P/8/8 b - - 0 81 

Flip 1.0.0.26520:
   4	00:01,500	         629	31.450	-5,48	81. ... Kh6 82.Bg6 g4 83.hxg4
   4	00:01,500	         650	32.500	 0,00	81. ... Kh8 82.Bb1
   4	00:01,500	         654	32.700	 0,00	81. ... Kh8 82.Bb1 g4
   5	00:01,500	         661	22.033	-5,58	81. ... Kh8 82.Bb1 g4 83.hxg4
   5	00:01,500	       1.241	31.025	-5,78	81. ... Kh8 82.Be4 g4 83.hxg4
   5	00:01,500	       1.579	39.475	-5,48	81. ... Kh6 82.Bg6 g4 83.hxg4
   5	00:01,500	       1.588	39.700	-5,48	81. ... Kh6 82.Bg6 g4 83.hxg4
   6	00:01,500	       2.005	40.100	-5,54	81. ... Kh6 82.Bg6 g4 83.hxg4 Kg5
   7	00:01,500	       9.306	132.942	-5,50	81. ... Kh6 82.Bg6 g4 83.hxg4 Kg5 84.Bf5 Kf4
   7	00:01,515	      14.892	212.742	-5,48	81. ... Kh8 82.Bc8 Kh7 83.Bd7 Kh6 84.Bc6
   7	00:01,515	      19.319	275.985	-3,88	81. ... Kh8 82.Kg6 Kg8 83.Be6+ Kf8 84.Kf6 Ke8 85.Bf7+
   7	00:01,515	      19.514	278.771	 0,00	81. ... Kh8 82.Kg6 Kg8 83.Be6+ Kh8 84.Kxg5
   7	00:01,515	      19.537	279.100	 0,00	81. ... Kh8 82.Kg6 Kg8 83.Be6+ Kh8 84.Kxg5
   8	00:01,515	      19.632	245.400	-4,22	81. ... Kh8 82.Kg6 Kg8 83.Be6+ Kf8 84.Kf6 Ke8
   8	00:01,531	      30.689	340.988	-3,94	81. ... Kh8 82.Kg6 Kg8 83.Bc8 Kf8 84.Be6 Ke7
   9	00:01,531	      52.814	480.127	-3,88	81. ... Kh8 82.Kg6 Kg8 83.Be6+ Kf8 84.Bd5 Ke7 85.Kg7 Kd6
  10	00:01,531	      74.933	624.441	-0,32	81. ... Kh8 82.Kf6 Kg8 83.Be6+ Kh7 84.h4 gxh4 85.Ke5 Kh6
  10	00:01,531	      87.133	670.253	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Be6+ Kh7 84.h4 gxh4 85.Ke5 Kh6 86.Bf5 h3
  11	00:01,531	     105.218	701.453	-3,50	81. ... Kh8 82.Kf6 Kg8 83.Kg6 Kf8 84.Be4 Ke7 85.Kg7 g4
  11	00:01,547	     164.778	915.433	-3,76	81. ... Kh8 82.Kg6 Kg8 83.Bd7 Kf8 84.Bc6 Ke7 85.Kg7 Ke6
  12	00:01,547	     267.990	1.165.173	-5,24	81. ... Kh8 82.Bd7 Kh7 83.Be8 Kh6 84.Kg8 g4 85.hxg4 Kg5
  13	00:01,562	     443.594	1.430.948	-5,00	81. ... Kh8 82.Bd7 Kh7 83.Be8 Kh6 84.Kg8 g4 85.hxg4 Kg5 86.Bd7 Kf4 87.Kf7
  14	00:01,000	     657.668	1.370.141	-5,28	81. ... Kh8 82.Bd7 Kh7 83.Be8 Kh6 84.Kg8 g4 85.hxg4 Kg5 86.Bd7 Kg6 87.Bc6 Kf6
  15	00:01,000	   1.163.725	1.639.049	-5,28	81. ... Kh8 82.Bd7 Kh7 83.Be8 Kh6 84.Ke7 Kh7 85.Bh5 Kh6 86.Bd1
  16	00:02,343	   1.987.997	1.807.270	-5,44	81. ... Kh8 82.Bc8 Kh7 83.Ke6 Kg6 84.Ba6 Kg7 85.Kd5 Kh6 86.Kc4 g4 87.hxg4
  17	00:02,015	   2.875.011	1.903.980	-5,54	81. ... Kh8 82.Bc8 Kh7 83.Bd7 Kh8 84.Bb5 Kh7 85.Bc4 Kh6 86.Bd5 Kh5 87.Be6 g4 88.hxg4+ Kg5
  18	00:03,500	   4.771.746	2.013.394	-5,54	81. ... Kh8 82.Bc8 Kh7 83.Bd7 Kh8 84.Bb5 Kh7 85.Ba4 Kh6 86.Bb3 Kh5 87.Be6 g4 88.hxg4+ Kg5
  19	00:04,000	   7.560.824	1.629.487	-5,56	81. ... Kh8 82.Bd7 Kh7 83.Ba4 Kh8 84.Bc6 Kh7 85.Be4+ Kh8 86.Bb7 Kh7 87.Ba6 Kh8 88.Bc4 Kh7 89.Ba6

stalemate detection:

Code: Select all

Flip 1.0.0.26521:
   4	00:00,500	         629	62.900	-5,48	81. ... Kh6 82.Bg6 g4 83.hxg4
   4	00:00,500	         961	96.100	-5,46	81. ... Kh8 82.Ke8 g4 83.hxg4
   4	00:00,500	       1.042	104.200	 0,00	81. ... Kh8 82.Ke8 Kg7 83.Bb1
   4	00:00,500	       1.049	104.900	 0,00	81. ... Kh8 82.Ke8 Kg7
   5	00:00,500	       1.692	169.200	-0,30	81. ... Kh8 82.Bh7 Kxh7 83.Kf6 Kg8 84.Kg6 Kf8
   6	00:00,500	       4.082	136.066	 0,00	81. ... Kh8 82.Bh7 Kxh7 83.Kf6 Kg8 84.Kg6 Kf8 85.Kxg5
   7	00:00,500	      10.799	215.980	 0,00	81. ... Kh8 82.Bh7 Kxh7 83.Kf6 Kh8 84.Kf5 Kg7 85.Kxg5 Kf6+
   8	00:00,500	      19.984	285.485	-0,18	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6
   9	00:00,500	      40.771	453.011	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4
  10	00:00,515	      75.898	689.981	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4
  11	00:00,515	     136.652	911.013	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
  12	00:00,515	     274.047	1.245.668	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
  13	00:00,515	     472.621	1.476.940	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
  14	00:01,000	     758.142	1.648.134	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
  15	00:01,000	   1.269.063	1.762.587	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
  16	00:01,500	   2.004.687	1.856.191	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
  17	00:02,921	   3.110.049	1.931.707	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
  18	00:02,500	   4.629.450	2.004.090	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
  19	00:03,515	   6.625.625	2.051.277	 0,00	81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6

And this is very simple quick and dirty solution; just in the case that there are no captures in quiescence I generate all remaining moves. If there are not any then return draw score. NPS drop seems to be very low, about 2-3%.
Filip