Author: John Lowe
Date: 14:41:09 12/27/02
Go up one level in this thread
On December 27, 2002 at 16:51:14, Robert Hyatt wrote: >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 I'm going to have to face this soon - I know it's not trivial and my conception, as usual, will be simplistic and naive. A repeat move becomes significant only when it is returned as the players move. If it leads to a draw it is in the interest af a side that is losing otherwise it is to be avoided. At some stage it must acquire a score of "0". Does the inclusion of the "repeat move" information in the search itself affect the move that will be made in avoiding the repetition? Or is the second best move found in the search (assuming not another repeat) either not adequate or uncertain?
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.