Re: Reflections on BitBoards

In article <b3d29$47cf3be6$5350c6a6$27094@xxxxxxxxxxxxxxxxxxxxxxx>, root@xxxxxxxxxxxxxxxxxxx says...
On Thu, 06 Mar 2008 12:02:33 +1300, Mike wrote:

I am using 64 bit integers to describe the 'state' of each square in an
8x8 board, and need to determine if two boards are equal, i.e. have the
same state for each square. But the boards are also considered equal if
one is the rotation or reflection of the other. I have to do many
billions of such comparisons (and must do this in real time) so need
fast board reflection or rotation algorithms. The seven possible
alternate symmetry states can be cycled through, for example, by
applying H,V,H,D,H,V,H to some board B, where H,V, and D are horizontal,
vertical, and diagonal reflections.

I have fast horizontal plane and vertical plane reflection algorithms,
(in Pascal-like poseudo-code) for example:

The first thing that comes to mind is: *why* do you want to do this ?
(The most common usage for bitboards (chess, Lines Of Action) does not
*need* mirroring)

OK - this is not chess (but a different game played on an 8x8 grid), and I need to do this to reduce some thousands of
millions of 'positions' to merely hundreds of millions for further processing. Symmetry positions are, in effect,
identical in this game, and I don't want to process each one more than once.

One way to solve it would be to treat it as a matrix-multiplication:
use
((value) & 0xff)
((value >> 8) & 0xff)
...
((value >> 56) & 0xff)
as an index into a precomputed array of the needed values,
I will look at this. At the moment the diagonal mirror requires 15 ands, 14 ors, and 14 shifts. A lookup could do it in
8 ands 8 ors (or 4 of each if I use 16 bits, 'cos I could afford 8x64K of LUT) plus the cost of extracting the values
from the LUT.

and add these up, or "or" them. You can have different lookuptables for
the different transformations. (Hint: don't rotate. Rotations can be
composed of two mirror-ops, which are cheaper.)
Not clear to me that rotations are necessarily more expensive, as any symmetry operation on the bitboard is equivalent
to a bit-permutation. If there is a 'short-cut' for rotation it could be possibly be cheaper...and as far as I can see,
your LUT method, for example, would be equally fast for _any_ bit-permutation so is just as good for a rotation as for
a reflection.

[The matrix-mult for bitstrings was mentioned by Knuth in his forthcoming
part of TAOCP. He even suggested to extend MIX, IIRC]

Another idea is to treat it as a matrix, and use a Morton-like adressing
scheme for the bit<-->location mapping, which could simplify the
transformations. YMMV.
Any reference to 'Morton-like' addressing?

Thanks
Mike
.

Relevant Pages

  • Re: Symmetry of "Improper Rotations"
    ... Of course it's a mirror image of what you started with. ... Rotation of a plane ... symmetry - i.e., reflective rotational symmetry. ... symmetry, and _no_ reflection symmetry. ...
    (talk.origins)
  • Re: Granite, Symmetry, and ID - Summary
    ... Of course it's a mirror image of what you started with. ... Rotation of a plane ... symmetry - i.e., reflective rotational symmetry. ... symmetry, and _no_ reflection symmetry. ...
    (talk.origins)
  • Re: isometries in E^3-
    ... Orientation preserving isometry in E^3 with unique fixed ... >>identity, reflection, rotation, translation, glide reflection (i.e. ... >>identity, plane reflection, rotation ...
    (sci.math)
  • Symmetry of "Improper Rotations"
    ... you have your octahedron via reflection and rotation. ... both sides of a plane (i.e., both of the pyramids have exactly the ... "Just as two rotational symmetry elements can be combined to ...
    (talk.origins)
  • Re: homomorphism from D6 to S5 or A5
    ... Dn is the group of all rigid symmetries of this n-gon. ... The element r corresponds to a rotation in the positive direction by ... The element s corresponds to the reflection about the ...
    (sci.math)