Author: Bruce Moreland
Date: 23:52:43 12/26/02
Go up one level in this thread
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
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.