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:

id, the identity transform
τ∘σ, the composition of two basic transforms τ and σ.
invertcolor,the color inversion transform
D₄, the dihedral transforms
V, H, and V∘H, the shift transforms: .
C₈, 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 τⁱ. Thus,

  τ¹ ≡ τ
  τ² ≡ ττ

We define τ⁰ 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" D₄ consists of 8 rigid transformations of the plane that act on a chessboard centered at the origin. Each element of D₄ 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₉₀: counterclockwise rotation about the board center by 90°
rotate₁₈₀: rotation by 180° about the board center
rotate₂₇₀: 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 a1-h8 diagonal.
reflect_h1a8: reflection about the h1-a8 diagonal.

Note that if τ and σ are each elements of D₄ 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₄. 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₉₀ is f4. Its image under reflect_a1h8 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

    rotate₉₀S ≡ S'

Likewise reflect_vS 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 [a1-8,b3] ≡ [a1-8,b6]
  rotate₉₀ [a1-8,b3] ≡ [a-h1,f2]
  reflect_v [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,

  reflect_h up ≡ down
  reflect_h left ≡ left
  rotate₉₀ 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₉₀ {check Ra3} ≡ {check Rf1}
  reflect_v {square x in [a1-8,b3] Q attacks x}
      ≡ 
   {square x in [h1-8,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ⁱ 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 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
  U³ a4 ≡ a7
  U³ 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.)

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

  U⁷[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 D₄ be the 8 dihedral transforms. Then D₄ 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₄ {Ka1 ka3} 
          ≡
     (Χ∘D₄){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₄ 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 (when there is a Ka1 and a ka8 in the current position), 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₄

flipcolor id,
invertcolor ∘ reflect_h

fliphorizontal id,
reflect_h

flipvertical id,
reflect_v

reversecolor invertcolor ∘ reflect_h

rotate45 C₈

rotate90 C₄

shift Uⁱ∘ V^j

shifthorizontal Uⁱ

shiftvertical V^j

In the above table, i and j are integers ranging between -7 and 7 inclusive.

Transform filters formally

filters and square designators

square designators

[] and invalid filters

basic transforms

identity transform

composition of basic transforms

color inversion transform

dihedral transforms

shift transforms

C₈ transforms

Sets of basic transforms and orbits

matching an orbit against a position

The set value of an orbit

The numeric value of an orbit

Transform filters in CQL

Transform filters matching a position

Numeric value of a CQL transform filter

Set value of a CQL transform filter

count parameter to a CQL transform filter

Redundant filters in the orbit

Table of basic transforms

INDEXES

CQL 6.1: CHESS QUERY LANGUAGE

GETTING AND RUNNING CQL

CQL KEY CONCEPTS

QUICK LINKS

Name	Set of basic transforms
flip	`D₄`
flipcolor	`id`, `invertcolor ∘ reflect_h`
fliphorizontal	`id`, `reflect_h`
flipvertical	`id`, `reflect_v`
reversecolor	`invertcolor ∘ reflect_h`
rotate45	`C₈`
rotate90	`C₄`
shift	`Uⁱ∘ V^j`
shifthorizontal	`Uⁱ`
shiftvertical	`V^j`

Transform filters formally

filters and square designators

square designators

[] and invalid filters

basic transforms

identity transform

composition of basic transforms

color inversion transform

dihedral transforms

shift transforms

C8 transforms

Sets of basic transforms and orbits

matching an orbit against a position

The set value of an orbit

The numeric value of an orbit

Transform filters in CQL

Transform filters matching a position

Numeric value of a CQL transform filter

Set value of a CQL transform filter

count parameter to a CQL transform filter

Redundant filters in the orbit

Table of basic transforms

C₈ transforms