funny, I've always used fail hard, because that's the way I originally wrote it (probably because 90% of sample pseudo-code on the web writes it as fail hard), and like you, I kind of forgot about it.
But now you have me thinking. Fail soft means boundary scores < Alpha or > Beta can be returned, which are better bounds than simply Alpha or Beta. Better bounds means less nodes to process in search.
So now I'm wondering why anyone would use fail hard...
Fail soft/Fail hard
Moderator: Ras
-
Zach Wegner
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Fail soft/Fail hard
Well, the improved bounds don't matter except for hashing, unless you somehow use them for some type of search decision (most people don't). And I don't even use the improved bounds for hashing, so maybe I should...AndrewShort wrote:funny, I've always used fail hard, because that's the way I originally wrote it (probably because 90% of sample pseudo-code on the web writes it as fail hard), and like you, I kind of forgot about it.
But now you have me thinking. Fail soft means boundary scores < Alpha or > Beta can be returned, which are better bounds than simply Alpha or Beta. Better bounds means less nodes to process in search.
So now I'm wondering why anyone would use fail hard...
-
hgm
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Fail soft/Fail hard
I use fail soft in Joker, and it works flawlessly. As it should, as it is theoretically 100% upward compatible with fail hard. I have never measured how much it does save, though.
The problem you sketch is merely that wrong scores in end leaves might propagate to the roor. The probability for that to happen if a single leaf has an erroneous score is very small, as one side will try (and usually succeed) to avoid the score if he doesn't like it, and at least one of them will not like it.
But it seems you gave totally wrong upper bounds for almost all leaf nodes, because of the futility error. You might argue that this shouldn't matter, as the score was below alpha anyway, and would thus cause a fail high in the parent no matter how bad it was. But the problem is that it gets stored in the hash, and then probed later, in branches were alpha is different. And then it retrieves scores below the new alpha, while they in reality might have been above alpha, as the 'upper limit' you stored was in fact no upper limit at all, and there were better moves, scoring below the old alpha, but above the new one. So you get fail lows where there should have been fail highs, and that tends to draw the PV to such nodes.
The idea of fail low is to increase efficiency by giving bounds that are as sharp as possible. But if you can only give sharper bounds by giving wrong bounds, it will corrupt the result rather than increase efficiency. And this is what you are seeing.
The problem you sketch is merely that wrong scores in end leaves might propagate to the roor. The probability for that to happen if a single leaf has an erroneous score is very small, as one side will try (and usually succeed) to avoid the score if he doesn't like it, and at least one of them will not like it.
But it seems you gave totally wrong upper bounds for almost all leaf nodes, because of the futility error. You might argue that this shouldn't matter, as the score was below alpha anyway, and would thus cause a fail high in the parent no matter how bad it was. But the problem is that it gets stored in the hash, and then probed later, in branches were alpha is different. And then it retrieves scores below the new alpha, while they in reality might have been above alpha, as the 'upper limit' you stored was in fact no upper limit at all, and there were better moves, scoring below the old alpha, but above the new one. So you get fail lows where there should have been fail highs, and that tends to draw the PV to such nodes.
The idea of fail low is to increase efficiency by giving bounds that are as sharp as possible. But if you can only give sharper bounds by giving wrong bounds, it will corrupt the result rather than increase efficiency. And this is what you are seeing.
-
michiguel
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Fail soft/Fail hard
No, it was only one position that contaminated everything little by little. That is what I am trying to say. (and yes, the origin was a futility problem). In fact, I think I remember now.hgm wrote:I use fail soft in Joker, and it works flawlessly. As it should, as it is theoretically 100% upward compatible with fail hard. I have never measured how much it does save, though.
The problem you sketch is merely that wrong scores in end leaves might propagate to the roor. The probability for that to happen if a single leaf has an erroneous score is very small, as one side will try (and usually succeed) to avoid the score if he doesn't like it, and at least one of them will not like it.
But it seems you gave totally wrong upper bounds for almost all leaf nodes, because of the futility error...
[d]8/Pk6/8/1K6/3B4/P7/8/8 w - - 1 12
In this position, the "winning" move inside the search is a8=R. Now we go to quiescence() and black sees that the stand pat score is -(P+B+R). Capturing the rook + margin will not bring the score to alpha, which is close to a drawish score (for positional reasons: wrong bishop). Of course, it depends of the margin (if it is bigger than B+P we would see no problem). As a consequence, it will return in a fail soft fashion a bound that is bad for black.
Note that a8=Q+ does not do it because it triggers the check evasion
Look at the crazy unstable search from this position
[d]1k6/8/PB6/1K6/8/P7/8/8 w - - 5 8
Code: Select all
analyze
567 7: 0.1 +0.00 Kb5-c4 Kb8-a8 a6-a7 Ka8-b7
Kc4-c5 Kb7-a8 <-transp
570 8 0.1 :-) Kb5-c4
619 8 0.1 +0.00 Kb5-c4 Kb8-a8 a6-a7 Ka8-b7
Kc4-c5 Kb7-a8 <-transp
669 8: 0.1 +0.00 Kb5-c4 Kb8-a8 a6-a7 Ka8-b7
Kc4-c5 Kb7-a8 <-transp
672 9 0.1 :-) Kb5-c4
729 9 0.1 +0.00 Kb5-c4 Kb8-a8 a6-a7 Ka8-b7
Kc4-c5 Kb7-a8 <-transp
783 9: 0.1 +0.00 Kb5-c4 Kb8-a8 a6-a7 Ka8-b7
Kc4-c5 Kb7-a8 <-transp
786 10 0.1 :-) Kb5-c4
846 10 0.1 +0.00 Kb5-c4 Kb8-a8 a6-a7 Ka8-b7
Kc4-c5 Kb7-a8 <-transp
906 10: 0.1 +0.00 Kb5-c4 Kb8-a8 a6-a7 Ka8-b7
Kc4-c5 Kb7-a8 <-transp
909 11 0.1 :-) Kb5-c4
9843 11 0.3 :-) Kb5-c4
14200 11 0.4 +0.00 Kb5-c4 Kb8-a8 Kc4-d4 Ka8-b8
Kd4-d3 Kb8-a8 a3-a4 Ka8-b8
Kd3-c4 Kb8-a8 Bb6-g1
126374 11: 2.9 +0.00 Kb5-c4 Kb8-a8 Kc4-d4 Ka8-b8
Kd4-d3 Kb8-a8 a3-a4 Ka8-b8
Kd3-c4 Kb8-a8 Bb6-g1
131532 12 3.0 :-) Kb5-c4
135822 12 3.1 :-) Kb5-c4
136314 12 3.1 :-) Kb5-c4
293775 12 6.6 +0.34 Kb5-c4 Kb8-a8 a3-a4 Ka8-b8
a4-a5 Kb8-a8 Bb6-e3 Ka8-b8
Kc4-d4 Kb8-a7 Kd4-e5 Ka7xa6
Be3-d2
410856 12 9.0 +0.57 a3-a4 Kb8-a8 Kb5-c5 Ka8-b8
Kc5-d6 Kb8-a8 Bb6-f2 Ka8-b8
Bf2-e3 Kb8-c8 Be3-a7 Kc8-d8
604076 12: 14.0 +0.57 a3-a4 Kb8-a8 Kb5-c5 Ka8-b8
Kc5-d6 Kb8-a8 Bb6-f2 Ka8-b8
Bf2-e3 Kb8-c8 Be3-a7 Kc8-d8
609196 13 14.1 :-) a3-a4
609625 13 14.2 :-) a3-a4
610301 13 14.2 :-) a3-a4
845789 13 19.3 +0.60 a3-a4 Kb8-a8 Kb5-c5 Ka8-b8
Kc5-c4 Kb8-a8 Bb6-f2 Ka8-b8
Kc4-c3 Kb8-c7 Kc3-d2 Kc7-c6
a4-a5
[d]kn6/2B5/8/1P6/1K6/P7/8/8 b - - 0 1
Code: Select all
analyze
7 1 0.0 -5.68 Nb8-c6 b5xc6
8 1 0.0 -2.77 Nb8-d7
21 1 0.0 -0.60 Nb8-a6 Kb4-c4 Na6xc7
23 1: 0.0 -0.60 Nb8-a6 Kb4-c4 Na6xc7
41 2 0.0 -0.60 Nb8-a6 Kb4-c4 Na6xc7
55 2: 0.0 -0.60 Nb8-a6 Kb4-c4 Na6xc7
156 3 0.0 -0.84 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
193 3: 0.0 -0.84 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
542 4 0.0 -0.75 Nb8-a6 Kb4-a5 Na6xc7 a3-a4
Nc7-e6
611 4: 0.0 -0.75 Nb8-a6 Kb4-a5 Na6xc7 a3-a4
Nc7-e6
1891 5 0.1 -0.80 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
Ka8-b8 Kc4-d4
2094 5: 0.1 -0.80 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
Ka8-b8 Kc4-d4
4237 6 0.2 -0.62 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-d5
<EMPTY> <-transp
4590 6: 0.2 -0.62 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-d5
<EMPTY> <-transp
12112 7 1.0 -0.71 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
Ka8-b7 Kc4-b3 Kb7-b6 Kb3-b4
<EMPTY> <-transp
12924 7: 1.0 -0.71 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
Ka8-b7 Kc4-b3 Kb7-b6 Kb3-b4
<EMPTY> <-transp
27026 8 1.4 -0.55 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
Ka8-b7 Kc4-c5 Nc7-a6 Kc5-d4
Kb7-b6 Kd4-d5
29006 8: 1.5 -0.55 Nb8-a6 Kb4-c4 Na6xc7 a3-a4
Ka8-b7 Kc4-c5 Nc7-a6 Kc5-d4
Kb7-b6 Kd4-d5
44948 9 1.9 :-( Nb8-a6
51535 9 2.2 :-(
51538 9 2.2 :-( Nb8-a6
54916 9 2.3 :-(
62297 9 2.4 :-( Nb8-a6
193365 9 7.0 -3.21 Nb8-d7 a3-a4 Ka8-b7 Bc7-d6
Nd7-b8 Bd6xb8 Kb7xb8 a4-a5
Kb8-a7 Kb4-c4 Ka7-b8
194890 9: 7.1 -3.21 Nb8-d7 a3-a4 Ka8-b7 Bc7-d6
Nd7-b8 Bd6xb8 Kb7xb8 a4-a5
Kb8-a7 Kb4-c4 Ka7-b8
318239 10 11.1 -3.29 Nb8-d7 a3-a4 Ka8-b7 Bc7-d6
Kb7-a8 a4-a5 Nd7-f6 Bd6-c5
Ka8-b8 Kb4-c4
368749 10 12.3 :-) Nb8-a6
369433 10 12.3 :-) Nb8-a6
371084 10 12.3 :-( Nb8-a6
371117 10 12.3 -3.29 Nb8-d7 a3-a4 Ka8-b7 <-transp
377041 10: 12.5 -3.29 Nb8-d7 a3-a4 Ka8-b7 <-transp
Code: Select all
script script8.txt
+-----------------+
| k n . . . . . . | [Black]
| . . B . . . . . |
| . . . . . . . . |
| . P . . . . . . | Castling:
| . K . . . . . . | ep: -
| P . . . . . . . |
| . . . . . . . . |
| . . . . . . . . |
+-----------------+
analyze
7 1 0.0 -5.68 Nb8-c6 b5xc6
8 1 0.0 -2.77 Nb8-d7
21 1 0.0 -0.60 Nb8-a6 Kb4-c4 Na6xc7
23 1: 0.0 -0.60 Nb8-a6 Kb4-c4 Na6xc7
41 2 0.0 -0.60 Nb8-a6 Kb4-c4 Na6xc7
56 2: 0.0 -0.60 Nb8-a6 Kb4-c4 Na6xc7
268 3 0.0 -0.48 Nb8-a6 Kb4-a5 Na6xc7 b5-b6
310 3: 0.0 -0.48 Nb8-a6 Kb4-a5 Na6xc7 b5-b6
552 4 0.0 -0.40 Nb8-a6 Kb4-a5 Na6xc7 b5-b6
Nc7-d5
653 4: 0.0 -0.40 Nb8-a6 Kb4-a5 Na6xc7 b5-b6
Nc7-d5
1795 5 0.0 -0.38 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b8 Kc4-d4
2060 5: 0.0 -0.38 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b8 Kc4-d4
3606 6 0.1 -0.37 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b8 Kc4-c5 Kb8-c8
3984 6: 0.1 -0.37 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b8 Kc4-c5 Kb8-c8
9710 7 0.2 -0.30 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-d5 Kc5-b5
Nd5xb6
10592 7: 0.2 -0.30 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-d5 Kc5-b5
Nd5xb6
19544 8 0.3 -0.30 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-d5 Kc5-b5
Nd5xb6
21875 8: 0.3 -0.30 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-d5 Kc5-b5
Nd5xb6
49821 9 0.7 -0.11 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4-b4
57311 9: 0.8 -0.11 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4-b4
111011 10 1.6 +0.00 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4-b4
Nd4-c2 Kb4-a4 Nc2xa3
117634 10: 1.7 +0.00 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4-b4
Nd4-c2 Kb4-a4 Nc2xa3
219295 11 2.9 +0.00 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4-b4
Nd4-c2 Kb4-a4 Nc2xa3
237558 11: 3.2 +0.00 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4-b4
Nd4-c2 Kb4-a4 Nc2xa3
447124 12 5.7 +0.00 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4xd4
483773 12: 6.2 +0.00 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4xd4
942311 13 11.4 +0.00 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4xd4
1041752 13: 12.9 +0.00 Nb8-a6 Kb4-c4 Na6xc7 b5-b6
Ka8-b7 Kc4-c5 Nc7-e6 Kc5-b5
Ne6-d4 Kb5-c4 Kb7xb6 Kc4xd4
Miguel
... You might argue that this shouldn't matter, as the score was below alpha anyway, and would thus cause a fail high in the parent no matter how bad it was. But the problem is that it gets stored in the hash, and then probed later, in branches were alpha is different. And then it retrieves scores below the new alpha, while they in reality might have been above alpha, as the 'upper limit' you stored was in fact no upper limit at all, and there were better moves, scoring below the old alpha, but above the new one. So you get fail lows where there should have been fail highs, and that tends to draw the PV to such nodes.
The idea of fail low is to increase efficiency by giving bounds that are as sharp as possible. But if you can only give sharper bounds by giving wrong bounds, it will corrupt the result rather than increase efficiency. And this is what you are seeing.
-
Zach Wegner
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Fail soft/Fail hard
There's your problem there, and that doesn't really have anything to do with fail soft. Fail soft _amplifies_ it, yes, because you return -9 or so instead of alpha, but the fundamental problem is that you are pruning Kxa8, when in fact the eval of the position right after that is right around alpha. Maybe the best way to solve this is to set a flag in the eval that there is a hanging piece and either not stand pat or increase the margin, or that the material is one conversion away from a draw. I'd prefer the former really, just a sort of static threat detection, but it's a tradeoff.michiguel wrote:In this position, the "winning" move inside the search is a8=R. Now we go to quiescence() and black sees that the stand pat score is -(P+B+R). Capturing the rook + margin will not bring the score to alpha, which is close to a drawish score (for positional reasons: wrong bishop).
And for the record, ZCT evaluates this pretty stably, but as won for white.
-
Harald Johnsen
Re: Fail soft/Fail hard
michiguel wrote:No, it was only one position that contaminated everything little by little. That is what I am trying to say. (and yes, the origin was a futility problem). In fact, I think I remember now.
[d]8/Pk6/8/1K6/3B4/P7/8/8 w - - 1 12
In this position, the "winning" move inside the search is a8=R. Now we go to quiescence() and black sees that the stand pat score is -(P+B+R). Capturing the rook + margin will not bring the score to alpha, which is close to a drawish score (for positional reasons: wrong bishop). Of course, it depends of the margin (if it is bigger than B+P we would see no problem). As a consequence, it will return in a fail soft fashion a bound that is bad for black.
Code: Select all
if( stand_pat_score + capture_value + margin < alpha ) {
prune;
}
if( stand_pat_score + capture_value + margin < alpha ) {
if( stand_pat_score + capture_value > bestScore )
bestScore = stand_pat_score + capture_value;
prune;
}Anyway pruning bad captures or pruning captures that won't make you reach alpha is unsound in endgames (because the value of the position has not a lot do to with the material).
I use recognizers, no pruning in qs when the stm has less than a rook :
Code: Select all
FEN: 8/Pk6/8/1K6/3B4/P7/8/8 w - - 0 12
Cyrano 0.5b1:
1/3 00:00 42 0 0,00 a8Q+ Kxa8
2/4 00:00 93 0 0,00 a8Q+ Kxa8 Bh8
3/5 00:00 149 0 0,00 a8Q+ Kxa8 Bh8 Ka7
4 00:00 210 0 0,00 a8Q+ Kxa8 Bh8 Ka7
5/8 00:00 278 0 0,00 a8Q+ Kxa8 Bh8 Ka7
6/10 00:00 428 0 0,00 a8Q+ Kxa8 Bh8 Ka7
7/10 00:00 520 0 0,00 a8Q+ Kxa8 Bh8 Ka7
8/10 00:00 622 0 0,00 a8Q+ Kxa8 Bh8 Ka7
...
FEN: 1k6/8/PB6/1K6/8/P7/8/8 w - - 0 8
Cyrano 0.5b1:
1/5 00:00 33 0 0,00 Bg1
2/4 00:00 59 0 0,00 Bg1 Ka8
3/4 00:00 98 0 0,00 Bg1 Ka8 a7
4/7 00:00 150 0 0,00 Bg1 Ka8 a7 Kb7
5/6 00:00 200 0 0,00 Bg1 Ka8 a7 Kb7
6/6 00:00 266 0 0,00 Bg1 Ka8 a7 Kb7
7/8 00:00 367 0 0,00 Bg1 Ka8 a7 Kb7
8/8 00:00 447 0 0,00 Bg1 Ka8 a7 Kb7
...
FEN: kn6/2B5/8/1P6/1K6/P7/8/8 b - - 0 1
Cyrano 0.5b1:
1/4 00:00 43 0 -0,48 Na6+ Kc4 Nxc7
2/4 00:00 66 0 -0,48 Na6+ Kc4 Nxc7
3/6 00:00 141 0 -0,74 Na6+ Kc4 Nxc7 b6
4/8 00:00 359 0 -0,36 Na6+ Kc4 Nxc7 b6 Kb7
5/10 00:00 616 0 -0,38 Na6+ Kc4 Nxc7 b6 Kb7 Kc5
6/10 00:00 985 0 -0,30 Na6+ Kc4 Nxc7 b6 Kb7 Kc5 Na6+ Kb5
7/12 00:00 1.590 0 -0,24 Na6+ Kc4 Nxc7 b6 Kb7 Kc5 Na6+ Kb5 Nc7+ Ka5
8/13 00:00 2.702 1 0,00 Na6+ Kc4 Nxc7 b6 Kb7 Kc5 Nd5 Kxd5 Kxb6
...HJ.
-
Jose Carlos
- Posts: 151
- Joined: Wed Mar 08, 2006 10:09 pm
- Location: Murcia (Spain)
Re: Fail soft/Fail hard
I think there's a misconception here: when you return a value lower than alpha, you're returning an upper bound. We must remember that.
If, at some point, you have a best score b, and you decide to prune next move because you have no chance to get to alpha, let's say you're sure you won't get above alpha-300, your upper bound now is max(b, alpha-300). This upper bound is what you return, not b.
I hope I didn't misuderstand the whole issue.
If, at some point, you have a best score b, and you decide to prune next move because you have no chance to get to alpha, let's say you're sure you won't get above alpha-300, your upper bound now is max(b, alpha-300). This upper bound is what you return, not b.
I hope I didn't misuderstand the whole issue.
__________________________
José Carlos Martínez Galán
José Carlos Martínez Galán
-
michiguel
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Fail soft/Fail hard
It really does not matter. Either version gives inaccurate results (the program does not see the draw). For instance,Harald Johnsen wrote:michiguel wrote:No, it was only one position that contaminated everything little by little. That is what I am trying to say. (and yes, the origin was a futility problem). In fact, I think I remember now.
[d]8/Pk6/8/1K6/3B4/P7/8/8 w - - 1 12
In this position, the "winning" move inside the search is a8=R. Now we go to quiescence() and black sees that the stand pat score is -(P+B+R). Capturing the rook + margin will not bring the score to alpha, which is close to a drawish score (for positional reasons: wrong bishop). Of course, it depends of the margin (if it is bigger than B+P we would see no problem). As a consequence, it will return in a fail soft fashion a bound that is bad for black.
You have the first version in your code, this is wrong in most positions.Code: Select all
if( stand_pat_score + capture_value + margin < alpha ) { prune; } if( stand_pat_score + capture_value + margin < alpha ) { if( stand_pat_score + capture_value > bestScore ) bestScore = stand_pat_score + capture_value; prune; }
Stand pat = -(R + B + P)
capture value = R
So version #2 returns -(B+P) which is a clearly a big losing bound that still create problems.
Returning (alpha - margin), let's call it version #3 (and I believe is what HGMuller is doing) is sounder than version #2 but also gives problems (unless you have a very small margin, which approaches in this case to fail hard).
The only way I have reasonable results is either with a very high margin (forces not to prune) or fail hard.
Ok, so you are recognizing that pruning in QS is risky in certain situations. What I am saying is that failing soft amplifies the problem unless to juggle things in a way than basically the advantage of failing soft (is there is any significant, which is my question) is gone. In your case, you dropped the pruning altogether. You could also fail hard and solve the problem.Anyway pruning bad captures or pruning captures that won't make you reach alpha is unsound in endgames (because the value of the position has not a lot do to with the material).
I use recognizers, no pruning in qs when the stm has less than a rook :
In other words, I am saying pruning + fail soft involves sometimes a serious risk. You solve it not pruning, and maybe is a good idea. Another solution is failing hard unless someone show me that you analyze a lot more nodes.
Miguel
Code: Select all
FEN: 8/Pk6/8/1K6/3B4/P7/8/8 w - - 0 12 Cyrano 0.5b1: 1/3 00:00 42 0 0,00 a8Q+ Kxa8 2/4 00:00 93 0 0,00 a8Q+ Kxa8 Bh8 3/5 00:00 149 0 0,00 a8Q+ Kxa8 Bh8 Ka7 4 00:00 210 0 0,00 a8Q+ Kxa8 Bh8 Ka7 5/8 00:00 278 0 0,00 a8Q+ Kxa8 Bh8 Ka7 6/10 00:00 428 0 0,00 a8Q+ Kxa8 Bh8 Ka7 7/10 00:00 520 0 0,00 a8Q+ Kxa8 Bh8 Ka7 8/10 00:00 622 0 0,00 a8Q+ Kxa8 Bh8 Ka7 ... FEN: 1k6/8/PB6/1K6/8/P7/8/8 w - - 0 8 Cyrano 0.5b1: 1/5 00:00 33 0 0,00 Bg1 2/4 00:00 59 0 0,00 Bg1 Ka8 3/4 00:00 98 0 0,00 Bg1 Ka8 a7 4/7 00:00 150 0 0,00 Bg1 Ka8 a7 Kb7 5/6 00:00 200 0 0,00 Bg1 Ka8 a7 Kb7 6/6 00:00 266 0 0,00 Bg1 Ka8 a7 Kb7 7/8 00:00 367 0 0,00 Bg1 Ka8 a7 Kb7 8/8 00:00 447 0 0,00 Bg1 Ka8 a7 Kb7 ... FEN: kn6/2B5/8/1P6/1K6/P7/8/8 b - - 0 1 Cyrano 0.5b1: 1/4 00:00 43 0 -0,48 Na6+ Kc4 Nxc7 2/4 00:00 66 0 -0,48 Na6+ Kc4 Nxc7 3/6 00:00 141 0 -0,74 Na6+ Kc4 Nxc7 b6 4/8 00:00 359 0 -0,36 Na6+ Kc4 Nxc7 b6 Kb7 5/10 00:00 616 0 -0,38 Na6+ Kc4 Nxc7 b6 Kb7 Kc5 6/10 00:00 985 0 -0,30 Na6+ Kc4 Nxc7 b6 Kb7 Kc5 Na6+ Kb5 7/12 00:00 1.590 0 -0,24 Na6+ Kc4 Nxc7 b6 Kb7 Kc5 Na6+ Kb5 Nc7+ Ka5 8/13 00:00 2.702 1 0,00 Na6+ Kc4 Nxc7 b6 Kb7 Kc5 Nd5 Kxd5 Kxb6 ...
HJ.
-
michiguel
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Fail soft/Fail hard
Yes, but what I am saying is that in some situations max(b, alpha-margin) is not enough unless you return alpha. I found this example that drove me nuts.José Carlos wrote:I think there's a misconception here: when you return a value lower than alpha, you're returning an upper bound. We must remember that.
If, at some point, you have a best score b, and you decide to prune next move because you have no chance to get to alpha, let's say you're sure you won't get above alpha-300, your upper bound now is max(b, alpha-300). This upper bound is what you return, not b.
I hope I didn't misuderstand the whole issue.
Miguel
-
hgm
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Fail soft/Fail hard
That merely means that your MARGIN was not large enough for this position, and your search makes an error because of an unjustified futility pruning.
Returning alpha (and storing it in the hash table) won't save you from this. If storing alpha or storing alpha-MARGIN makes a difference, it means that you are probing the entry in a node that has a new alpha (say alpha') between those values, where a stored alpha-MARGIN would cause a hash cutoff fail low, but a stored upper bound alpha > alpha' would have required a re-search.
But that re-search would now exactly run into the same problem: if alpha-MARGIN < alpha', it means that the move is still futile, and will also be pruned during the re-search with this new window. So you will again get a fail low. The fail hard has solved nothing, just triggered the extra effort of searching the non-futile moves.
Returning alpha (and storing it in the hash table) won't save you from this. If storing alpha or storing alpha-MARGIN makes a difference, it means that you are probing the entry in a node that has a new alpha (say alpha') between those values, where a stored alpha-MARGIN would cause a hash cutoff fail low, but a stored upper bound alpha > alpha' would have required a re-search.
But that re-search would now exactly run into the same problem: if alpha-MARGIN < alpha', it means that the move is still futile, and will also be pruned during the re-search with this new window. So you will again get a fail low. The fail hard has solved nothing, just triggered the extra effort of searching the non-futile moves.