# 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