Author: Don Dailey
Date: 08:21:27 10/01/98
Go up one level in this thread
On October 01, 1998 at 08:10:23, Roberto Waldteufel wrote: > >On October 01, 1998 at 00:47:55, John Coffey wrote: > >>On October 01, 1998 at 00:25:44, James Robertson wrote: >> >>>How do programs detect draws by repetition in a search? I can think of many >>>possible ways, but they all seem really slow. How do most programs quickly >>>detect draws by repetition? >>> >>>Thanks, >>> >>>James >> >> >>James, >> >>I am not sure how other programs do it. Here is an idea I had to >>do it on my program: >> >>Most programs look try to find the position in a hash table if they >>can. If they don't find the position (and sometimes if they do find >>the position) then they are going to search the position deeper. >>Since we are going to access the hash table anyway, then maybe >>we could make use of this fact. >> >>Let us assume that we do/don't find the position in the hash table, >>but we are going to search the position deeper. We can store the >>position and mark that we are doing a search. If later we encounter >>the same position, then we would have to take some action to prevent >>us getting caught in a loop. Once the deeper search is complete then >>we can fill in the result into the hash table and unmark the flag that >>says we are doing a search on this position. >> >>Just an idea. >> >>John Coffey > >I tried this at first, but there are problems to be considered. You have to be >certain that the entry in the table with the draw flag set is not overwritten >during the subtree search beneath that node. You must be certain to reset all >the relavent draw flags if the search is interrupted before finishing. Also, >what happens if you find that the place in the hash table where you would expect >to find your position is already occupied with another position that you don't >want to overwrite (eg if it has been searched deeper than your currant depth)? >Then you have nowhere to store the draw flag. I had so many problems doing it >this way that eventually I set up a separate hash table just for repetitions, >independant from the transposition table. I have found this to be fast, >effective and easy to implement, but rather extravagent with memory. I took the >view that memory is cheap and speed/accuracy are crucial. > >Best wishes, >Roberto You can do a couple of things. One is to use some kind of set associativty scheme in your hash table like cray blitz (I think) used. Basically the idea is to block up your hash table into groups of (n) entries (a power of two, typically 4 or 8 for instance) and then make an effort to put your entry in one of these (n) locations. If your priority is to never overwrite one of these history entries then you will almost certainly never have to overwrite since you will have 8 chances to find an available slot. Another idea is to use some time of rehashing or simply linear probing to find an entry that is free. I don't recommend this in a hash table however. Perhaps the best idea (and will make your program parallel ready) is to use the linear search method. Don't use a hash table at all and just maintain a list of keys for each position. If you do this you should keep a counter of the number of moves since the last irreversible move so you can simply search every other key backwards. We have done tests and in the middlegame the number of tests you will do on the average is slightly more than one in the main search! In principle the hash table method seems far superior but in practice this is not the case. If you are committed to the hash table method and never want to parallelize the search then probably what you are doing is ok. You should get a collision on one of these overwrite addresses very infrequently. In the rare case you do get a collision (and it is a different entry of course), then one messy possible is to keep an overflow table and set a bit in the hash table entry. But this involved additional bookeeping and may not be worth the trouble. I would be interested in finding out if anyone out there has a clever way to deal with this problem or whether they just ignore it. I believe ignoring the problem may be the best solution but I could be wrong. I think address collisions will be extremely rare and we already accept the possibility that we can get two identical keys which are based on totally different positions, so we probably should not get too fussy about this. You can easily do an empirical study to find out how often this is happening. Run a long suite of positions and count how many times you get the collision problem with your sticky hash table history entries. You can also do the additional test of finding out how often this affects the move choice which really is the bottom line! I'll bet this is rare indeed but I could be wrong. - Don idea
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.