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