This post is a bit different from my usual content. It's not about Haskell or functional programming, and not strictly about software. But I think it's a nice little brain teaser that may be of interest. Some may view it as too much tedium (congruent to 3 or 4 mod 5 in Knuth's scoring system), but I found the multitude of beautiful patterns in this problem interesting enough that I didn't notice the tedium.

Consider a chessboard with squares numbered as follows (in octal):

8| 70 71 72 73 74 75 76 77 7| 60 61 62 63 64 65 66 67 6| 50 51 52 53 54 55 56 57 5| 40 41 42 43 44 45 46 47 4| 30 31 32 33 34 35 36 37 3| 20 21 22 23 24 25 26 27 2| 10 11 12 13 14 15 16 17 1| 00 01 02 03 04 05 06 07 a b c d e f g h

This is a natural 0-63 (decimal) numbering where the 3 high bits (first octal digit) of the position index indicate the row and the 3 low bits (second octal digit) indicate the column. This isn't the only way the chessboard can be enumerated. Consider the following numbering scheme (also in octal):

8| 64 04 14 24 26 16 06 66 7| 05 65 34 44 46 36 67 07 6| 15 35 74 54 56 76 37 17 5| 25 45 55 75 77 57 47 27 4| 21 41 51 71 73 53 43 23 3| 11 31 70 50 52 72 33 13 2| 01 61 30 40 42 32 63 03 1| 60 00 10 20 22 12 02 62 a b c d e f g h

You might want to take a moment to analyze the patterns in this numbering. They're very interesting.

The bottom line is that the location of a piece can be described using 6 bits and some known numbering system. Therefore, all possible locations of one piece are equivalent to all 6 bit numbers. All possible arrangements of two pieces can be enumerated with a 12 bit number, 6 bits for the location of each piece. (Note that this representation includes positions where two pieces are on the same square, but we won't worry about that for the purpose of this problem.) And of course this can be extended to more pieces very easily. But instead of just storing 6 bits of one piece and then 6 bits of the other, it's useful to put the 3 high bits of each piece together and the 3 low bits together.

To illustrate, let's assume that our piece list is an array {rook, king} and their positions are another array {052, 046} (octal. I'll use the C notation of starting with a leading zero to denote octal from now on.).

Our index for this position will be the 12 bit number 04562. To make it very clear, the ordering here is: piece 1 high bits, piece 0 high bits, piece 1 low bits, piece 0 low bits. The nice thing about having this index all in one number is that you can do operations on all the piece positions at the same time rather than looping through an array handling each piece location individually.

It is useful to be able to flip the board in different directions. When there are no pawns, there are 3 ways to flip the board that do not change the meaning of the position. You can flip around the horizontal, vertical, and diagonal axes. If you are using the first square numbering, you can flip a single piece position around the horizontal axis by calculating highBits XOR 7. You can flip around the vertical axis by calculating lowBits XOR 7. And you can flip around the diagonal axis by swapping the high bits and low bits. But that's for a single piece. For an n-piece endgame position index with the high and low bits together as described above, the following C code will do it.

const uint numBits = 3*numPieces; const u64 lowBits = ((1ULL << numBits)-1); const u64 highBits = lowBits << numBits; // Flip around horizontal axis flippedIndex = index ^ lowBits; // Flip around vertical axis flippedIndex = index ^ highBits; // Flip around diagonal axis flippedIndex = ((index&highBits) >> numBits) | ((index&lowBits) << numBits);

Again, this code works for the first square numbering. The puzzle is to write code that does these flips for the second square numbering. Now the easy way would be to create three tables of 64 values each that you can use to look up the flipped squares. But in order to use that, you'd have to loop through each piece, extract the piece's location from the index, lookup that square in the table, and store the flipped square into the correct bits of the new index. Looping through the pieces is slow. How can you do it without having to loop through the pieces?

## 11 comments:

You don't need to keep the low and high bits together to be able to flip around the diagonal... you can do something like

x ^= ((x ^ (x>>3))&0707070707)*011;

Basically, as long as the sets of bits you want to swap are the same distance from eachother, you can do it with two xors. It's basically

t = a ^ b;

a ^= t;

b ^= t;

except in parallel.

The reason the low and high bits are kept together is not related to the problem of flipping the board. That index organization was chosen for reasons outside the scope of the problem as I've described it here. I just figured I'd keep the index organization the same.

That said, I'm familiar with the xor method of swapping and I like your application of it here.

For a single element:

To flip along the horizontal axis: \(hi,lo) -> (hi, lo `xor` 4)

To flip along the vertical axis: \(hi, lo) -> (hi, lo `xor` 2)

To flip along the diagonal: \(hi, lo) -> (hi , lo `xor` 6)

You are correct for horizontal and vertical, but not for diagonal. Your transformation achieves a 180 rotation of the board, not a flip around the diagonal axis. For clarification, I'm looking for a flip around the a1-h8 diagonal. This transformation should transform 6 into 7.

Right, I realized that as I was heading to bed. There's surely an easier way, but one correct answer for the diagonal is:

diag (hi,lo) = (hi, lo')

where

lo' = if (hi .|. 1) == 7

then if lo .&. 2 == shiftR (lo .&. 4) 1

then lo

else compl 6 lo .|. lo .&. 1

else shiftR (lo .&. 4) 1 .|. shiftL (lo .&. 2) 1 .|. compl 1 lo

compl mask = \x -> (x .&. mask) `xor` mask

Oh, of course:

diag (hi,lo) = (hi, shiftR (lo .&. 4) 1 .|. shiftL (lo .&. 2) 1 .|. (if hi > 5 then id else (`xor` 1)) (lo .&. 1))

Though I'm sure there's a better trick for swapping the bits

Your last two solutions work for a single element, but they don't fulfill my criteria of working with an index of several piece locations packed together like I describe without looping. Since you use conditionals, your solutions require looping through each individual piece in the index.

For a single element with the conditionals eliminated:

diag (hi,lo) = (hi, lo')

where lo' = (lo .&. 1 .|. swap lo 1 2) `xor` mul hi 1 2 `xor` 1

mul x i j = shiftR x i .&. shiftR x j .&. 1

swap x i j = shift (x .&. bit i) (j-i) .|. shift (x .&. bit j) (i-j)

I wonder if it'd be possible to extend for n elements

withoutobfuscating the lo' definition much. Some monadic or typeclass magic maybe?And a prettier version:

diag (hi, lo) = (hi, lo')

where lo' = swap lo 1 2 `xor` mul hi 1 2 `xor` 1

mul x i j = shiftR x i .&. shiftR x j .&. 1

swap x i j = x `xor` (x' .|. shift x' (i-j))

where x' = (shift x (j-i) `xor` x) .&. bit j

Nice. Now for the extension to n elements... :)

An easy and ugly way is to redefine the bit function:

church 0 f x = x

church n f x = church (n-1) f (f x)

pieceBits = 3

numPieces = 1

diag (hi,lo) = (hi, lo')

where lo' = swap lo 1 2 `xor` mul hi 1 2 `xor` bit 0

bit x = church numPieces (\a -> shiftL a pieceBits .|. shiftL 1 x) 0

mul x i j = shiftR x i .&. shiftR x j .&. bit 0

swap x i j = x `xor` (x' .|. shift x' (i - j))

where x' = (shift x (j - i) `xor` x) .&. bit j

I see a couple choices about where to define the bit function but they all have drawbacks.

btw, the lowBits and hightBits seem the other way around in this c example above:

// Flip around horizontal axis

flippedIndex = index ^ lowBits

Post a Comment