Author: Rémi Coulom
Date: 06:55:34 12/11/00
Go up one level in this thread
On December 11, 2000 at 03:52:45, Gian-Carlo Pascutto wrote: >Hi all, > >My program has had trouble with getting back a best line from >its search since a long time. I decided to try to fix this and >have it working now, but I have a question on one of the changes >I had to introduce. I use a triangular system like e.g. TSCP does. > >In the psuedocode below, which is the non-first move part of PVS: > > value = -PrincipalVariation(depth-1, -alpha-1, -alpha); > > if (value > alpha && value < beta) > best = -PrincipalVariation(depth-1, -beta, -value); > >I will get truncated PV's. The way to fix this is to replace the >-value in the last call by -value+1. This is needed because the >first call can get a fail-high, and return an exact value if the >new best move is one unit better than the previous one (I use >fail-hard). The research will then fail low (score is equal to >alpha) and get a truncated PV. > >Did I get this correct? Is there anybody else who had to do >something similar? > >-- >GCP I am not sure I understand all you wrote, but I see a small problem in using -value+1 instead of -value: it should not change anything in practice if you are using a hash table. If the first search returns a value that is > alpha, this means that this search failed low. So your hash table should know that the score for the next position is <= -value. Then you re-search the same position with a beta equal to -value+1. But if the first search had been stored in the hash table and you use the hash table as everyone does, then your algorithm should lower beta to -value, and it would make no difference as compared to the original algorithm. I do not know of an easy way to get the full PV all the time. Maybe those who use MTD(f) have thought about it. I think that if there is a way, then it must use the hash table because of the problem I have mentionned above. I do not know how, though. This does not look like an easy problem. Remi
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.