Author: Robert Hyatt
Date: 09:28:09 01/19/04
Go up one level in this thread
On January 19, 2004 at 11:43:21, Sune Fischer wrote: >On January 18, 2004 at 22:39:23, Robert Hyatt wrote: > > >> >>I have heard that Shredder (and others) try to reconstruct the PV by probing the >>hash table at the end of the search. This simply does not work with any degree >>of accuracy. > >It works just fine. > I will say this again with authority: It works just fine _most_ of the time. But _not_ all of the time. I've explained why, carefully. Unless you have some way to realize that a table entry is a PV entry when you store it, so that you can say "never overwrite this entry" then you _will_ suffer losses. You will get short PVs. And you will get PVs with wrong moves.. There is simply nothing you can do about it, any more than you can fix the draw problem with hashing... >A while back I ran lots of test positions and compared the PVs between the two >methods. >What I generally saw was that they were identical, only the hash extracted PV >usually were a few moves longer. > >I don't use the same replacement scheme as Crafty, so that may be part of the >reason. > >The only thing I have noticed is that PV's tend to reach a maximum length, they >rarely grow beyond 20 plies (with my replacement strategy anyway). That is simply a more visible case of a broader problem. > >My explanation is that once the PV has actually reached that kind of depth the >search has been going on for so long that old PV entries have been replaced. That is certainly the problem in any of the cases being discussed. The only solution is to have a table so big you _never_ overwrite, and then on top of that you need a replacement policy that _never_ replaces an existing entry even if the hash signature matches, if the existing entry is a PV position. Of course I know of no way to identify a PV position at the point you store it... > >>IE suppose you search and reach position A while searching the PV. >> Later, at very shallow depths, you reach position A again and >>overwrite it with different "best moves" depending on the depth remaining, >>extensions triggered, etc. Now when you try to recover the PV from the hash >>table, you get the right position A, but the wrong best move. And then the PV >>looks funny. It doesn't happen every time, but if the PV is reconstructed >>enough this way, it happens often enough. I tried this _years_ ago and ran into >>the same problem. Never saw it in debugging. Saw it regularly when kibitzing >>PVs on ICC. :) >> >>I now do it the correct way, backing the PV up along with the score... > >IMO the PV is a non-essential feature, having to do it "correctly" messes up the >code and slows down the engine. It doesn't cost .1%. Just add the code, and then see how many times you actually use it. Hint: only when alpha < score < beta. With PVS that is essentially _never_. You might think it is used all the time, but in reality it is not very frequent. > >That's just more than I want to spend on a fun-to-have feature. > >>Remember that this is speculation since I have never seen Shredder's source. But >>recovering the PV in this way is simply going to produce errors, and there is >>nothing that can be done about it. The first move and score will be correct, of >>course. But beyond that, who knows, and the farther out, the greater the >>probability of a bogus move. > >And? >All engines produce not very bright move way out in the PV. Yes, but the moves they display are the moves that led to the position that produced the score that was backed up. Using the HT to produce the PV doesn't guarantee that. It is not about the quality of the moves. It is about the correlation of the moves to the score being scored. That was what Martin first pointed out. A piece was hanging according to the PV. According to the score all was even. >You can't really rely on anything but the first few moves to be good, unless it >ends in a mate or or tactical win. > >As long as you extract PV moves you won't see outright blunders, if you do you >need to debug your search :) You can definitely see outright blunders. When you probe to find the PV move at ply=11, the entry you find will usually be for the right position, but the wrong depth. That can certainly produce a blunder, such as leaving a mate in 1 that the q-search couldn't find. > >-S.
This page took 0.02 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.