# Difference between revisions of "Triangular PV-Table"

GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||

(One intermediate revision by the same user not shown) | |||

Line 123: | Line 123: | ||

=External Links= | =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] | * [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] | ||

− | * [[: | + | * [https://en.wikipedia.org/wiki/Sonny_Stitt Sonny Stitt] - [https://en.wikipedia.org/wiki/The_Champ_(Sonny_Stitt_album) The Eternal Triangle] <ref>[https://en.wikipedia.org/wiki/List_of_jazz_contrafacts List of jazz contrafacts from Wikipedia]</ref>, [https://en.wikipedia.org/wiki/YouTube YouTube] Video |

− | : {{#evu:https://www.youtube.com/watch?v= | + | : feat.: [https://en.wikipedia.org/wiki/Joe_Newman_(trumpeter) Joe Newman], [https://en.wikipedia.org/wiki/Duke_Jordan Duke Jordan], [https://en.wikipedia.org/wiki/Sam_Jones_(musician) Sam Jones], [https://en.wikipedia.org/wiki/Roy_Brooks Roy Brooks] |

+ | : {{#evu:https://www.youtube.com/watch?v=cBbnBHdr1Eg|alignment=left|valignment=top}} | ||

=References= | =References= | ||

Line 130: | Line 131: | ||

'''[[Data|Up one Level]]''' | '''[[Data|Up one Level]]''' | ||

[[Category:Indigo Jam Unit]] | [[Category:Indigo Jam Unit]] | ||

+ | [[Category:Music]] |

## Revision as of 15:45, 18 May 2020

**Home * Programming * Data * Triangular PV-Table**

A **Triangular PV-Table** is an array of principal variations indexed by ply (distance to root). It is employed to collect the principal variation of best moves inside an alpha-beta or principal variation search - like the best score propagated up to the root. Inside an iterative deepening framework, it is most important to play the principal variation first during the next iteration. With some care in not overwriting PV-nodes, many programmers have abandoned PV-Table and reveal the PV from the transposition table ^{[2]} ^{[3]} .

## Contents

# Layout

Assuming a maximum search depth of N plies with pre-allocated 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.

maxLengthPV(ply) = N - ply

Therefor the triangular structure.

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| +-+

# Implementations

## One-Dimensional Array

### Size

The total size of the triangular array in moves can be calculated by the Triangular number:

size = 1+2+3+ ... +(N-1)+N = ½ N(N+1)

### Index

To calculate the index or offset of a PV into a one-dimensional move array by ply either requires storing incremental offsets

index(0) = 0 index(ply+1) = index(ply) + N - ply

or variable multiplication from scratch:

index(ply) = ½ ply (2N + 1 - ply )

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 ^{[4]} .

### 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.

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); } } ...

## 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).

## Linked List on the Stack

An option in C as well in Java is to reserve space for one PV on the stack as automatic variable inside the recursive search routine, and to pass a reference or pointer to the child nodes as demonstrated by Bruce Moreland ^{[5]} . Inside PVS, these arrays are not needed in the zero window search at all, and, C99 conform variable-length arrays on 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.

# PV in PVS

As demonstrated by Daniel Shawul with TSCP ^{[6]} , and explained by Harm Geert Muller ^{[7]} , inside a perfectly stable NegaScout aka Principal Variation Search, a fail-high at a PV-node compared to a null window is always confirmed by the re-search with an exact score improving alpha and will either become part of a new PV at the root or overwritten by a further improvement. Thus, under such conditions, there is no need to keep an array of principal variations, but only one.

MoveType pvArray[N];

However, with a transposition table, aspiration, selectivity and that like, one cannot guarantee such stable behavior.

# See also

# Forum Posts

## 1998 ...

- Storing the PV in a search routine by Scott Gasch, CCC, June 09, 1998

## 2000 ...

- PV array by Nagendra Singh Tomar, CCC, October 10, 2002
- triangular pv vs. hash move pv by Stuart Cracraft, CCC, September 11, 2004
- Instability thing... by Sune Fischer, CCC, September 18, 2004

## 2005 ...

- 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
^{[8]} - restartable nodes and the tri-angular array by Harm Geert Muller, CCC, July 11, 2012
- triangular pv by Daniel Shawul, CCC, March 22, 2013

## 2015 ...

- Collecting Principal variation by Syed Fahad, CCC, March 29, 2015
- Collecting PVs of Qsearch ? by Mahmoud Uthman, CCC, October 22, 2016 » Principal Variation, Quiescence Search
- capturing PV in QSearch by thevinenator, OpenChess Forum, January 20, 2017
- Collecting PV in a PVS search ? by Mahmoud Uthman, CCC, June 11, 2017 » Principal Variation

# External Links

- Collecting the Principal Variation from Bruce Moreland's Programming Topics
- Sonny Stitt - The Eternal Triangle
^{[9]}, YouTube Video

- feat.: Joe Newman, Duke Jordan, Sam Jones, Roy Brooks

# References

- ↑ Elements by Lizzie Furniture - Tables by Elizabeth Battaglia
- ↑ triangular pv vs. hash move pv by Stuart Cracraft, CCC, September 11, 2004
- ↑ Extracting PV from TT by Colin, CCC, September 12, 2009
- ↑ Java: Two-dimensional arrays as arrays of arrays
- ↑ Collecting the Principal Variation from Bruce Moreland's Programming Topics
- ↑ Re: triangular pv by Daniel Shawul, CCC, March 22, 2013
- ↑ Re: triangular pv by Harm Geert Muller, CCC, March 22, 2013
- ↑ See also Robert Hyatt's idea from the principal variation page
- ↑ List of jazz contrafacts from Wikipedia