Aspiration window - effect? Issue with hashtables?!

[ZirconiumX]

Well, IMO the best depends on a kind of speed-stability tradeoff.

If you go for the Bruce Moreland approach you have something which gives a decent improvement for its coding time, is stable and easy to optimize.

The robbolito version is faster, but when your search is unstable, do you actually gain anything when your search is failing constantly, and you are having to research?

It's something to debate - maybe the robbolito version needs a thrashing counter that opens the window to [-Inf, +Inf] after say 5 fails in a single iteration? If all else fails, it would make analysis mode smoother.

Matthew:out

[dchoman]

I recently tried something different, motivated by an experiment with MTD(f).

Here is the idea:

Why does one have to continue and widen the windows to research after you have both failed high and failed low successively? At that point you have bounded the score, and you know what the best move is (from the fail high), so you are done... Obviously, search instabilities can cause this to happen when that really isn't true, but what if we pretend it is true and move on? I found this works better in real games than any of the schemes above, at least for EXchess. Here is my PVS driver code:

Note g_last = score from last iteration.

Code: Select all

    //------------------------------------------
    // choose alpha/beta limits for root search
    //  -- only narrow window after a few 
    //     iterations
    //------------------------------------------
    if(max_ply > MAX(start_depth,3))
     { root_alpha = g_last-15; root_beta = g_last+15; }
    else
     { root_alpha = -MATE; root_beta = +MATE; }

   /* use PVS Algorithm with aspiration windows */
    //------------------------------------------
    // loop to call root search with increasing
    //   alpha/beta limits, will break if
    //   - fail high and fail low happen sequentially
    //   - score (g) is between alpha/beta limits
    // Also uses fail_high reduction trick reported
    //     by Robert Houdart on CCC to resolve fail highs
    //     more quickly
    //------------------------------------------
    int fail_low = 0, fail_high = 0;
    while(1) {
     g = n[0].root_pvs(root_alpha, root_beta, max_ply-1-fail_high);
     if(g == -TIME_FLAG) break;
     if(g <= root_alpha && !fail_high) {
       root_beta = root_alpha+1; fail_low = 1;
       root_alpha = MAX(-MATE,g+2*(root_alpha-g_last));
     } else if(g >= root_beta && !fail_low) {
       root_alpha = root_beta-1; fail_high = 1;
       root_beta = MIN(+MATE,g+2*(root_beta-g_last));
     } else break;
     if(root_alpha < MAX(-5000,g_last-500)) root_alpha = -MATE;
     if(root_beta > MIN(5000,g_last+500)) root_beta = +MATE;
    }

[dchoman]

I just realized this could be even more aggressive by trusting the fail-soft returns of the search and setting the root bounds appropriately. Here is the modification....

Code: Select all

    //------------------------------------------ 
    // choose alpha/beta limits for root search 
    //  -- only narrow window after a few 
    //     iterations 
    //------------------------------------------ 
    if(max_ply > MAX(start_depth,3)) 
     { root_alpha = g_last-15; root_beta = g_last+15; } 
    else 
     { root_alpha = -MATE; root_beta = +MATE; } 

   /* use PVS Algorithm with aspiration windows */ 
    //------------------------------------------ 
    // loop to call root search with increasing 
    //   alpha/beta limits, will break if 
    //   - fail high and fail low happen sequentially 
    //   - score (g) is between alpha/beta limits 
    // Also uses fail_high reduction trick reported 
    //     by Robert Houdart on CCC to resolve fail highs 
    //     more quickly 
    //------------------------------------------ 
    int fail_low = 0, fail_high = 0; 
    while(1) { 
     g = n[0].root_pvs(root_alpha, root_beta, max_ply-1-fail_high); 
     if(g == -TIME_FLAG) break; 
     if(g <= root_alpha && !fail_high) { 
       root_beta = g; fail_low = 1; 
       root_alpha = MAX(-MATE,g+2*(root_alpha-g_last)); 
     } else if(g >= root_beta && !fail_low) { 
       root_alpha = g; fail_high = 1; 
       root_beta = MIN(+MATE,g+2*(root_beta-g_last)); 
     } else break; 
     if(root_alpha < MAX(-5000,g_last-500)) root_alpha = -MATE; 
     if(root_beta > MIN(5000,g_last+500)) root_beta = +MATE; 
    } 

Appears a bit faster than the previous on a small number of testsuites, but the real test is games which I am running now.

[JBNielsen]

when you save a score in the hashtable you have also to save what they call bounds.
what "bounds" mean?

it means that if you are saving a score after you found a score inside the desidered window (alpha-beta) the score is exact, but if you are saving a score after a beta Cutoff you are saving a lowBound because the beta cutoff only tell you that you have found a score above the beta, you don't know how much higher, and you haven't searched all the nodes because you have done a cutoff at the first node failing high.

so when you use this score you have to look at the score and at the bound info.
if You are searching with a window (-20,50) and your score is 70 lowBound you can safely use the score to create a betacutoff because you know that the score means >=70, but if your window is (80,100) you can't use he score for a cutoff because you are searching a value x between 80 and 100 and you know the result is >70, so it's not useful.

You could found the code inside every strong engine

When I made my hashtables back in 1997 I had read some theory about it, but I mainly used my intuition and common sense

I felt that if I had found a score for a position, I could always use that score again later in the search if the score was found at the same or deeper depth as the current search depth...

But with these posts here I realize, that I should redo my hashtables...

It is not a complete surprise. Long ago I made a test where I only used the best-move in the hashtables, and it performed almost as well as the full use of hashtables with scores.
So I assume the faulty scores sometimes helps my search, and sometimes they make noise...

[hgm]

Another problem is that in an alpha-beta search tree hardly any nodes will have exact scores. So if you only keep and act on exact scores, this will happen so rarely that it has no measurable impact. The most important effect of the hash table is storing the cut-moves, but after that it is using the upper and lower-bound scores for satisfying search requests without search.

[lucasart]

HGM is right. To begin with, I suggest you start with that:
- do not use TT for pruning at PV nodes (only for move ordering)
- use it for pruning at non PV nodes, using only the lower and upper bounds (not the exact bounds), and allow for non exact depth match (ie. TT entry has a depth >= current depth, then OK)

A couple of gotchas:
- mate scores need to be adjusted by the ply (because of the non exact depth match)
- you need to consider a single repetition as a draw, rather than a triple repetition. otherwise you will be screwed with draws by 3-repetition