strange code for tt

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
flok
Posts: 146
Joined: Tue Jul 03, 2018 8:19 am
Full name: Folkert van Heusden
Contact:

strange code for tt

Post by flok » Tue Jun 18, 2019 3:21 pm

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;
                        }
                }
        }
www.vanheusden.com: Micah / Embla / PuppetMaster / DeepBrutePos / Pos / Feeks

Sven
Posts: 3788
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: strange code for tt

Post by Sven » Tue Jun 18, 2019 7:55 pm

flok wrote:
Tue Jun 18, 2019 3:21 pm
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?
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

User avatar
hgm
Posts: 23311
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: strange code for tt

Post by hgm » Tue Jun 18, 2019 8:35 pm

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
Posts: 4426
Joined: Tue Feb 28, 2012 10:56 pm

Re: strange code for tt

Post by syzygy » Tue Jun 18, 2019 11:25 pm

flok wrote:
Tue Jun 18, 2019 3:21 pm
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
Posts: 146
Joined: Tue Jul 03, 2018 8:19 am
Full name: Folkert van Heusden
Contact:

Re: strange code for tt

Post by flok » Fri Jun 21, 2019 11:43 am

syzygy wrote:
Tue Jun 18, 2019 11:25 pm
flok wrote:
Tue Jun 18, 2019 3:21 pm
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.
www.vanheusden.com: Micah / Embla / PuppetMaster / DeepBrutePos / Pos / Feeks

syzygy
Posts: 4426
Joined: Tue Feb 28, 2012 10:56 pm

Re: strange code for tt

Post by syzygy » Fri Jun 21, 2019 12:33 pm

flok wrote:
Fri Jun 21, 2019 11:43 am
syzygy wrote:
Tue Jun 18, 2019 11:25 pm
flok wrote:
Tue Jun 18, 2019 3:21 pm
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
Posts: 146
Joined: Tue Jul 03, 2018 8:19 am
Full name: Folkert van Heusden
Contact:

Re: strange code for tt

Post by flok » Fri Jun 21, 2019 7:25 pm

syzygy wrote:
Fri Jun 21, 2019 12:33 pm
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!
www.vanheusden.com: Micah / Embla / PuppetMaster / DeepBrutePos / Pos / Feeks

User avatar
hgm
Posts: 23311
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: strange code for tt

Post by hgm » Fri Jun 21, 2019 9:12 pm

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
Posts: 146
Joined: Tue Jul 03, 2018 8:19 am
Full name: Folkert van Heusden
Contact:

Re: strange code for tt

Post by flok » Sat Jun 22, 2019 6:04 am

hgm wrote:
Fri Jun 21, 2019 9:12 pm
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
www.vanheusden.com: Micah / Embla / PuppetMaster / DeepBrutePos / Pos / Feeks

User avatar
hgm
Posts: 23311
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: strange code for tt

Post by hgm » Sat Jun 22, 2019 8:30 am

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.

Post Reply