Changes

Jump to: navigation, search

Triangular PV-Table

534 bytes removed, 17:44, 12 May 2018
no edit summary
=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.
===Size===
The total size of the triangular array in moves can be calculated by the [https://en.wikipedia.org/wiki/Triangular_number Triangular number]:
size = 1+2+3+ ... +(N-1)+N = &#189; N(N+1)
<span style="font-size: 140%;">size = 1+2+3+ ... +(N-1)+N</span>
<span style="font-size: 140%;"> = &#189; N(N+1) = &#189;(N&#178;+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) = &#189; 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> .
Retrieved from "https://www.chessprogramming.org/Special:MobileDiff/1764"

Navigation menu