Principal Variation
Home * Search * Principal Variation
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 [2] [3] .
Contents
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
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 [4] :
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 [5] 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.
Separate PV TT
No matter how the PV is determined, the issue of short principal variations due to exact score hits with sufficient draft from the Transposition table at PV-nodes is one reason, why many programs ignore those matches and continue searching that node. Despite the search overhead seems tiny, since PV-nodes are rare, even more with exact hits, there are other solutions to address the short PV problem, which looses the information of the path that leads to that score, in conjunction with a more difficult debugging task.
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 hash signature, squash it to something relatively small like 12-16 bits and use that as an index into a PV-holder table [6] [7] [8] [9]. As an alternative, Steven Edwards proposed a structure of binary trees to recover the PV without any danger of overwriting causing a loss of information [10].
- Pro: almost always full length PV returned
- Contra: may slow down the search a little and has some space requirement
Multiple PVs
Multiple PVs, that is collecting not only one PV of the best move and testing others don't improve alpha, but collecting and reporting multiple PVs of one or more next best moves for analyzing purposes, requires a less efficient root search, where subsequent moves are searched with a wider alpha-beta window.
See also
- Best Move
- Hash Move
- Move List
- Move Ordering
- Principal Variation Search
- PV Extensions
- PV-Move
- PV-Nodes
- Transposition Table
- Triangular PV-Table
Publications
- Selim Akl, Monroe Newborn (1977). The Principal Continuation and the Killer Heuristic. 1977 ACM Annual Conference Proceedings, pp. 466-473. ACM, Seattle, WA.
- Robert Hyatt (2014). A Solution to Short PVs Caused by Exact Hash Matches. ICGA Journal, Vol. 37, No. 3 » Separate TT for the PV
Forum Posts
1995 ...
- pv score oscillation by Willie Wood, CCC, October 18, 1997
- Storing the PV in a search routine by Scott Gasch, CCC, June 09, 1998
- PV verification heuristic by Peter Jacobi, CCC, July 05, 1998
- Re: PV verification heuristic by Robert Hyatt, CCC, July 06, 1998
- Building the Principal Variation in MTD(f) searches by Andrew Williams, CCC, July 18, 1999 » MTD(f)
2000 ...
- Getting a PV using MTD(f) by Tijs van Dam, CCC, February 08, 2000 » MTD(f)
- MTD(f) and PV by David Rasmussen, rgcc, March 09, 2000 » MTD(f)
- PV update after retrieval from hash table by Leen Ammeraal, CCC, November 30, 2000
- MTD(f) and the PV by Adrian Jackson, rgcc, March 16, 2001 » MTD(f)
- Principal Variation by Benny Antonsson, CCC, December 28, 2001
- Problem with short PV by Benny Antonsson, CCC, January 15, 2002
- Where is Principal Variation? by Severi Salminen, CCC, November 22, 2000
- calculating the PV using MTD by Fabien Letouzey, CCC, September 11, 2002 » MTD(f)
- Returning PV from hash table by Nathan Thom, CCC, January 15, 2003
- Fruit - Question for Fabien by Dan Honeycutt, CCC, March 11, 2004 » Fruit, Node Types, Transposition Table, Principal Variation Search
- My fail soft reduces quality of collected PV. Help needed by Volker Böhm, CCC, April 20, 2004 » Fail-Soft
- triangular pv vs. hash move pv by Stuart Cracraft, CCC, September 11, 2004
2005 ...
- PV based decisions by Mark Lefler, Winboard Forum, April 27, 2006
- Thinker output by Matthias Gemuh, CCC, March 22, 2009 » Thinker
- Extracting PV from TT by Colin, CCC, September 12, 2009
2010 ...
- Taken from CCC (Stockfish & mainlines) by Rebel, OpenChess Programming Forum, July 12, 2010
- Full Principal Variation Retrieval by Hieu Nguyen, CCC, September 06, 2010
- Re: Full Principal Variation Retrieval by Robert Hyatt, CCC, September 07, 2010 » Separate TT for the PV
- working! by Robert Hyatt, CCC, September 17, 2010 » Separate TT for the PV
- Root node search by Onno Garms, CCC, March 13, 2011 » Onno, Root
- An alternative means of PV recovery by Steven Edwards, CCC, April 17, 2011
- Hashing the PV by Stef Luijten, CCC, June 06, 2011
- UCI multipv question by Martin Sedlak, CCC, June 11, 2011 » UCI
- About UCI multipv by Fermin Serrano, CCC, January 17, 2012 » UCI
- Null move in PV by Harm Geert Muller, CCC, July 18, 2012 » Null Move
- triangular pv by Daniel Shawul, CCC, March 22, 2013 » PV Array in PVS
- Hash cutoffs and analysis by Harm Geert Muller, CCC, June 17, 2013 » Transposition Table
- Hashed PVs by Natale Galioto, CCC, August 19, 2013
- Stockfish search by Harm Geert Muller, CCC, October 28, 2013 » Stockfish
- TT with Null Move Cuts A PV Node/Line by Cheney Nattress, CCC, February 21, 2014 » Transposition Table, Null Move Pruning, PV-node
- Cache over-writing and PV's by Forrest Hoch, CCC, October 16, 2014 » Transposition Table | Replacement Strategies
- Stockfish and accurate PV by Matthew Lai, CCC, December 25, 2014 » Stockfish
2015 ...
- epd multipv by J. Wesley Cleveland, CCC, July 28, 2015 » Extended Position Description
- help me test multipv by Alexandru Mosoi, CCC, June 19, 2016
- Collecting the pv in Search by David Cimbalista, CCC, July 19, 2016
- Implementing Multi pv by Charles Thomas, CCC, July 29, 2016
- Collecting PVs of Qsearch ? by Mahmoud Uthman, CCC, October 22, 2016 » Triangular PV-Table, Quiescence Search
- Extracting Principal Variation during search by Dabil, OpenChess Forum, November 18, 2016
- capturing PV in QSearch by thevinenator, OpenChess Forum, January 20, 2017 » Triangular PV-Table, Quiescence Search
- multi-pv analysis by Gregory Strong, CCC, April 23, 2017 Multi-PV
- Collecting PV in a PVS search ? by Mahmoud Uthman, CCC, June 11, 2017 » Triangular PV-Table
- Why PVs aren't displayed -- Robert Hourdart in TCEC chat by Thomas Ewers, CCC, December 01, 2017
External Links
- Collecting the Principal Variation from Bruce Moreland's Programming Topics
- Variation (game tree) from Wikipedia
References
- ↑ Variation (game tree) from Wikipedia
- ↑ triangular pv vs. hash move pv by Stuart Cracraft, CCC, September 11, 2004
- ↑ Extracting PV from TT by Colin, CCC, September 12, 2009
- ↑ Collecting the Principal Variation from Bruce Moreland's Programming Topics
- ↑ memcpy - C++ Reference
- ↑ Re: Full Principal Variation Retrieval by Robert Hyatt, CCC, September 07, 2010
- ↑ working! by Robert Hyatt, CCC, September 17, 2010
- ↑ Re: Hashing the PV by Robert Hyatt, CCC, June 06, 2011
- ↑ Robert Hyatt (2014). A Solution to Short PVs Caused by Exact Hash Matches. ICGA Journal, Vol. 37, No. 3
- ↑ An alternative means of PV recovery by Steven Edwards, CCC, April 17, 2011