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 guess most generate all captures and quiet moves in two runs (likely after hash and killer moves) into a move list to score them and to pick the best one by selection sort. This keeps the state space quites small, since attack bitboards are kept inside tempory registers while serialized to the move/capture list inside a bitscan loop.
I do it quite differently with kogge-stone and keep legal move target bitboards for 16 directions as unsorted fixed sized "move list", plus what is attacked/defended at least once or at least twice for a cheap set-wise SEE which covers most simple cases like hanging pieces. A finite state generator with several hundred states (most usually skipped on conditions) to get one move after the other, specially captures in a plausible MVV-LVA/cheap set-wise SEE order.
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.
I read the initial post in the other forum by Volker Annuss some time ago, and I decided to try for myself to reduce the table size as much as I could. This was my only goal. The post is headed "Fixed shift magics with 800KB lookup table". However, I found that a smaller table could be achieved with variable shift magics which of course requires a lookup table to get the shift. I obviously did not make this clear in my posts.
Anyway, I think that 620Kb is pretty good going though I still maintain that the table can be still further reduced, but the effort required will not be worth the result.
As to the issue of the magics not working... they work for me.
Grant
Thank you for the clarification Grant.
It now makes sense, as you say you were using variable shifts that Teemu had difficulties verifying your numbers. Do you really think variable shifts are a prerequisite for table sizes < 700kb when bit packing is used? When using larger shifts then needed, wouldn't this also decrease the density and thus favor bit packing?
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?
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.
