Tuesday, September 17, 2013

Collecting the Principle Variation (PV)

Since the early days of iCE I did not spent to much thought about collecting the principle variation (PV) for a given search. The PV represents the moves sequence from both sides in a given position.
The evaluation of the last position reached when the moves are played is the final resulting score of the just performed search.

My approach was just to collect the PV from the main transposition table. The way it works enables as a side effect to collect the PV by following the exact entries in it.

This is an easy and fast way without overhead. Unfortunately especially on long searches the PV is incomplete because
  • necessary entries were overwritten
  • the PV extends into the quiescence search (where I don't store hash entries)
This did not bother me to much. I considered displaying the PV a rather cosmetic thing anyway.

However for debugging reasons it is helpful to have the complete PV so it is possible to really track down the position whose eval is responsible for the final score. So recently I decided to change my implementation.

Now I collect the PV during search. This involves some storing and copying moves between arrays when a new best move is found.

// update the pv
pv[0] = ml->moves[i];
for (int j = 0; j < STATIC_QSEARCH_MAX_DEPTH; j++)

    // copy the moves from the subtree that this move generated to the pv until we hit an invalid move = end of list    
     if (INVALID_MOVE == (pv[j + 1] = subtree_pv[j])) break; 

I thought this to be really slow but the performance impact was almost not measurable.

Now iCE will display the correct and full PV much more often. There are still some rare cases left (Hash cutoffs in PV Nodes) where the PV is truncated. But this is rather rare.