Simplest bitboard attack generation

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
rreagan
Posts: 102
Joined: Sun Sep 09, 2007 4:32 am

Simplest bitboard attack generation

Post by rreagan » Thu Oct 03, 2013 9:52 pm

What's the simplest attack generation you've seen with bitboards? By simple, let's say it's the smallest code that works, something anyone could copy and use to start playing with bitboards. Speed is not important, this is mainly for initializing other things and sanity tests to make sure your magics are working, and so on.

Here is what I came up with. It uses a general shift function, so you can shift by negative numbers. src is the attacker square, occ is all occupied squares, dir is the attacking direction, and n is the number of iterations. So for king/knight n=1, bishop/rook/queen n=7, two-square pawn push n=2. Can it be simplified?

Code: Select all

uint64 attacks (uint64 src, uint64 occ, int dir, size_t n = 7)
{
    uint64 a = uint64(0);
    uint64 keep = map_lookup(table, dir, all_squares);
    for &#40;int i = 0; i < n; i++) &#123;
        src = shift&#40;src, dir&#41;;
        src &= keep;
        a |= src;
        if &#40;src & occ&#41;
            break;
    &#125;
    return a;
&#125;
Here's the full code in case any details are not obvious. You'll have to do -std=c++11.

Code: Select all

#include <iostream>
#include <string>
#include <map>

typedef unsigned long long uint64;

template <typename MAP_T, typename SEARCH_T, typename RETURN_T>
RETURN_T map_lookup &#40;MAP_T the_map, SEARCH_T find_me, RETURN_T default_val&#41; &#123;
    auto found = the_map.find&#40; find_me );
    if ( found != the_map.end&#40;) )
        return found->second;
    return default_val;
&#125;

uint64 mask &#40;int i&#41; &#123; return uint64&#40;1&#41; << i; &#125;

std&#58;&#58;string bbstr ( uint64 bits, uint64 bits2 = uint64&#40;0&#41; )
&#123;
    std&#58;&#58;string s;
    for &#40;int y = 7; y >= 0; --y&#41;
    &#123;
        for &#40;int x = 0; x <= 7; ++x&#41;
        &#123;
            int square = &#40;y * 8&#41; + x;
            if ( bits & mask&#40;square&#41; )
                s += '#';
            else if &#40;bits2 & mask&#40;square&#41;)
                s += 'X';
            else
                s += '.';
        &#125;
        s += '\n';
    &#125;
    return s;
&#125;

uint64 shift &#40;uint64 b, int n&#41; &#123;
    return &#40;n > 0&#41; ? &#40;b << n&#41; &#58; &#40;b >> -n&#41;;
&#125;

uint64 file_a = 0x0101010101010101;
uint64 file_b = 0x0202020202020202;
uint64 file_g = 0x4040404040404040;
uint64 file_h = 0x8080808080808080;
uint64 all_squares = 0xffffffffffffffff;

std&#58;&#58;map< int, uint64 > table = &#123;
    &#123;  17, ~file_a            &#125;,
    &#123;  15, ~file_h            &#125;,
    &#123;  10, ~&#40;file_a | file_b&#41; &#125;,
    &#123;   9, ~file_a            &#125;,
    &#123;   7, ~file_h            &#125;,
    &#123;   6, ~&#40;file_g | file_h&#41; &#125;,
    &#123;   1, ~file_a            &#125;,
    &#123;  -1, ~file_h            &#125;,
    &#123;  -6, ~&#40;file_a | file_b&#41; &#125;,
    &#123;  -7, ~file_a            &#125;,
    &#123;  -9, ~file_h            &#125;,
    &#123; -10, ~&#40;file_g | file_h&#41; &#125;,
    &#123; -15, ~file_a            &#125;,
    &#123; -17, ~file_h            &#125;,
&#125;;

uint64 attacks &#40;uint64 src, uint64 occ, int dir, size_t n = 7&#41;
&#123;
    uint64 a = uint64&#40;0&#41;;
    uint64 keep = map_lookup&#40;table, dir, all_squares&#41;;
    for &#40;int i = 0; i < n; i++) &#123;
        src = shift&#40;src, dir&#41;;
        src &= keep;
        a |= src;
        if &#40;src & occ&#41;
            break;
    &#125;
    return a;
&#125;

uint64 bishop_attacks &#40;uint64 src, uint64 occ&#41; &#123;
    uint64 a = uint64&#40;0&#41;;
    for &#40;int dir &#58; &#123;-9, -7, 7, 9&#125;)
        a |= attacks&#40;src,occ,dir,7&#41;;
    return a;
&#125;

int main &#40;int argc, char * argv&#91;&#93;) &#123;
    // 28=e5, 9=b2, etc.
    uint64 src = mask&#40;28&#41;;
    uint64 occupied = src | mask&#40;9&#41; | mask &#40;14&#41; | mask&#40;54&#41; | mask&#40;49&#41;;

    std&#58;&#58;cout << "OCCUPIED\n";
    std&#58;&#58;cout << bbstr&#40;occupied&#41; << std&#58;&#58;endl;

    std&#58;&#58;cout << "ATTACKS\n";
    uint64 a = bishop_attacks&#40;src,occupied&#41;;
    std&#58;&#58;cout << bbstr&#40;a,src&#41; << std&#58;&#58;endl;

    return 0;
&#125;
And the output.

Code: Select all

OCCUPIED
........
.#....#.
........
........
....#...
........
.#....#.
........

ATTACKS
........
.#.....#
..#...#.
...#.#..
....X...
...#.#..
..#...#.
.#......

bob
Posts: 20914
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Simplest bitboard attack generation

Post by bob » Fri Oct 04, 2013 4:53 am

rreagan wrote:What's the simplest attack generation you've seen with bitboards? By simple, let's say it's the smallest code that works, something anyone could copy and use to start playing with bitboards. Speed is not important, this is mainly for initializing other things and sanity tests to make sure your magics are working, and so on.

Here is what I came up with. It uses a general shift function, so you can shift by negative numbers. src is the attacker square, occ is all occupied squares, dir is the attacking direction, and n is the number of iterations. So for king/knight n=1, bishop/rook/queen n=7, two-square pawn push n=2. Can it be simplified?

Code: Select all

uint64 attacks &#40;uint64 src, uint64 occ, int dir, size_t n = 7&#41;
&#123;
    uint64 a = uint64&#40;0&#41;;
    uint64 keep = map_lookup&#40;table, dir, all_squares&#41;;
    for &#40;int i = 0; i < n; i++) &#123;
        src = shift&#40;src, dir&#41;;
        src &= keep;
        a |= src;
        if &#40;src & occ&#41;
            break;
    &#125;
    return a;
&#125;
Here's the full code in case any details are not obvious. You'll have to do -std=c++11.

Code: Select all

#include <iostream>
#include <string>
#include <map>

typedef unsigned long long uint64;

template <typename MAP_T, typename SEARCH_T, typename RETURN_T>
RETURN_T map_lookup &#40;MAP_T the_map, SEARCH_T find_me, RETURN_T default_val&#41; &#123;
    auto found = the_map.find&#40; find_me );
    if ( found != the_map.end&#40;) )
        return found->second;
    return default_val;
&#125;

uint64 mask &#40;int i&#41; &#123; return uint64&#40;1&#41; << i; &#125;

std&#58;&#58;string bbstr ( uint64 bits, uint64 bits2 = uint64&#40;0&#41; )
&#123;
    std&#58;&#58;string s;
    for &#40;int y = 7; y >= 0; --y&#41;
    &#123;
        for &#40;int x = 0; x <= 7; ++x&#41;
        &#123;
            int square = &#40;y * 8&#41; + x;
            if ( bits & mask&#40;square&#41; )
                s += '#';
            else if &#40;bits2 & mask&#40;square&#41;)
                s += 'X';
            else
                s += '.';
        &#125;
        s += '\n';
    &#125;
    return s;
&#125;

uint64 shift &#40;uint64 b, int n&#41; &#123;
    return &#40;n > 0&#41; ? &#40;b << n&#41; &#58; &#40;b >> -n&#41;;
&#125;

uint64 file_a = 0x0101010101010101;
uint64 file_b = 0x0202020202020202;
uint64 file_g = 0x4040404040404040;
uint64 file_h = 0x8080808080808080;
uint64 all_squares = 0xffffffffffffffff;

std&#58;&#58;map< int, uint64 > table = &#123;
    &#123;  17, ~file_a            &#125;,
    &#123;  15, ~file_h            &#125;,
    &#123;  10, ~&#40;file_a | file_b&#41; &#125;,
    &#123;   9, ~file_a            &#125;,
    &#123;   7, ~file_h            &#125;,
    &#123;   6, ~&#40;file_g | file_h&#41; &#125;,
    &#123;   1, ~file_a            &#125;,
    &#123;  -1, ~file_h            &#125;,
    &#123;  -6, ~&#40;file_a | file_b&#41; &#125;,
    &#123;  -7, ~file_a            &#125;,
    &#123;  -9, ~file_h            &#125;,
    &#123; -10, ~&#40;file_g | file_h&#41; &#125;,
    &#123; -15, ~file_a            &#125;,
    &#123; -17, ~file_h            &#125;,
&#125;;

uint64 attacks &#40;uint64 src, uint64 occ, int dir, size_t n = 7&#41;
&#123;
    uint64 a = uint64&#40;0&#41;;
    uint64 keep = map_lookup&#40;table, dir, all_squares&#41;;
    for &#40;int i = 0; i < n; i++) &#123;
        src = shift&#40;src, dir&#41;;
        src &= keep;
        a |= src;
        if &#40;src & occ&#41;
            break;
    &#125;
    return a;
&#125;

uint64 bishop_attacks &#40;uint64 src, uint64 occ&#41; &#123;
    uint64 a = uint64&#40;0&#41;;
    for &#40;int dir &#58; &#123;-9, -7, 7, 9&#125;)
        a |= attacks&#40;src,occ,dir,7&#41;;
    return a;
&#125;

int main &#40;int argc, char * argv&#91;&#93;) &#123;
    // 28=e5, 9=b2, etc.
    uint64 src = mask&#40;28&#41;;
    uint64 occupied = src | mask&#40;9&#41; | mask &#40;14&#41; | mask&#40;54&#41; | mask&#40;49&#41;;

    std&#58;&#58;cout << "OCCUPIED\n";
    std&#58;&#58;cout << bbstr&#40;occupied&#41; << std&#58;&#58;endl;

    std&#58;&#58;cout << "ATTACKS\n";
    uint64 a = bishop_attacks&#40;src,occupied&#41;;
    std&#58;&#58;cout << bbstr&#40;a,src&#41; << std&#58;&#58;endl;

    return 0;
&#125;
And the output.

Code: Select all

OCCUPIED
........
.#....#.
........
........
....#...
........
.#....#.
........

ATTACKS
........
.#.....#
..#...#.
...#.#..
....X...
...#.#..
..#...#.
.#......
The hardest part is the attacks. I did a version of Crafty for the Nintendo DS several years back, a processor very limited in memory where rotated bit boards were no good.

Here's a simple C macro approach that produces correct attack bitmaps, maybe 10% slower than rotated which is not that bad, and they require no huge arrays:

# define AttacksBishop(square, occ) \
(plus7dir[square] ^ plus7dir[LSB(plus7dir[square] & (occ))] | \
plus9dir[square] ^ plus9dir[LSB(plus9dir[square] & (occ))] | \
minus7dir[square] ^ minus7dir[MSB(minus7dir[square] & (occ))] | \
minus9dir[square] ^ minus9dir[MSB(minus9dir[square] & (occ))])
# define AttacksRook(square, occ) \
(plus1dir[square] ^ plus1dir[LSB(plus1dir[square] & (occ))] | \
plus8dir[square] ^ plus8dir[LSB(plus8dir[square] & (occ))] | \
minus1dir[square] ^ minus1dir[MSB(minus1dir[square] & (occ))] | \
minus8dir[square] ^ minus8dir[MSB(minus8dir[square] & (occ))])

A simple explanation. I generated each sliding piece in 4 parts. You can probably figure out what "plus7dir[square] contains. All the bits from square to the end of that diagonal/ray. If you AND that with occupied squares you end up with 1's on the "blocker squares" down that ray. Find the closest one, and then the final attack for that ray is "xxxxdir[square] xor ssssdir[blocking square]". Repeat for the other 3 rays and you are done. Small arrays, easy to do. For knights it is trivial of course, ditto for kings. Pawns require a bit of thought to prevent pawns wrapping from an edge file to the other edge when capturing.

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Simplest bitboard attack generation

Post by Gerd Isenberg » Sat Oct 05, 2013 6:01 pm

Occluded fill and trailing shift allows a simpler loop.

bob
Posts: 20914
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Simplest bitboard attack generation

Post by bob » Sat Oct 05, 2013 7:54 pm

If you use the macros I posted, which directly compute sliding piece attacks, here's an estimated cost of using that approach rather than either magic or rotated attack generation:


time=22.19 n=117008633 afhm=1.19 predicted=0 50move=0 nps=5.3M
time=27.94 n=117008633 afhm=1.19 predicted=0 50move=0 nps=4.2M

Actual cost is about 20%, not the 10% I had guessed. But it is highly simple, if that is what you want.

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Simplest bitboard attack generation

Post by Gerd Isenberg » Sat Oct 05, 2013 8:33 pm

bob wrote:If you use the macros I posted, which directly compute sliding piece attacks, here's an estimated cost of using that approach rather than either magic or rotated attack generation:


time=22.19 n=117008633 afhm=1.19 predicted=0 50move=0 nps=5.3M
time=27.94 n=117008633 afhm=1.19 predicted=0 50move=0 nps=4.2M

Actual cost is about 20%, not the 10% I had guessed. But it is highly simple, if that is what you want.
Do you use them to initialize magics? For that purpose you like something with almost no lookup at all.

Also, your LSB and MSB need to deal with empty sets ...

Rein Halbersma
Posts: 688
Joined: Tue May 22, 2007 9:13 am

Re: Simplest bitboard attack generation

Post by Rein Halbersma » Sat Oct 05, 2013 8:41 pm

Gerd Isenberg wrote:
Also, your LSB and MSB need to deal with empty sets ...
Do you know what the technical reasons are that some architectures return 64 for __builtin_ctzll(0) and others yield undefined behavior?

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Simplest bitboard attack generation

Post by Gerd Isenberg » Sat Oct 05, 2013 8:48 pm

Rein Halbersma wrote:
Gerd Isenberg wrote:
Also, your LSB and MSB need to deal with empty sets ...
Do you know what the technical reasons are that some architectures return 64 for __builtin_ctzll(0) and others yield undefined behavior?
Different x86 instructions. Trailing zero count versus bitscan. The latter is undefined with empty source.

see Bitscan versus Zero Count

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Simplest bitboard attack generation

Post by Gerd Isenberg » Sat Oct 05, 2013 9:06 pm

Rein Halbersma wrote:
Gerd Isenberg wrote:
Also, your LSB and MSB need to deal with empty sets ...
Do you know what the technical reasons are that some architectures return 64 for __builtin_ctzll(0) and others yield undefined behavior?
I would consider that a bug of __builtin_ctzll(i) if implemented by bsf without the leading condition:

Code: Select all

int trailingZeroCount&#40;U64 bb&#41; &#123;
    if ( bb )
       return bitScanForward&#40;bb&#41;;
    return 64;
&#125; 
Haswell and other none intel architectures have a machine instruction for trailing zero count.

bob
Posts: 20914
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Simplest bitboard attack generation

Post by bob » Sat Oct 05, 2013 9:43 pm

Gerd Isenberg wrote:
bob wrote:If you use the macros I posted, which directly compute sliding piece attacks, here's an estimated cost of using that approach rather than either magic or rotated attack generation:


time=22.19 n=117008633 afhm=1.19 predicted=0 50move=0 nps=5.3M
time=27.94 n=117008633 afhm=1.19 predicted=0 50move=0 nps=4.2M

Actual cost is about 20%, not the 10% I had guessed. But it is highly simple, if that is what you want.
Do you use them to initialize magics? For that purpose you like something with almost no lookup at all.

Also, your LSB and MSB need to deal with empty sets ...
They do. LSB/MSB use bsf/bsr instructions and are coded in asm to deal with all zeroes. I don't use that code for anything, it was the ORIGINAL bit board code from Crafty before I did rotated bit boards. I used it for the DS version since the rotated tables were way too big...

Post Reply