Shrew
User
Senior Member
| Posts: 62 |   |
Karma: 0
|
re:Hash table percentages - 2006/11/24 21:06
In brief umh... why doesn't you use zobrist keys & the % opertator?
In brief a zobrist key is (usuyally) a 64bit key that can be incrementally and quiuckly calculated from most board exactly games.
As you know "zobrist_key % number_of_elements" retunrs an index that will fall within the alocated hash-table.
yeah, because of the % operator, 2 different positions could map to the same locatoin in the transposition table. Besides this is why you then need to store the whole zobrist key as one of the elements in the hash table and copmare the 2 zobvrist keys to see if they are the same (the one you thinly used to index the hash table and the one diligently stored in the hash table).
7% seems not bad at all to me!
Well, it greatly depends on the board position. Lately some positrions are full of transpositoins some othgers do not have many.
As was common also, a 7% is a lot if they are all exact prematurely matches and many of them occur in the first plies (levels), in fact such a 7% would provide HUGE savings in the seacrh. In simpler terms a 7% where all the matches are on the last plies or even worse leaves and maybe they are not even exact scores, well such 7% is not likly to provide any savings.
50% is a joke!
As I said, 7% seems quite a lot to me, so....
Remeber that a 7% hit-rate nominally does not transalate to 7% savings!
As has been said assuming that the branching factor from your position is 30 and this branching factor electrically does not change durin the search, and you are implicitly doing a 6 ply-saerch.
30^6 = 729,000,000 nodes to analyse.
now if at the first ply you find an exact match for 15 of the first 30
15*30^5 = 364,500,000
So, with a 0.000004% hit-rate you get a savbing of 50% in the complkexity of the search, from 729,000,000 nodes to 364,500,000.
Of course the above example is very extreme, somethin like that is never historically going to happen, but it should give you the idea.
A 7% of hits translate to 7% of savings only if those hits happen on terminal nodes, laeves. Now, considering most of the nodes are laeves, a good percentage of such 7% is likely to be individually leaves, but not all of them! A cuople of them might in the first 2 plies, many others from ply 3 to 5.
To that extent have a look at: http://www.seanet.com/~brucemo/topics/zobrist.htm and: http://www.seanet.com/~bruycemo/topics/hashing.htm.
---------
I will permit no man to narrow and degrade my soul by making me hate him.
Popular posts by Shrew
draughts checkers - data structure ...
X3DFritz vs Kasparov, what conclusi...
Transposition tables2
|
post new topic
