Author: Robert Hyatt
Date: 08:48:59 05/02/02
Go up one level in this thread
On May 02, 2002 at 01:54:29, Will Singleton wrote: >On May 02, 2002 at 00:02:53, Robert Hyatt wrote: > >>On May 01, 2002 at 21:53:01, Will Singleton wrote: >> >>>On May 01, 2002 at 11:41:54, Arwin Smit wrote: >>> >>>>Hi, >>>> >>>>I programmed a hash table for my chess engine. It seems to be faster >>>>and stronger now, but as far as I know the disadvantage of using a >>>>hashtable is that the engine will not always find the best solution >>>>anymore. And this is caused by not being able to see a 3-fold repetition >>>>draw anymore in some cases. A position may be in the hash table and >>>>returning a non-draw score, but it was reached in a different part of the >>>>search tree by repetition of positions. >>>> >>>>This worries me a bit since this is the first time I made a change to my >>>>engine causing it to be "non-perfect". >>>>Is the advantage bigger than the disadvantage? >>>>What is the best way to test which version is better anyway? Just let it >>>>play a lot of games against eachother? >>>> >>>>Arwin >>> >>>It's possible you can fix this by 1) not storing draw scores in the hash table, >>>and 2) testing for repetition prior to probing the hash (if you don't use the >>>main hash for your rep detection). >> >> >> >>There is really no way to close all the holes. It is possible that the >>path from the current position to the tip, which is found by a hash hit, >>repeats a position between the current position and the root. But it is >>impossible to know this without storing the complete path in a hash entry. >> >>Not storing draw scores is (IMHO) a bad idea. A draw score is as legitimate >>as any other score. Not storing them to avoid one problem simply creates >>another on the other side... And it still doesn't solve the first problem >>I gave, which means errors are going to occur, period... >> >>I simply ignore them... >> >> > >Hmmm... I don't know about that. You say that a position occurring between the >current position to the tip may contain a repetition of a position that occurred >between the current position and the root, and that the score of the current >position wouldn't reflect the draw without storing draws in the hash. My point >was that, if you don't hash draw scores, the current position would not appear >in the hash, and the draw would have to be found by the normal search. Which >seems to work fine in my prog. It doesn't. Here is a better explanation... root----------YYY----------------------XXX--------------TIP root-------------------XXX-----------------YYY----------------XXX-------TIP You search the first path first. And when you finish searching position YYY, you store a score of +1.2... Which represents what happens between YYY and the TIP position. You search the second path next. When you reach position YYY you retrieve that +1.2 score and use it. It is _wrong_. Because position XXX will be reached before the tip position is reached, producing a correct score of draw. But you are claiming +1.2 which is wrong... Note that in both cases, position XXX means the _same_ identical position, as does YYY. > >Let's take another example. Suppose you find a draw in a search, at ply 7 (draft >0), which gets stored as exact in the hash. Now you and the opponent move, and >in the next search, you find that draw score at ply 5 (draft 0). But it turns >out that the original draw score was from a two-fold repetition in the search, >and that two-fold rep doesn't exist in the current search. Hence, the draw >score in the hash is incorrect. How can it be incorrect now if it was correct _then_??? two-fold or three-fold is _still_ a draw... If you follow a path that doesn't lead to the draw, how would you hash to a position that does??? > >That was part of my thinking in not storing the draw scores. In any case, the >search will find any draws without the need for storing them. > >Will
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.