Author: Uri Blass
Date: 12:44:44 09/14/02
Go up one level in this thread
On September 14, 2002 at 15:21:04, Tony Werten wrote: >On September 14, 2002 at 14:00:14, Uri Blass wrote: > >>On September 14, 2002 at 13:27:12, Tony Werten wrote: >> >>>On September 14, 2002 at 13:00:09, scott farrell wrote: >>> >>>>I have been reading plenty on hash replacement schemes. >>>> >>>>I have read Breuker's thesis, and done some (slow) searching through the CCC >>>>archives. >>>> >>>>I am going over my code and redoing the hashing parts, only to realise I have >>>>borken IID (internal iterative deepening). >>>> >>>>Now I am unsure of what I should be aiming at in relation to hashing code. >>>> >>>>I am also unsure of exactly what multi-probing the hash tables is. I am guessing >>>>there is still only one hashtable, and different equations to go from >>>>key/checkkey to the hashtable index, so that there can be several alternative >>>>slots that a hash entry for a position could appear at. Is Multi-probe just >>>>aiming at reducing collisions - or is the idea to store more than one hash entry >>>>for popular positions (say 1 for "depth based", and one for "replace always")? >>>> >>>>I think I am correct that I need atleast one of the probes as "replace always" >>>>to get IID to work. What else do I need to guarantee that I get the best moves >>>>from IID backed up to the main search? >>>> >>>>When people say "replace always" do that mean literaly, just store it all the >>>>time? It seems over simplistic - but I tried it, and it works pretty much the >>>>same as my code below that tries to keep the deeper entries. >>>> >>>>Any help apprecated. >>> >>>What most people do is have 2 tables. In the first you only store if the >>>searchdepth >= table depth (and you move the former entry to the second table). >>>If not then store in 2nd table. >>> >>>Tony >> >>For programmers who implemented hash tables in an effective way(see definition >>later): >> >>Did you look at the source code of another program before implementing hash >>tables with 2 tables and if yes which source code did you look at? >> >>When I say using hash tables in an effective way I mean that the following >>conditions happen: >> >>1)hash tables are used to save move generation >>2)hash tables are used to prune the tree >>3)hash tables are used to avoid null move pruning >>4)the program is using 2 tables or one table that can have more than one >>position at each entry. >> >> >>Movei of today is still using only hash tables for order of moves >>and does nothing of 1-4. >> >>I think that the first thing that I will do about changing the hash tables >>management is using hash tables to save move generation. > >This is only an optimization that doesn't effect the size of the tree. Yes but I expect it to make movei clearly faster. The reason is that generating all the legal moves takes significant time. The fact that it should not change the size of the tree is another reason to start first with it because it is more easy to check for bugs. > >The pruning should make a big difference. It's not that difficult. >Add a byte to your hashtable. Make 3 flags: OR_HIGHER=1, OR_LOWER=2, EXACT=3 > >When storing an entry, check it to alpha and beta. If the score >=beta then send >the flag OR_HIGHER, if score<=alpha then send OR_LOWER else send EXACT. > >When taking an entry from the table and the hashtable_depth >= remaining depth >then check the flags. >If flag=EXACT then cutoff >If score>=beta and flag=OR_HIGHER then cutoff. >If score<=alpha and flag=OR_LOWER then cutoff. > >Tony Thanks but it is not so simple in movei. The problem is that the depth is not represented by one number. I have 2 variables for the depth one for partial extension and one is the depth in plies. Today I store only the depth in plies in the hash tables. I can change the definition of depth to depth that is not in plies in order to prune in the same way as crafty but in that case I am going to have less space in the hash tables. Another option is to prune only when the hash_table depth>remaining depth but in that case I do not prune in the best way. The last option is to prune also when hash_table=remaining depth but in that case I may prune based on smaller depth than the depth that I want to search. Uri
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.