Do you use hash pruning inside PV nodes?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.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
And from this position (posted by Uri, I found it searching the archives)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
I started with this position and I tracked the problem to the first one I showed. Once I fail hard or increase the futility margin I get a reasonable result: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
So, the problem is one position that contaminates the rest iteration after iteration. Returning the score adjusted by the margin will improve things, but it depends on the margin. Yes, I know, this is rare, but still amazed me how the hashtable had the ability to poisoned the search.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.
Fail soft/Fail hard
Moderator: Ras
-
Karlo Bala
- Posts: 373
- Joined: Wed Mar 22, 2006 10:17 am
- Location: Novi Sad, Serbia
- Full name: Karlo Balla
Re: Fail soft/Fail hard
Best Regards,
Karlo Balla Jr.
Karlo Balla Jr.