Wednesday, April 20, 2011

Patterns in Chess Square Enumerations

In my bit manipulation post awhile back I posed a problem involving "closed form" calculation of chess endgame table indices. Back when I originally solved the problem, it was a big help to create some visualizations of some of the patterns embedded in the square numbering scheme. I had mentioned that I thought the patterns were interesting, so I thought I'd come back and elaborate on that statement.

One way of visualizing some of the patterns involved is to partition the squares according to the equivalence classes defined by the binary bits of the index. Bits 0-2 are the three low-order bits and bits 3-5 are the three high-order bits. Here are the equivalence classes defined by each of the bits of the natural square numbering.

Bit 0

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 3

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 1

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 4

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 2

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Bit 5

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Here we can clearly see the natural row and column oriented behavior of the index. Nothing earth shattering. If we take octal digits instead of binary digits to define our equivalence class, we get the following more colorful partition.

Low Digit

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

High Digit

7071727374757677
6061626364656667
5051525354555657
4041424344454647
3031323334353637
2021222324252627
1011121314151617
0001020304050607

Now on to the interesting stuff. Here are the same six equivalence classes of the less obvious square numbering for which I posed my puzzle.

Bit 0

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 3

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 1

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 4

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 2

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Bit 5

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

And for the octal digits...

Low Digit

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

High Digit

6404142426160666
0565344446366707
1535745456763717
2545557577574727
2141517173534323
1131705052723313
0161304042326303
6000102022120262

Ahhhhhh....I don't know about you, but I think that's a beautiful square numbering. There's also plenty of group theory going on. What do you see here?

The Haskell code used to generate these tables is here.

No comments: