Author: Bruce Moreland
Date: 17:02:32 08/05/99
Go up one level in this thread
On August 05, 1999 at 16:59:21, Scott Gasch wrote: >Hi there, > >I am finding that due to the check extension code my search slows way down in >positions where checks are frequent. I believe this to be because of lines >containing repeated positions which continue possibly infinitely because I do >not check for draw by repetition. I think this is not terribly likely. There are other things going on in positions where checks are extremely frequent, for instance you get long deep lines, lots of pseudo-legal moves that aren't legal, and usually there are a lot of pieces on the board. Also, your check extension may be going completely out of control. If you turn repetition testing completely off, do you crash? This is perhaps another way of asking if you can do a check and a response to check without decrementing draft in either case. If this is the case, you are probably searching a zillion plies deep. >I am already hashing positions in a transposition table so finding repeated >positions should be pretty easy. I looked at Crafty's code, though, and it >seems that Bob has a special list of positions he searches to determine whether >the one passed in is repeating. > >I was thinking of adding a "count" field to the hash table structure. Then, in >the MakeMove routine, increment the "count" of the table entry. In the >UnmakeMove routine decrement it. In the IsDraw routine check for insufficient >material, fifty move, and, to detect repetition, check the hash table count >field of the position. As far as I see the only drawback of this method is that >there might not be a transposition table entry for a position when we enter >MakeMove yet. Do most people use the "list of position keys" method or has >anyone done something like this? I am worried that searching backwards in the >list of positions might take longer AND that there are really two lists -- one >of search tree nodes and another of real game positions up until now. If you use your main hash table for doing repetitions, it sounds like you'd have to write it during the probes, which I don't like, because the implication is that you always overwrite something. Until about a year ago I was doing this though, I had one always-overwrite table that I'd do repeition testing in, and another one that was more selective about what was overwritten. This idea comes from Ken Thompson as far as I know. Last year I switched to a transposition hash table. This is a small table that is written upon node entry, and written again when a node is exited. The table can be small because you won't have more than about 100 entries in it at one time due to the 50-move rule, and you don't have to worry about killing elements in your main table. You can use a different replacement scheme here than in the main hash table, and the whole thing ends up being pretty simple to write. I don't know how the performance of this compares with other methods, but I didn't notice much if any difference, so I just did it. bruce
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.