Don wrote:While we are on the subject of magics, I have a question for the developers on this forum.
Is it better to populate a data structure with the move lists for the pieces or just create them from a bitmap stored in the magics destination array? There are some tradeoffs for each method and I have never payed much attention to my move generator (it's the same as it was 3 years ago.)
Any thoughts on this? I'm looking to tweak Komodo's speed and I'm cleaning up some things now.
When bit scanning was expensive, I tried this approach. Instead of storing the movelist, I pack the destination squares into 6 bits all into a 64bit value and terminated by the from square. So instead of doing bit scanning, you only do bit shifting. For knight and king, it will fit into 64 bits. For sliders, it has to be split into the two separate directions.
This speeded up my perft by 10%. I've since abandon that approach as hardware bitscanning is now available.
Don wrote:While we are on the subject of magics, I have a question for the developers on this forum.
Is it better to populate a data structure with the move lists for the pieces or just create them from a bitmap stored in the magics destination array? There are some tradeoffs for each method and I have never payed much attention to my move generator (it's the same as it was 3 years ago.)
Any thoughts on this? I'm looking to tweak Komodo's speed and I'm cleaning up some things now.
I think the direct computation is the simplest and fastest. A second level of indirection (move lists for each piece) just adds complexity and only replaces a memory look-up. I tried the piece-list idea years ago (with rotated, not magic) and did not find any improvement at all. It was very slightly slower, and added to the code size as well...
Of course, YMMV, so testing is the only way to answer it for _your_ program. There are way too many unknown interactions within a chess engine already, sometimes adding something makes it faster rather than slower, sometimes deleting code makes it slower, not faster. Etc.
My intuition says to build the list from the bitmap just as you suggest. However I don't really trust my intuition that much so I guess I have to take your advice and try it both ways.
Don
I guess I got your question wrong. What exactly do you mean with "to populate a data structure with the move lists" versus to build the list from the bitmap?
You basically have a separate table that returns a list of "to squares" instead of a btmap of attacked squares. So after the move 1. e4 e5 the magic bitmap for the bishop on f1 contains all the squares the bishop attacks (perhaps stored in 8 bits per square.) This consumes memory but saves the bit scanning which is expensive and has lot's of conditional branching. In other words the list of moves is precomputed. Unfortunately, there is still additional work to be done to form a proper list of moves that you can work with.
Don wrote:
You basically have a separate table that returns a list of "to squares" instead of a btmap of attacked squares. So after the move 1. e4 e5 the magic bitmap for the bishop on f1 contains all the squares the bishop attacks (perhaps stored in 8 bits per square.) This consumes memory but saves the bit scanning which is expensive and has lot's of conditional branching. In other words the list of moves is precomputed. Unfortunately, there is still additional work to be done to form a proper list of moves that you can work with.
OK, I see. A pre-computed move-list (instead of a bitset) has the advantage to save bitscans but isn't that versatile if it is about serializing subsets, i.e. to generate captures only in qsearch, and in general to exclude own attacked pieces as move target squares, which could better be done in the set-wise world by intersection (and) with opponent piece for captures and empty squares for quiet moves.
Don wrote:
You basically have a separate table that returns a list of "to squares" instead of a btmap of attacked squares. So after the move 1. e4 e5 the magic bitmap for the bishop on f1 contains all the squares the bishop attacks (perhaps stored in 8 bits per square.) This consumes memory but saves the bit scanning which is expensive and has lot's of conditional branching. In other words the list of moves is precomputed. Unfortunately, there is still additional work to be done to form a proper list of moves that you can work with.
OK, I see. A pre-computed move-list (instead of a bitset) has the advantage to save bitscans but isn't that versatile if it is about serializing subsets, i.e. to generate captures only in qsearch, and in general to exclude own attacked pieces as move target squares, which could better be done in the set-wise world by intersection (and) with opponent piece for captures and empty squares for quiet moves.
I never payed much attention to move generation because in good (evaluation heavy) chess programs it's a very small percentage of the execution time anyway. But Komodo is at the point now where I need to revisit the smallest details.
I was inspired enough by this thread to re-implement magics. My previous scheme was my own formula which was based on magic bit-boards but I was generating slider moves in 2 passes (one for each diagonal or orthogonal), which gives a very compact "fixed shift" data structure but requires a bit more work. I'm sure the Android guys will hate me for this
The previous scheme stored a list of target squares as well as an attack board. The new magics (where I do not store the squares) actually appears to have slowed the program down slightly when it comes to just generating quiet moves for the sliding pieces. I cannot say for sure why. But I'm still getting a 2% speedup overall because this is improving all the routines where I need to know if specific targets are attacked.
So I don't think it matters much how you generate moves but it might matter a little. Because standard magics is so much more memory hungry I am reluctant to implement and test a version that also keeps a list of attacked squares.
