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 [a1-8,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 a1|h8 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 [a-h1-8]. Thus, K is the same as K[a-h1-8] .

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 invalid

There are six kinds of basic transforms:

  1. id, the identity transform
  2. τσ, the composition of two basic transforms τ and σ.
  3. invertcolor,the color inversion transform
  4. D4, the dihedral transforms
  5. V, H, and VH, the shift transforms: .
  6. C8, the rotations by multiples of 45°

Let τ be a basic transform and F a filter. We write

  τF
for 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 transform id 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 transform invertcolor interchanges the colors black and white in every piece type, game result, color designator, or side-to-move designator in its argument filter. It does not affect square designators:

  invertcolor white  black
  invertcolor black  white
  invertcolor result 0-1  result 1-0
  invertcolor result 1-0  result 0-1
  invertcolor elo white  elo black
  invertcolor elo black  elo white
  invertcolor wtm  btm
  invertcolor btm  wtm
  invertcolor K  k
  invertcolor [Krn_]  [kRN_]
  invertcolor Nd2-4  nd2-4

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 so-called "dihedral group" D4 consists of 8 rigid transformations of the plane that act on a chessboard centered at the origin. Each element of D4 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
  • rotate90: counterclockwise rotation about the board center by 90°
  • rotate180: rotation by 180° about the board center
  • rotate270: clockwise rotation about the board center by 90°
  • reflecth: reflection about the horizontal bisector.
  • reflectv: reflection about the vertical bisector.
  • reflecta1h8 reflection about the a1-h8 diagonal.
  • reflecth1a8: reflection about the h1-a8 diagonal.

Note that if τ and σ are each elements of D4 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 C4. For example, the image of the square d3 under reflecth is the square d6. The image of d3 under reflectv is e3. Its image under rotate90 is f4. Its image under reflecta1h8 is c4.

Let δ be any dihedral transform. Let S be any set of squares. Then

    δS
is 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

    rotate90S  S'

Likewise reflectvS 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)
  reflecth [a1-8,b3]  [a1-8,b6]
  rotate90 [a1-8,b3]  [a-h1,f2]
  reflectv [a1-8,b3]  R[h1-8,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,

  reflecth up  down
  reflecth left  left
  rotate90 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.

  reflecth {check Ra3}  {check Ra6}
  rotate90 {check Ra3}  {check Rf1}
  reflectv {square x in [a1-8,b3] Q attacks x}
       
   {square x in [h1-8,g3] Q attacks x}
  reflectv {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  reflecth U reflecth 

The vertical shift transforms V are the set of unit transforms of the form Ui 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

  reflecth V reflecth

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 VH.

Let S be a set of squares. Then US is defined as the set of squares t such that either:

  • t = U s for some s on ranks 1 through 7, with s in S,
  • t is in a file of 8 squares which is contained in S

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
  U3 a4  a7
  U3 a6  []
  U [a1-8,b3]  [a1-8,b4]
  U-2 {check Ra3 n[a1-8,b4]}  {check Ra1 n[a1-8,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 | a8 
is 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.)

C8 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 C8 to be the basic transforms consist of the eight distinct powers of σ: σi for i ranging from 0 to 7. (C8 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

  τF
for 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:

  U7[a1,a8]  a8

However, V [a1-8] contains only one filter, namely a1-8. 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 non-identity 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 D4 be the 8 dihedral transforms. Then D4 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 VH

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

     Χ D4 {Ka1 ka3} 
          
     (ΧD4){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

D4 Ra1
are 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 does O
  • Otherwise, O has value equal to the maximum of all the values of the filters in O 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 parameter count 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 K
willl 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.

NameSet of basic transforms
flipD4
flipcolorid,
invertcolorreflecth
fliphorizontalid,
reflecth
flipverticalid,
reflectv
reversecolorinvertcolorreflecth
rotate45C8
rotate90C4
shiftUiVj
shifthorizontalUi
shiftverticalVj
In the above table, i and j are integers ranging between -7 and 7 inclusive.