An approach to precomputed move generation bitboards

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.
User avatar
Desperado
Posts: 638
Joined: Mon Dec 15, 2008 10:45 am

Incremental bitboard attack computations

Post by Desperado » Tue Dec 01, 2015 8:28 pm

Hello, Michael,

currently i try to implement bitboard attacks in an incremental way too.
so, if we ignore the implementation details for the moment, we can focus on some more general questions in this context (imo).

For simplicity let's say we talk about attacks for the current piece locations.


1. Let's assume further we have a pretty fast (like magic bitboards) AttackGetter at hand.

1a.

Magic bitboards are finally an index computation with a lookup (parallel in context to lines).
A simplified view on this makes clear that storing different bitboards on some stack won't improve
the basic computation time just by having another lookup approach.
(with some overhead to update the bitboards on the stack after making a move and not to forget to revert the attacks again)

1b.

Anyway, if we manage to get some speed gain within the "node activities", that means that the incremental overhead must be
equalized and our incremental lookups must be faster to some degree. The better the utilization of the once computed set of attacks is,
the higher the speed gain will be.


1c.

By default there are two places where the attacks are used. First, the move generation part, which as you already pointed out,
can be disabled at leave nodes, to save some time. But you won't disalbe the "incremental" attack computation because of the second
component, the evaluation. Each leave node will be evaluated, so this is the place where you really might need your attack sets.
Finally, you save some time in a perft frame, but the real engine needs the attack computation for evaluation too.

2. Where might the speed gain come from (thinking of implementation contents) ?

2a.

Non sliders aren't affected as long the piece location does not change. Sliders may be affected
by move types. The general algorithm might look like this to determine necessary attack updates:

* reset the attack information for the source square of a move
* compute the attack for the destination square of a move

* mask the diagonals for the source square and check for bishops and queens
* mask the straight lines for the source square and check for rooks and queens
* mask the diagonals for the destination square and check for bishops and queens
* mask the straight lines for the source square and check for rooks and queens.

* compute/update the attacks for the checked bishops/rooks/queens.

En passent/Castling/Promotion moves need some minimal refinements for the masking part.

Well, at this point the question arises and it needs to be checked, if a simple computation for all pieces is really slower on average,
than to determine which pieces needs to be updated. But i still talk of a one time computation after a makeMove operation.

2b

Depending on the implementation, this update needs to be reverted which requires an analog computation like 2a or a restore of some data.
If you restore "Attackmaps" you will shift many (a lot more) bytes over the search and the copy operation will take a lot of time too.

2c

The best case is, that sliders aren't affected and you simply reset the attacks for the source and compute one attack for the destination square,
while having all attacks at hand. This is a minimal computation but finally you still look it up (as you do with magics for example)

2d

Finally i don't see a good reason to use incremental attack computation for "attack from squares"(simple piece locations).
I you use a less optimal AttackGetter like Magic Bitboards, there a different other ways like "caching attack sets" which improve the speed,
to get a better performance.

3. But anyway, there is potential from another view point imho.

There are different kinds of attacks you might be interested in. These are about, from which location/piece the current square is attacked,
how many times it is attacked and so on. The use is the bool squareIsAttacked() function (incheck) or pin computations or attack counts for a square,
these more complex computations can be solved in one run too and can be retrieved at any time at the current node. The base to compute and
store these attacks are the attackFrom sets of course. The idea starts with:

Having a new node:
1. Compute all piece attacks(attackFrom) (optional: store the attacks to look them up, maybe this is not necessary if your AttackGetter is magic like)
2. Compute the "complex" attacks out of it one time and retrieve the information on demand.

(At this point i solved my own problem LOL, thx ;-) )

So, if the option is to use direct computations (AttackGetter functions) without storing them you just need to think foward in the tree.
Find a representation to keep the "complex" attack sets. If then the use is stack based, there is no need for copy/revert operations.
I guess to handle it with make/unmake would be to expensive then.

Just my 2 cents.

Michael Sherwin
Posts: 3148
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Incremental bitboard attack computations

Post by Michael Sherwin » Wed Dec 02, 2015 6:14 am

(At this point i solved my own problem LOL, thx Wink )
Your welcome :)

Yes, I did not consider needing to generate moves/attacks in/for the evaluation. So basically if all that move generation work has to be done at the leaves then basically the savings lower in the tree will not have a large impact. I've often wondered if positional evaluation could be done a few nodes from the leaves and then just do a material balance search to the leaves. Then the incremental approach combined with time savings could work together super synergistically.

Thanks for your detailed reply!
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Michael Sherwin
Posts: 3148
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: An approach to precomputed move generation bitboards

Post by Michael Sherwin » Wed Dec 02, 2015 6:20 am

stegemma wrote: At the end, it was not faster than generating all the moves from scratch.
Seems to be a recurring observation. Thanks
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

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

Re: An approach to precomputed move generation bitboards

Post by Aleks Peshkov » Wed Dec 02, 2015 12:17 pm

I have a matrix PieceIndex(16) x SquareBitsOnTheSingleChessRank.
So I have to split attacks bitboard into 8 bytes when updating my attack_matrix.

1) But on the other end: AttacksTo() function is simple reading the 16-byte vector (fits one XMM register) and a few very simple bit operations.

2) To gather all attacked squares by all pieces of one side into one bitboard is also very simple function.

Cardoso
Posts: 297
Joined: Thu Mar 16, 2006 6:39 pm

Re: Incremental bitboard attack computations

Post by Cardoso » Wed Dec 02, 2015 12:57 pm

Hi,
assuming one has a reasonable move generator, that doesn't take a huge ammount of time to compute, then going from that to a move generator that would take zero time to compute wouldn't make any ELO difference IMO.
The evaluation function usually dominates the search time as you already know.

best regards,
Alvaro

Henk
Posts: 6135
Joined: Mon May 27, 2013 8:31 am

Re: Incremental bitboard attack computations

Post by Henk » Wed Dec 02, 2015 1:14 pm

Counting material is much faster than collecting and sorting captures.

Henk
Posts: 6135
Joined: Mon May 27, 2013 8:31 am

Re: Incremental bitboard attack computations

Post by Henk » Thu Dec 03, 2015 12:45 pm

Maybe we should organize the yearly move generator competition. Fastest move generator wins of course. Problem is that all generators should run on same hardware.

Post Reply