Storing both alpha and beta scores in TT

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
thomasahle
Posts: 74
Joined: Thu Feb 27, 2014 7:19 pm

Storing both alpha and beta scores in TT

It's seems that most people have three kinds of nodes in their transposition tables: exact, alpha/low and beta/high. Naturally we prefer exact scores, but often we only know an upper or lower bound.

What I'm wondering is what you do if you find a lower bound in a node where the precious value stored was an upper bound? (Is there any reason this shouldn't happen often?)

A natural solutions seems to be storing both, so you now have an interval in which the correct score might lie. I haven't been able to find any previous discussion of this, so I was wondering if anyone has any experience to share?

Alternatively, in what cases would you replace am upper bound stored with a lower bound, or vise versa?

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Storing both alpha and beta scores in TT

thomasahle wrote:It's seems that most people have three kinds of nodes in their transposition tables: exact, alpha/low and beta/high. Naturally we prefer exact scores, but often we only know an upper or lower bound.

What I'm wondering is what you do if you find a lower bound in a node where the precious value stored was an upper bound? (Is there any reason this shouldn't happen often?)
It shouldn't happen often in PVS at least. most of your searching will be done with a null window with a single value (or a small movement from that value) - so a node will usually stay either lowerbound or upperbound. Assuming you have space for only one value in the TT, you store the most recent - because that's what you're most likely to need again. If you were using mtd(f), it may be important to store both a lower and upper bound for every node as your zero window searches would be bouncing back and forth trying to find the right range. You could experiment with storing both anyways, but most people prefer to make the TT entry as small as possible in order to squeeze more entries into the same size of table, and thus have opted for only storing a bound type,depth,score set instead of needing two depths and two scores per entry.

Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Storing both alpha and beta scores in TT

What you decribe is known as a "dual bound" table, there's some discussion to be found about these. It indeed helps in situations where the score oscilates between fail high and fail low, which is not that common. It can help with analysis of complicated positions; strength wise there is little point.
My engine Postduif uses one and I'm planning to switch Jazz over as well.

thomasahle
Posts: 74
Joined: Thu Feb 27, 2014 7:19 pm

Re: Storing both alpha and beta scores in TT

kbhearn wrote:If you were using mtd(f), it may be important to store both a lower and upper bound for every node as your zero window searches would be bouncing back and forth trying to find the right range.
I am indeed using MTD, so this makes a lot of sense. I also just realized that Aske Plaat does indeed store both values in his examples. I just only looked at PVS table code until now :-)

thomasahle
Posts: 74
Joined: Thu Feb 27, 2014 7:19 pm

Re: Storing both alpha and beta scores in TT

Evert wrote:What you decribe is known as a "dual bound" table, there's some discussion to be found about these.
Things are so much easier to find, when you know the right name, Thank you! I found this discussion http://www.talkchess.com/forum/viewtopi ... 49&t=39889 which was very helpful.

The author of that thread also considered storing multiple depths. I'm not quite sure what the idea was to do with them..

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Storing both alpha and beta scores in TT

thomasahle wrote:
Evert wrote:What you decribe is known as a "dual bound" table, there's some discussion to be found about these.
Things are so much easier to find, when you know the right name, Thank you! I found this discussion http://www.talkchess.com/forum/viewtopi ... 49&t=39889 which was very helpful.

The author of that thread also considered storing multiple depths. I'm not quite sure what the idea was to do with them..
you need two, one for each bound, since they can come from different depths...

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Storing both alpha and beta scores in TT

thomasahle wrote:
kbhearn wrote:If you were using mtd(f), it may be important to store both a lower and upper bound for every node as your zero window searches would be bouncing back and forth trying to find the right range.
I am indeed using MTD, so this makes a lot of sense. I also just realized that Aske Plaat does indeed store both values in his examples. I just only looked at PVS table code until now :-)
one note then on them sharing a tt entry then, the move should probably be kept from the fail high/lowerbound entry whether it's most recent or not as this should represent a reasonable move for ordering while a fail low/upperbound move is pretty random.

thomasahle
Posts: 74
Joined: Thu Feb 27, 2014 7:19 pm

Re: Storing both alpha and beta scores in TT

Ah, I didn't think of that. Then I could even have contradicting upper and lower bounds. That would be awkward.

I guess that's just general search instability. Though I'm wondering if saving a value for each depth, and thus getting a more stable, though less accurate search, would actually be good or bad for performance..

thomasahle
Posts: 74
Joined: Thu Feb 27, 2014 7:19 pm

Re: Storing both alpha and beta scores in TT

Right. Fail low/upper bound moves are no better than random moves.

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Storing both alpha and beta scores in TT

thomasahle wrote:Ah, I didn't think of that. Then I could even have contradicting upper and lower bounds. That would be awkward.

I guess that's just general search instability. Though I'm wondering if saving a value for each depth, and thus getting a more stable, though less accurate search, would actually be good or bad for performance..
If they are contradictory, the depth would have to be different. Deepest draft should "rule" probably.