Author: J. Wesley Cleveland
Date: 13:35:07 05/02/02
Go up one level in this thread
On May 02, 2002 at 13:22:49, Robert Hyatt wrote: >On May 02, 2002 at 12:32:49, J. Wesley Cleveland wrote: > >>On May 02, 2002 at 11:48:59, Robert Hyatt wrote: >> >>>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... >> >>This is interesting, because the value +1.2 is right for XXX, *but* you need to >>follow the path that leads to TIP, and not to YYY. > >However you can't. There is always a path from XXX to the good score at TIP that does not repeat XXX, of course, but there are reasons why a program might not take it. Hash table overwrites are the most likely. Another ugly one is if the value at TIP goes down when searched deeper. Then the program would prefer the path to YYY because it appears to have a higher value at the same depth. >Perhaps YYY lies just beyond TIP??? then you are screwed. >You are committed, and can't back out, and _then_ you realize that you are going >to _have_ to pass thru YYY and accept the draw, or avoid YYY and lose. > >Not a good choice... and it has happened... > >> >>>Note that in both cases, position XXX means the _same_ identical position, as >>>does YYY.
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.