25,161
edits
Changes
Created page with "'''Home * Programming * Data * Triangular PV-Table''' FILE:triangular_table.JPG|border|right|thumb|link=http://www.elementsbylizzie.com/Furn_Tables.ht..."
'''[[Main Page|Home]] * [[Programming]] * [[Data]] * Triangular PV-Table'''
[[FILE:triangular_table.JPG|border|right|thumb|link=http://www.elementsbylizzie.com/Furn_Tables.html|Triangular Table <ref>[http://www.elementsbylizzie.com/Furn_Tables.html Elements by Lizzie Furniture - Tables] by [http://www.elementsbylizzie.com/Home_Page.html Elizabeth Battaglia]</ref> ]]
A '''Triangular PV-Table''' is an [[Array|array]] of [[Principal Variation|principal variations]] indexed by [[Ply|ply]] (distance to [[Root|root]]). It is employed to [[Principal Variation#CollectionDuringSearch|collect the principal variation]] of [[Best Move|best moves]] inside an [[Alpha-Beta|alpha-beta]] or [[Principal Variation Search|principal variation search]] - like the best score propagated up to the root. Inside an [[Iterative Deepening|iterative deepening]] framework, it is most important to play the principal variation first during the next iteration. With some care in not overwriting [[Node Types#PV|PV-nodes]], many programmers have abandoned PV-Table and reveal the PV from the [[Transposition Table|transposition table]] <ref>[https://www.stmintz.com/ccc/index.php?id=387179 triangular pv vs. hash move pv] by [[Stuart Cracraft]], [[CCC]], September 11, 2004</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29730 Extracting PV from TT] by Colin, [[CCC]], September 12, 2009</ref> .
=Layout=
Assuming a [[Depth#MaxPly|maximum search depth]] of N plies with pre-allocated [[Stack|stacks]], the maximum possible PV-length decreases with increasing distance to root aka ply index during search, and actually needs one move less each ply deeper.
<span style="font-size: 140%;">maxLengthPV(ply) = N - ply</span>
Therefor the triangular structure.
<pre>
ply maxLengthPV
+--------------------------------------------+
0 |N |
+------------------------------------------+-+
1 |N-1 |
+----------------------------------------+-+
2 |N-2 |
+--------------------------------------+-+
3 |N-3 |
+------------------------------------+-+
4 |N-4 |
... /
N-4 |4 |
+-----+-+
N-3 |3 |
+---+-+
N-2 |2 |
+-+-+
N-1 |1|
+-+
</pre>
=Implementations=
==One-Dimensional Array==
===Size===
The total size of the triangular array in moves can be calculated by the [https://en.wikipedia.org/wiki/Triangular_number Triangular number]:
<span style="font-size: 140%;">size = 1+2+3+ ... +(N-1)+N</span>
<span style="font-size: 140%;"> = ½ N(N+1) = ½(N²+N)</span>
<span style="font-size: 140%;"> =</span> <span style="font-size: 300%;">(<span style="font-size: 40%; vertical-align: super;">N</span><span style="font-size: 40%; vertical-align: sub;">2</span><span style="font-size: 40%; vertical-align: super;">+1</span>)</span>
===Index===
To calculate the index or offset of a PV into a one-dimensional move array by ply either requires storing incremental offsets
<span style="font-size: 140%;">index(0) = 0</span>
<span style="font-size: 140%;">index(ply+1) = index(ply) + N - ply</span>
or variable multiplication from scratch:
<span style="font-size: 140%;">index(ply) = ½ ply (2N + 1 - ply )</span>
This index calculation might as well be replaced by a redirection via a small pre-calculated lookup table with N entries of indices, pointers or references, similar to two-dimensional [[Java]] arrays as arrays of arrays with different size <ref>[http://leepoint.net/notes-java/data/arrays/arrays-2D-2.html Java: Two-dimensional arrays as arrays of arrays]</ref> .
===Pseudo Code===
A didactic implementation of the Triangular PV-Table inside an [[Alpha-Beta]] routine. The routine ''movcpy'' copies up to ''n'' moves, but may terminate after copying a null move. To avoid the second condition, it is quite common to store the current length of the PV inside a PV structure.
<pre>
MoveType pvArray[(N*N + N)/2];
void movcpy (MoveType* pTarget, const MoveType* pSource, int n) {
while (n-- && (*pTarget++ = *pSource++));
}
int AlphaBeta(int alpha, int beta, int depth, int ply, int pvIndex) {
...
pvArray[pvIndex] = 0; // no pv yet
pvNextIndex = pvIndex + N - ply;
while ( move = getNextMove() ) {
make (move);
score = -AlphaBeta(-beta, -alpha, depth-1, ply+1, pvNextIndex);
unmake (move);
...
if (score > alpha) {
alpha = score;
pvArray[pvIndex] = move;
movcpy (pvArray + pvIndex + 1, pvArray + pvNextIndex, N - ply - 1);
}
}
...
</pre>
==Quadratic PV-Table==
To avoid the above index calculation, many programmers roughly double the table space for an homogeneous two-dimensional array with all PVs of maximum size N. This allows cheaper indexing due the multiplication by the constant N only, possibly replaced by cheap instructions, i.e. shift for N == 128 (power of two).
<span id="LinkedListontheStack"></span>
==Linked List on the Stack==
An option in [[C]] as well in [[Java]] is to reserve space for one PV on the [[Stack|stack]] as automatic variable inside the [[Recursion|recursive]] search routine, and to pass a reference or pointer to the child nodes as [[Principal variation#PVListontheStack|demonstrated]] by [[Bruce Moreland]] <ref>[http://web.archive.org/web/20040427013839/brucemo.com/compchess/programming/pv.htm Collecting the Principal Variation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics]</ref> . Inside [[Principal Variation Search|PVS]], these arrays are not needed in the [[Principal Variation Search#ZWS|zero window search]] at all, and, [[C|C99]] conform [https://en.wikipedia.org/wiki/Variable-length_array variable-length arrays] on [[Array#Stack|the stack]] are the way to "half" the required stacksize for linked "triangular" PV-arrays.
==Pointer Array==
Another alternative is an array of N pointers to global, homogeneous PV-arrays with size N each. Instead of copying moves alá memcpy, one may swap pointers. While this sounds promising at the first glance, the copy costs are negligible since PV-Nodes and raising alpha are quite rare.
<span id="PVinPVS"></span>
=PV in PVS=
As demonstrated by [[Daniel Shawul]] with [[TSCP]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47573&start=4 Re: triangular pv] by [[Daniel Shawul]], [[CCC]], March 22, 2013</ref> , and explained by [[Harm Geert Muller]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47573&start=10 Re: triangular pv] by [[Harm Geert Muller]], [[CCC]], March 22, 2013</ref> , inside a [[Search Instability|perfectly stable]] [[NegaScout]] aka [[Principal Variation Search]], a [[Fail-High|fail-high]] at a [[Node Types#PV|PV-node]] compared to a [[Null Window|null window]] is always confirmed by the re-search with an [[Exact Score|exact score]] improving [[Alpha|alpha]] and will either become part of a new PV at the [[Root|root]] or overwritten by a further improvement. Thus, under such conditions, there is no need to keep an array of [[Principal Variation|principal variations]], but only one.
<pre>
MoveType pvArray[N];
</pre>
However, with a [[Transposition Table|transposition table]], [[Aspiration Windows|aspiration]], [[Selectivity|selectivity]] and that like, one cannot guarantee such stable behavior.
=See also=
* [[Best Move]]
* [[Hash Move]]
* [[Killer Move]]
* [[Principal variation]]
* [[PV-Move]]
* [[Refutation Table]]
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=20265 Storing the PV in a search routine] by [[Scott Gasch]], [[CCC]], June 09, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=258053 PV array] by Nagendra Singh Tomar, [[CCC]], October 10, 2002
* [https://www.stmintz.com/ccc/index.php?id=387179 triangular pv vs. hash move pv] by [[Stuart Cracraft]], [[CCC]], September 11, 2004
* [https://www.stmintz.com/ccc/index.php?id=388106 Instability thing...] by [[Sune Fischer]], [[CCC]], September 18, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=29730 Extracting PV from TT] by Colin, [[CCC]], September 12, 2009
==2010 ...==
* [http://www.open-chess.org/viewtopic.php?f=5&t=434 Taken from CCC (Stockfish & mainlines)] by [[Ed Schroder|Rebel]], [[Computer Chess Forums|OpenChess Programming Forum]], July 12, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=35982 Full Principal Variation Retrieval] by [[Hieu Nguyen]], [[CCC]], September 06, 2010 <ref>See also [[Robert Hyatt|Robert Hyatt's]] [[Principal Variation#SeparateTT|idea]] from the [[Principal Variation|principal variation page]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=44371 restartable nodes and the tri-angular array] by [[Harm Geert Muller]], [[CCC]], July 11, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=47573 triangular pv] by [[Daniel Shawul]], [[CCC]], March 22, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55819 Collecting Principal variation] by [[Syed Fahad]], [[CCC]], March 29, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=61796 Collecting PVs of Qsearch ?] by [[Mahmoud Uthman]], [[CCC]], October 22, 2016 » [[Principal Variation]], [[Quiescence Search]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=3072 capturing PV in QSearch] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], January 20, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64256 Collecting PV in a PVS search ?] by [[Mahmoud Uthman]], [[CCC]], June 11, 2017 » [[Principal Variation]]
=External Links=
* [http://web.archive.org/web/20040427013839/brucemo.com/compchess/programming/pv.htm Collecting the Principal Variation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics]
=References=
<references />
'''[[Data|Up one Level]]'''
[[FILE:triangular_table.JPG|border|right|thumb|link=http://www.elementsbylizzie.com/Furn_Tables.html|Triangular Table <ref>[http://www.elementsbylizzie.com/Furn_Tables.html Elements by Lizzie Furniture - Tables] by [http://www.elementsbylizzie.com/Home_Page.html Elizabeth Battaglia]</ref> ]]
A '''Triangular PV-Table''' is an [[Array|array]] of [[Principal Variation|principal variations]] indexed by [[Ply|ply]] (distance to [[Root|root]]). It is employed to [[Principal Variation#CollectionDuringSearch|collect the principal variation]] of [[Best Move|best moves]] inside an [[Alpha-Beta|alpha-beta]] or [[Principal Variation Search|principal variation search]] - like the best score propagated up to the root. Inside an [[Iterative Deepening|iterative deepening]] framework, it is most important to play the principal variation first during the next iteration. With some care in not overwriting [[Node Types#PV|PV-nodes]], many programmers have abandoned PV-Table and reveal the PV from the [[Transposition Table|transposition table]] <ref>[https://www.stmintz.com/ccc/index.php?id=387179 triangular pv vs. hash move pv] by [[Stuart Cracraft]], [[CCC]], September 11, 2004</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29730 Extracting PV from TT] by Colin, [[CCC]], September 12, 2009</ref> .
=Layout=
Assuming a [[Depth#MaxPly|maximum search depth]] of N plies with pre-allocated [[Stack|stacks]], the maximum possible PV-length decreases with increasing distance to root aka ply index during search, and actually needs one move less each ply deeper.
<span style="font-size: 140%;">maxLengthPV(ply) = N - ply</span>
Therefor the triangular structure.
<pre>
ply maxLengthPV
+--------------------------------------------+
0 |N |
+------------------------------------------+-+
1 |N-1 |
+----------------------------------------+-+
2 |N-2 |
+--------------------------------------+-+
3 |N-3 |
+------------------------------------+-+
4 |N-4 |
... /
N-4 |4 |
+-----+-+
N-3 |3 |
+---+-+
N-2 |2 |
+-+-+
N-1 |1|
+-+
</pre>
=Implementations=
==One-Dimensional Array==
===Size===
The total size of the triangular array in moves can be calculated by the [https://en.wikipedia.org/wiki/Triangular_number Triangular number]:
<span style="font-size: 140%;">size = 1+2+3+ ... +(N-1)+N</span>
<span style="font-size: 140%;"> = ½ N(N+1) = ½(N²+N)</span>
<span style="font-size: 140%;"> =</span> <span style="font-size: 300%;">(<span style="font-size: 40%; vertical-align: super;">N</span><span style="font-size: 40%; vertical-align: sub;">2</span><span style="font-size: 40%; vertical-align: super;">+1</span>)</span>
===Index===
To calculate the index or offset of a PV into a one-dimensional move array by ply either requires storing incremental offsets
<span style="font-size: 140%;">index(0) = 0</span>
<span style="font-size: 140%;">index(ply+1) = index(ply) + N - ply</span>
or variable multiplication from scratch:
<span style="font-size: 140%;">index(ply) = ½ ply (2N + 1 - ply )</span>
This index calculation might as well be replaced by a redirection via a small pre-calculated lookup table with N entries of indices, pointers or references, similar to two-dimensional [[Java]] arrays as arrays of arrays with different size <ref>[http://leepoint.net/notes-java/data/arrays/arrays-2D-2.html Java: Two-dimensional arrays as arrays of arrays]</ref> .
===Pseudo Code===
A didactic implementation of the Triangular PV-Table inside an [[Alpha-Beta]] routine. The routine ''movcpy'' copies up to ''n'' moves, but may terminate after copying a null move. To avoid the second condition, it is quite common to store the current length of the PV inside a PV structure.
<pre>
MoveType pvArray[(N*N + N)/2];
void movcpy (MoveType* pTarget, const MoveType* pSource, int n) {
while (n-- && (*pTarget++ = *pSource++));
}
int AlphaBeta(int alpha, int beta, int depth, int ply, int pvIndex) {
...
pvArray[pvIndex] = 0; // no pv yet
pvNextIndex = pvIndex + N - ply;
while ( move = getNextMove() ) {
make (move);
score = -AlphaBeta(-beta, -alpha, depth-1, ply+1, pvNextIndex);
unmake (move);
...
if (score > alpha) {
alpha = score;
pvArray[pvIndex] = move;
movcpy (pvArray + pvIndex + 1, pvArray + pvNextIndex, N - ply - 1);
}
}
...
</pre>
==Quadratic PV-Table==
To avoid the above index calculation, many programmers roughly double the table space for an homogeneous two-dimensional array with all PVs of maximum size N. This allows cheaper indexing due the multiplication by the constant N only, possibly replaced by cheap instructions, i.e. shift for N == 128 (power of two).
<span id="LinkedListontheStack"></span>
==Linked List on the Stack==
An option in [[C]] as well in [[Java]] is to reserve space for one PV on the [[Stack|stack]] as automatic variable inside the [[Recursion|recursive]] search routine, and to pass a reference or pointer to the child nodes as [[Principal variation#PVListontheStack|demonstrated]] by [[Bruce Moreland]] <ref>[http://web.archive.org/web/20040427013839/brucemo.com/compchess/programming/pv.htm Collecting the Principal Variation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics]</ref> . Inside [[Principal Variation Search|PVS]], these arrays are not needed in the [[Principal Variation Search#ZWS|zero window search]] at all, and, [[C|C99]] conform [https://en.wikipedia.org/wiki/Variable-length_array variable-length arrays] on [[Array#Stack|the stack]] are the way to "half" the required stacksize for linked "triangular" PV-arrays.
==Pointer Array==
Another alternative is an array of N pointers to global, homogeneous PV-arrays with size N each. Instead of copying moves alá memcpy, one may swap pointers. While this sounds promising at the first glance, the copy costs are negligible since PV-Nodes and raising alpha are quite rare.
<span id="PVinPVS"></span>
=PV in PVS=
As demonstrated by [[Daniel Shawul]] with [[TSCP]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47573&start=4 Re: triangular pv] by [[Daniel Shawul]], [[CCC]], March 22, 2013</ref> , and explained by [[Harm Geert Muller]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47573&start=10 Re: triangular pv] by [[Harm Geert Muller]], [[CCC]], March 22, 2013</ref> , inside a [[Search Instability|perfectly stable]] [[NegaScout]] aka [[Principal Variation Search]], a [[Fail-High|fail-high]] at a [[Node Types#PV|PV-node]] compared to a [[Null Window|null window]] is always confirmed by the re-search with an [[Exact Score|exact score]] improving [[Alpha|alpha]] and will either become part of a new PV at the [[Root|root]] or overwritten by a further improvement. Thus, under such conditions, there is no need to keep an array of [[Principal Variation|principal variations]], but only one.
<pre>
MoveType pvArray[N];
</pre>
However, with a [[Transposition Table|transposition table]], [[Aspiration Windows|aspiration]], [[Selectivity|selectivity]] and that like, one cannot guarantee such stable behavior.
=See also=
* [[Best Move]]
* [[Hash Move]]
* [[Killer Move]]
* [[Principal variation]]
* [[PV-Move]]
* [[Refutation Table]]
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=20265 Storing the PV in a search routine] by [[Scott Gasch]], [[CCC]], June 09, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=258053 PV array] by Nagendra Singh Tomar, [[CCC]], October 10, 2002
* [https://www.stmintz.com/ccc/index.php?id=387179 triangular pv vs. hash move pv] by [[Stuart Cracraft]], [[CCC]], September 11, 2004
* [https://www.stmintz.com/ccc/index.php?id=388106 Instability thing...] by [[Sune Fischer]], [[CCC]], September 18, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=29730 Extracting PV from TT] by Colin, [[CCC]], September 12, 2009
==2010 ...==
* [http://www.open-chess.org/viewtopic.php?f=5&t=434 Taken from CCC (Stockfish & mainlines)] by [[Ed Schroder|Rebel]], [[Computer Chess Forums|OpenChess Programming Forum]], July 12, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=35982 Full Principal Variation Retrieval] by [[Hieu Nguyen]], [[CCC]], September 06, 2010 <ref>See also [[Robert Hyatt|Robert Hyatt's]] [[Principal Variation#SeparateTT|idea]] from the [[Principal Variation|principal variation page]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=44371 restartable nodes and the tri-angular array] by [[Harm Geert Muller]], [[CCC]], July 11, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=47573 triangular pv] by [[Daniel Shawul]], [[CCC]], March 22, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55819 Collecting Principal variation] by [[Syed Fahad]], [[CCC]], March 29, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=61796 Collecting PVs of Qsearch ?] by [[Mahmoud Uthman]], [[CCC]], October 22, 2016 » [[Principal Variation]], [[Quiescence Search]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=3072 capturing PV in QSearch] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], January 20, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64256 Collecting PV in a PVS search ?] by [[Mahmoud Uthman]], [[CCC]], June 11, 2017 » [[Principal Variation]]
=External Links=
* [http://web.archive.org/web/20040427013839/brucemo.com/compchess/programming/pv.htm Collecting the Principal Variation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm Programming Topics]
=References=
<references />
'''[[Data|Up one Level]]'''
