Hash table division

[hgm]

And so it makes sense to declare a bigger odd-ply-HT than an even-ply-HT.

Not really. Number of stores in meaningless. Number of hits is only a little bit less meaningless. What really counts is how much search time the hits save you.

When you say 'odd ply', do you mean counted from the root or counting from the leaves?

[diep]

And so it makes sense to declare a bigger odd-ply-HT than an even-ply-HT.

Not really. Number of stores in meaningless. Number of hits is only a little bit less meaningless. What really counts is how much search time the hits save you.

When you say 'odd ply', do you mean counted from the root or counting from the leaves?

He means iterations.

[Rebel]

AFAIK i was the first one really using 4 sequential or more probes. Bob described in 90s doing 8 random probes (to avoid chaining), but of course at modern memory systems using more than 1 table is pretty slow and/or gives some overhead.

Yes, I think we all have expirimented with the optimal number of slots in the HT. For me it was 4.

[diep]

AFAIK i was the first one really using 4 sequential or more probes. Bob described in 90s doing 8 random probes (to avoid chaining), but of course at modern memory systems using more than 1 table is pretty slow and/or gives some overhead.

Yes, I think we all have expirimented with the optimal number of slots in the HT. For me it was 4.

DDR3 ram can do a quicker abort when requesting <= 32 bytes.
that's why DDR3 is so much faster than DDR2 ram in latency tests requesting small amounts of bytes.

When you don't use the quick abort suddenly you get 192 bytes for free at i7.

How many bytes per entry do you use in Rebel and how many bits stored in hashtable for the position?

I store 70 bits or so for position in hashtable with Diep. Using 128 bits Zobrist.

[Rebel]

And so it makes sense to declare a bigger odd-ply-HT than an even-ply-HT.

Not really. Number of stores in meaningless. Number of hits is only a little bit less meaningless. What really counts is how much search time the hits save you.

When you say 'odd ply', do you mean counted from the root or counting from the leaves?

From the root. The perfect search (except for the best move) goes like this:

odd - xxxxxxxxxxxxxxxxxxxxx (all moves searched) (no beta cut-off)
even - x (beta cut-off) (only one move searched)
odd - xxxxxxxxxxxxxxxxxxxxx (all moves searched) (no beta cut-off)
even - x (beta cut-off) (only one move searched)

etc.

Of course I agree with you that a faster search should be the end result and for me it does, I am just trying to explain the logic behind the approach.

On top of that consider the better flexibility how to profit from the available memory at your disposal. If your PC (for example) has 1GB you (probably) can only use a HT of 512MB. With 2 tables you can use 768MB, one of 512Mb and one of 256Mb.

[Rebel]

AFAIK i was the first one really using 4 sequential or more probes. Bob described in 90s doing 8 random probes (to avoid chaining), but of course at modern memory systems using more than 1 table is pretty slow and/or gives some overhead.

Yes, I think we all have expirimented with the optimal number of slots in the HT. For me it was 4.

DDR3 ram can do a quicker abort when requesting <= 32 bytes.
that's why DDR3 is so much faster than DDR2 ram in latency tests requesting small amounts of bytes.

When you don't use the quick abort suddenly you get 192 bytes for free at i7.

How many bytes per entry do you use in Rebel and how many bits stored in hashtable for the position?

I store 70 bits or so for position in hashtable with Diep. Using 128 bits Zobrist.

I am using 16 bytes per entry. It can be reduced to 14 but I prefer to keep those 2 free bytes for expirimental purposes.

[diep]

And so it makes sense to declare a bigger odd-ply-HT than an even-ply-HT.

Not really. Number of stores in meaningless. Number of hits is only a little bit less meaningless. What really counts is how much search time the hits save you.

When you say 'odd ply', do you mean counted from the root or counting from the leaves?

From the root. The perfect search (except for the best move) goes like this:

odd - xxxxxxxxxxxxxxxxxxxxx (all moves searched) (no beta cut-off)
even - x (beta cut-off) (only one move searched)
odd - xxxxxxxxxxxxxxxxxxxxx (all moves searched) (no beta cut-off)
even - x (beta cut-off) (only one move searched)

etc.

Of course I agree with you that a faster search should be the end result and for me it does, I am just trying to explain the logic behind the approach.

On top of that consider the better flexibility how to profit from the available memory at your disposal. If your PC (for example) has 1GB you (probably) can only use a HT of 512MB. With 2 tables you can use 768MB, one of 512Mb and one of 256Mb.

Your table is split based upon expected outcome of what the position is, so positions >= beta in 1 table and positions <= alfa in 1 table?

That reduces of course the impact of a Zobrist error.

As for the 1GB size being able to use 768 in your approach versus less with 1 table,l that's not entirely true.

I can also use 919191 entries for hashtable easily if i want to.
No need for a slow modulo.

Take 32 bits of your zobrist key, multiply it by 919191 and then take the top bits, so forget about the lowest significant 32 bits.

It's one 32 bits multiplication. Sure that is slower than a single AND, but gives more flexibility

[Rebel]

When implementing hash tables in the days that memory was limited (1 Mb if you were rich) I set-up my hash table data structure as follows:

- One hash table for odd plies
- One hash table for even plies

And where ever possible make the odd ply HT twice as big as the even ply HT because that one is accessed the most due to the AB behaviour. And it also worked great in case of a full HT. Anno 2012 I wonder if that's still the case.

Anyone using a somewhat similar system ?

You realize that if you do an even-ply search, 1/2 of the hash stores are going to be from that last layer of even-ply searches??? That is, for every depth N-1 node where N-1 is odd, you will always see a depth N search (and probe).

I don't see why this makes any sense at all...

I have a display, it gives the percentages how both HT tables fill and the odd-ply HT fills a lot faster than the even ply HT. It's exactly what one might expect from a well ordered search. And so it makes sense to declare a bigger odd-ply-HT than an even-ply-HT. Just try yourself.

Maybe Bob didn't understand you mean odd iterations versus even iterations.

That's of course possible. But I mean from the root.

Code: Select all

ply-1 e2-e4  (odd)   --> into odd-HT
ply-2 e7-e5  (even)  --> into even-HT
ply-3 Ng1-f3 (odd)   --> into odd-HT
ply-4 Nb8-c6 (even)  --> into even HT

Hope that clears things up

[diep]

AFAIK i was the first one really using 4 sequential or more probes. Bob described in 90s doing 8 random probes (to avoid chaining), but of course at modern memory systems using more than 1 table is pretty slow and/or gives some overhead.

Yes, I think we all have expirimented with the optimal number of slots in the HT. For me it was 4.

DDR3 ram can do a quicker abort when requesting <= 32 bytes.
that's why DDR3 is so much faster than DDR2 ram in latency tests requesting small amounts of bytes.

When you don't use the quick abort suddenly you get 192 bytes for free at i7.

How many bytes per entry do you use in Rebel and how many bits stored in hashtable for the position?

I store 70 bits or so for position in hashtable with Diep. Using 128 bits Zobrist.

I am using 16 bytes per entry. It can be reduced to 14 but I prefer to keep those 2 free bytes for expirimental purposes.

Problem of diep is that score is 20 bits and evaluation 20 bits. I have to store evaluation of a position as well - avoids doing a lot of evaluations.

Then i want to store more bits than others for zobrist. From the 70+ i'm currently storing 47 bits. Also side to move i store on top of that.

A bit or 15 i also inverse based upon who has the side to move.

All this results in huge entry size. It's 20 bytes now, but soon it'll be 24 bytes for experimental reasons and i fear for it becoming 28 bytes one day.

[Houdini]

Of course I agree with you that a faster search should be the end result and for me it does, I am just trying to explain the logic behind the approach.

Why does it result in a faster search?