bob wrote:No, just for 5 pieces. The rest are just direct lookups that are computed before the game starts. Only sliders use the magic stuff.
That would still make 10 if you count the opponent's pieces (whose moves you would need for SEE, f.e.). And you would still have to do the lookups for the 22 others, intersect them with targets...
My mobility is as cheap as the magic stuff. I pre-compute mobility per square, then use the same magic math, but instead of looking up a 64 bit attack set for the piece, I look up a 1 byte mobility score for the piece, since this includes just squares the piece can reach anyway.
Does that mean it was included in the 10%, or that it takes another 10%?
Don't follow you there. When I was using incremental update, all I got were attack bitmaps just as I do with magic. With either approach I had to "unroll" the bitmap into a set of from/to/etc actual moves.
When the bits naturally extract in the order you want to play them, (MVV/LVA) you can defer that to when you actually play them (so don't do it at all after a cutoff), and there is no need for further sorting. SEE can be done by feeding the word in the attack map for the target square to a sinmpel table lookup.
bob wrote:No, just for 5 pieces. The rest are just direct lookups that are computed before the game starts. Only sliders use the magic stuff.
That would still make 10 if you count the opponent's pieces (whose moves you would need for SEE, f.e.). And you would still have to do the lookups for the 22 others, intersect them with targets...
My mobility is as cheap as the magic stuff. I pre-compute mobility per square, then use the same magic math, but instead of looking up a 64 bit attack set for the piece, I look up a 1 byte mobility score for the piece, since this includes just squares the piece can reach anyway.
Does that mean it was included in the 10%, or that it takes another 10%?
Don't follow you there. When I was using incremental update, all I got were attack bitmaps just as I do with magic. With either approach I had to "unroll" the bitmap into a set of from/to/etc actual moves.
When the bits naturally extract in the order you want to play them, (MVV/LVA) you can defer that to when you actually play them (so don't do it at all after a cutoff), and there is no need for further sorting. SEE can be done by feeding the word in the attack map for the target square to a sinmpel table lookup.
I only need the moves for one side at any given ply.
For the "naturally extract" that doesn't work for bit boards. All I get is a set of squares the piece on the square in question attacks. That has no order since each bit maps to exactly one square on the board.
Seems like we are not exactly on the same page somehow...
As far as mobility goes, it takes zero time. It is just a table lookup. The magic attack generation also takes essentially zero time. The actual time is spent in unrolling the attack bitmaps into an array of compressed moves. If I do a line-by-line profile using intel's tune, those lines for magic lookup are all zero in terms of time used. Mobility uses the same indexing, but just fetches one byte rather than a 64 bit map.
For the "naturally extract" that doesn't work for bit boards. All I get is a set of squares the piece on the square in question attacks. That has no order since each bit maps to exactly one square on the board.
But if you extract them from the attack map, you can arrange it such that you extract them in the natural order. So the attack map saves you time on move sorting, compared to bitboards, as you would only unroll one move at a time, and after that you might get a cutoff.
For the "naturally extract" that doesn't work for bit boards. All I get is a set of squares the piece on the square in question attacks. That has no order since each bit maps to exactly one square on the board.
But if you extract them from the attack map, you can arrange it such that you extract them in the natural order. So the attack map saves you time on move sorting, compared to bitboards, as you would only unroll one move at a time, and after that you might get a cutoff.
The only viable orders are based on MSB and LSB. IE squares closes to a1 or h8. It turned out to be far faster to extract the moves in natural order, then search in whatever order is wanted.
If you store the attak maps in bitboard form, yes. So that is a poor method. If you store them as piece sets of attackers, the bits ordered in LVA order, and store the sets not as a mailbox board (i.e. in square order), but as piece list, in MVV order, they would extract in the desired order.
All I am saying is that if you use a poorly designed attack map, waste time on updating it when you don't need it at all, hardly use it for anything but keep doing all the stuff in your engine independently... Then it would not be much of a surprise if the attack map was just a burden. An attack map is a design choice around which you build the engine, not an add on.
hgm wrote:If you store the attak maps in bitboard form, yes. So that is a poor method. If you store them as piece sets of attackers, the bits ordered in LVA order, and store the sets not as a mailbox board (i.e. in square order), but as piece list, in MVV order, they would extract in the desired order.
All I am saying is that if you use a poorly designed attack map, waste time on updating it when you don't need it at all, hardly use it for anything but keep doing all the stuff in your engine independently... Then it would not be much of a surprise if the attack map was just a burden. An attack map is a design choice around which you build the engine, not an add on.
I don't follow the "bits ordered in LVA order". A "set" has no "order" in the context of bitmaps as I (or most, apparently) use them. Just a set of 1's that represent valid destination squares...
But in any case, if you look up a bit vector that contains a set of destination squares, that is essentially what I do with a magic move generation as well. One table access per piece, just as you would have for an incrementally updated attack bitmap for a specific piece (square). And there is no incremental update overhead at all. In place of the incremental update, I have a single AND, MUL and SHR triplet of instructions. Array indexing only eliminates the non-power-of-2 MUL operation so that it becomes a SHL (to scale to 8 byte entries) inside the CPU.
bob wrote: A "set" has no "order" in the context of bitmaps as I (or most, apparently) use them. Just a set of 1's that represent valid destination squares...
Indeed. So that is why I consider what you are doing (bitboards) not very competitive, speedwise.
bob wrote: A "set" has no "order" in the context of bitmaps as I (or most, apparently) use them. Just a set of 1's that represent valid destination squares...
Indeed. So that is why I consider what you are doing (bitboards) not very competitive, speedwise.
Then exactly how many engines are actually faster than Crafty, speedwise (for tree search)? How many of these are mailbox programs?
bob wrote: A "set" has no "order" in the context of bitmaps as I (or most, apparently) use them. Just a set of 1's that represent valid destination squares...
Indeed. So that is why I consider what you are doing (bitboards) not very competitive, speedwise.
bob wrote: A "set" has no "order" in the context of bitmaps as I (or most, apparently) use them. Just a set of 1's that represent valid destination squares...
Indeed. So that is why I consider what you are doing (bitboards) not very competitive, speedwise.
Then exactly how many engines are actually faster than Crafty, speedwise (for tree search)? How many of these are mailbox programs?
How many programs use incrementally updated move sets?
