Transposition Tables

[cms271828]

Considering the pseudo code.. http://www.seanet.com/~brucemo/topics/hashing.htm

There are 3 times when RecordHash could be called.
In RecordHash, we are required to set best to the best move.

But for the case when D==0

Code: Select all

if(D==0)
{
    val=EVAL();
    RecordHash(D,  val,   hashfEXACT);
    return val;
}

There is no move, so do we just ignore best=BestMove(), or just make it 0 or some default value to represent a no move?

I don't have QS set up yet, so D==0 will be the leaf nodes.

Thanks

[Zach Wegner]

You want to ignore the move, yes. I have code so that when I pass a nullmove into the hash store function, it doesn't overwrite the previous move stored there.

Also, be sure that you don't store the "best" move on a fail low node, as it's just a random move.

[hgm]

I don't think it really hurts to store a move for fail-low nodes. You are not sure it is the best, because its score is only an upper bound, so it might be arbitrarily worse. But it is always better to start with that move, than with one for which you already know for sure that it is very bad, because it has an even lower upper bound.

Note that the first time you encounter a node is usually at low depth, (if not, you should do IID), and that low-depth searches are often not bad at getting the true value. In particular in QS, if you do a capture that is bad, there is often only one way for the opponent to refute it. So he will find that one way, and thus get the true score.

If the moves you normally try first (e.g. MMV/LVA HxL captures of a piece that turns out to be defended, or good captures according to SEE with a soft-pinned or overloaded piece, or even more common, because a threat already exists to one of your other pieces,) are punished badly, it would be quite useless to start trying these moves again. If the node keeps failing low, the order did not matter anyway, but just on the chance that it might fail high at the new depth, you want to at least start with a move that has some chance.

It might be an idea to use the hash move in a fail-low entry to inform the search that all moves before the given one in the normal move ordering are crap, and should be tried last.

[Jaap Weidemann]

Hi HG,

You make a fine Santa!

Jaap

[cms271828]

Thanks for help, I still have infinitely many more smaller problems...

I don't really want to bother with null entries in my TT,
ignoring QS, can I set an entries' depth to 0, to indicate it is empty?

Obviously I could just test the 64-bit key as being 0, so I know its empty (1 in 2^64 chance of it not being empty),
but I need to overwrite entry with smallest depth anyway, so makes more sense to examine the depths.

But I'm not sure we can say that an entry with depth 0 must be empty, since during the search, when D==0, we have to record the entry in the TT with depth as 0.

Would it be easier when I initialise table, to set all depths as -1 (Again, I don't know how things change using QS, but I'm ignoring it for now).

Thanks for any help, merry xmas

[Harald Johnsen]

You can not just check the depth.
This can work for the current search, but not for the next one (after your opponent makes his move or during pondering). You are not supposed to raz your hash table after each move, that's why ppl add a date field in their entry. You increment a global date counter after each otb move, when you do an insert in the transposition table you can compare the date to know if the entry is up to date or if it comes from a previous search, when you probe the tt you don't compare the date, you compare only the key and depth.

HJ.

edit: http://citeseer.ist.psu.edu/130130.html

[cms271828]

Thanks for reply, but doesn't really help me, just adds more to the confusion.

I'm trying to build a simple TT, where I probe for an entry at entry index / index+1.

So, when I record an entry, I need to insert it into entry index / index+1.

So there are several cases now:
1. BOTH positions are empty
Then I will store into index.

2. ONE position is empty/ has a different 64-bit key,
and the other has 64-bit key matching actual key.
Here, I guess I just overwrite the old entry with the matching key.

3. ONE position is empty, and the other has a different 64-bit key to the actual key.
Here, I think I need to just insert into the empty position.

4. BOTH positions have same matching 64-bit key.
Here, I hink I need to replace the one with the smallest depth.

This brings me back to where I was before, I need to test for depths, and also for empty entries, so perhaps initializing every entry with depth -1, will mean I always write new entry into empty entry, or the one with smallest depth.

Any thoughts? please try and be clear/specific if replying, since your advice will be probably be wasted if I don't understand.

Thanks again.

[hgm]

You could do as you say, always replace the lowest depth if the same key was not already present in one of the two. By initializing empty entries to a 'depth' lower than every filled entry, you then automatically ensure that, in case the choice exist between an empty entry and one filled with a node of the lowest possible depth, it will store in the empty, and spare the filled one.

In practice no one worries, as after a few seconds the table will not contain any empty entries. So it is a purely academic matter how you would encode them. You might as well give empty entries the same depth as the lowest depth that you ever store, or even one higher. There will be no measurable difference, they are quickly overwritten. So in practice people use 0 for empty entries, because memory starts out as 0, so then you don't have to bother with initializing.

Of much more practical importance is to make the entries as small as possible. So that you can store more positions in your hash table. Using negative numbers is probably a bad idea in this respect, as with, say, a six bit unsigned integer you can represent 0-63, while a 6-bit signed integer only runs from -32 to +31. And you probably won't use any of the numbers below -1, so you wasted half the expressing power of your variable by requiring it to represent negative numbers. If 31 as largest depth would be deep enough, it would be better to use a 5-bit unsigned integer for the depth. (Or, if the language you are programming in forces you to use 8 bits always, use some of the bits for spmething else, like bound type, or an indicator that the hash entry was used.)

[Dirt]

...because memory starts out as 0...

Really? I've never found this to be true, unless something initializes it.

[hgm]

Yes, really. You are probably talking about local variables declared within functions. These are residing in the stack, and so are used over and over again. And then you see what the previous user left there.

But for global data that is used for only one purpose, it starts at 0. Never seen it different, except of course when you let the compiler initialize it.