Author: James Swafford
Date: 05:12:39 06/01/02
Go up one level in this thread
On June 01, 2002 at 00:13:11, Dann Corbit wrote:
>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?
I think you've got it. The union is pretty clever, avoiding some mask/shift
operations.
I'm curious, though - what do you need to rotate that you're not doing
incrementally in make()? Updating a rotated board incrementally takes
two table indexes and an xor. If you're not updating incrementally,
I'm guessing you're not using that bitboard in your move generator, so
what's up? :)
Interesting.
--
James
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.