Home * Search * Principal Variation
Principle_variation_16bit.PNG

The Principal variation (PV) is a sequence of moves that programs consider best and therefore expect to be played. All the nodes included by the PV are PV-nodes. Inside an iterative deepening framework, it is the most important move ordering consideration to play the PV collected during the current iteration, as the very first left moves of the next iteration. Although not needed for pure chess playing, most engines print the Principal Variation every time it changes or a new depth is reached for analyzing purposes. There are several implementations to determine the PV - most notably the three mentioned below, which were often controversial discussed in Computer Chess Forums with all their pros and contras [1] [2] .
Variation (game tree), PV of a Minimax tree in blue [3]

Transposition Table

The best moves from the exact entries of the Transposition table may reveal the PV without (much) extra effort.
  • Pro: implementation without extra effort
  • Contra: dependent on the replacement scheme, TT-overwrites may shorten the PV

Separate TT

Programs like Glass use a separate Transposition table exclusively for PV-nodes - however similar results may be achieved with TT multi-tiers or bucket systems and replacement schemes taking care of exact scores of stored PV-nodes. Robert Hyatt had the idea to take the 64 bit signature, squash it to something relatively small like 12-16 bits and use that as an index into a PV-holder table [4] [5] [6] .
  • Pro: almost always full length PV returned
  • Contra: may slow down the search a little and has some space requirement

Collection during search

PV-Tables (or Refutation Tables) are used to collect and propagate best moves and the PV up to the root similar to the best score.
  • Pro: easy implementation; does not risk the cut PV lines in case of PV overwrites
  • Contra: slows down search a little; PV might be cut in case of TT-cutoffs

Triangular PV-Table

A Triangular PV-Table is the most dense implementation of a pre-allocated PV-Table, taking into account that the farther the root the shorter the maximal PVs along the maximum search depth. The space advantage requires a more complicated index scheme though.

PV-List on the Stack

A simple implementation with a linked PV-List on the stack is described on Bruce Moreland's Computer Chess Pages [7] :
typedef struct LINE {
    int cmove;              // Number of moves in the line.
    MOVE argmove[moveMAX];  // The line.
}   LINE;
 
int AlphaBeta(int depth, int alpha, int beta, LINE * pline) {
 
    LINE line;
    if (depth == 0) {
        pline->cmove = 0;
        return Evaluate();
    }
    GenerateLegalMoves();
    while (MovesLeft()) {
 
        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha, &line);
        UnmakeMove();
 
        if (val >= beta) return beta;
        if (val > alpha) {
            alpha = val;
            pline->argmove[0] = ThisMove();
            memcpy(pline->argmove + 1, line.argmove, line.cmove * sizeof(MOVE));
            pline->cmove = line.cmove + 1;
        }
    }
    return alpha;
}

LINE (a buffer that holds the PV) is created at the beginning of every node and a pointer to it is passed to every child nodes. If one of those raise alpha (become a new PV node) they copy their own PV - which is created in the same way as described now - into the pointer received from their parent node. Iteratively this returns the whole Principal Variation. Generally memcpy [8] is an expensive instruction but as alpha is raised only very rarely this does not harm performance too much. The main downside is the allocation of the struct LINE every node which might be dangerous for deep searches with a small stack available.

See also


Publications

  • Selim Akl, Monroe Newborn (1977). The Principal Continuation and the Killer Heuristic. 1977 ACM Annual Conference Proceedings, pp. 466-473. ACM, Seattle, WA.

Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...


External Links


References

  1. ^ triangular pv vs. hash move pv by Stuart Cracraft, CCC, September 11, 2004
  2. ^ Extracting PV from TT by Colin, CCC, September 12, 2009
  3. ^ Variation (game tree) from Wikipedia
  4. ^ Re: Full Principal Variation Retrieval by Robert Hyatt, CCC, September 07, 2010
  5. ^ working! by Robert Hyatt, CCC, September 17, 2010
  6. ^ Re: Hashing the PV by Robert Hyatt, CCC, June 06, 2011
  7. ^ Collecting the Principal Variation from Bruce Moreland's Programming Topics
  8. ^ memcpy - C++ Reference
  9. ^ See also Robert Hyatt's idea

What links here?


Up one Level