Author: Robert Hyatt
Date: 13:51:14 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. What are you doing to prevent a processor searching one pathway of the tree from seeing a repetition position from a processor searching a completely different path in the tree? IE repetition information is unique to a particular path, regardless of how many are searching it, but they can't "cross" over a "fork" in the path... > >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
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.