Author: Roberto Waldteufel
Date: 05:10:23 10/01/98
Go up one level in this thread
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
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.