Synopsis
ancestor(Position Position)⇒ Boolean
child⇒ Position
child(Number)⇒ Position
currentposition⇒ Position
depth⇒ Number
descendant(Position Position)⇒ Boolean
distance(Position Position)⇒ Number
initial⇒ Boolean
initialposition⇒ Position
lca(Position Position)⇒ Position
mainline⇒ Boolean
parent⇒ Position
positionNumber ⇒ Position
positionid⇒ Number
terminal⇒ Boolean
variation⇒ Boolean
virtualmainline⇒ Boolean
The Game Tree
A chess game forms a tree with nodes representing individual positions and edges that connect two nodes representing the moves that transitions from one position to another. When there are no variations, this tree is flat with each node having at most one child and a single path from the initial position to the last position. The PGN format provides a syntax for specifying variations (alternate moves) by enclosing moves corresponding to the variation in parentheses. Variations can be nested and the resulting game tree may have many branches consisting of nodes with two or more children.
For example, given the PGN game
1.e4 (1.d4 Nf6 (1...d5) 2.c4) 1...c5 (1...e5) (1...e6 2.d4 (2.d3) 2...c5 (2...d5))
the corresponding tree representation will look something like:
The number in each node is the position id which is the number that CQL assigns to each position in a game and reflects the order in which positions are visited during game traversal.
The position with position id 0 represents the initial position of the game. Each non-initial position has exactly one parent which is the position that immediately precedes it. Each position contains zero or more children which represent positions reachable from it with a single move. In the figure above, the initial position has two children, positions 1 and 9, and the parent of both of these children is position 0.
Given two positions A and B occurring in a game, A is considered to be an ancestor of B if A can be reached from B by iteratively traversing parent nodes, starting at B. In other words, if and only if there exists a sequence of one or more moves, starting at A, that reaches B, then A is an ancestor of B. The initial position is an ancestor of all other positions. In the above diagram, position 1 is an ancestor of positions 2-8, position 4 is an ancestor of positions 5-8, etc. Position B is called a descendant of A if A is an ancestor of B.
The Comparison Filters may be used to check for ancestral relationships. The filter A < B matches the position when A is an ancestor of B and A > B matches when A is a descendant of B. The filters A <= B and A >= B will also match when A and B are the same position.
If a position does not have any children (there are no recorded moves at the position), the position is called a terminal position. The first move specified at a position is called the primary move and any alternate moves specified are called secondary moves. The initial position and all positions reachable from it via primary moves are called mainline positions, all other positions (those that require traversing a secondary move to reach) are called variation positions. In the above diagram, the left-most child always represents the position reached from its parent via the primary move and all other children are reached via secondary moves. In the diagram below, terminal positions are represented by double-circled nodes and mainline positions are highlighted in green.
1.e4 (1.d4 Nf6 (1…d5) 2.c4) 1…c5 (1…e5) (1…e6 2.d4 (2.d3) 2…c5 (2…d5))
The variation depth of a position is an integer that indicates how many secondary moves are traversed to reach the position from the initial position. The variation depth also corresponds to the number of unclosed parentheses at the corresponding position in the PGN file. Any position with a variation depth of zero is a mainline position.
The latest common ancestor (LCA) of two positions A and B is the position with the greatest ply that is a generalized ancestor of positions A and B. A generalized ancestor of A is either an ancestor of A or A itself. Therefore, the LCA of positions A and B will be one of: A, B, or an ancestor of both A and B. In the above figure, the LCA of positions 1 and 2 is position 1, the LCA of positions 6 and 7 is position 5, and the LCA of 4 and 9 is the initial position. The distance between two positions A and B is the sum of the number of moves that separates each of A and B from the LCA of A and B. For example, the distance between positions 4 and 9 is 3 (the integer 3, not position 3) because the LCA of positions 4 and 9 is position 0, there are 2 moves separating position 0 from position 4 and 1 move separating position 9 from position 0; the sum of which is 3.
A position is a virtual mainline position if it is a mainline position or if it can be reached from a mainline position without traversing secondary moves when it is White to move. All children of a virtual mainline position are virtual mainline positions if it is Black to move, otherwise only the position resulting from the primary move is a virtual mainline position. In the following diagram, all virtual mainline positions are highlighted in green and nodes that represent a position where it is Black to move are designated as btm.
1.e4 (1.d4 Nf6 (1…d5) 2.c4) 1…c5 (1…e5) (1…e6 2.d4 (2.d3) 2…c5 (2…d5))
The ancestor and descendant Filters
The ancestor and descendant filters accept a parenthesized list of two Position filters. The filter ancestor(x y) matches the position if x and y are valid positions and position x is an ancestor of position y. The filter descendant(x y) matches the position if x and y are valid positions and position x is a descendant of position y. Note that ancestor(x y) is equivalent to descendant(y x). The ancestor and descendant filters are now deprecated in favor of the equivalent comparison filters: x < y for ancestor(x y) and x > y for descendant(x y). Note that x <= y and x >= y may also be used to test for generalized ancestor or descendant relationships.
The child and parent Filters
The parent filter yields the position that is the parent of the current position. The parent will fail to match the initial position which does not have a parent.
The child filter yields the position that results from the first child of the current position (the one resulting from the primary move at the current position). The child(n) filter yields the nth child at the current position. child(0) is equivalent to child and child(n) yields the position that results from the nth secondary move at the current position. If the specified child does not exist at the current position, the child filter does not match.
Every position, except for the initial position, has exactly one parent. Every position will also have zero or more children. To determine the number of children at the current position, the following filter may be used:
currentposition: move countThe use of currentposition: prevents linearization within a line filter from restricting the visible moves to those in the line being processed.
The currentposition, initialposition, position, and positionid Filters
The currentposition filter yields the position that is currently being evaluated, curpos is a shorthand alias for currentposition. The position filter takes a single numeric argument and yields the position with the provided position ID. If there is no position with the specified position ID, position yields the None value. The positionid filter yields the numeric position ID of the current position. The initialposition filter yields the position that is the initial position of the game, it is equivalent to position 0. initialposition always matches as all games, even those with no moves, have an initial position.
The initial and terminal Filters
The initial filter matches if the current position is the initial position, i.e. the position with position id 0 and no parent. Note that while the initial position is usually the standard starting position in chess, this need not be the case if the FEN PGN tag is used to specify an alternate initial position for the game. initial is equivalent to not parent and positionid == 0.
The terminal filter matches if the current position ends the mainline or a variation, i.e. if the position has no children. terminal is equivalent to not child.
The mainline and variation Filters
A mainline position is one that can be reached from the initial position exclusively via primary moves, all other positions are variations. The mainline filter matches if the current position is a mainline position. The variation filter matches if the current position is a variation position. mainline is equivalent to not variation and depth == 0. variation is equivalent to not mainline and depth > 0.
The depth, distance, and lca Filters
The depth filter yields the variation depth of the current position, i.e. the number of secondary moves that need to be traversed from the initial position to reach the current position. The distance and lca filters each accept a parenthesized argument list containing two position arguments. The lca filter yields the position that is the LCA (latest common ancestor) of the provided positions. The distance filter yields the numeric distance between the provided positions, i.e. the sum of the number of moves separating each position from the LCA of the positions.
The virtualmainline Filter
The virtualmainline filter yields true if the current position is a virtual mainline position, i.e. if it can be reached from the initial position without traversing secondary moves when it is White to move.