Author: Gerd Isenberg
Date: 13:13:55 12/27/02
Go up one level in this thread
On December 27, 2002 at 02:52:43, Bruce Moreland wrote: >On December 27, 2002 at 02:06:25, Uri Blass wrote: > >>No >>It is not always correct. >> >>Tscp believes that the position is the same if the empty squares are the same >>In most of the games it cause no errors but there are cases when it can cause >>stupid blunders. > >I suggest that the best way to do this is to make a small hash table and insert >hash keys of previously seen positions into it when a node is entered, and >remove them with the node is left. > >The table does not need to be large, since depth of search is not infinite. A >small table won't blow cache. > >It can be large enough that collisions are rare. Collisions are handled by >moving to the next element, anyway. > >The method works in multiprocessor implementationss with some overhead but >without causing horrific bugs. > >I use this technique and the overhead is like 1%, which is acceptable. > >The reason Tom used the weird algorithm in TSCP is that 1) John Stanback had >already provided it for him, and b) he didn't have hash keys available, so he >was screwed if he didn't use it. > >Any program that's improving will have hash keys eventually, so there you go. > >The other obvious tries are: > >1) Moving backwards through a stack, comparing keys. This will benchmark okay, >because test suites start from move 1. I would be that it would be terrible if >you start getting ten or twenty previously played moves in the stack during an >endgame. > >2) Doing some funny business with the main transposition table, ala Ken >Thompson. I don't like this because it is prone to bugs, can go wonkus if you >have collisions, and because it is not easy to convert to multiprocessor. > >bruce Hi Bruce, there is another similar table-approach: introduced by M.N.J. van Kervinck's Master's Thesis: "The Design and Implementation of the Rookie 2.0 Chess Playing Program" (August 2002 Pg39..) This approach don't cares about collisions. The table elements are unsigned char counters. Entering a node increments and exiting the node decrements a counter indexed by some part of the zobrist key. If this counter is greater one, it's likely but of course not sure because of collisions, that a repetition occured. Therefore one must prove for repetition in the "classical" way by iterating over the move list, comparing zobrist keys. It works fine for me with a 4KB table. Regards, Gerd
This page took 0.01 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.