Author: Dan Newman
Date: 02:29:04 08/03/99
Go up one level in this thread
On August 03, 1999 at 04:02:43, Steve Maughan wrote: >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.