Search instability or bug?

[stegemma]

Because i've almost always used my own algorithm, i'm not so expert with alphabeta (ora alfabeta, in italian style) and i want to know it in any detail. At present, i'm experimenting with alphabeta aspiration windows. The problem in my program is that the results that i get are not the one i would expect. In my engine, i use a "pure alfabeta", without any kind of extension or further pruning, no hash tables, no null moves and no quiescence search nor SEE etc. In this situation, i think that there must not be search instability, so that this kind of code would never return "bad window":

Code: Select all

for(...any move at root...)
{
  Execute(move);

  int val = -AlfaBeta(-valInfinity, valInfinity, iDepth - 1);
  int valok = val;
  val = -AlfaBeta(-valok, valok, iDepth - 1);
  if &#40;val != valok&#41; std&#58;&#58;cout << "# !!! bad window";

  UndoMove&#40;);
&#125;

I've oversimplified the code, just to make it more clear. The output of the real code gives me some bad value:

Code: Select all

# _________________________ alfabeta : 2
# f2f4: nodes gain 21-2=19 90.48%
# g2g4: nodes gain 21-3=18 85.71%
# h2h4: !! bad window val -6 valok -10
# d2d4: nodes gain 21-21=0 0.00%
# a2a4: !! bad window val -9 valok -10
# b2b4: !! bad window val -9 valok -10
# c2c4: !! bad window val 1 valok -3
# e2e4: nodes gain 21-21=0 0.00%
# b1a3: nodes gain 21-2=19 90.48%
# b1c3: nodes gain 21-2=19 90.48%
# g1h3: nodes gain 21-2=19 90.48%
# g1f3: nodes gain 21-21=0 0.00%
# b2b3: nodes gain 21-2=19 90.48%
# c2c3: nodes gain 21-2=19 90.48%
# d2d3: nodes gain 21-2=19 90.48%
# e2e3: nodes gain 21-2=19 90.48%
# f2f3: nodes gain 21-2=19 90.48%
# g2g3: nodes gain 21-2=19 90.48%
# h2h3: nodes gain 21-2=19 90.48%
# a2a3: nodes gain 21-2=19 90.48%
# nodes 519 ms 16 nodes/s 32437 branch 9.02
# _________________________ alfabeta : 4
# d2d4: nodes gain 1910-1636=274 14.35%
# g1f3: nodes gain 1415-1334=81 5.72%
# e2e4: nodes gain 2395-1924=471 19.67%
# c2c4: nodes gain 1807-1532=275 15.22%
# b1c3: nodes gain 1796-1542=254 14.14%
# d2d3: nodes gain 2059-1167=892 43.32%
# f2f4: nodes gain 1148-652=496 43.21%
# e2e3: nodes gain 2476-2331=145 5.86%
# h2h4: !! bad window val 1 valok -1
# g1h3: nodes gain 1687-935=752 44.58%
# b2b4: !! bad window val -10 valok -11
# a2a4: !! bad window val 1 valok -1
# b1a3: nodes gain 1919-1169=750 39.08%
# b2b3: nodes gain 2087-1956=131 6.28%
# g2g4: nodes gain 839-22=817 97.38%
# f2f3: !! bad window val 11 valok -11
# g2g3: nodes gain 1645-1496=149 9.06%
# h2h3: !! bad window val 1 valok -1
# a2a3: !! bad window val 1 valok -1
# c2c3: nodes gain 1936-1830=106 5.48%
# nodes 52886 ms 78 nodes/s 678025 branch 7.85
# _________________________ alfabeta : 6
# e2e3: nodes gain 151487-92930=58557 38.65%
# e2e4: nodes gain 135119-93179=41940 31.04%
# c2c4: nodes gain 51816-36452=15364 29.65%
# g2g3: nodes gain 79390-70300=9090 11.45%
# b2b3: nodes gain 143942-95926=48016 33.36%
# c2c3: nodes gain 107472-94094=13378 12.45%
# d2d4: nodes gain 152200-103558=48642 31.96%
# f2f3: !! bad window val 6 valok -6
# g1f3: nodes gain 166724-126492=40232 24.13%
# b1c3: nodes gain 90857-82384=8473 9.33%
# b1a3: nodes gain 89943-34078=55865 62.11%
# d2d3: nodes gain 139871-97309=42562 30.43%
# f2f4: nodes gain 137687-70944=66743 48.47%
# g1h3: nodes gain 60966-30612=30354 49.79%
# a2a4: nodes gain 122183-113062=9121 7.47%
# h2h4: nodes gain 67355-56393=10962 16.27%
# h2h3: nodes gain 95791-77593=18198 19.00%
# a2a3: nodes gain 102746-75184=27562 26.83%
# b2b4: nodes gain 95665-77630=18035 18.85%
# g2g4: nodes gain 63612-54526=9086 14.28%
# nodes 3667316 ms 3682 nodes/s 996011 branch 8.44

The nodes gain seems very important, when it not fail low, and i suppose that it is the maximum that we can get in this situation, because i use the pre-compute value, from a full search.

Should i search for a bug in my alfabeta or it's normal to get fail-low/high, even in a "pure alfabeta" function?

I plan to compare alfabeta returned value to those that perft can return, to know if alfabeta works in a perfect way.

[Henk]

Because i've almost always used my own algorithm, i'm not so expert with alphabeta (ora alfabeta, in italian style) and i want to know it in any detail. At present, i'm experimenting with alphabeta aspiration windows. The problem in my program is that the results that i get are not the one i would expect. In my engine, i use a "pure alfabeta", without any kind of extension or further pruning, no hash tables, no null moves and no quiescence search nor SEE etc. In this situation, i think that there must not be search instability, so that this kind of code would never return "bad window":

Code: Select all

for(...any move at root...)
{
  Execute(move);

  int val = -AlfaBeta(-valInfinity, valInfinity, iDepth - 1);
  int valok = val;
  val = -AlfaBeta(-valok, valok, iDepth - 1);
  if &#40;val != valok&#41; std&#58;&#58;cout << "# !!! bad window";

  UndoMove&#40;);
&#125;

I've oversimplified the code, just to make it more clear. The output of the real code gives me some bad value:

Code: Select all

# _________________________ alfabeta : 2
# f2f4: nodes gain 21-2=19 90.48%
# g2g4: nodes gain 21-3=18 85.71%
# h2h4: !! bad window val -6 valok -10
# d2d4: nodes gain 21-21=0 0.00%
# a2a4: !! bad window val -9 valok -10
# b2b4: !! bad window val -9 valok -10
# c2c4: !! bad window val 1 valok -3
# e2e4: nodes gain 21-21=0 0.00%
# b1a3: nodes gain 21-2=19 90.48%
# b1c3: nodes gain 21-2=19 90.48%
# g1h3: nodes gain 21-2=19 90.48%
# g1f3: nodes gain 21-21=0 0.00%
# b2b3: nodes gain 21-2=19 90.48%
# c2c3: nodes gain 21-2=19 90.48%
# d2d3: nodes gain 21-2=19 90.48%
# e2e3: nodes gain 21-2=19 90.48%
# f2f3: nodes gain 21-2=19 90.48%
# g2g3: nodes gain 21-2=19 90.48%
# h2h3: nodes gain 21-2=19 90.48%
# a2a3: nodes gain 21-2=19 90.48%
# nodes 519 ms 16 nodes/s 32437 branch 9.02
# _________________________ alfabeta : 4
# d2d4: nodes gain 1910-1636=274 14.35%
# g1f3: nodes gain 1415-1334=81 5.72%
# e2e4: nodes gain 2395-1924=471 19.67%
# c2c4: nodes gain 1807-1532=275 15.22%
# b1c3: nodes gain 1796-1542=254 14.14%
# d2d3: nodes gain 2059-1167=892 43.32%
# f2f4: nodes gain 1148-652=496 43.21%
# e2e3: nodes gain 2476-2331=145 5.86%
# h2h4: !! bad window val 1 valok -1
# g1h3: nodes gain 1687-935=752 44.58%
# b2b4: !! bad window val -10 valok -11
# a2a4: !! bad window val 1 valok -1
# b1a3: nodes gain 1919-1169=750 39.08%
# b2b3: nodes gain 2087-1956=131 6.28%
# g2g4: nodes gain 839-22=817 97.38%
# f2f3: !! bad window val 11 valok -11
# g2g3: nodes gain 1645-1496=149 9.06%
# h2h3: !! bad window val 1 valok -1
# a2a3: !! bad window val 1 valok -1
# c2c3: nodes gain 1936-1830=106 5.48%
# nodes 52886 ms 78 nodes/s 678025 branch 7.85
# _________________________ alfabeta : 6
# e2e3: nodes gain 151487-92930=58557 38.65%
# e2e4: nodes gain 135119-93179=41940 31.04%
# c2c4: nodes gain 51816-36452=15364 29.65%
# g2g3: nodes gain 79390-70300=9090 11.45%
# b2b3: nodes gain 143942-95926=48016 33.36%
# c2c3: nodes gain 107472-94094=13378 12.45%
# d2d4: nodes gain 152200-103558=48642 31.96%
# f2f3: !! bad window val 6 valok -6
# g1f3: nodes gain 166724-126492=40232 24.13%
# b1c3: nodes gain 90857-82384=8473 9.33%
# b1a3: nodes gain 89943-34078=55865 62.11%
# d2d3: nodes gain 139871-97309=42562 30.43%
# f2f4: nodes gain 137687-70944=66743 48.47%
# g1h3: nodes gain 60966-30612=30354 49.79%
# a2a4: nodes gain 122183-113062=9121 7.47%
# h2h4: nodes gain 67355-56393=10962 16.27%
# h2h3: nodes gain 95791-77593=18198 19.00%
# a2a3: nodes gain 102746-75184=27562 26.83%
# b2b4: nodes gain 95665-77630=18035 18.85%
# g2g4: nodes gain 63612-54526=9086 14.28%
# nodes 3667316 ms 3682 nodes/s 996011 branch 8.44

The nodes gain seems very important, when it not fail low, and i suppose that it is the maximum that we can get in this situation, because i use the pre-compute value, from a full search.

Should i search for a bug in my alfabeta or it's normal to get fail-low/high, even in a "pure alfabeta" function?

I plan to compare alfabeta returned value to those that perft can return, to know if alfabeta works in a perfect way.

What happens if you keep one bound unchanged that doesn't fail ? I mean set one bound to +- infinity. The bound that did not exceed valok.

[stegemma]

[...]
What happens if you keep one bound unchanged that doesn't fail ?

Good hint, i'll try it right now. In the meantime, i've found that it doesn't fail at level 8 but i would need some hour to try level 10:

Code: Select all

# _________________________ alfabeta : 8
# time has expired
# e2e3: val 995 nodes gain 6264106-5355982=908124 14.50%
# e2e4: val 995 nodes gain 6879110-5026019=1853091 26.94%
# g2g3: val 990 nodes gain 3442437-2494313=948124 27.54%
# c2c3: val 992 nodes gain 4726775-3636073=1090702 23.07%
# b1c3: val 990 nodes gain 6338525-3470422=2868103 45.25%
# g1f3: val 991 nodes gain 9205603-7562542=1643061 17.85%
# d2d4: val 991 nodes gain 7661419-4652298=3009121 39.28%
# h2h4: val 992 nodes gain 4673010-4206651=466359 9.98%
# a2a3: val 989 nodes gain 4725107-3729534=995573 21.07%
# h2h3: val 990 nodes gain 5475637-4854946=620691 11.34%
# g2g4: val 989 nodes gain 2950243-2024963=925280 31.36%
# a2a4: val 989 nodes gain 6685056-5716322=968734 14.49%
# c2c4: val 991 nodes gain 3076806-2164055=912751 29.67%
# b2b3: val 988 nodes gain 7259654-5574100=1685554 23.22%
# d2d3: val 987 nodes gain 8542556-5881894=2660662 31.15%
# b2b4: val 980 nodes gain 4698803-3640389=1058414 22.53%
# f2f4: val 981 nodes gain 6125696-4710924=1414772 23.10%
# f2f3: val 4 nodes gain 4568708-1368238=3200470 70.05%
# b1a3: val 975 nodes gain 4959386-3206515=1752871 35.34%
# g1h3: val 973 nodes gain 4833289-3604177=1229112 25.43%
# nodes 199639600 ms 206092 nodes/s 968691 branch 9.19

PS: faster than light: it doesn't fail if i call again alfabeta with the same window after a good call. The returned value remains the same and it continue failing on the same moves than in the first try. The hint was good and this way i can exclude some dirty data (maybe... but not 100% sure, of course).

[bob]

Because i've almost always used my own algorithm, i'm not so expert with alphabeta (ora alfabeta, in italian style) and i want to know it in any detail. At present, i'm experimenting with alphabeta aspiration windows. The problem in my program is that the results that i get are not the one i would expect. In my engine, i use a "pure alfabeta", without any kind of extension or further pruning, no hash tables, no null moves and no quiescence search nor SEE etc. In this situation, i think that there must not be search instability, so that this kind of code would never return "bad window":

Code: Select all

for(...any move at root...)
{
  Execute(move);

  int val = -AlfaBeta(-valInfinity, valInfinity, iDepth - 1);
  int valok = val;
  val = -AlfaBeta(-valok, valok, iDepth - 1);
  if &#40;val != valok&#41; std&#58;&#58;cout << "# !!! bad window";

  UndoMove&#40;);
&#125;

I've oversimplified the code, just to make it more clear. The output of the real code gives me some bad value:

Code: Select all

# _________________________ alfabeta : 2
# f2f4: nodes gain 21-2=19 90.48%
# g2g4: nodes gain 21-3=18 85.71%
# h2h4: !! bad window val -6 valok -10
# d2d4: nodes gain 21-21=0 0.00%
# a2a4: !! bad window val -9 valok -10
# b2b4: !! bad window val -9 valok -10
# c2c4: !! bad window val 1 valok -3
# e2e4: nodes gain 21-21=0 0.00%
# b1a3: nodes gain 21-2=19 90.48%
# b1c3: nodes gain 21-2=19 90.48%
# g1h3: nodes gain 21-2=19 90.48%
# g1f3: nodes gain 21-21=0 0.00%
# b2b3: nodes gain 21-2=19 90.48%
# c2c3: nodes gain 21-2=19 90.48%
# d2d3: nodes gain 21-2=19 90.48%
# e2e3: nodes gain 21-2=19 90.48%
# f2f3: nodes gain 21-2=19 90.48%
# g2g3: nodes gain 21-2=19 90.48%
# h2h3: nodes gain 21-2=19 90.48%
# a2a3: nodes gain 21-2=19 90.48%
# nodes 519 ms 16 nodes/s 32437 branch 9.02
# _________________________ alfabeta : 4
# d2d4: nodes gain 1910-1636=274 14.35%
# g1f3: nodes gain 1415-1334=81 5.72%
# e2e4: nodes gain 2395-1924=471 19.67%
# c2c4: nodes gain 1807-1532=275 15.22%
# b1c3: nodes gain 1796-1542=254 14.14%
# d2d3: nodes gain 2059-1167=892 43.32%
# f2f4: nodes gain 1148-652=496 43.21%
# e2e3: nodes gain 2476-2331=145 5.86%
# h2h4: !! bad window val 1 valok -1
# g1h3: nodes gain 1687-935=752 44.58%
# b2b4: !! bad window val -10 valok -11
# a2a4: !! bad window val 1 valok -1
# b1a3: nodes gain 1919-1169=750 39.08%
# b2b3: nodes gain 2087-1956=131 6.28%
# g2g4: nodes gain 839-22=817 97.38%
# f2f3: !! bad window val 11 valok -11
# g2g3: nodes gain 1645-1496=149 9.06%
# h2h3: !! bad window val 1 valok -1
# a2a3: !! bad window val 1 valok -1
# c2c3: nodes gain 1936-1830=106 5.48%
# nodes 52886 ms 78 nodes/s 678025 branch 7.85
# _________________________ alfabeta : 6
# e2e3: nodes gain 151487-92930=58557 38.65%
# e2e4: nodes gain 135119-93179=41940 31.04%
# c2c4: nodes gain 51816-36452=15364 29.65%
# g2g3: nodes gain 79390-70300=9090 11.45%
# b2b3: nodes gain 143942-95926=48016 33.36%
# c2c3: nodes gain 107472-94094=13378 12.45%
# d2d4: nodes gain 152200-103558=48642 31.96%
# f2f3: !! bad window val 6 valok -6
# g1f3: nodes gain 166724-126492=40232 24.13%
# b1c3: nodes gain 90857-82384=8473 9.33%
# b1a3: nodes gain 89943-34078=55865 62.11%
# d2d3: nodes gain 139871-97309=42562 30.43%
# f2f4: nodes gain 137687-70944=66743 48.47%
# g1h3: nodes gain 60966-30612=30354 49.79%
# a2a4: nodes gain 122183-113062=9121 7.47%
# h2h4: nodes gain 67355-56393=10962 16.27%
# h2h3: nodes gain 95791-77593=18198 19.00%
# a2a3: nodes gain 102746-75184=27562 26.83%
# b2b4: nodes gain 95665-77630=18035 18.85%
# g2g4: nodes gain 63612-54526=9086 14.28%
# nodes 3667316 ms 3682 nodes/s 996011 branch 8.44

The nodes gain seems very important, when it not fail low, and i suppose that it is the maximum that we can get in this situation, because i use the pre-compute value, from a full search.

Should i search for a bug in my alfabeta or it's normal to get fail-low/high, even in a "pure alfabeta" function?

I plan to compare alfabeta returned value to those that perft can return, to know if alfabeta works in a perfect way.

I would have to think about this a bit, but the idea does seem a bit flawed. IE if you know the exact score is X, the searching with a window -X and +X might be risky, since you really don't want to ever return a score that is equal to the bound, because it would be ambiguous (is it a real score or is it the lower bound and we need to re-search).

What happens if you search with -val-1 and +val + 1 so that the score you expect "val" is returned as an exact score rather than a bound?

[stegemma]

[...]
I would have to think about this a bit, but the idea does seem a bit flawed. IE if you know the exact score is X, the searching with a window -X and +X might be risky, since you really don't want to ever return a score that is equal to the bound, because it would be ambiguous (is it a real score or is it the lower bound and we need to re-search).

Yes but it should be equal to the bound, in clean alfabeta.

[...]
What happens if you search with -val-1 and +val + 1 so that the score you expect "val" is returned as an exact score rather than a bound?

It fail even with this kind of window, so it surely must be a bug somewhere. It fails more in low depth than in bigger one. It seems as the bug/instability decrease with the level.

i'm an expert in putting bugs into software

[Joost Buijs]

Searching with a window from -val to +val doesn't seem right.
When val is negative alpha gets larger than beta.
For a zero window search it should be -(val+1) to -val. which is the same as -val-1 to -val.

Edit:

I guess Bob meant -val-1 to -val+1.

[Sven]

Searching with a window from -val to +val doesn't seem right.
When val is negative alpha gets larger than beta.
For a zero window search it should be -(val+1) to -val. which is the same as -val-1 to -val.

Edit:

I guess Bob meant -val-1 to -val+1.

That is exactly the problem. In all "bad window" messages shown in the output "valok" has a negative value. Searching with a window (X, Y) when Y < X does not ensure at all to return Y.

[stegemma]

Searching with a window from -val to +val doesn't seem right.
When val is negative alpha gets larger than beta.
For a zero window search it should be -(val+1) to -val. which is the same as -val-1 to -val.

Edit:

I guess Bob meant -val-1 to -val+1.

That is exactly the problem. In all "bad window" messages shown in the output "valok" has a negative value. Searching with a window (X, Y) when Y < X does not ensure at all to return Y.

Ok, i think that this is the problem. When the value is negative, something happens in alfabeta. As a "side effect", it seems that an alfabeta search without quiescence can give positive value only in depth greater than 6. Maybe this is because stepping 2 by 2 the last move is always to the opponent. this is true from the starting position but even in complex position i've get similar results (but with more "bad window").

I'm trying to understand why it still fails on -val-1 to val+1.

For completeness, i post the [-val-1, val+1] window results:

Code: Select all

# _________________________ alfabeta : 2 board value 0
# f2f4: !! bad window val 2 valok -3
# g2g4: !! bad window val 9 valok -10
# h2h4: !! bad window val -6 valok -10
# d2d4: val 5 nodes gain 21-21=0 0.00%
# a2a4: !! bad window val -9 valok -10
# b2b4: !! bad window val -9 valok -10
# c2c4: !! bad window val 1 valok -3
# e2e4: val 3 nodes gain 21-21=0 0.00%
# b1a3: !! bad window val 8 valok -9
# b1c3: val 0 nodes gain 21-21=0 0.00%
# g1h3: !! bad window val 5 valok -6
# g1f3: val 3 nodes gain 21-21=0 0.00%
# b2b3: !! bad window val 9 valok -10
# c2c3: !! bad window val 9 valok -10
# d2d3: !! bad window val 1 valok -2
# e2e3: !! bad window val 3 valok -4
# f2f3: !! bad window val 9 valok -10
# g2g3: !! bad window val 9 valok -10
# h2h3: !! bad window val 9 valok -10
# a2a3: !! bad window val 9 valok -10
# nodes 538 ms 16 nodes/s 33625 branch 9.07
# _________________________ alfabeta : 4 board value 0
# a2a3: val 0 nodes gain 1464-5=1459 99.66%
# g2g4: !! bad window val -13 valok -14
# h2h3: val 0 nodes gain 1572-4=1568 99.75%
# b2b3: val 982 nodes gain 2087-2008=79 3.79%
# g2g3: val 982 nodes gain 1645-1550=95 5.78%
# f2f3: !! bad window val 10 valok -11
# c2c3: val 978 nodes gain 1936-1859=77 3.98%
# b1a3: val 5 nodes gain 1919-1249=670 34.91%
# g1h3: val 2 nodes gain 1687-1060=627 37.17%
# d2d4: val 15 nodes gain 1910-1817=93 4.87%
# g1f3: val 11 nodes gain 1415-1415=0 0.00%
# e2e4: val 991 nodes gain 2395-1994=401 16.74%
# e2e3: val 992 nodes gain 2476-2373=103 4.16%
# f2f4: val 2 nodes gain 1148-820=328 28.57%
# d2d3: val 4 nodes gain 2059-1279=780 37.88%
# c2c4: val 987 nodes gain 1807-1571=236 13.06%
# b1c3: val 10 nodes gain 1796-1579=217 12.08%
# h2h4: val 0 nodes gain 830-4=826 99.52%
# b2b4: !! bad window val -10 valok -11
# a2a4: val 0 nodes gain 1343-4=1339 99.70%
# nodes 53975 ms 94 nodes/s 574202 branch 7.86
# _________________________ alfabeta : 6 board value 0
# e2e3: val 992 nodes gain 151487-109733=41754 27.56%
# e2e4: val 992 nodes gain 135119-106212=28907 21.39%
# c2c4: val 984 nodes gain 51816-37968=13848 26.73%
# b2b3: val 981 nodes gain 143942-100797=43145 29.97%
# g2g3: val 990 nodes gain 79390-71174=8216 10.35%
# c2c3: val 990 nodes gain 107472-98340=9132 8.50%
# d2d4: val 987 nodes gain 152200-112812=39388 25.88%
# g1f3: val 987 nodes gain 166724-136625=30099 18.05%
# b1c3: val 988 nodes gain 90857-85920=4937 5.43%
# f2f3: !! bad window val 5 valok -6
# b1a3: val 5 nodes gain 89943-36062=53881 59.91%
# d2d3: val 980 nodes gain 139871-102108=37763 27.00%
# g1h3: val 4 nodes gain 60966-34868=26098 42.81%
# f2f4: val 12 nodes gain 137687-81254=56433 40.99%
# h2h4: val 985 nodes gain 67355-62671=4684 6.95%
# h2h3: val 985 nodes gain 95791-84080=11711 12.23%
# a2a3: val 985 nodes gain 102746-85138=17608 17.14%
# a2a4: val 985 nodes gain 122183-115649=6534 5.35%
# b2b4: val 969 nodes gain 95665-80793=14872 15.55%
# g2g4: val 985 nodes gain 63612-57699=5913 9.30%
# nodes 3785662 ms 3682 nodes/s 1028153 branch 8.45
# _________________________ alfabeta : 8 board value 0
# time has expired
# e2e3: val 995 nodes gain 6264106-5704743=559363 8.93%
# e2e4: val 995 nodes gain 6879110-5467084=1412026 20.53%
# g2g3: val 990 nodes gain 3442437-2563359=879078 25.54%
# c2c3: val 992 nodes gain 4726775-3919506=807269 17.08%
# b1c3: val 990 nodes gain 6338525-4081888=2256637 35.60%
# g1f3: val 991 nodes gain 9205603-7942416=1263187 13.72%
# d2d4: val 991 nodes gain 7661419-5317269=2344150 30.60%
# a2a4: val 989 nodes gain 6685056-6003896=681160 10.19%
# a2a3: val 989 nodes gain 4725107-4231404=493703 10.45%
# h2h3: val 990 nodes gain 5475637-5098553=377084 6.89%
# g2g4: val 989 nodes gain 2950243-2214756=735487 24.93%
# h2h4: val 992 nodes gain 4673010-4227815=445195 9.53%
# c2c4: val 991 nodes gain 3076806-2226929=849877 27.62%
# b2b3: val 988 nodes gain 7259654-5964448=1295206 17.84%
# d2d3: val 987 nodes gain 8542556-6455263=2087293 24.43%
# b2b4: val 980 nodes gain 4698803-3691803=1007000 21.43%
# f2f4: val 981 nodes gain 6125696-4746955=1378741 22.51%
# b1a3: val 975 nodes gain 4959386-3220158=1739228 35.07%
# f2f3: val 4 nodes gain 4568708-1656367=2912341 63.75%
# g1h3: val 973 nodes gain 4833289-3778814=1054475 21.82%
# nodes 205391015 ms 201630 nodes/s 1018653 branch 9.20
# _________________________ alfabeta : 10 board value 0
# e2e3: val 995 nodes gain 360210910-257698757=102512153 28.46%
# e2e4: val 995 nodes gain 243056136-178414504=64641632 26.60%
# h2h4: val 992 nodes gain 169531089-129445723=40085366 23.64%
# c2c3: val 995 nodes gain 213075737-184956061=28119676 13.20%
# d2d4: val 993 nodes gain 304737357-195311383=109425974 35.91%
# g1f3: val 992 nodes gain 418818388-315496981=103321407 24.67%
# c2c4: val 993 nodes gain 138590227-94741935=43848292 31.64%
# h2h3: val 991 nodes gain 204519424-164063728=40455696 19.78%
# b1c3: val 993 nodes gain 270516502-201929553=68586949 25.35%
# g2g3: val 992 nodes gain 152192640-115136251=37056389 24.35%
# g2g4: val 991 nodes gain 123150169-107830830=15319339 12.44%
# a2a3: val 991 nodes gain 162823787-131467412=31356375 19.26%
# a2a4: val 991 nodes gain 254100644-230292213=23808431 9.37%

PS: the values are in 1/1000 of a pawn

[bob]

[...]
I would have to think about this a bit, but the idea does seem a bit flawed. IE if you know the exact score is X, the searching with a window -X and +X might be risky, since you really don't want to ever return a score that is equal to the bound, because it would be ambiguous (is it a real score or is it the lower bound and we need to re-search).

Yes but it should be equal to the bound, in clean alfabeta.

[...]
What happens if you search with -val-1 and +val + 1 so that the score you expect "val" is returned as an exact score rather than a bound?

It fail even with this kind of window, so it surely must be a bug somewhere. It fails more in low depth than in bigger one. It seems as the bug/instability decrease with the level.

i'm an expert in putting bugs into software

I assume you don't do lazy eval either?

You could just dump the two trees and see where they differ, since they should not.

[elpapa]

I'm trying to understand why it still fails on -val-1 to val+1.

Why are you inverting the sign of alpha but not beta? It should be -val-1, -ival for a null window or -val-x, -val+x for an aspiration window.