relation LCA parametersAn LCA parameter is a type of relation parameter that which matches a source/target pair depending on the sequence of moves that lead to the source and to the target. More precisely, given any two positions in the PGN file, there is a unique position, called their latest common ancestor, or LCA. The LCA is always an ancestor of both the source and the target
To determine if an LCA parameter matches a source and target, first the LCA of the source and target is computed. Next, two sequences of moves are computed: from the LCA to the source; and from the LCA to the target. Depending on the length or composition of these sequences of moves, the LCA parameter matches (or fails to match) the target and source). The LCA is defined below, and the syntax and meaning of the LCA parameters are defined in the following table:
|Syntax of LCA parameter||Meaning|
||maximum of the distances of source and target to LCA is in range|
||sum of distances of source and target to LCA is in range|
||distance between source and LCA is in range|
||distance between target and LCA is in range|
||target is an ancestor of source|
||target is a descendant of source|
||length of the longest common sequence of consecutive moves from LCA to source, and from LCA to target, is in range|
Latest Common Ancestor
The latest common ancestor of two positions in a PGN file is the latest position in the game that is an ancestor of both of the positions.
In this definition, a position X is an ancestor of a position Y if there is a sequence of one or more consecutive moves in the PGN file beginning at X and reaching Y. We say Y is a descendant of X if X is an ancestor of Y.
A position X is thus the latest common ancestor of positions Y and Z if:
- X is an ancestor of Y
- X is an ancestor of Z
- X is the latest such common ancestor: if some other position X' is also an ancestor of both Y and Z, then X' is also an ancestor of X.
As a note, by "position" here we don't just mean the board position; we mean the exact position at a particular location within the PGN file. The same board position can recur at multiple places in the same PGN file; each of these occurrences is considered a distinct "position".
For example, consider this simple game from the start position :
1. e4 e5 2. Nf3 Nc6 3. Bb5 (3. Bc4 Bc5) a6 4. Ba4 Nf6Suppose the source is the position after
3. Bc4in the variation, and suppose the target is the position after
4...Nf6in the mainline. The LCA of the source and the target is the position after
2...Nc6,because that position leads to both the source and to the target, and no later position also does.
Now suppose the source is the position after
2. Nf3 and the target is as before - the position after
Then the LCA is the same as the source, because the source is an ancestor of the target (equivalently, the target is a descendant of the source).
LCA Distance ParametersAll of the LCA parameters except for
lcasubstringdepend only on the distances between the LCA and the source/target. By distance between two positions is meant the number of moves required to get from one to the other (in the PGN file).
For example, as can be seen from the above table the relation parameter
(ancestor) matches a source and target if the target is an ancestor of the source. This is equivalent to requiring that the distance from the LCA to the target equals 0, or
(lcatarget 0). This is because:
- if the target is an ancestor of the source, then the target is the LCA of the source and the target;
- The distance between the two identical positions is 0
(lcatarget 0)matches if the distance between the LCA and the target is 0.
As another example, the lca parameter
(lcasum range) will match a source and target if the sum of the distances between the LCA and the target and between the LCA and the source lie within range.
For example, consider the relation filter in the CQL file underpromotion-relation.cql. This example looks for studies that arise from a White underpromotion. The square parameters in that file were discussed here, but the full relation filter also includes an
relation variation (tomove match) (sourcesquares [RNBQ] targetsquares [RNBQ] mismatch 1) (mismatch 1) (lcasum 20 1000)The
lcasumparameter limits the results to targets for which the sum of the distances between the LCA and the target, and between the LCA and the source, to be at least 20. If we removed this line, we would get technically correct but uninteresting promotions studies in which, for example, the differently promoted pieces were shown just after promotion, on the promotion square. By restricting
lcasumto be at least 20, we limit the results to be deeper studies, in which the point of the underpromotion only becomes clear long after the promotion. Thus, the The
lcasumparameter ensures that the source and the target are fairly far away in the game tree. The length of the path from the source to the target in this case must be at least 20 (lie within the range
20 1000, where we tacitly assume that the distance is less than 1000 ply).
The lcasubstring parameterThe
lcasubstringparameter is used to find sequences of moves from the LCA to the target and from the LCA to the source that are similar in some sense. Like the other LCA parameters, it takes a single argument, a range:
Let P1 be the sequence of moves that were used to reach the source from the LCA. Let P2 be the sequence of moves that were used to reach the target from the LCA. The longest common substring of these sequences is the length of the longest sequence of consecutive moves that is identical in P1 and P2.
An example of the use of
lcasubstring is in zugzwang2.cql. This simple CQL file looks for zugzwangs in which the same position recurs in the mainline and in the variations but with
btm in the mainline and
wtm in the variation. The relation filter is:
relation wtm variation (mismatch 0) (lcasubstring 15 1000)The two target filters
wtm variationof the relation filter ensure that the target is wtm and in a variation. The square parameter
(mismatch 0)ensures that the positions are identical. The
(lcasubstring 15 1000)parameter requires that the paths of moves from the LCA to the source and to the target share a contiguous sequence of at least 15 identical moves.
The filter therefore finds studies like the following:
sp.p Uralsky Problemist - 20 JT
|try: after 8..Ke3||solution: after 9.c4|
sorting by relationA relation filter cannot be sorted directly, but you can sort by the value of any LCA parameter by prefacing the name of the LCA parameter with
sort documentation-string. In this case, the output is sorted by the maximum value of that LCA parameter in any matching target.
For example, the example file zugzwang2.cql looks for positions that are black-to-move in the main line, with the same position recurring with white-to-move in the variation. The output is sorted by the length of the longest common contiguous subsequence of moves from the
latest common ancestor of the source and the target, if this length is at least 5. The relevant
relation filter is:
relation wtm variation (mismatch 0) (sort "Common consecutive move sequence" lcasubstring 5 1000)The other lca parameters:
lcasum, lcatarget, lcasource, lcamaxcan all be sorted in this fashion.