Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: SSE2 bit[64] * byte[64] dot product

Author: Russell Reagan

Date: 02:05:21 07/20/04

Go up one level in this thread


On July 20, 2004 at 04:03:26, Tony Werten wrote:

>Not sure. My problem was the combination of the several different rotated
>bitboards, not the rotated boards itselves.
>
>Rotated bitboards are "normalised" to normal bitboards ie You put in a
>rotated45_piece BB and get out a normal attack BB. To do my lookup stuff I
>needed something like pieces_rotated45 in, attacks_rotated90 out and then do an
>efficient lookup.
>
>With Gerds method, it takes more than the table lookup, but it doesn't need the
>(way to expensive) rotation conversion.
>
>But maybe there are more ways.

I think so. You can generate rotated attacks if you switch the lookup tables and
rotate the square. Here is an example. Let's say you normally generate rank and
file attacks like this.

Bitboard RankAttacks (int square)
{
    return rank_attacks[square][(rotated0 >> (square & 56)) & 255];
}

Bitboard FileAttacks (int square)
{
    return file_attacks[square][(rotated90 >> (square & 56)) & 255];
}

You could generate rotated attacks like this.

Bitboard RankAttacksRotated90 (int square)
{
    square = rotate90[square];
    return file_attacks[square][(rotated0 >> (square & 56)) & 255];
}

Bitboard FileAttacksRotated90 (int square)
{
    square = rotate90[square];
    return rank_attacks[square][(rotated90 >> (square & 56)) & 255];
}

I assume you could do the same with the diagonals as well.

Tim Foden showed me another method of generating attacks that allows you to use
very small lookup tables (compared to normal rotated bitboards) which might work
better in this case. The basic idea is that you take the state of any rank,
file, or diagonal, and you put it into a single lookup table to get the attacks.
Then you extend those attacks and mask off the ones you are interested in.
Something like this.

Rook on e4, with various other pieces
--------
--------
----X---
--------
-X--X-X-
----X---
--------
--------

Mask out rank state
-X--X-X-

Put into attack table (array[8][256] = 2KB)
-XXX-XX-

Extend upward (lookup table, array[256] = 2KB)
-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-

Mask out the desired rank
--------
--------
--------
--------
-XXX-XX-
--------
--------
--------

If you wanted file attacks instead, you just extend horizontally (using the same
pattern, -XXX-XX-).

--------
XXXXXXXX
XXXXXXXX
--------
XXXXXXXX
XXXXXXXX
XXXXXXXX
--------

And mask out the desired file.

--------
----X---
----X---
--------
----X---
----X---
----X---
--------

It works for diagonals too. Take this.

-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-
-XXX-XX-

And mask it with this.

-------X
------X-
-----X--
----X---
---X----
--X-----
-X------
X-------

And you get attacks. So you can basically take any rank, file, or diagonal
state, extend in the appropriate direction and mask correctly, and you get
rotated attacks. If I need to explain anything in more detail, just let me know
and I will (after I get some sleep) :-)



This page took 0 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.