Transform filters

A transform filter takes a single argument filter and transforms it into a new filter. For example, the transform filter

flipvertical Ph1-8

is a transform filter whose argument filter is Ph1-8. The transform filter is equivalent to

Ph1-8 or Pa-8

which is to say, it matches a white pawn on the edge of the board.

Each transform filter has an associate set of transforms. A transform is an operation that can change a board position to another (possibly illegal) board position. Transforms also transform filters into new filters. Examples of transforms are the transform that shifts all the pieces in the position up 2 squares; or the transform that reflects a position about the main diagonal. The set of transforms of transform filter always includes the identity transform, which leaves its argument unchanged. (Sometimes we conflate the name of a transform with the name of its associated filter: we might speak of a "shift transform" when we technically mean a "shift transform filter.")

In the above example, the set of transforms associated to flipvertical has two elements:

1. the identity transform
2. the transform that reflects all pieces about the vertical bisector of the board

This set of two transforms, when applied to its argument filter Ph1-8, resulted in the new filter Ph1-8 or Pa1-8. That is why flipvertical Ph1-8 was equivalent to this or filter, which matches white pawns on the edge of the board.

The possible transform filters and their associated sets of transforms are summarized in th following table:

Name of transform filter	category of transform	transform set (not including identity transform)
flipvertical	dihedral transform	reflection about vertical bisector
fliphorizontal	dihedral transform	reflection about horizontal bisector
flip	dihedral transform	all 7 rotations and reflections of the board
flipdihedral	dihedral transform	(same as flip)
rotate90	dihedral transform	rotations by 90°, 180°, and 270°
rotate45	rotate45 transform	rotations by multiples of 45°
flipcolor	color transform	swap colors followed by reflection about horizontal bisector
shifthorizontal	shift transform	shift horizontally
shiftvertical	shift transform	shift vertically
shift	shift transform	shift orthogonally

Thus, flipvertical Ba4 is a dihedral transform filter (one which is equivalent to Ba4 or Bh4. Similarly shift {Pd4 pd5} is a transform filter which matches a position in which there is a white pawn blocking a black pawn.

A transform is a function that transforms the board in some way. Example transforms includes reflections about an axis, rotations, and shifts. Each transform filter is associated with a particular set of transforms.

A transform filter matches the current position if Each transform filter is associated with a set of transforms. The set of transforms always includes the identity transform Transform filters can also take a range between the name of the transform filter and the the argument filter, as in:

flip 3 4 [Qq]a8    

. The range counts the number of transforms for which the filter is true, as explained in more detail below.

Dihedral transforms

Imagine a transparent chess board without any pieces placed at the origin of a coordinate plane, with its sides parallel to the coordinate axes. There are eight rigid transforms to that chessboard that can be performed and still leave it looking the same as the original:

• The identity transform. This does nothing, leaves the chessboard as it is.
• The four reflections about the horizontal bisector of the chessboard (the x axis); the vertical bisector of the chessboard (the y axis); and the two diagonals.
• The three rotations: by 90 degree counterclockwise, by 180 degrees, and by 90 degrees clockwise.

These transforms are called "dihedral" because the composition of any two of them results in a third: if you apply one dihedral transform, then another one, you get a third dihedral transform. This defines the so-called "order 8 dihedral group" of the 8 dihedral transforms.

Each dihedral transform transforms a square on the chessboard to a new square. For example, the square g6 is transformed into the square g3 by the reflection about the horizontal; into b6 by reflection about the vertical; into c7 by rotation 90 degrees counterclockwise; into b3 by rotation 180 degrees; into f2 by rotation 270 degrees; into f7 by rotation about the main diagonal, and into c2 by rotation about the off-diagonal. Of course, g6 is also transformed into itself by the identity transform.

To apply all dihedral transforms to a CQL filter, preface the filter with the word "flip":

fliphorizontal Pg6	flipvertical Pg6	flip Pg6
[Pg6,Pb6]	[Pg6,Pg3]	[Pg6,Pg3,Pb6,Pc7, Pb3,Pf2,Pf7,Pc2]

rotate90 creates an or filter with four clauses corresponding to rotations of 0°, 90°, 180°, and 270°.

rotate90 Pg6	rotate90 Ra1
≡ [Pg6,Pc7,Pb3,Pf2]	≡ [Ra1,Rh1,Rh8,Ra8]

rotate90 does a 4-fold transform on a position. When combined with fliphorizontal or flipvertical it is in fact equivalent to flip. For example:

flip g6 
≡ rotate90 fliphorizontal g6 
≡ rotate90 [g6,g3] 
≡ [g6,g3,b6,b7,b3,f2,f7,c2]

Any transform can be applied recursively to the constituents of a filter. For example,

flipvertical attack (Rg6 K)

is equivalent to

attack (Rg6 k) or
attack (Rb6 k)

Likewise,

rotate90 attack (Rg6 k)

is equivalent to

attack (Rg6 k)
or attack (Rc7 k)
or attack (Rb3 k)
or attack (Rf2 k)

Directions are also transformed:

rotate90 ray up (R[g6,a1] k)

is equivalent to

ray up (R[g6,a1] k) or
ray left (R[c7,h1] k) or
ray down (R[b3,h8] k) or
ray right (R[f2,a8] k)

shift transforms

A shift transform shifts the squares in its single argument filter 0 or more times along some direction. There are three shift filters:

• shiftvertical
• shifthorizontal
• shift

shifthorizontal {Kb1 kg6}	shiftvertical {Kb1 kg6}	shift {Kb1 kg6}
Kb1 kg6 or Ka1 kf6 or Kc1 kh6	Kb1 kg6 or Kb2 kg7 or Kb3 kg8	Kb1 kg6 or Kb2 Kg7 or Kb3 Kg8 Ka1 kf6 or Ka2 Kf7 or Ka3 Kf8 Kc1 kh6 or Kc2 Kh7 or Kc3 Kh8

shiftvertical shifts its argument 0 or more squares vertically:

shiftvertical g6
≡ g1 or g2 or... or g8
≡ g1-8

. Likewise,

shiftvertical [g2,g4]
≡ g1-8

When a square is shifted off the board it normally disappears. Piece designators with empty square sets eliminate the entire transform:

shiftvertical {Kb1 kg6}
  ≡
 {Kb1 Kg6}
 or {Kb2 Kg7}
 or {Kb3 Kg8}

There is no downward shift of kg6 because doing so would eliminate the b1 square for the K.

shifthorizontal works likewise.
shift is equivalent to shifthorizontal shiftvertical. Using the example above:

shift {Kb1 kg6} 
≡ shifthorizontal shiftvertical {Kb1 kg6} 
≡ shifthorizontal {Kb1 kg6} or shifthorizontal {Kb2 kg7} or shifthorizontal {Kb3 kg8}
     ≡
{Kb1 kg6} or {Ka1 kf6} or {Kc1 kh6} or
{Kb2 kg7} or {Ka2 kf7} or {Kc2 kh7} or
{Kb3 kg8} or {Ka3 kf8} or {Kc3 kh8}

This also means that

shift Ka2 ≡ K

wraparound As a special rule, shiftvertical does not alter a file of 8 squares:

shiftvertical {Kd1-8 Ba2} 
     ≡
  {Kd1-8 Ba2} or
  {Kd1-8 Ba3} or
  {Kd1-8 Ba4} or
   ...
  {Kd1-8 Ba8} or
  {Kd1-8 Ba1}

which turns out to be equivalent to

{Kd1-8 Ba1-8}

. But

shiftvertical {Kd2-8 Ba2}
    ≡  
 {Kd2-8 Ba2} or
 {Kd3-8 Ba3} or
 {Kd4-8 Ba4} or
 {Kd5-8 Ba5} or
 {Kd6-8 Ba6} or
 {Kd7-8 Ba7} or
 {Kd8 Ba8} or
 {Kd1-7 Ba1}

which is entirely different. Similarly, shifthorizontal does not change ranks with 8 squares:

shifthorizontal {Ka-h2 Ba4}
≡  {Ka-h2 Ba-h4}

The shift transform doesn't change full ranks or files in the direction of its shift:

shift {Ka-h2 Ba4}
     ≡
 {Ka-h2 Ba-h4} or
 {Ka-h3 Ba-h5} or
 {Ka-h4 Ba-h6} or
 {Ka-h5 Ba-h7} or
 {Ka-h6 Ba-h8} or
 {Ka-h1 Ba-h3}

Note that any transform applied to a piece designator without an explicit square qualifier leaves the piece designator unchanged:

shift K
≡ K

and likewise

flip K
≡ K

The flipcolor transform

The flipcolor transform applied to filter is the or of filter with the new filter formed from the filter as follows:

• the colors of any piece designators in filter are changed;
• wtm is changed to btm and vice versa;
• player white is changed to player black and vice versa;
• elo white is changed to elo black and vice versa
• result 0-1 is changed to result 1-0 and vice versa
• All piece designators in filter are reflected about the horizontal bisector of the board.

flipcolor Ba1 
    ≡
 Ba1 or ba8

Similarly,

flipcolor {wtm result 1-0 [Pk]a-h2}
         ≡
  {wtm result 1-0 [Pk]a-h2}
  or {btm result 0-1 [pK]a-h7}

The rotate45 transform and the cyclic group of order 8

rotate45 is an unusual transform in that it is not allowed to operate on individual squares. Imagine an old-fashioned analogue clock. We will only focus on the minute hand of that clock.

Moving the minute-hand counterclockwise 45 degrees is the same as moving it back in time by 7.5 minutes. I will call this transform the unit counterclockwise transform. If we apply the unit counterclockwise transform twice, then the minute hand goes back by 15 minutes. If we apply it 8 times, then the minute hand stays unchanged.

Therefore, if we are only allowed to apply the unit counterclockwise transform to the minute hand, there are exactly 8 possible transformations of the minute hand, corresponding to moving the hand back 7.5 minutes, 15 minutes, 22.5 minutes, 30 minutes, 37.5 minutes, 45 minutes, 52.5 minutes, and leaving it unchanged.

These 8 transformations are the so-called cyclic group of order 8.

The transformations apply to a CQL filter as well, as long as the filter doesn't name any specific squares. All such a transformation does is change directions. A direction corresponds to a position of the minute hand: up is 12:00; down is 12:30; northeast is 12:07:30; and so on. So the unit counterclockwise transformation transforms up into northwest; northwest into left; left into southwest; and so on.

Thus, rotate45 filter takes the or of all the elements of the order 8 cyclic group applied to the filter. For example,

rotate45 up 1 K
    ≡
up 1 K
or northwest 1 K
or left 1 K
or southwest 1 K
or down 1 K
or southeast 1 K
or right 1 K
or north east 1 K

Note that this is exactly the King's field: the set of squares adjacent to the King. However, we cannot of course apply rotate45 to a filter that names any particular square, because a particular square cannot be rotated 45 degrees. Thus,

    rotate45 Kd3 ; ERROR

Transforms with ranges

If followed by a range, any transform becomes countable and counts the number of transforms of the argument filter that match a position. For example,

    shift 10 20 [Pp]a4

would match positions with between 10 and 20 pawns on the board (although of course it would be much slower than simply writing Pp 10 20.

This gives us a compact way to check, say, if at some point in the game all 4 corners of the board are visited by a rook:

    initial
    rotate90 4
     next* Ra1

Here, next* Ra1 is true if at the current position or in the future, a white rook is on a1. The 4 rotations of this filter are:

rotate90 next* Ra1
    ≡
{next* Ra1} or
{next* Rh1} or
{next* Rh8} or
{next* Ra8}

Here, however, the 4 following the rotate90 means that each of the 4 elements of the rotation group must match. Thus

rotate90 4 next* Ra1
   ≡
{next* Ra1
 next* Rh1
 next* Rh8
 next* Ra8}

That is, each of the 4 clauses must be true. (Recall that in a compound filter enclosed in braces each filter must match for the filter to match). This idea is used to give a compact statement of the problem of finding games in which the same rook visits all 4 corners of the board.

Using ranges to count occurrences of configurations

As another example, consider a configuration where a white queen and a black queen are separated by a single square, with a piece on that square. For example, Qd4 ne4 qf4 is an example of such a configuration. There are eight possible orientations of the queens: the Q can be below the q, or northeast of the q and so on.

How can we find all games in which at least 5 of these configurations occur, sorted by the number of the configurations?

The simplest way is first to express one of valid configurations, say the one we listed above where the q is two squares to the right of the Q and a piece is between them. This configuration turns out to be:

q on right 1 [Aa] on right 1 Q

Written with braces, this expression is:

    q on
      {right 1
        {[Aa] on 
           {right 1 Q}}}

Suppose the position is as in our example: Qd4 ne4 qf4. Will it match?

Well, Q is d4, so this is:

    q on
      {right 1
        {[Aa] on 
           {right 1 d4}}}

But right 1 d4 is e4, so this is:

    q on
      {right 1
        {[Aa] on e4}

There is a [Aa] on e4, namely a black knight, so the last expression is just e4

    q on
      {right 1 e4}
    ≡
    q on f4
    ≡ qf4

So this does in fact match our test position. And this should make clear why it would in fact match the positions where the Q is two squares right of the q separated by a piece. But the key thing to notice is that the right direction can be any of the eight compass directions. Thus, to count configurations where 5 of the eight configurations occur, we stick a rotate45 in front and sort

   sort rotate45 5 8
      next* q on right 1 [Aa] on right 1 Q

This example is taken from Qq-rotations.cql.

If you just want to test for rotations by multiples of 90 degrees, and not the 45 degree rotations, this code might be easier to follow, which tests for rotations of the theme configuration by multiples of 90 degrees: it names explicit squares and does not use direction operators.

     rotate90 4
         next* shift {Qd4 [Aa]e4 qf4}

However, in general shift is much slower and less flexible than using the direction operators . This example code is in Qq-rotations-90-degree.cql

Things to watch out for when using transforms

Using transforms can create code that is concise and easy to understand compared to using square and piece. But there are some pitfalls:

1. transforms create code that is less flexible and more difficult to generalize than using square and piece. Counting and sorting can be more difficult.
2. transforms can make the automatically generated comments more difficult to understand
3. transforms can be slower than using square or piece.

Examples