Transform filters formally
This page describes transform filters more formally than does the main transform documentation, but at the cost of some extra notation. The description here is intended mainly for CQL developers.For most CQL users, we recommend reading the introduction to transforms and perhaps the documentation of flipcolor and other transforms as needed, rather than this page. The goal of CQL, in some sense, is for the user not to need to rely on the detailed analysis here. But for certain edge cases, it might be helpful.
filters and square designators
A filter is a syntactic element which can match a position. Some filters have a value in a position that is either a set, a position, or a number. If a filter does not match a position, it has no value in that position.square designators
A square designator is a kind of CQL filter denoting a set of squares. For example, the square designator a3
denotes the square a3
; the square designator [a18,b3]
denotes the a
file together with b3
.
Note: A square designator must be of the form specified at the square designator link. The filter a1h8
is not a square designator: it is a  filter containing the two square designators a1
and h8
.
A square designator s
represents (or denotes) a particular set of squares
squares(s)
in any position. When we say s
represents a set of squares, we assume that s
is not contained in some larger square square designator (for instance, b1
is contained in [a1,b1]
.)
In a piece designator like K
or [RB]
the square designator is absent and implicitly represents the square designator [ah18]
. Thus, K
is the same as K[ah18]
.
In the discussion below it is sometimes important to distinguish, or at any rate to be cognizant of the fact that a distinction exist, between a square designator and the set of squares it represents.
[] and invalid filters
We augment the set of valid square designators with the special square designator[]
which denotes the empty set.
Even though []
is not a valid CQL filter, we include it in the set of filters. However, any filter containing []
is considered invalid .
basic transforms
A basic transform is a function from filters to filters. A basic transform takes as input a particular CQL filter, its argument, and returns another filter, its image. The image of an invalid filter is invalidThere are six kinds of basic transforms:
id
, the identity transform
τ∘σ
, the composition of two basic transformsτ
andσ
. 
invertcolor
,the color inversion transform 
D_{4}
, the dihedral transforms 
V
,H
, andV∘H
, the shift transforms: . 
C_{8}
, the rotations by multiples of 45°
Let τ
be a basic transform and F
a filter. We write
τFfor the image of
F
under the basic transform τ
.
A filter G
is contained in (or is a constituent of) a filter F
if G
appears within the textual definition of F
. For example,
the filter A attacks z
appears within the filter
square all z in _ attacked by k A attacks z
We now define how any filter F
behaves under each of the six types of basic transforms.
identity transform
The identity transformid
leaves its argument unchanged (or invariant):
id F ≡ F
composition of basic transforms
Ifτ
and σ
are basic transforms, then their composition
τ∘σ
is defined as follows:
(τ∘σ)F ≡
τ(σF)
We often omit the ∘
symbol, so that τσ
is defined as τ∘σ
.
The composition of a basic transform τ
with itself i
times is written τ^{i}
. Thus,
τ^{1} ≡ τ τ^{2} ≡ ττ
We define τ^{0}
to be id.
Let Χ
and Υ
be sets of basic transforms. Then their composition Χ∘Υ
is the set of all basic transforms χ∘υ
for χ
in Χ
and υ
in Υ
.
color inversion transform
The color inversion transforminvertcolor
interchanges the colors black and white in every piece type, game result, color designator, or sidetomove designator in its argument filter. It does not affect square designators:
invertcolor white ≡ black invertcolor black ≡ white invertcolor result 01 ≡ result 10 invertcolor result 10 ≡ result 01 invertcolor elo white ≡ elo black invertcolor elo black ≡ elo white invertcolor wtm ≡ btm invertcolor btm ≡ wtm invertcolor K ≡ k invertcolor [Krn_] ≡ [kRN_] invertcolor Nd24 ≡ nd24
Thus,
invertcolor square all z in _ attacked by k
A attacks z
≡
square all z in _ attacked by K
a attacks z
Note that
invertcolor invertcolor F ≡ id F
for all filters F.
dihedral transforms
The socalled "dihedral group" D_{4} consists of 8 rigid transformations of the plane that act on a chessboard centered at the origin. Each element of D_{4} is a permutation of the set of squares of the chessboard, and is called a dihedral transformation. The elements of this group are:
 id, the identity
 rotate_{90}: counterclockwise rotation about the board center by 90°
 rotate_{180}: rotation by 180° about the board center
 rotate_{270}: clockwise rotation about the board center by 90°
 reflect_{h}: reflection about the horizontal bisector.
 reflect_{v}: reflection about the vertical bisector.
 reflect_{a1h8} reflection about the
a1h8
diagonal.  reflect_{h1a8}: reflection about the
h1a8
diagonal.
Note that if τ
and σ
are each elements of D_{4}
then so is their composition τ∘σ
.
The first 4 entries in the above list, the 4 rotations by multiples of 90°
, form the group of basic transforms called C_{4}
.
For example, the image of the square d3
under reflect_{h}
is the square d6
.
The image of d3
under reflect_{v}
is e3
. Its image under rotate_{90}
is f4
. Its image under reflect_{a1h8} is c4
.
Let δ
be any dihedral transform. Let S
be any set of squares. Then
δSis defined as the set of all squares
δs
, for s
in S
.
For example, if S
is the set of squares on the b
file, and S'
is the set of squares on the second rank, then
rotate_{90}S ≡ S'
Likewise reflect_{v}S
is the set of squares on the g
file.
Let s
be a square designator denoting a set of squares S ≡ squares(s)
. Let
δ
be a dihedral transform.
Then δs
is a square designator denoting the set of squares
δS
:
squares(δs) ≡ δ squares(s) reflect_{h} [a18,b3] ≡ [a18,b6] rotate_{90} [a18,b3] ≡ [ah1,f2] reflect_{v} [a18,b3] ≡ R[h18,g3]
If F is a filter containing a direction specifier d
, and if τ
is a
dihedral transform, then τ
modifies d
according to how a vector pointing in the direction d
on the chessboard would be changed by the action of δ
.
For example,
reflect_{h} up ≡ down reflect_{h} left ≡ left rotate_{90} up ≡ left
For any dihedral transform δ
,
δ(orthogonal) ≡ orthogonal δ(anydirection) ≡ anydirection δ(diagonal) ≡ diagonal
If light F
is a light square filter then
τ(light F)
is either light τF
or dark τF
depending on whether τ
transforms light squares into light squares or dark squares.
A similar rule applies to dark F
.
reflect_{h} {check Ra3} ≡ {check Ra6} rotate_{90} {check Ra3} ≡ {check Rf1} reflect_{v} {square x in [a18,b3] Q attacks x} ≡ {square x in [h18,g3] Q attacks x} reflect_{v} {stalemate right 3 light Qa1&Rb3} ≡ {stalemate left 3 dark Qh1&Rg3}
shift transforms
The unit upward shift transform U
sends any square to its neighbor one rank higher, if that neighbor exists. Thus, U
sends d4
to d5
. U
is defined on the squares in ranks 1 through 7.
We define U^{1}
to be the unit downward shift transform:
it sends any square to its neighbor one rank lower. It is defined for squares in ranks 2 through 8.
Thus,
U^{1} ≡ reflect_{h} U reflect_{h}
The vertical shift transforms V
are the set of unit transforms of the form U^{i}
for i
ranging from 7 to 7. Note that this includes id
as a basic vertical shift transform.
The horizontal shift transforms H are the set
reflect_{h} V reflect_{h}
That, is, vertical shift transformations shift the board up or down a fixed number of squares. Horizontal shift transformations shift the board left or right a fixed number of squares.
The set of shift transforms is the set of basic transformations that are the composition of a vertical shift transform and a horizontal shift transform, namely
the set
V ∘ H
.
Let S
be a set of squares. Then US
is defined as the set of squares t
such that either:

t = U s
for somes
on ranks 1 through 7, withs
inS
, 
t
is in a file of 8 squares which is contained inS
Since shift transforms are defined as compositions of U
and
other basic transforms, this defines the effect of a
shift transform on any set of squares S
. The idea here is that a shift transform acts on a set of squares rigidly, but if S
contains a complete rank or file of squares, then that rank or file is not affected by shifts along that rank or file.
If s
is a square designator representing a set of squares S
, and τ
is a shift transform, then τs
is the square designator representing the set τS
.
squares(τs) ≡ τ squares(s) U a4 ≡ a5 U^{3} a4 ≡ a7 U^{3} a6 ≡ [] U [a18,b3] ≡ [a18,b4] U^{2} {check Ra3 n[a18,b4]} ≡ {check Ra1 n[a18,b2]}
We let
U light F ≡ dark U F U dark F ≡ light U F
which, by the rules for composition, defines the effect of a shift transform on the light
and dark
filters.
As noted above,
a1  a8is not a square designator. Rather, it is a  filter containing two distinct square designators. Its value is the set of squares
[a1,a8]
, but it does not transform in the same way:
U (a1  a8) ≡
a2  []
which is invalid because any filter containing [] is invalid.
However:
U [a1,a8] ≡
a2
This is because U acts on the single square designator [a1,a8]
, transforming it into a new nonempty square designator a2
. (This class of examples is why we have been careful to distinguish between the set of squares represented by a filter and the filter itself: two filters can represent the same set of squares but transform differently.)
C_{8} transforms
Letσ
be the transform that conceptually rotates the board 45° counterclockwise.
Let F
be a filter.
If F
contains a square designator that is not either all 64 squares or the empty square designator, then σF
is undefined.
Any direction specifier in F is rotated counterclockwise 45° under the action of σ
:
σ(up) ≡ northwest σ(northwest) ≡ west σ(orthogonal) 1 K ≡ diagonal 1 K σ(ray diagonal (R b n)) ≡ ray orthogonal (R b n)
We define C_{8} to be the basic transforms consist of the eight distinct powers of σ: σ^{i}
for i
ranging from 0 to 7. (C_{8}
is very rarely required).
Sets of basic transforms and orbits
We saw above that a single basic transform can be applied to a filter resulting in a new filter.Likewise, a set of basic transforms can also be applied to a filter, resulting in a set of filters.
Let Χ
be a set of basic transforms and let F
be a filter.
The orbit of Χ
on F
, written
ΧF
is the set of valid filters
τFfor all
τ
in Χ
.
For example, suppose that Χ
has two elements, id
and invertcolor
.
Then the orbit of Χ
on K
has two elements: the filter K
and the filter k
.
This is because
id K ≡ K invertcolor K ≡ k
On the other hand,
Χ[Kk]
has one element: the filter [Kk]
.
Now let V
be the set of vertical shift transformations: rigid shifts of board upward or downward a distance between 0 and 7.
Then V a1
contains 8 filters, one for each square on the a
file.
Similarly, V [a1,a8]
contains 9 filters:
[a1,a8] a1 a2 a3 a4 a5 a6 a7 a8
For example, a8
is the filter reached by shifting [a1,a8]
up a distance 7:
U^{7}[a1,a8] ≡ a8
However,
V [a18]
contains only one filter, namely a18
. This is because of the vertical shift transforms are defined to leave invariant any full file contained in its argument.
Note that
V {a1  a8} ≡ {a1  a8}
That is because any nonidentity vertical shift transformation will turn either a1
or a8
into [], which in turn will make its containing filter invalid.
Such an invalid filter is not included in the generated orbit of Χ.
Let D_{4} be the 8 dihedral transforms. Then D_{4} a1
has 4 elements, namely the corners of the board: a1
, h1
, a8
, and h8
.
matching an orbit against a position
LetΧ
be a set of filters and let F be a filter. We saw above that
ΧF
is also a set of filters, called the orbit.
An orbit can match a position just like a filter. The orbit
ΧF
matches the current position if and only if some element of the orbit matches the current position.
For example, suppose Χ
contains two filters: the id
and invertcolor
nn.
Suppose F is true if the black king is in double check:
F ≡ A attacks k == 2 invertcolorF ≡ a attacks K == 2
Therefore, the orbit ΧF
contains two filters, and will be true if either white or black is in double check.
Now suppose Χ
is the set of basic shift transforms
V ∘ H
Then the orbit Χ{Ka1 ka3}
will have 48 elements:
{Ka1 ka3} {Kb1 kb3} ... {Kg6 kg8} {Kh6 kh8}This orbit will match a position in which the black king is two squares above the white king.
The orbit
Χ D_{4} {Ka1 ka3}
≡
(Χ∘D_{4}){Ka1 ka3}
has 192 elements, since the Kings here can align in any of the four orthogonal directions, and there
are 48 possible oppositions in each direction. This will match any position in which the two Kings are distance 2 apart in rank or file but not both. It is equivalent to (but slower than) the CQL code
orthogonal 2 K == k
The set value of an orbit
LetΧ
be a set of basic transforms and let F
be a set filter. Then the orbit ΧF
is also a set filter.
ΧF
in the current position represents that union of the sets of squares represented by the filters in the orbit ΧF
in the current position.
For example, the elements of the orbit
D_{4} Ra1are the four filters corresponding to a rook on the corner squares:
Ra1
, Rh1
, Ra8
, Rh8
. The value of this filter is the set of corners on which there is a white rook:
Ra1  Ra8  Rh1  Rh8
The numeric value of an orbit
LetΧ
be a set of basic transforms and let F
be a filter.
Let O
be the orbit ΧF
. Thus, O
is a set of filters.
If F
is a numeric filter, then O
will be a numeric filter:
 If none of the filters in
O
match the current position, then neither doesO
 Otherwise,
O
has value equal to the maximum of all the values of the filters inO
that do match the current position
For example, let Χ
be the set of two basic filters containing id
and invertcolor
, the color inversion filter.
Let F
be the numeric filter that matches if there are 4 or more white pawns in the position:
P>= 4
If there are 4 or more white pawns in the position, then F
has a value equal to that number of pawns; otherwise, F
does not match the position.
Then
Χ(P>= 4)
is an orbit with the two elements P>= 4
and p>= 4
. It will match any position in which either the number of white pawns or the number of black pawns is greater than or equal to 4, in which case
its value will equal the maximum of these numbers.
Transform filters in CQL
In CQL, a transform filter is a filter that represents a set of basic transforms. The syntax of each transform filter is one of:
ΧF Χ count F
where Χ
is the name of the transform filter (a set of basic transforms) and F
is any filter, the argument.
Note that Χ F
is both a particular CQL filter and as well it represents an orbit: namely the the orbit of the filter F
under the set of basic transforms represented by xtransform
.
Transform filters matching a position
IfΧ
is a CQL transform filter, then
ΧF
matches a position if and only if the orbit ΧF
matches the position, that is, if there is some basic transform τ
in Χ
such that τF
matches the current position.
Numeric value of a CQL transform filter
IfΧ
is a CQL transform filter, and if F
is a numeric filter, then then ΧF
is also numeric.
The value is simply the value of the orbit ΧF
(which is the maximum of the value of the elements of the orbit in the position.)
Set value of a CQL transform filter
IfΧ
is a CQL transform filter, and F
is a set filter, then ΧF
is also a set filter whose value is the value of the orbit (which is the union of the values of the elements of the orbit in the position).
count parameter to a CQL transform filter
If the optional parametercount
is present, then the value of Χ count F
is the number of elements in the orbit ΧF
which match the current position.
If F
is itself a
transform filter of the form ΥG
then
the orbit is the orbit of F
under the composition
Χ∘Υ
:
ΧF ≡ Χ (ΥG) ≡ (Χ∘Υ) G
That is, the orbit consists of all filters χυG
such that
χ
is in Χ
and υ
is in Υ
.
Redundant filters in the orbit
Since CQL 6.0.3, CQL tries to remove identical filters from an orbit. Thus,shift flip count Kwilll have value 1.
Unfortunately, the current version is not sophisticated enough to understand equality on a deeper level. For example
flipcolor count {Ka1 ka8}will have value 2 instead of 1, because CQL does not yet realize that
{Ka1 ka8}
and {ka8 Ka1}
mean the same thing here even though they appear to be different filters in this particular context. (In some contexts, like
a8=={Ka1 ka8}
the two filters are not equivalent because they have different set values.)
Table of basic transforms
The CQL filters and the sets of basic transforms to which they correspond are listed in the following table.
Name  Set of basic transforms 

flip  D_{4} 
flipcolor  id ,
invertcolor ∘ reflect_{h} 
fliphorizontal  id ,reflect_{h} 
flipvertical  id ,reflect_{v} 
reversecolor  invertcolor ∘ reflect_{h} 
rotate45  C_{8} 
rotate90  C_{4} 
shift  U^{i}∘ V^{j} 
shifthorizontal  U^{i} 
shiftvertical  V^{j} 
i
and j
are integers ranging between 7
and 7
inclusive.