Piece attacks count

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Piece attacks count

Post by mcostalba » Mon May 18, 2009 6:03 am

In case someone is interested this is my last version of piece attacks bit counting functions. They work for bisop, rooks, knights and queens, although for queen is faster the usual function.

They work also with taboo squares, where some of the otherwise set bits are at zero because square is removed from attack set.

Code is somewhat optimized for 32 bit case. For 64 bit case we could spare some instruction.

Of interest there is the counting of bishops and knights attacks using _only one_ multiply instead of two (one per diagonal) as previously posted.

Following code is a working code and tested to be functionally identical to stock version.

Code: Select all

template<PieceType Piece>
inline int attack_count&#40;Bitboard b, int sq&#41; &#123;

  unsigned w = unsigned&#40;b >> 32&#41;;
  unsigned fl = sq & 7;
  unsigned k = BitCount8Bit&#91;w >> &#40;24 + fl&#41;&#93;;

  b *=FileBB&#91;7-fl&#93;;

  w = unsigned&#40;b >> 32&#41;;
  unsigned first = unsigned&#40;b >> &#40;sq - fl&#41;) & 0xFF;
  unsigned top = w >> 24;

  return BitCount8Bit&#91;first&#93; + BitCount8Bit&#91;top - first&#93; + k;
&#125;

template<>
inline int attack_count<QUEEN>&#40;Bitboard b, int&#41; &#123;

    return count_1s&#40;b&#41;;
&#125;

template<>
inline int attack_count<ROOK>&#40;Bitboard b, int sq&#41; &#123;

    int fl = sq & 7;
    unsigned w = unsigned&#40;((&#40;b >> fl&#41; & FileABB&#41; * FileABB&#41; >> 32&#41;;
    return BitCount8Bit&#91;unsigned&#40;b >> &#40;sq - fl&#41;) & 0xFF&#93; + &#40;w >> 24&#41;;
&#125;
FileABB is a bitboard with ones on the A file only

FileBB[8] is an array of file bitboards indexed by the file. FileBB[x] is a bitboard with ones on the file x only.

int BitCount8Bit[256] is a table for looking up bit counts of a byte.


In case someone is interested in WHY it works and doesn't manage to understund it (it is not so trivial, especially the bishop case) please ask, I will post a little rationale of the formulas.

Ryan Benitez
Posts: 719
Joined: Thu Mar 09, 2006 12:21 am
Location: Portland Oregon

Re: Piece attacks count

Post by Ryan Benitez » Mon May 18, 2009 7:23 am

Making sure I understand the external parts right.
mcostalba wrote: FileABB is a bitboard with ones on the A file only

Code: Select all

const uint64 FileABB = 0x0101010101010101;
mcostalba wrote: FileBB[8] is an array of file bitboards indexed by the file. FileBB[x] is a bitboard with ones on the file x only.

Code: Select all

const uint64 FileBB&#91;8&#93; = &#123;
	0x0101010101010101,
	0x0202020202020202,
	0x0404040404040404,
	0x0808080808080808,
	0x1010101010101010,
	0x2020202020202020,
	0x4040404040404040,
	0x8080808080808080
&#125;;
mcostalba wrote: int BitCount8Bit[256] is a table for looking up bit counts of a byte.

Code: Select all

   for &#40;int b = 0; b< 256; b++) &#123;

      int n = 0;

      for &#40;int i = 0; i < 8; i++) &#123;
         if (&#40;b& &#40;1<<i&#41;) != 0&#41; n++;
      &#125;
      
      BitCount8Bit&#91;b&#93; = n;
   &#125;

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Piece attacks count

Post by mcostalba » Mon May 18, 2009 7:31 am

Ryan Benitez wrote:Making sure I understand the external parts right.
mcostalba wrote: FileABB is a bitboard with ones on the A file only

Code: Select all

const uint64 FileABB = 0x0101010101010101;
mcostalba wrote: FileBB[8] is an array of file bitboards indexed by the file. FileBB[x] is a bitboard with ones on the file x only.

Code: Select all

const uint64 FileBB&#91;8&#93; = &#123;
	0x0101010101010101,
	0x0202020202020202,
	0x0404040404040404,
	0x0808080808080808,
	0x1010101010101010,
	0x2020202020202020,
	0x4040404040404040,
	0x8080808080808080
&#125;;
mcostalba wrote: int BitCount8Bit[256] is a table for looking up bit counts of a byte.

Code: Select all

   for &#40;int b = 0; b< 256; b++) &#123;

      int n = 0;

      for &#40;int i = 0; i < 8; i++) &#123;
         if (&#40;b& &#40;1<<i&#41;) != 0&#41; n++;
      &#125;
      
      BitCount8Bit&#91;b&#93; = n;
   &#125;

Yes! to all three :-)

Ryan Benitez
Posts: 719
Joined: Thu Mar 09, 2006 12:21 am
Location: Portland Oregon

Re: Piece attacks count

Post by Ryan Benitez » Mon May 18, 2009 7:49 am

Very good, fun to play with. I do too many things with the attack mask to make use of it in my eval though. With an i7 the cost of popcnt is low so it is easy to justify many types of mobility (total,safe,pawn safe,forward) and use the mask for king attacks also. I have all the attack masks calculated before eval anyway for move_gen(), eval(), and the worlds slowest in_check().

Post Reply