# Structure of the game tree

The game tree represented by a game in a PGN file conceptually consists of a tree of positions. Each position has a unique location: two positions with the same board position and side to move are distinct if they occur at different places in the game tree.

The first position in game is called the initial position. Each position P other than the initial position was reached by a single move from another unique position Q in the game tree.

The position Q which reaches P by a single move is called the parent of P. Each position other than the initial position has a unique parent. The initial position has no parent.

A given position P in the game tree can have 0 or more children. Each of its children are reached by a single move from P, and each such child has P as its parent. Thus, the children of P are the positions whose parent is P.

In the PGN file, there can be several moves that follow a particular position P. The first of these moves is called the primary move.

Any remaining moves are called secondary moves. In the PGN file, the secondary moves are enclosed in parentheses:

`      1. e4 (1. d4 Nf6 (1...d5 2. c4)) (1. Nf3 d5) 1...e5 2. d4`
In the above PGN fragment, the primary move from the initial position is `1.e4`. The secondary moves from the initial position are `1. d4` and `1. Nf3`. The primary move from the position after `1.d4` is `1...Nf6` and the secondary move is `1...d5`. Each position P can be reached from the initial position by a unique sequence of 0 or more moves (it is 0 moves if P is the initial position).

The number of moves in the unique sequence of moves from the initial position to P is called the ply of P. Thus, the initial position has a ply of 0, and the ply of any other position is one greater than the ply of its parent.

The depth of a position P is the number of secondary moves which occur in the sequence of moves from the initial position to P. Thus, the depth of the initial position is 0. If P is reached by a primary move from its parent, then the depth of P is equal to the depth of its parent. Otherwise the depth of P is one greater than the depth of its parent. In the above PGN fragment, the depth of the position after `1. d4` is `1`. The depth of the position after `1. e4 e5 2. d4` is 0.

A position whose depth is 0 is a mainline position. A position that is not a mainline position, and thus whose depth is greater than 0, is a variation position. Each position is either a mainline or a variation position, but not both.

A position with no children is called terminal. Each move from a specific position P has a unique move index. The primary move from P has move index 0. If a move is the i'th move from P occuring in the PGN file, then its move index is i (where we start the count from 0). Thus, a move is secondary if and only if its move index is greater than 0.

The number of children of P equals the number of moves from P. Each child of P has a unique child index which is equal to the move index of the move from P that reaches that child.

The child of P with index 0 is called the primary child of P.

## the game tree and the variations parameter

By default, CQL only considers mainline positions, that is, positions whose variation depth is 0. That is, when CQL reads a PGN file, it conceptually prunes all positions that are not mainline positions from the game tree (when the game is output, the pruned positions are restored however).

This default behavior can be changed by specifying `variations` in the CQL header:

```      (cql input foo.pgn variations)
...```

It can also be changed by invoking cql with the `-variations` option:

`     cql -variations foo.cql`

Note that `variations` as a CQL header parameter is not the same as variation, which is a filter that tests if the current position is in a variation.

Note as well that when `variations` is not set, so the default situation arises, then:

• Every position is a mainline position: `mainline` is always true.
• Every child is primary child. Thus, there is no reason to use the more complex
`      child ( i )`
form to get the i'th child of the current position. Instead, just use `child`.
• If X and Y are positions, then
`      X<Y `
is true if and only if X is an ancestor of Y.
• There is at most one move from a position.
• The position id of a position is equal to its ply, so that the following filter is always true:
`      ply==positionid`

Much of the complexity in CQL comes from dealing with variations. Users interested in full chess don't need to worry about it.

# List of game tree filters

CQL has several filters for getting information about the location of the current position in the game tree and for traversing the tree.

In the table below, any filter that would return a position that does not exist does not match the current position. Also, as usual in CQL, if any of the arguments of a filter do not match, neither does the filter.

For example, if the current position is the initial position, then `parent` does not match. Similarly, if the current position is a terminal position, then `child` does not match.

In the table below, i always represents a numeric argument, that is to say, any numeric filter. For example, because the syntax of the `position` filter is given as:

`  position i`
that means that we can write
`  position 0`

which is the initial position.

Also in the table below, the symbols x and y represent filters whose values are positions. Thus, because the syntax of the `ancestor` filter is given as

`  ancestor (x y)`

That means we can write something like

`  ancestor (parent child)`

This will be true whenever the parent of the current position is an ancestor of the primary child of the current position, which is true whenever they exist. Thus, the filter will be true whenever the current position is neither initial nor terminal.

filter name example description
initial `initial` current position is first position of game
mainline `mainline` current position is in the mainline
`movenumber` `movenumber` move number of current position
`terminal` `terminal` current position has no successors
`ply` `ply` the ply of the current position
`variation` `variation` current position is in a variation
`virtualmainline` `virtualmainline` current position is in a virtual mainline
`positionid` `positionid` position id of current position
`position` `position i ` position whose position id is equal to the i
`depth` `depth` variation depth of current position
`child` `child`
`child (i)`
primary child of current position;
the i'th child of the current position
`parent` `parent` parent of current position
`lca` `lca(x y)` latest common ancestor of its two arguments
`ancestor` `ancestor(x y)` position x is an ancestor of position y
`descendant` `descendant(x y)` position x is a descendant of position y
`distance` `distance(x y)` The number of moves distance between positions x and y
`relop` `x<y` for relop a relational operator, whether the position ids of its argument have the specified relation
`sidetomove` `sidetomove==white` the side to move of the current position