strange code for tt

[flok]

Hi,

For ages (micah, embla, feeks, etc, all of them) I had this piece of code for updating the transposition table:

Code: Select all

        if (alpha > start_alpha && !to_flag) {
                tt_entry_flag flag = EXACT;

                if (best_score <= start_alpha)
                        flag = UPPERBOUND;
                else if (best_score >= beta)
                        flag = LOWERBOUND;

                meta->tti->store(pos.hash(), flag, depth, best_score, best_score <= start_alpha ? MOVE_NONE : best_move);
        }

Today I looked at it and it doesn't make sense I think. if alpha > start_alpha (which is the alpha at the start of search()), then the best_score can never be <= start_alpha. So never an upperbound. I tried removing the alpha > start_alpha check but that makes it play -80 elo.

Any insights?



For completeness, here's also the look-up code:

Code: Select all

        tt_entry te;
        libchess::Move tt_move;
        if (meta->tti->lookup(pos.hash(), &te)) {
                tt_move = libchess::Move(te.data_._data.m);

                if (tt_move != libchess::constants::MOVE_NONE && !pos.is_legal_move(tt_move))
                        tt_move = libchess::constants::MOVE_NONE;
                else if (te.data_._data.depth >= depth) {
                        bool use = false;

                        if (te.data_._data.flags == EXACT)
                                use = true;
                        else if (te.data_._data.flags == LOWERBOUND && te.data_._data.score >= beta)
                                use = true;
                        else if (te.data_._data.flags == UPPERBOUND && te.data_._data.score <= alpha)
                                use = true;

                        if (use && (!is_root_position || tt_move != libchess::constants::MOVE_NONE)) {
                                *m = tt_move;

                                return te.data_._data.score;
                        }
                }
        }

[Sven]

if alpha > start_alpha (which is the alpha at the start of search()), then the best_score can never be <= start_alpha.

That depends on your type of alpha-beta search. With "fail hard" you are right but with "fail soft" best_score is initialized to -INF and can certainly be below your current window.

I'm not sure why you maintain three values: start_alpha, alpha, and best_score. Wouldn't two be sufficient, in both "fail hard" and "fail soft" worlds?

[hgm]

Well, that depends. Alpha = max(start_apha, best_score), and thus redundant. But you have to pass alpha to every recursive call, and you might not want to calculate the maximum every time, but keep track of it incrementally. Then you only have to do something when best_score is incremented, which is rare. (As in negamax you have to pass -alpha it might actually be smarter to keep -alpha incrementally. But you could of course also write the negamax search routine such that it uses -beta instead of beta. As you basically only use beta to test for a cutoff, the test could become if(score + minus_beta >= 0), and you would not have to flip sign while passing alpha and beta down the recursion.)

[syzygy]

Any insights?

What happens when you store MOVE_NONE? Does that delete the old tt move (if there was one for the current position)?

It is correct not to store the new "best" move if you haven't actually found a move that is better than start_alpha, but you should not delete the old tt move if there is one.

[flok]

Any insights?

What happens when you store MOVE_NONE? Does that delete the old tt move (if there was one for the current position)?

It is correct not to store the new "best" move if you haven't actually found a move that is better than start_alpha, but you should not delete the old tt move if there is one.

Thanks for this. I tested it and for Micah it gave no improvement but I'll leave it in (keeping the old tt-move) for correctness.

[syzygy]

Any insights?

What happens when you store MOVE_NONE? Does that delete the old tt move (if there was one for the current position)?

It is correct not to store the new "best" move if you haven't actually found a move that is better than start_alpha, but you should not delete the old tt move if there is one.

Thanks for this. I tested it and for Micah it gave no improvement but I'll leave it in (keeping the old tt-move) for correctness.

No wonder, because you're still checking for alpha > start_alpha before updating the TT entry.

The reason you were losing 80 Elo when you remove alpha > start_alpha is that you clear the TT move. Now that you keep the old TT move, you should no longer lose 80 Elo but gain something.

[flok]

Thanks for this. I tested it and for Micah it gave no improvement but I'll leave it in (keeping the old tt-move) for correctness.

No wonder, because you're still checking for alpha > start_alpha before updating the TT entry.

The reason you were losing 80 Elo when you remove alpha > start_alpha is that you clear the TT move. Now that you keep the old TT move, you should no longer lose 80 Elo but gain something.

Oh indeed! I gained ~9 elo now (6k tests)
thanks!

[hgm]

Amazing that this matters so much. After all, the move did fail low. 80 Elo amounts to more than halving the search speed (time-to-depth). It shouldn't be that common that you search the same position with a different window, so that the move would be useful to get above beta again. Was this in a PVS search or vanilla alpha-beta?

[flok]

Amazing that this matters so much. After all, the move did fail low. 80 Elo amounts to more than halving the search speed (time-to-depth). It shouldn't be that common that you search the same position with a different window, so that the move would be useful to get above beta again. Was this in a PVS search or vanilla alpha-beta?

vanilla a/b

[hgm]

OK, that perhaps explains it. With plain alpha-beta the search window varies much more throughout the tree than with PVS, where it is mostly a null window around the current root score.

I once noticed that (in end-games, at least) the alpha-beta search often needs two different kind of bound types (upper and lower) for the same position, and then keeps re-searching a sufficiently deep hash hit because it had the wrong bound type, time after time. This was so bad that a minimax search (forcing the window to be {-INF, INF} in every node, rather than {-beta, -alpha}) was an order of magnitude faster than the alpha-beta search. Because it just searched ever position once at a certain depth, and then was done with it, as the score was then exact, and could satisfy any future request for that depth.