Author: Steve Maughan
Date: 04:21:22 08/03/99
Go up one level in this thread
Dan That's really helpful! Thanks! Steve Maughan >>My program uses hash tables to detect 3 move repitition. However, I was thinking >>that chess computers have been able to detect 3 move repitition long before hash >>tables. How did they do this? Does everyone use hash tables for detecting >>draws or is there another way? >> >>Regards >> >>Steve Maughan > > >You can use the position hashcode itself. Just keep a list of hashcodes >of positions along the current path (including actual played game positions) >and scan back through them to find repetitions of the current position. You >don't need to look any further back in the list than the position reached by >the last irreversible move. When scanning backwards, skip every other entry >in the list since those correspond to the other side's positions. Also (I >believe this to be correct), you can skip back by 4 the first time since it >takes at least 4 half moves to repeat a position. > >This technique (magically) isn't as slow as it sounds. I'm not sure >why, but I suspect that most of the time you don't have to do very many >comparisons till you hit the last position reached by an irreversible move. >It seems like it would be a real killer in some positions... But I haven't >noticed any deleterious effect in my program. > >You can do a little trick to reduce the work using a very small hash table >with perhaps 256 entries (just an array of integers). You index this table >with a few bits of the position hashcode whenever you reach a new position >and increment that entry (and decrement it when you leave). If the entry is >> 2, you may have a repetition and need to do a scan of the hashcode list to >make sure. If it's 2 or less you can't have a repetition, so you can skip >the more expensive test. This table is reset whenever an irreversible move >is made (on the board, not in the search). [I think I saw this in Gnuchess, >but I can’t remember.] > >Since the hashcodes don't really correspond to unique positions, there is >the possibility or error of course. But since there are so few hashcodes >involved in the repetition test list, I suspect errors are exceedingly rare. > >-Dan.
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.