Attacks From table

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.
bob
Posts: 20583
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Attacks From table

Post by bob » Tue Aug 14, 2018 4:18 pm

unless you have a power of 2 size, a table lookup is going to include a multiply. Shift and add really don't count in a super-scalar architecture. I don't think there is anything to gain here. I used to do what Slate and Atkin did. Maintained an array of attacks. One showing all squares attacked from each occupied square (now replaced by direct computation via magic) and one showing all squares that attack a given square (kind of info used in SEE for example). The updating was quite expensive, and very cache unfriendly. I dropped the latter one completely and converted the other to a table lookup (initially rotated bit boards, then to magic bit boards) and the speed climbed dramatically.

I can probably dig up my old slate/atkin style code, but it was really big (and really clever and really cache-unfriendly). Much nicer to have a simple direct-computation macro that expands into something very simple.

Aleks Peshkov
Posts: 870
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: Attacks From table

Post by Aleks Peshkov » Thu Aug 16, 2018 11:02 am

This representaion is as fast as the fastest perft known engines.

My principal chess representation consists of 16-byte vector for each 16 chess piece from each side.

attackMap is array of Ranks of BitRank vectors for each piece;

BitRank: byte of 8 squares per rank (1/8 of bitboard);
PieceId: index to 16 pieces of one side;

BitRank attackMap[Rank 0..8][PieceId 0..15];

There are 3 basic operations:
1) writing 8 separate bytes of attackTo bitboard into each attackMap rank;
2) fetching set (16-byte mask or 16-bit using _mm_movemask_epi8) of pieces that attack a given square (trivial operation within single SIMD register);
3) transforming attackMap into legal moves matrix (excluding pinned moves, adding pawn non capture moves).

Source code of Perft Engine:
https://bitbucket.org/alekspeshkov/petrel

Edsel Apostol
Posts: 762
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Attacks From table

Post by Edsel Apostol » Wed Aug 22, 2018 11:28 am

bob wrote:
Tue Aug 14, 2018 4:18 pm
unless you have a power of 2 size, a table lookup is going to include a multiply. Shift and add really don't count in a super-scalar architecture. I don't think there is anything to gain here. I used to do what Slate and Atkin did. Maintained an array of attacks. One showing all squares attacked from each occupied square (now replaced by direct computation via magic) and one showing all squares that attack a given square (kind of info used in SEE for example). The updating was quite expensive, and very cache unfriendly. I dropped the latter one completely and converted the other to a table lookup (initially rotated bit boards, then to magic bit boards) and the speed climbed dramatically.

I can probably dig up my old slate/atkin style code, but it was really big (and really clever and really cache-unfriendly). Much nicer to have a simple direct-computation macro that expands into something very simple.
You are probably right. There' s not much to gain besides code complexity. I've implemented the usual PEXT optimization to the magic bitboards and sliding piece attacks are now almost just a table lookup.

Post Reply