Author: Dann Corbit
Date: 21:13:11 05/31/02
Go up one level in this thread
On June 01, 2002 at 00:06:14, Dann Corbit wrote:
>I have already asked on a few USENET forums, but maybe CCC has already solved it
>optimally.
>
>Bitboard time.... Now, we can have the bits be represented normally (rotated by
>zero degrees), or rotated 90, 270, 45, or 315 degrees. Here are some C arrays
>that hold such representations:
>
>typedef enum {
> a8, b8, c8, d8, e8, f8, g8, h8,
> a7, b7, c7, d7, e7, f7, g7, h7,
> a6, b6, c6, d6, e6, f6, g6, h6,
> a5, b5, c5, d5, e5, f5, g5, h5,
> a4, b4, c4, d4, e4, f4, g4, h4,
> a3, b3, c3, d3, e3, f3, g3, h3,
> a2, b2, c2, d2, e2, f2, g2, h2,
> a1, b1, c1, d1, e1, f1, g1, h1
>} board_bit;
>
>board_bit rot0[64] = {
> a8, b8, c8, d8, e8, f8, g8, h8,
> a7, b7, c7, d7, e7, f7, g7, h7,
> a6, b6, c6, d6, e6, f6, g6, h6,
> a5, b5, c5, d5, e5, f5, g5, h5,
> a4, b4, c4, d4, e4, f4, g4, h4,
> a3, b3, c3, d3, e3, f3, g3, h3,
> a2, b2, c2, d2, e2, f2, g2, h2,
> a1, b1, c1, d1, e1, f1, g1, h1
>};
>
>board_bit rot90[64] = {
> h8, h7, h6, h5, h4, h3, h2, h1,
> g8, g7, g6, g5, g4, g3, g2, g1,
> f8, f7, f6, f5, f4, f3, f2, f1,
> e8, e7, e6, e5, e4, e3, e2, e1,
> d8, d7, d6, d5, d4, d3, d2, d1,
> c8, c7, c6, c5, c4, c3, c2, c1,
> b8, b7, b6, b5, b4, b3, b2, b1,
> a8, a7, a6, a5, a4, a3, a2, a1,
>};
>
>board_bit rot270[64] = {
> a1, a2, a3, a4, a5, a6, a7, a8,
> b1, b2, b3, b4, b5, b6, b7, b8,
> c1, c2, c3, c4, c5, c6, c7, c8,
> d1, d2, d3, d4, d5, d6, d7, d8,
> e1, e2, e3, e4, e5, e6, e7, e8,
> f1, f2, f3, f4, f5, f6, f7, f8,
> g1, g2, g3, g4, g5, g6, g7, g8,
> h1, h2, h3, h4, h5, h6, h7, h8
>};
>
>board_bit rot45[64] = {
> a8,
> a7, b8,
> a6, b7, c8,
> a5, b6, c7, d8,
> a4, b5, c6, d7, e8,
> a3, b4, c5, d6, e7, f8,
> a2, b3, c4, d5, e6, f7, g8,
> a1, b2, c3, d4, e5, f6, g7, h8,
> b1, c2, d3, e4, f5, g6, h7,
> c1, d2, e3, f4, g5, h6,
> d1, e2, f3, g4, h5,
> e1, f2, g3, h4,
> f1, g2, h3,
> g1, h2,
> h1
>};
>
>board_bit rot315[64] = {
> h8,
> g8, h7,
> f8, g7, h6,
> e8, f7, g6, h5,
> d8, e7, f6, g5, h4,
> c8, d7, e6, f5, g4, h3,
> b8, c7, d6, e5, f4, g3, h2,
> a8, b7, c6, d5, e4, f3, g2, h1,
> a7, b6, c5, d4, e3, f2, g1,
> a6, b5, c4, d3, e2, f1,
> a5, b4, c3, d2, e1,
> a4, b3, c2, d1,
> a3, b2, c1,
> a2, b1,
> a1
>};
>
>Now, my question is:
>
>What is the fastest way to transform a 64 bit integer in the format rot0 into
>the other formats and back? Iteration over all 64 bits is agonizingly painful.
>Since all of these are fairly simple permutations, it seems that there ought to
>be a very rapid way to do it.
Notion:
Arrays of 256x8 bitboards, where 256 is the number of possible states for a
byte, and 8 is the number of bytes in our source bitboard.
Now, what I am thinking is that for each of the 256 bitboards, we have an OR
mask for rows 0 to 8.
We could make one to transform from any rotation back to any rotation.
Just rotate over the 8 unsigned characters in a union with a 64 bit bitboard.
For each byte, the contents of the byte are an index into the array of bitmaps
with the appropriate OR mask. So in 8 OR operations, we can transform any
bitmap into any other sort (after we have set up the initial tables).
Notions?
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.