# transform filters

We often want to repeat the same CQL filter but just changing some things: we might want to change the side to move, or shift all the pieces one square up the board.

Transform filters are a group of filters that allow for this behavior. The transform filters are `flip`, `flipcolor`, ....

A transform filter always has this syntax:

`  transform_filter argument`

Here, transform_filter is the name of the transform filter (e.g., `flip`, `flipcolor`, `shift`). The argument is any filter.

Each transform filter has an associated with a set of basic transforms. A basic transform transforms a filter into a new filter. We say a basic transform transforms a filter to create a transformed filter.

Consider a transform filter T with an associated set of basic transforms

`  T1, T2,...,Tn`

There are two cases.

If argument is a set filter, then `T argument` is replaced in the CQL file with:

```  {T1 argument}
| {T2 argument}
| ...
| {Tn argument}```

If argument is not a set filter, then `T argument` is replaced in the CQL file with:

```  {T1 argument}
or {T2 argument}
or ...
or {Tn argument}```

By "replaced" we mean that the effect is of `T argument` in a CQL file is exactly the same as writing one of these two substitutions.

For example, the most common transform filter is `flipcolor`. The associated set of transforms to `flipcolor` has two elements:

1. The identity basic transform
2. The color swap basic transform

The first of these two basic transforms, the identity basic transform, is straightforward: it just leaves its argument unchanged.

The second of these two basic transforms, the color swap, swaps any colors in its arguments and reflects any squares in its argument about the horizontal bisector. For example,

``` colorswap R ≡ r
colorswap n ≡ N
colorswap [Rnq] ≡ [rNQ]
colorswap wtm ≡ btm
colorswap a2 ≡ a7
colorswap Pa2 ≡ pa7```

Therefore, the code

`  flipcolor Pa2`
is equivalent to
`   Pa2 | pa7`

and

`  flipcolor {[Rnq]a3 wtm stalemate}`
is the same as
```   {[Rnq]a3 wtm stalemate}
or
{[rNQ]a6 btm stalemate}```

All the transform filters correctly handle directions:

```   flipcolor up P
≡
{up P} | {down p}```

## The basic transforms

A basic transform transforms a filter into a different filter. There are three kinds of basic transforms:
1. dihedral basic transforms. These rotate or reflect the board.
2. shift basic transforms. These shift squares by a specific vertical or horizontal offset
3. color transform. The color transform swaps the colors in a filter and flips the squares about the horizontal bisector

Each transform filter has an associated set of basic transforms consisting of basic transforms from exactly one of the above classes, together with the identity transform (except in the case of `reversecolor`).

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
`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
`reversecolor` non-identity color transform like flipcolor, but do not allow the identity transform
`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 | 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

## 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 another: 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` has associated basic transforms 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 {Rg6 attacks k)`
is equivalent to
`{Rg6 attacks k} | {Rb6 attacks k}`
`rotate90 {Rg6 attacks k} `
is equivalent to
```{Rg6 attacks k}
| {Rc7 attacks k}
| {Rb3 attacks k}
| {Rf2 attacks k}```

Directions are also transformed:

`rotate90 ray up (R[g6,a1] k)`
is equivalent to
```ray up (R[g6,a1] k) |
ray left (R[c7,h1] k) |
ray down (R[b3,h8] k) |
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 | Ka1 kf6 | Kc1 kh6 Kb1 kg6 | Kb2 kg7 | Kb3 kg8 Kb1 kg6 | Kb2 Kg7 | Kb3 Kg8 Ka1 kf6 | Ka2 Kf7 | Ka3 Kf8 Kc1 kh6 | Kc2 Kh7 | Kc3 Kh8

`shiftvertical` shifts its argument 0 or more squares vertically:

```shiftvertical g6
≡ g1 | g2 | ... | 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}
| {Kb2 Kg7}
| {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} | {Ka1 kf6} | {Kc1 kh6} |
{Kb2 kg7} | {Ka2 kf7} | {Kc2 kh7} |
{Kb3 kg8} | {Ka3 kf8} | {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} |
{Kd1-8 Ba3} |
{Kd1-8 Ba4} |
...
{Kd1-8 Ba8} |
{Kd1-8 Ba1}```
which turns out to be equivalent to
`{Kd1-8 Ba1-8}`
. But
```shiftvertical {Kd2-8 Ba2}
≡
{Kd2-8 Ba2} |
{Kd3-8 Ba3} |
{Kd4-8 Ba4} |
{Kd5-8 Ba5} |
{Kd6-8 Ba6} |
{Kd7-8 Ba7} |
{Kd8 Ba8} |
{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} |
{Ka-h3 Ba-h5} |
{Ka-h4 Ba-h6} |
{Ka-h5 Ba-h7} |
{Ka-h6 Ba-h8} |
{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 and reversecolor transforms

The `flipcolor` transform applied to filter is the `or` (or | in the case of a set filter argument) 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 | 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 `reversecolor` transform is the same as the `flipcolor` transform except that the identity transform is not allowed. Instead, the colors are reversed and the board flipped. Because `reversecolor` can always be done by hand in the CQL file itself, it is normally only used at the command line using `-reversecolor`

For example,

```reversecolor Ba1
≡
ba8```

## 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` (or the | in the case of a set filter) of all the elements of the order 8 cyclic group applied to the filter. For example,

```rotate45 up 1 K
≡
up 1 K
| northwest 1 K
| left 1 K
| southwest 1 K
| down 1 K
| southeast 1 K
| right 1 K
| 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 a numeric filter 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
find Ra1```
Here, find 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 find Ra1
≡
{find Ra1}
| {find Rh1}
| {find Rh8}
| {find Ra8}```
Here, however, the `4` following the `rotate90` means that each of the 4 elements of the rotation group must match. Thus

```rotate90 4 find Ra1
{find Ra1
find Rh1
find Rh8
find Ra8}```
That is, each of the 4 clauses must be true. (Recall that when a sequence of filters is enclosed in braces each constituent filter must 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&right 1 [Aa]&right 1 Q`

Written with braces, this expression is:

```    q &
{right 1
{[Aa]&
{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 &
{right 1
{[Aa]&
{right 1 d4}}}```
But `right 1 d4` is e4, so this is:
```    q &
{right 1
{[Aa]&e4}```
There is a `[Aa]` on e4, namely a black knight, so the last expression is just `e4`
```    q &
{right 1 e4}
≡
q&f4```
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
find q&right 1 [Aa]&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
find 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, especially shift transforms, can be slower than using `square ` or `piece`.