stalemate detection in quiescence search

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
hgm
Posts: 27788
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: stalemate detection in quiescence search

Post by hgm »

OK, I see. The scores are about +4, to describe the advantage of B+P, plus possible passer bonuses.

It would probably sufficient to only test for stalemate (if there are no captures) in positions that have a bare King, or King + Pawns where all Pawns are blocked.
Top
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 8:30 pm
Location: Chicago, Illinois, USA

Re: stalemate detection in quiescence search

Post by michiguel »

hgm wrote:OK, I see. The scores are about +4, to describe the advantage of B+P, plus possible passer bonuses.

It would probably sufficient to only test for stalemate (if there are no captures) in positions that have a bare King, or King + Pawns where all Pawns are blocked.
Exactly. That solved it in my engine. I detect stalemate if there is a bare king (blocked paws will be next but it is not necessary in this case). The good thing is this can be done in eval, without the necessity to test it in quiescence search, which could be costly if you try to generate moves and test them for legality.

Miguel
Top
jan.klima

Re: stalemate detection in quiescence search

Post by jan.klima »

Thanks for your answers.

4Filip: I assume you did this in positions with side to move having only the king?

4Miguel:How exactly do you test for stalemate in your evaluation? My guess: you have attack_from table computed for every piece, "or-ing" these together? Then all you would have to do is checking whether there is a safe square for the king to move to. Unfortunately, I can't get this information from my evaluation.

To sum it up: One straightforward way to solve this problem could be:

once there are no captures and the side to move has got only king with pawns
1)test for blocked pawns(that is easy)
2)if there are no pawn pushes, test all king moves for legality(somehow, it probably doesn't matter)
Top
User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 7:31 pm
Location: Bonn, Germany

Re: stalemate detection in quiescence search

Post by Onno Garms »

jan.klima wrote: I think it does solve it.
If you want to convince me, you'll have to implement stalemate detection in an opensource engine. This should be quite easy in Toga. But I think you'll waste your time because it does not solve the problem.

EDIT: I saw Filip's post now. Strange. Maybe his engine has a faulty implementation of wrong-bishop-draws, forgetting the bold condition below? What evaluation does it give on
7k/p7/6p1/6p1/6B1/7P/8/K7 w - -
which should be a win for white according to my limitted chess knowledge.

I'll eventually try myself in Toga.
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...
Put the white king on A1 and the search will have much more difficulties to get the pawn on a good file. But the position is still a win for white.

Of course it still is possible to teach an engine that your position is a draw. But it is a very specialized position and I doubt that it is worth the efford.

The rule that is implemented in Toga says that a position is a draw if one side has a rook pawn and a bishop that cannot attack the promotion square. The weaker side has its king on the promotion square or next to it and no pawn in the file adjacent to the rook pawn and on a higher rank from the stronger's side view
Top
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 8:30 pm
Location: Chicago, Illinois, USA

Re: stalemate detection in quiescence search

Post by michiguel »

jan.klima wrote:Thanks for your answers.

4Filip: I assume you did this in positions with side to move having only the king?

4Miguel:How exactly do you test for stalemate in your evaluation? My guess: you have attack_from table computed for every piece, "or-ing" these together? Then all you would have to do is checking whether there is a safe square for the king to move to. Unfortunately, I can't get this information from my evaluation.
I used to have that information but I don't anymore.
Now I calculate that information when I needed, right there, on the spot. I have the routines that I calculate the attacks for each piece, and I do "or" while I loop them. It is much cheaper than testing for legality and moving the king. Besides, in these cases, you have few pieces.

If you have "incheck" routines, you can do that for each square that surrounds the king.

I think this is worth it because the cost is not important when a king is alone. We should be accurate. Also, this avoids any other side effect since it is done in eval. It is pretty well isolated.

I did this inspired by your post, so I have to say thanks. I always wanted this knowledge (B+rookP vs K) in my engine and this was a great opportunity to jump on it.

Miguel

To sum it up: One straightforward way to solve this problem could be:

once there are no captures and the side to move has got only king with pawns
1)test for blocked pawns(that is easy)
2)if there are no pawn pushes, test all king moves for legality(somehow, it probably doesn't matter)
Top
tvrzsky
Posts: 128
Joined: Sat Sep 23, 2006 7:10 pm
Location: Prague

Re: stalemate detection in quiescence search

Post by tvrzsky »

jan.klima wrote:Thanks for your answers.

4Filip: I assume you did this in positions with side to move having only the king?
Not really. I was not accurate in my description so I will try it again with some pseudocode.

Code: Select all

BestEval = Evaluation();
if (BestEval >= Beta) return BestEval;
int Moves = GenerateCaptures();
if (Moves)
{
... check those moves ...
}
// IN FACT I HAVE JUST ADDED NEXT FIVE LINES
else
{
  Moves = GenerateRemainingMoves();
  if (!Moves) return DRAW;
}
Of course it should have been done much more sophisticated way. This was only a quick hack with purpose to try if it could work at all.
Top
tvrzsky
Posts: 128
Joined: Sat Sep 23, 2006 7:10 pm
Location: Prague

Re: stalemate detection in quiescence search

Post by tvrzsky »

Onno Garms wrote: EDIT: I saw Filip's post now. Strange. Maybe his engine has a faulty implementation of wrong-bishop-draws, forgetting the bold condition below?
Definitely it is faulty and very simplistic neverless I have improved it little bit so it is able to somehow cope with your positions now.
[D]8/5K1k/8/5Bp1/8/7P/8/8 b - - 0 81
Flip 1.0.0.26532:
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 84.600 -0,30 81. ... Kh8 82.Bh7 Kxh7 83.Kf6 Kg8 84.Kg6 Kf8
6 00:00,500 4.082 102.050 0,00 81. ... Kh8 82.Bh7 Kxh7 83.Kf6 Kg8 84.Kg6 Kf8 85.Kxg5
7 00:00,500 10.799 179.983 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,516 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,516 75.898 632.483 0,00 81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4
11 00:00,516 136.652 854.075 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,516 274.047 1.191.508 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,516 472.621 1.432.184 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.613.068 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.787.412 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.909.225 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,781 3.110.049 1.956.005 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.021.593 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,500 6.625.625 2.076.998 0,00 81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
20 00:04,500 9.315.448 1.961.146 0,00 81. ... Kh8 82.Kf6 Kg8 83.Bb1 Kh8 84.Bh7 Kxh7 85.Kf7 Kh6 86.Ke6 g4 87.hxg4 87.Kf6
[D]8/5K1k/6p1/6p1/6B1/7P/8/8 w - - 0 1
Flip 1.0.0.26532:
4 00:00,500 163 16.300 -0,50 1.h4 gxh4 2.Kf6 g5
4 00:00,500 180 18.000 +2,56 1.Bc8 Kh6 2.Ba6 g4
4 00:00,500 351 35.100 +3,62 1.Bc8 Kh6 2.Be6 Kh7
5 00:00,500 1.157 57.850 +3,46 1.Bc8 Kh6 2.Be6 Kh7 3.Ke7
5 00:00,500 1.408 70.400 +3,48 1.Bd1 Kh6 2.Ba4 Kh7
5 00:00,500 1.463 73.150 +3,68 1.Bd1 Kh6 2.Bf3 Kh7
5 00:00,500 1.525 76.250 +3,70 1.Be2 Kh6 2.Bd3 Kh7
5 00:00,500 1.548 77.400 +3,70 1.Be2 Kh6 2.Bd3 Kh7
5 00:00,516 1.568 78.400 +3,72 1.Be6 Kh6 2.Bd5 Kh7
5 00:00,516 1.588 79.400 +3,72 1.Be6 Kh6 2.Bd5 Kh7
5 00:00,516 1.633 81.650 +3,76 1.Bf3 Kh6 2.Be4 Kh7
5 00:00,516 1.660 83.000 +3,76 1.Bf3 Kh6 2.Be4 Kh7
6 00:00,516 3.898 97.450 +3,60 1.Bf3 Kh6 2.Ke6 Kh7 3.Be4
6 00:00,516 4.727 118.175 +3,64 1.Bd1 Kh6 2.Be2 Kh7 3.Bc4
6 00:00,531 5.015 125.375 +3,52 1.Bd1 Kh6 2.Bf3 Kh7 3.Ke6
6 00:00,531 5.082 127.050 +3,64 1.Bc8 Kh6 2.Be6 Kh7 3.Ke7
6 00:00,531 5.136 128.400 +3,50 1.Bc8 Kh6 2.Bb7 Kh5
6 00:00,547 5.451 136.275 +3,56 1.Bd7 Kh6 2.Bc6 Kh5 3.Bd7 Kh6
6 00:00,547 5.787 144.675 +3,56 1.Bd7 Kh6 2.Bc6 Kh5 3.Ke6
6 00:00,547 7.546 188.650 +3,60 1.Ke7 Kg7 2.Kd6 Kf7 3.Bf3 Kf6
6 00:00,547 8.247 206.175 +3,70 1.Ke7 Kg7 2.Bf3 Kg8 3.Be4 Kg7
7 00:00,563 12.621 252.420 +3,64 1.Ke7 Kg7 2.Ke6 Kg8 3.Kd5 Kf7
7 00:00,563 13.420 268.400 +3,66 1.Be6 Kh8 2.Bd5 Kh7 3.Ke6 Kg7
7 00:00,563 13.924 232.066 +3,76 1.Be6 Kh8 2.Bd5 Kh7 3.Kf6 Kh6
7 00:00,578 15.740 262.333 +3,78 1.Ke6 Kg7 2.Bf3 Kf8 3.Be4 Kg7
7 00:00,578 15.860 264.333 +3,78 1.Ke6 Kg7 2.Bf3 Kf8 3.Be4 Kg7
8 00:01,594 22.255 317.928 +3,76 1.Ke6 Kg7 2.Bf3 Kf8 3.Be4 Ke8 4.Bd3 Kf8
8 00:01,594 23.303 332.900 +3,80 1.Be6 Kh8 2.Ke7 Kh7 3.Kd6 Kg7
8 00:01,594 23.458 335.114 +3,80 1.Be6 Kh8 2.Ke7 Kh7 3.Kd6 Kg7
8 00:01,609 29.628 423.257 +3,84 1.Kf6 Kg8 2.Be6+ Kh7 3.Bc4 Kh6 4.Ke5 Kg7
8 00:01,609 32.017 400.212 +3,84 1.Kf6 Kh6 2.Be6 Kh7 3.Bc4 Kh6
9 00:01,609 44.949 499.433 +3,80 1.Kf6 Kh6 2.Bf3 Kh7 3.Ke6 Kg7 4.Bd5 Kh6
9 00:01,625 53.518 535.180 +3,84 1.Bf3 Kh6 2.Ke6 Kh7 3.Bd5 Kg8
9 00:01,625 55.726 557.260 +3,88 1.Bf3 Kh6 2.Ke6 Kh7 3.Bd5 Kg8 4.Kd6+ Kg7
10 00:01,625 114.816 820.114 +3,78 1.Bf3 Kh8 2.Ba8 Kh7 3.Be4 Kh8 4.Bb1 Kh7 5.Be4 Kh6
10 00:01,641 118.476 846.257 +3,80 1.Be6 Kh6 2.Ke7 Kh7 3.Bc4 Kg7
10 00:01,641 119.132 850.942 +3,80 1.Be6 Kh6 2.Ke7 Kh7 3.Kf8 Kh6 4.Ke7
11 00:01,656 215.013 1.075.065 +3,78 1.Be6 Kh6 2.Bc8 Kh7 3.Bb7 Kh6 4.Bg2 Kh5
11 00:01,656 216.574 1.082.870 +3,80 1.Bf3 Kh8 2.Bd5 Kh7 3.Ke6 Kh6 4.Bc4
11 00:01,656 217.261 1.086.305 +3,82 1.Bf3 Kh8 2.Be4 Kh7 3.Ke7 Kh6 4.Kd6 Kg7
12 00:01,672 331.684 1.228.459 +3,82 1.Bf3 Kh8 2.Be4 Kh7 3.Bd3 Kh8 4.Ba6 Kh7
13 00:01,672 548.482 1.443.373 +3,80 1.Bf3 Kh8 2.Be2 Kh7 3.Bd1 Kh8 4.Ba4 Kh7 5.Bb5 Kh6
13 00:01,672 608.312 1.520.780 +3,82 1.Be6 Kh6 2.Ke7 Kh5 3.Bg4+ Kh4 4.Kf6 Kg3 5.Kxg5
13 00:01,688 611.446 1.491.331 +3,80 1.Be6 Kh6 2.Ke7 Kh5 3.Bg4+ Kh4 4.Kf6 Kg3 5.Kxg5 Kf2 6.Bf3
13 00:01,688 613.364 1.496.009 +3,82 1.Kf6 Kh6 2.Bd1 Kh7 3.Bb3 Kh6 4.Ke5 Kh5 5.Be6
13 00:01,703 627.051 1.529.392 +3,82 1.Kf6 Kh6 2.Ke5 Kg7 3.Be6 Kh6 4.Bf7 Kh7
14 00:01,000 1.122.732 1.675.719 +3,80 1.Kf6 Kg8 2.Be6+ Kh7 3.Bc8 Kh6 4.Ke5 Kh7 5.Bb7 Kh6 6.Bd5 Kg7 7.Bb3
14 00:01,000 1.143.587 1.681.745 +3,82 1.Be6 Kh6 2.Ke7 Kg7 3.Bc4 Kh7 4.Kd6 Kg7 5.Ke5 Kh6 6.Be6 Kh5
14 00:01,000 1.310.705 1.747.606 +3,82 1.Be6 Kh8 2.Ba2 Kh7 3.Bd5 Kh6 4.Bb3
15 00:01,016 1.618.840 1.818.921 +3,84 1.Be6 Kh8 2.Ba2 Kh7 3.Bd5 Kh6 4.Bb3 Kh7 5.Kf6 Kh6 6.Ke5 Kh5 7.Be6 Kh6
16 00:01,500 2.194.537 1.925.032 +3,84 1.Be6 Kh8 2.Ba2 Kh7 3.Bd5 Kh6 4.Bb3 Kh7 5.Kf6 Kh6 6.Be6 Kh7 7.Bc4 Kh8 8.Bd5 Kh7
17 00:02,844 3.065.974 2.003.904 +3,84 1.Be6 Kh8 2.Ba2 Kh7 3.Bd5 Kh6 4.Bb3 Kh7 5.Kf6 Kh6 6.Be6 g4 7.hxg4
18 00:02,500 4.667.400 2.102.432 +3,84 1.Be6 Kh8 2.Bb3 Kh7 3.Bc2 Kh8 4.Ba4 Kh7 5.Bc6 Kh8 6.Bd5 Kh7 7.Ke6 Kg7 8.Be4 Kf8
18 00:03,844 5.782.163 2.125.795 +3,86 1.Bd7 Kh8 2.Be6 Kh7 3.Kf8 g4 4.hxg4 Kh6 5.Bc8 Kg5 6.Kf7 Kf4
18 00:03,844 5.810.502 2.120.621 +5,16 1.Bd7 Kh8 2.Be6 Kh7 3.Kf8 g4 4.hxg4 Kh8 5.Bd5 Kh7 6.Bg8+ Kh6 7.Be6 Kh7
18 00:03,844 5.832.982 2.121.084 +5,02 1.Bd7 Kh8 2.Be8 Kh7 3.h4 g4 4.Kf6 Kh6 5.Bf7 Kh7 6.Bxg6+ Kg8
19 00:04,844 7.481.915 1.760.450 +5,56 1.Bd7 Kh8 2.Be6 Kh7 3.Kf8 Kh6 4.Kg8 Kh5 5.Kg7 Kh4 6.Kxg6 Kg3 7.Kxg5 Kf3 8.Bd5+ Ke3
20 00:04,500 9.119.938 1.919.986 +5,52 1.Bd7 Kh8 2.Be6 Kh7 3.Kf8 Kh6 4.Kg8 Kh5 5.Kh7 Kh4 6.Kxg6 Kg3 7.Bg4 Kf4
[D]7k/p7/6p1/6p1/6B1/7P/8/K7 w - - 0 1
Flip 1.0.0.26532:
4 00:00,500 189 18.900 -1,40 1.h4 gxh4 2.Kb2 g5
4 00:00,500 238 23.800 +0,80 1.Bc8 Kg7 2.Ba6 g4
4 00:00,500 466 46.600 +1,82 1.Bc8 Kg7 2.Kb2 a5
4 00:00,500 552 55.200 +1,88 1.Bd7 a5 2.Kb2 Kg7
4 00:00,500 571 57.100 +1,88 1.Bd7 a5 2.Kb2 Kg7
4 00:00,500 640 64.000 +2,08 1.Be6 a5 2.Kb2 a4
4 00:00,500 661 66.100 +2,08 1.Be6 a5 2.Kb2 a4
5 00:00,500 1.646 82.300 +1,90 1.Be6 a5 2.Kb2 a4 3.Kc3
6 00:00,500 4.838 120.950 +2,04 1.Be6 a5 2.Kb2 Kg7 3.Kb3 Kf6
7 00:00,516 10.265 205.300 +1,78 1.Be6 a5 2.Kb2 Kg7 3.Kb3 Kf6 4.Bd5
7 00:00,516 16.280 271.333 +1,94 1.Ka2 Kg7 2.Kb3 Kf6 3.Bd7 a5
7 00:00,516 17.922 298.700 +1,94 1.Ka2 Kg7 2.Be6 Kf6 3.Bd5 a6 4.Kb3
8 00:00,516 36.179 452.237 +2,00 1.Ka2 Kg7 2.Kb3 Kf6 3.Kb4 Ke7 4.Bc8 Kd6
8 00:00,516 49.441 549.344 +2,02 1.Kb2 Kg7 2.Kb3 Kf6 3.Kb4 Ke7 4.Bf3 a6
8 00:00,532 51.380 570.888 +2,04 1.Kb2 Kg7 2.Kb3 Kf6 3.Kb4 Ke7 4.Kc4 a5
9 00:00,532 85.437 711.975 +1,92 1.Kb2 Kg7 2.Kb3 Kf6 3.Ka4 Ke5 4.Kb5 Kd4
10 00:00,532 136.731 911.540 +2,02 1.Kb2 Kg7 2.Kb3 Kf6 3.Kb4 Ke5 4.Bf3 Kf4 5.Bd5
11 00:00,547 275.279 1.146.995 +2,00 1.Kb2 Kg7 2.Kb3 Kf6 3.Kc4 Ke5 4.Kb4 Kd5 5.Bf3+ Ke6 6.Bg4+ Kd5
12 00:01,000 655.069 1.393.763 +2,60 1.Kb2 Kg7 2.Kb3 Kf6 3.Kc4 Ke5 4.Kb5 Kd5 5.Ka6 Kd4 6.Kxa7
12 00:01,000 656.809 1.397.465 +2,62 1.Ka2 Kg7 2.Kb3 Kf6 3.Kb4 Kg7 4.Ka4 Kh7
12 00:01,000 658.071 1.400.151 +2,38 1.Ka2 Kg7 2.Kb3 Kf6 3.Kb4 Ke5 4.Be2 Kf4
13 00:01,016 799.478 1.427.639 +2,84 1.Ka2 Kg7 2.Kb3 Kf6 3.Kb4 Ke7 4.Ka5 Kf6 5.Ka6 Ke5 6.Kxa7 Kd4 7.Bf3
14 00:01,500 1.706.800 1.537.657 +3,00 1.Ka2 Kg7 2.Ka3 Kf8 3.Ka4 Ke8 4.Kb5 Kf7 5.Bc8 Ke8 6.Be6 Ke7
14 00:01,500 1.783.314 1.550.707 +3,02 1.Kb2 Kg7 2.Ka3 Kf8 3.Kb4 a5+ 4.Kxa5
14 00:01,500 1.795.281 1.547.656 +3,02 1.Kb2 Kg7 2.Ka3 Kf8 3.Kb4 a6 4.Ka5 Ke7 5.Kxa6 Kd6
15 00:02,594 2.467.353 1.612.649 +2,98 1.Kb2 Kg7 2.Ka3 Kf6 3.Ka4 Ke5 4.Ka5 Kd4 5.Ka6 Kc4 6.Kxa7 Kb5 7.Kb7 Kc5 8.Be6
16 00:04,000 5.950.042 1.400.009 +3,14 1.Kb2 Kg7 2.Ka3 Kf6 3.Kb4 Ke5 4.Kb5 Kd4 5.Ka6 Kc5 6.Kxa7 Kc6 7.Be6 Kd6 8.Bc4 Ke5
17 00:05,000 7.975.610 1.519.163 +3,26 1.Kb2 Kg7 2.Ka3 Kf6 3.Ka4 Ke5 4.Ka5 Kd5 5.Ka6 Kc6 6.Kxa7 Kc5 7.Bf3 Kb5 8.Bd5 Kc5
18 00:07,000 11.666.772 1.609.209 +3,40 1.Kb2 Kg7 2.Kb3 Kf6 3.Ka4 Ke5 4.Kb5 Kd4 5.Ka6 Kc5 6.Kxa7 Kb5 7.Kb7 Ka4 8.Ka6 Kb3 9.Bf3
19 00:09,500 16.008.553 1.641.902 +3,40 1.Kb2 Kg7 2.Ka3 Kf6 3.Ka4 Ke5 4.Bd7 Kd4 5.Be8 a6 6.Ka5 Kc3 7.Kxa6 Kb3 8.Bf7+ Kb2
20 00:12,594 20.394.141 1.699.511 +3,42 1.Kb2 Kg7 2.Ka3 Kf6 3.Ka4 Ke5 4.Kb5 Kd4 5.Ka6 Kc5 6.Kxa7 Kb5 7.Bd7+ Kc4 8.Kb6 Kd5 9.Kb5 Ke4 10.Bc6+ Kd4
Top
tvrzsky
Posts: 128
Joined: Sat Sep 23, 2006 7:10 pm
Location: Prague

Re: stalemate detection in quiescence search

Post by tvrzsky »

tvrzsky wrote:
jan.klima wrote:Thanks for your answers.

4Filip: I assume you did this in positions with side to move having only the king?
Not really. I was not accurate in my description so I will try it again with some pseudocode.

Code: Select all

BestEval = Evaluation();
if (BestEval >= Beta) return BestEval;
int Moves = GenerateCaptures();
if (Moves)
{
... check those moves ...
}
// IN FACT I HAVE JUST ADDED NEXT FIVE LINES
else
{
  Moves = GenerateRemainingMoves();
  if (!Moves) return DRAW;
}
Of course it should have been done much more sophisticated way. This was only a quick hack with purpose to try if it could work at all.
P.S. All my move generators are legal ones ...
Top
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 8:30 pm
Location: Chicago, Illinois, USA

Re: stalemate detection in quiescence search

Post by michiguel »

Onno Garms wrote:
jan.klima wrote: I think it does solve it.
If you want to convince me, you'll have to implement stalemate detection in an opensource engine. This should be quite easy in Toga. But I think you'll waste your time because it does not solve the problem.

EDIT: I saw Filip's post now. Strange. Maybe his engine has a faulty implementation of wrong-bishop-draws, forgetting the bold condition below? What evaluation does it give on
7k/p7/6p1/6p1/6B1/7P/8/K7 w - -
which should be a win for white according to my limitted chess knowledge.

I'll eventually try myself in Toga.
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...
Put the white king on A1 and the search will have much more difficulties to get the pawn on a good file. But the position is still a win for white.

Of course it still is possible to teach an engine that your position is a draw. But it is a very specialized position and I doubt that it is worth the efford.

The rule that is implemented in Toga says that a position is a draw if one side has a rook pawn and a bishop that cannot attack the promotion square. The weaker side has its king on the promotion square or next to it and no pawn in the file adjacent to the rook pawn and on a higher rank from the stronger's side view
The detection of stalemate in quiescence search certainly has an effect.
Look at the PV in iteration 12

Without detection (Gaviota unreleased debug version):

Code: Select all


      4361   5       0.2    -0.33  Kh7-h8   Bf5-e4   g5-g4    h3-h4
                                   g4-g3
      4363   5:      0.2    -0.33  Kh7-h8   Bf5-e4   g5-g4    h3-h4
                                   g4-g3
      8394   6       0.3    -0.38  Kh7-h8   Bf5-e4   g5-g4    h3-h4
                                   g4-g3    Kf7-e6
      8418   6:      0.3    -0.38  Kh7-h8   Bf5-e4   g5-g4    h3-h4
                                   g4-g3    Kf7-e6
     22085   7       0.7    -0.23  Kh7-h8   Kf7-f6   Kh8-g8   Bf5-e6
                                   Kg8-h7   Be6-f7   Kh7-h8   Kf6-f5
     22127   7:      0.7    -0.23  Kh7-h8   Kf7-f6   Kh8-g8   Bf5-e6
                                   Kg8-h7   Be6-f7   Kh7-h8   Kf6-f5
     51954   8       1.6    -0.23  Kh7-h8   Kf7-f6   Kh8-g8   Bf5-e6
                                   Kg8-f8   Be6-d5   Kf8-e8   Kf6-f5
                                   Ke8-d8
     52013   8:      1.6    -0.23  Kh7-h8   Kf7-f6   Kh8-g8   Bf5-e6
                                   Kg8-f8   Be6-d5   Kf8-e8   Kf6-f5
                                   Ke8-d8
    106685   9       2.9    -0.36  Kh7-h8   Kf7-f6   Kh8-g8   Bf5-e6
                                   Kg8-f8   Be6-f7   g5-g4    h3-h4
                                   g4-g3    Bf7-d5
    106765   9:      3.0    -0.36  Kh7-h8   Kf7-f6   Kh8-g8   Bf5-e6
                                   Kg8-f8   Be6-f7   g5-g4    h3-h4
                                   g4-g3    Bf7-d5
    191931  10       5.3      :-(  Kh7-h8
    192077  10       5.4      :-(
    192188  10       5.4      :-(  Kh7-h8
    192219  10       5.4      :-(
    267331  10       7.0    -3.53  Kh7-h8   Bf5-e6   Kh8-h7   Be6-d5
                                   Kh7-h6   Bd5-f3   Kh6-h7   Bf3-e4
                                   Kh7-h6   Be4-g6   g5-g4    h3xg4
    267368  10:      7.0    -3.53  Kh7-h8   Bf5-e6   Kh8-h7   Be6-d5
                                   Kh7-h6   Bd5-f3   Kh6-h7   Bf3-e4
                                   Kh7-h6   Be4-g6   g5-g4    h3xg4
    528141  11      12.7    -3.53  Kh7-h8   Bf5-e6   Kh8-h7   Be6-d5
                                   Kh7-h6   Bd5-f3   Kh6-h7   Bf3-e4
                                   Kh7-h6   Be4-g6   g5-g4    h3xg4
    528793  11:     12.8    -3.53  Kh7-h8   Bf5-e6   Kh8-h7   Be6-d5
                                   Kh7-h6   Bd5-f3   Kh6-h7   Bf3-e4
                                   Kh7-h6   Be4-g6   g5-g4    h3xg4
   1084841  12      25.0    -3.55  Kh7-h8   Bf5-d7   Kh8-h7   Bd7-e8
                                   Kh7-h8   Kf7-f8   Kh8-h7   Be8-f7
                                   Kh7-h6   Kf8-g8   g5-g4    h3xg4
   1085785  12:     25.0    -3.55  Kh7-h8   Bf5-d7   Kh8-h7   Bd7-e8
                                   Kh7-h8   Kf7-f8   Kh8-h7   Be8-f7
                                   Kh7-h6   Kf8-g8   g5-g4    h3xg4
With detection of stalemate of bare kings in the evaluation

Code: Select all


      1288   5       0.1    -0.33  Kh7-h8   Bf5-e4   g5-g4    h3-h4
                                   g4-g3
      1294   5:      0.1    -0.33  Kh7-h8   Bf5-e4   g5-g4    h3-h4
                                   g4-g3
      5187   6       0.2    -0.38  Kh7-h8   Bf5-e4   g5-g4    h3-h4
                                   g4-g3    Kf7-e6
      5210   6:      0.2    -0.38  Kh7-h8   Bf5-e4   g5-g4    h3-h4
                                   g4-g3    Kf7-e6
     16255   7       0.5    -0.22  Kh7-h8   Kf7-f6   Kh8-g8   Bf5-e4
                                   Kg8-f8   Be4-c6   Kf8-g8
     16289   7:      0.5    -0.22  Kh7-h8   Kf7-f6   Kh8-g8   Bf5-e4
                                   Kg8-f8   Be4-c6   Kf8-g8
     42976   8       1.2    -0.23  Kh7-h8   Kf7-g6   Kh8-g8   Bf5-e6
                                   Kg8-f8   Kg6xg5   Kf8-e7   h3-h4
                                   Ke7-d6
     43038   8:      1.2    -0.23  Kh7-h8   Kf7-g6   Kh8-g8   Bf5-e6
                                   Kg8-f8   Kg6xg5   Kf8-e7   h3-h4
                                   Ke7-d6
     98815   9       2.5    -0.24  Kh7-h8   Kf7-g6   Kh8-g8   Bf5-e6
                                   Kg8-f8   Kg6-f6   Kf8-e8   Kf6xg5
                                   Ke8-f8   h3-h4
     98904   9:      2.6    -0.24  Kh7-h8   Kf7-g6   Kh8-g8   Bf5-e6
                                   Kg8-f8   Kg6-f6   Kf8-e8   Kf6xg5
                                   Ke8-f8   h3-h4
    260778  10       6.8    -0.33  Kh7-h8   Bf5-e6   Kh8-h7   Be6-d5
                                   Kh7-h6   Bd5-f3   Kh6-h7   Bf3-e4
                                   Kh7-h8   Be4-f5   g5-g4    <-transp
    260947  10&#58;      6.8    -0.33  Kh7-h8   Bf5-e6   Kh8-h7   Be6-d5
                                   Kh7-h6   Bd5-f3   Kh6-h7   Bf3-e4
                                   Kh7-h8   Be4-f5   g5-g4    <-transp
    510613  11      12.3    -0.33  Kh7-h8   Bf5-e6   Kh8-h7   Be6-d5
                                   Kh7-h6   Bd5-f3   Kh6-h7   Bf3-e4
                                   Kh7-h8   Be4-f5   g5-g4    <-transp
    511240  11&#58;     12.3    -0.33  Kh7-h8   Bf5-e6   Kh8-h7   Be6-d5
                                   Kh7-h6   Bd5-f3   Kh6-h7   Bf3-e4
                                   Kh7-h8   Be4-f5   g5-g4    <-transp
   1102171  12      26.9    -0.33  Kh7-h8   Bf5-e6   Kh8-h7   Be6-g4
                                   Kh7-h6   Bg4-d1   Kh6-h7   Bd1-c2
                                   Kh7-h8   Bc2-e4   g5-g4    h3-h4
                                   g4-g3
   1103284  12&#58;     26.9    -0.33  Kh7-h8   Bf5-e6   Kh8-h7   Be6-g4
                                   Kh7-h6   Bg4-d1   Kh6-h7   Bd1-c2
                                   Kh7-h8   Bc2-e4   g5-g4    h3-h4
                                   g4-g3
Regards,
Miguel
Top

Return to “Computer Chess Club: Programming and Technical Discussions”