Author: Vasik Rajlich
Date: 10:25:12 12/10/05
Go up one level in this thread
On December 10, 2005 at 06:33:42, Tord Romstad wrote: >Hi Vasik, > Hi Tord, >I agree that full PVs shouldn't be very important to the end user. If a >correspondence player pays lots of attention to the moves late in the PV, >he is probably not using the program in a very effective way. > >On the other hand, I have sometimes found full PVs useful when trying >to improve my program. When the search returns some really strange >score, I like to be able to easily find the exact position my program >misevaluated. > Yes, that's true - although it's hard to imagine a user wanting to do this. Anyway I am just grabbing the PVs from the HT :) >On December 10, 2005 at 05:24:19, Vasik Rajlich wrote: > >>3) What I call "key variations". A PV is the variation which gives you the root >>score. A KV is a variation which best explains the difference between the >>analysis of an engine at two iterations, and captures tactical themes much >>better. I have a formal definition for this, and KVs may soon be part of some >>UCI extensions which are under consideration. > >This sounds very similar to Johan Melin's "Critical Variations". Right now I >cannot find Johan's description of the idea except in a cached page at Google, >which is poorly formatted and somewhat hard to read. I have tried to beautify >it below: > > One cute feature in KnightDreamer 3.0 is the critical variations(CV). > Most programs only give the principal variation(PV) at each iteration. > That is what is considered best play by both sides according to that > iteration. > > The critical variation is used when there is a disagreement between > two iterations. The two iterations gets to play the moves of the side > which they think is better(relative to what the other iteration scores > it as). The moves from the previous iteration are stored in the > transposition table, and this wastes memory, which is one reason > most programs don’t do this. Another problem is that in long > searches entries in the transposition table can be overwritten, so > only partial CVs can be retrieved. > > CVs can be very helpful when writing a chess engine. It helps you > understand what the engine needs to see to solve a tactical problem, > such as when null moves delay a tactical finding. > > Example: >[D]rn3rk1/4bppp/1q2p3/p2pP3/8/1PN2B1P/P4PP1/2RQ1RK1 w - - bm Bxd5; id "ECM.961"; > > > On iteration 5 KD doesn’t find the right move and gets an even > score. On iteration 6 it finds the move with a score of more than > a pawn. But the PV begins with: Bxd5 Ra7, so black doesn’t > recapture. What happens if black recaptures? Iteration 5 thought > the recapture worked, so for building the CV we let iteration 6 > take the white pieces and iteration 5 the black: > > CV: Bxd5 exd5? Nxd5 Qd8? Rc8! Qd7 Rc7! None > > In this case, the last position seen by iteration 5 when it decided > “good for black”, black has no move that avoids losing a bishop, > and that is seen by iteration 6. Moves marked ‘!’ were not found > by iteration 5. Moves marked ‘?’ were chosen by iteration 5 but > rejected by iteration 6. (These markers can often be very silly.) > >(End of quote). > >Is this the same as your "Key variations", or is your idea something >different or more general? > Yes, this is on the right track, however it's not quite complete. Let's say you have: Iteration x: move A, move B, move C, etc .., leading to score == Score(x) Iteration y: move A, move B, move D, etc .., leading to score == Score(y) Your "kv" of course starts with A B. Now, you must decide if the "kv" continues with C or D. You compute: Score (x,D) = the score for variation A B D at iteration x Score (y,C) = the score for variation A B C at iteration y If abs (Score (y) - Score (x,D)) > abs (Score (x) - Score (y,C)) then "kv" continues with D, annotated with ! (or !! if score rise is big enough) else "kv" continues with C, annotated with ? (or ?? if score drop is big enough) You then repeat this above procedure until one of the iterations had no opinion about a position along the "kv". You can probably get the point: you want to know if the new iteration showed that a new move (ie. D) became better, or if an old move (ie. C) became worse. Note that each iteration gives you one "kv" with an associated magnitude. (This magnitude could be something like the sum of the score diffs from the equation above along that kv. Of course difference in iteration scores is not good enough.) You can also put together a best "kv" for the search, based on some combination of depth and magnitude. Anyway one other thing to note is that for defining a UCI extension for this, we don't need to tell the engine programmer how he must compute it. Only how to send it, and maybe how to annotate each move along the variation. It should be simple. We can talk about this via email the next few weeks. Vas >Your other ideas are all very interesting. Keep up the good work. > >Tord
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.