Transforming Boards in a CQL Universe

This document (still under development) is a companion to the CQL by Example document presented on the Scid++ project site. Most CQL users will have no interest in the material presented below. It addresses an issue which we've only encountered with the application of CQL in a domain which amounts to a niche within a niche within a niche. So why do we bother? What, exactly, is the issue?

If x is a set variable and if τ is a transform filter, then τx ≡ x.

That pretty much sums it up. Within the context of the niche to which we refer, we need to be able to apply a transform to a representation of the board, i.e., set variable, a.k.a. bitboard. In the CQL world, transform filters never modify the board itself or any representation of the board, but are effectively applied to a [compound] filter.

Fortunately, the language is robust and capable, affording us the opportunity to provide for ourselves. We'll construct something of a library of functionality giving us the operations on bitboards (and perhaps FEN strings) that we will need in conducting our little experiment in the problem domain. For those choosing to read further, we recommend having an ample supply of Tylenol at the ready.

Definitions and interfaces

There seems to be little agreement on exactly what it means to flip a board.1 In some quarters it is taken to mean along a line and in other quarters it's taken to mean about a line. We'll subscribe to the definitions given by the Chess Programming Wiki, flipping along the horizontal and vertical and about the diagonals.

This leaves us somewhat at odds with the solving engine semantics, which are effectively along both orthogonal and diagonal lines (at least it's consistent), and with the CQL definition which is about the horizontal and vertical bisectors as well as the diagonals (again, consistent). But the CPW purportedly represents something of a consensus (if there is such a thing) within the chess programming world, and so we've chosen to tag along like the lemmings that we are.

For the board transforms, we'll implement both a primitive interface and a high level interface on a layer just above that. The former we adopt from the [not yet exposed] transform primitives implemented by the python chess module, while the latter accommodates the solving engine's twinning specification. We're familiar with both from our experience in generating the twin series database found with this project's support files, and so it seems like a natural pairing.

The primitives

A rotation is effectively a pair of flips, and so we provide primitives only for shifting and flipping the board. All operations are on a single set variable.

Shifting

The shift primitives are trivial, to be sure, but we're not entirely convinced that it will always be thus. In any event, we hold a place for the shift primitives to make two points: 1) the direction filters are the real primitives, and 2) a function is implemented essentially as a macro and therefore incurs no penalty when invoked.

  • Shift up
  • function shiftUp(BB C) { up C BB }

  • Shift down
  • function shiftDown(BB C) { down C BB }

  • Shift right
  • function shiftRight(BB C) { right C BB }

  • Shift left
  • function shiftLeft(BB C) { left C BB }

Flipping

We started out hoping to keep the flip transforms simple and to the point, transforming the board square by occupied square. Then some distant relative with too little to occupy her time pointed out that we were cheating. That we had promised a library of transforms à la direction filter and had failed to deliver. So, okay, we've thrown in a few flips with direction filters.

  • Flip horizontal
  • Square by square... 
  • function flipH(BB) {
  xfm_FlippedH = []
  square xfm_SqH in BB
    xfm_FlippedH |= makesquare(8 - file xfm_SqH + 1   rank xfm_SqH)
  xfm_FlippedH
}
  • ... and by direction filter. 
  • function flipH(BB) {
  xfm_FlippedH = []
  shifthorizontal {
    xfm_RangeH = 8 - 2*file a1 + 1
    xfm_FlippedH |= right xfm_RangeH (a1-8 & BB)
  }
  xfm_FlippedH
}

  • Flip vertical
  • Square by square... 
  • function flipV(BB) {
  xfm_FlippedV = []
  square xfm_SqV in BB
    xfm_FlippedV |= makesquare(file xfm_SqV   8 - rank xfm_SqV + 1)
  xfm_FlippedV
}
  • ... and by direction filter. 
  • function flipV(BB) {
  xfm_FlippedV = []
  shiftvertical {
    xfm_RangeV = 8 - 2*rank a1 + 1
    xfm_FlippedV |= up xfm_RangeV (a-h1 & BB)
  }
  xfm_FlippedV
}

  • Flip diagonal
  • Square by square... 
  • function flipD(BB) {
  xfm_FlippedD = []
  square xfm_SqD in BB
    xfm_FlippedD |= makesquare(rank xfm_SqD   file xfm_SqD)
  xfm_FlippedD
}
  • ... and by direction filter. 
  • function flipD(BB) {
  xfm_FlippedD = []
  shiftvertical {
    xfm_RangeD = rank a1 - 1
    xfm_FlippedD |= southeast xfm_RangeD ((northeast 0 7 a1) & BB)
  }
  shifthorizontal {
    xfm_RangeD = 1 - file a1
    xfm_FlippedD |= southeast xfm_RangeD ((northeast 0 7 a1) & BB)
  }
  xfm_FlippedD
}

  • Flip anti-diagonal
  • Square by square... 
  • function flipAD(BB) {
  xfm_FlippedAD = []
  square xfm_SqAD in BB
    xfm_FlippedAD |= makesquare(8 - rank xfm_SqAD + 1   8 - file xfm_SqAD + 1)
  xfm_FlippedAD
}
  • ... and by direction filter. 
  • function flipAD(BB) {
  xfm_FlippedAD = []
  shiftvertical {
    xfm_RangeAD = 1 - rank h1
    xfm_FlippedAD |= northeast xfm_RangeAD ((northwest 0 7 h1) & BB)
  }
  shifthorizontal {
    xfm_RangeAD = 8 - file h1
    xfm_FlippedAD |= northeast xfm_RangeAD ((northwest 0 7 h1) & BB)
  }
  xfm_FlippedAD
}

The layered interface

The interface is defined in accordance with the solving engine's twinning specification (see the link at the end of this document). We also include, for each class of operation, a method for detecting that one board is an operation apart from another board.

Shifting

  • Shift Sq1 Sq2
  • The entire board is shifted in the same directions and by the same distances as determined by the two squares. Negative distances run in the opposite directions.

    Shifting pieces (bits) off the board is allowed without complaint. The pieces might not like it, but we firmly believe in the freedom to commit blunders. 

  • function Shift(BB Sq1 Sq2) {
  xfm_deltaRank = rank Sq2 - rank Sq1
  xfm_deltaFile = file Sq2 - file Sq1
  shiftUp(shiftRight(BB xfm_deltaFile) xfm_deltaRank)
}

  • isShift
  • In checking for shifted boards, we generate pairs of squares from the edges with both positive and negative slope, as well as for zero or infinite slope. That pretty much covers all possibilities2 when we effectively reverse the ordering of the pairs from the eigth rank.

    The degree of slope over which we iterate is admittedly a bit of an overkill. For twinning, most shifts are of one or two squares in a given direction. But we allow that the function might find use outside of the twinning domain. 

  • function isShift(BB1 BB2) {
  square xfm_hSq in [a-h1,a-h8]
    square xfm_vSq in [a1-8,h1-8]
      xfm_hSq != xfm_vSq and BB1 == Shift(BB2 xfm_hSq xfm_vSq)
}
  • In a twinning context it's obviously bad form to shift an occupied square all the way off the board. The order in which the function arguments are given is significant in determining whether shifted boards with dropped pieces will fail the test. If the original board is given first in the argument list, shifted boards with pieces that have fallen off the edge will fail the test. If the original board is given last, the test will succeed. Adjust accordingly.

Flipping

The solving engine twinning specification has all flip (mirror) transforms taking place along the given lines. This can be a bit confusing (and has been for many of the transcribers of twinned compositions), especially for the diagonal flips.

  • Flip Sq1 Sq2
  • Though one could allow lines to be described by any two squares, the specification sticks to the corner squares and in a particular order. We'll follow suit. 
  • function Flip(BB Sq1 Sq2) {
       if Sq1 == a1 and Sq2 == h1 then xfm_Flipped = flipH(BB)
  else if Sq1 == a1 and Sq2 == a8 then xfm_Flipped = flipV(BB)
  else if Sq1 == a1 and Sq2 == h8 then xfm_Flipped = flipAD(BB)
  else if Sq1 == a8 and Sq2 == h1 then xfm_Flipped = flipD(BB)
  xfm_Flipped
}

  • isFlip
  • More or less self-documenting... 
  • function isFlip(BB1 BB2) {
  BB1 == Flip(BB2 a1 h1) or
  BB1 == Flip(BB2 a1 a8) or
  BB1 == Flip(BB2 a1 h8) or
  BB1 == Flip(BB2 a8 h1)
}

Rotating

In the Popeye and Olive worlds, rotations are counter-clockwise. One might think that an easy concept to get one's head around, but (remarkably) we've come across scores of twinned compositions — consciously and intentionally targeting the Popeye specification — that have gotten it wrong.

Apparently, the digital timepiece has unceremoniously cancelled out clockwiseness with GenXYZ, and so we feel compelled to explain. If one were to stand at the magnetic north pole, for example, looking down on planet Earth, the planet would be revolving (slowly, unless Albert is playing games) in a counter-clockwise direction. Unless, of course, the magnetic field had recently flipped, in which case, who knows (see flipping above).

We cannot begin to overstate the grief that has been caused by this and the diagonal/anti-diagonal fiascos. All of these screwups must be corrected by hand, boys and girls. Wikis are the bane of humanity. Please try harder.

On a lighter note, we should point out that a rotation is basically realized as a pair of flips. Which flips? Well, that depends (but for the 180) on whether the rotation is clockwise or counter-clockwise. But we'll take care of the details, not to worry.

  • Rotate 90|180|270
  • To string it or not to string it, that is always the question. Strings are easier to play with than are numerics and they're much more fun to work with and we've been waiting forever to do some string stuff, and so goes our rationale for choosing the former over the latter for our Tilt parameter. (See the Examples section below for a totally gratuitous exhibition of the ~~ form of the while filter.) 
  • function Rotate(BB Tilt) {
       if  "90" in Tilt then xfm_Flipped = flipD(flipV(BB))
  else if "180" in Tilt then xfm_Flipped = flipH(flipV(BB))
  else if "270" in Tilt then xfm_Flipped = flipAD(flipV(BB))
  xfm_Flipped
}
  • Note that the order in which the flips are applied is significant for the 90 and 270.

  • isRotate
  • More or less self-documenting... 
  • function isRotate(BB1 BB2) {
  BB1 == Rotate(BB2 "90") or
  BB1 == Rotate(BB2 "180") or
  BB1 == Rotate(BB2 "270")
}

Examples

Each of the subsections below gives two examples of its respective transform. The first is a test (or exercise) of the interface and the second demonstrates the transform of an actual board representation while writing the transformed board to an EPD file. The latter borrows from the Translating FEN companion document.

Note that a suite of bitboards is required to fully represent a position that we wish to transform. We could generate that suite in any number of ways, but we have chosen to assemble the bitboards from a FEN string and carry their square designators in a dictionary. Thus, a transformed FEN string.

Shifting

  • Testing the interface
  • Though we are not testing edge cases, we do try out shifting in all directions and by a range of distances vertically and horizontally. We obviously must be careful in the selection of our test position and test ranges else we'll be shifting pieces off the board. In fact, the negative test would simply expand the ranges to deliberately shift off occupied squares.

    The test is just a little bit incestuous in that we are employing the same facilities in generating the test cases that we are attempting to verify by the test. Hence, the dump to stdout for visual inspection. 

  • cql(include libcql/libxfm.cql quiet)
initial

// Shifting a maximum of two squares in any one direction.
square all Square1 in [a-c1,a-c3] {
  message("      " [Aa])
  square all Square2 in [a1-3,c1-3] {
    if Square1 != Square2 {
      isShift([Aa] Shift([Aa] Square1 Square2))
      message(Square1 " " Square2 " " Shift([Aa] Square1 Square2))
    }
  }
}

  • Shift to EPD
  • Executing the query on a range of games in a database of non-standard starts, we shift the initial positions in all directions with extent not greater than two in any one direction. We write the shifted boards to an EPD file, alternating each shifted board with the original for easy comparison. 
  • cql(include libcql/libfen.cql include libcql/libxfm.cql quiet)
initial
fen2bb(fen)

// Shift a maximum of two squares in any one direction.
if gamenumber == 1 then persistent ID = 0
square all Square1 in [a-c1,a-c3]
  square all Square2 in [a1-3,c1-3] {
    while ("KQRBNPkqrbnp" ~~ ".")
      exportBB[\0] = Shift(importBB[\0] Square1 Square2)
    FEN = bb2fen()
    ID += 1
    writefile("/tmp/out.cqo"
      str(fen ~~ "^[^ ]+ [bw] " "- - c0 "
          \" "original position" \" "; id " \" ID \" \n))
    ID += 1
    writefile("/tmp/out.cqo"
      str(FEN + fen ~~ " [bw] " "- - c0 "
          \" "shift " Square1 " " Square2 \" "; id " \" ID \" \n))
  }

Flipping

  • Testing the interface
  • Okay, so it's more like an exercise of the interface. But everything looks to be in order. 
  • cql(include libcql/libxfm.cql quiet)
initial

// Check for all four flips.
message("      " [Aa])
while ("a1h1 a1a8 a1h8 a8h1" ~~ "([a-h][1-8])([a-h][1-8])") {
  Sq1 = makesquare \1  Sq2 = makesquare \2
  message(\1 " " \2 " "
      Flip([Aa] Sq1 Sq2) " " isFlip([Aa] Flip([Aa] Sq1 Sq2)))
}

  • Flip to EPD
  • Executing the query on a range of games in a database of non-standard starts, we flip the initial positions along all bisectors. We write the flipped boards to an EPD file, alternating each flipped board with the original for easy comparison. 
  • cql(include libcql/libfen.cql include libcql/libxfm.cql quiet)
initial
fen2bb(fen)

// Check for all four flips.
if gamenumber == 1 then persistent ID = 0
while ("a1h1 a1a8 a1h8 a8h1" ~~ "([a-h][1-8])([a-h][1-8])") {
  Square1 = makesquare \1  Square2 = makesquare \2
  while ("KQRBNPkqrbnp" ~~ ".")
    exportBB[\0] = Flip(importBB[\0] Square1 Square2)
  FEN = bb2fen()
  ID += 1
  writefile("/tmp/out.cqo"
    str(fen ~~ "^[^ ]+ [bw] " "- - c0 "
        \" "original position" \" "; id " \" ID \" \n))
  ID += 1
  writefile("/tmp/out.cqo"
    str(FEN + fen ~~ " [bw] " "- - c0 "
        \" "flip " Square1 " " Square2 \" "; id " \" ID \" \n))
}

Rotating

  • Testing the interface
  • Once the flip primitives have been verified, there's really not much to test. But we like to be thorough... 
  • cql(include libcql/libxfm.cql quiet)
initial

// Check for all three rotations.
message("    " [Aa])
while (" 90|180|270"~~"[^\|]+")
  message(\0 " " Rotate([Aa] \0) " " isRotate([Aa] Rotate([Aa] \0)))

  • Rotate to EPD
  • Executing the query on a range of games in a database of non-standard starts, we rotate the initial positions iterating over 90 degree increments. We write the flipped boards to an EPD file, alternating each flipped board with the original for easy comparison. 
  • cql(include libcql/libfen.cql include libcql/libxfm.cql quiet)
initial
fen2bb(fen)

// Check for all three rotations.
if gamenumber == 1 then persistent ID = 0
while (" 90|180|270"~~"[^\|]+") {
  Arg = \0
  while ("KQRBNPkqrbnp" ~~ ".")
    exportBB[\0] = Rotate(importBB[\0] Arg)
  FEN = bb2fen()
  ID += 1
  writefile("/tmp/out.cqo"
    str(fen ~~ "^[^ ]+ [bw] " "- - c0 "
        \" "original position" \" "; id " \" ID \" \n))
  ID += 1
  writefile("/tmp/out.cqo"
    str(FEN + fen ~~ " [bw] " "- - c0 "
        \" "rotate " Arg \" "; id " \" ID \" \n))
}

See also

Credits

This document is Copyright (c) 2019-2022 Lionel Hampton. The Chess Query Language was originally developed by Gady Costeff and Lewis Stiller. The upstream Scid vs PC project is managed by Steven Atkinson.

Footnotes

1 We use the terms flip, mirror, reflect interchangeably.

2 We failed combinatorial analysis, so who knows, really. We believe we have come close to the mark, though.

Content