title: Chess: Extracting the principal variation from the transposition table
body: <p>Earlier, I was having an issue involving my principal variation becoming truncated by an alpha-beta search. Indeed, this appears to be a common issue. From the authors of Crafty:</p>
  
  <blockquote>
    <p>Another solution with even worse properties is to extract the full PV
    from the transposition table, and avoid using the triangular array
    completely.  If the transposition table is large enough so that
    nothing gets overwritten at all, this would almost work.  But there is
    a hidden “gotcha”.  Once you search the PV, you continue to search
    other parts of the tree, and you will frequently encounter some of
    those same positions again, but the hash draft will not be deep enough
    to allow the entry to be used.  You continue searching and now have to
    overwrite that entry (exact hash signature match requires this) and
    you now leave a transposition “trail” to a different endpoint, one
    which does not match the original score.  Or any one of the trans/ref
    entries between the root and the actual PV endpoint get overwritten by
    a different position completely, and you now have no way to search the
    transposition table to find the actual endpoint you want to display. 
    Several use this approach to produce the PV, and the complaints are
    generally frequent and loud, because an evaluation paired with an
    unrelated PV is not very useful, either for debugging or for analyzing
    your own games.</p>
  </blockquote>
  
  <p>This makes a lot of sense.</p>
  
  <p>Consider that the principal variation is ABCDEF, but AB returns the board to its original position. Then, an alternative line examined later might be CDEFGH, which results in a different evaluation than the earlier search of just CDEF. Thus, the transposition table entry for the board state after AB is overwritten, potentially with a node that will be cut off by alpha-beta (!!), and the PV of ABCDEF is destroyed forever.</p>
  
  <p>Is there any way around this problem, or do I have to use an external data structure to save the PV?</p>
  
  <p><strong>Specifically, what is wrong with replacing if and only if the new entry is deeper and exact?</strong> This doesn't seem to work, but I'm not sure why.</p>