Accelerated Move Gen in Null Move

[Tennison]

Is this already tried ?

1. I generate moves at first ply of Null Move.
2. After this I only generate moves for affected pieces and pawns.

How ?

For this I need a bitboard with :
- the actual position (the to)
- the position at ply-1 (the from)
- the squares affecting to and from

Yes I explain this very difficult (but my English isn't enough good). But here is a picture to explain better (I hope) :



With this bitboard you easily find that you don't have to generate moves for pieces in the "saved squares" area.

So in these 3 examples you have a gain of 14,19 and 16 squares (so 25% of the board).

Do you think this can save time ?

Anybody wants to try this and give speed results ?

Thanks for your nice comments.

Benoît (please don't forget I'm a bad bad programmer) ...

[xmas79]

Everything depends on the move generation structure. If you have a staged move generation then the idea is not worth any significant speed improvement IMHO. You also seems not to cover discovery moves: in the case of a rook move for example you have to check if a bishop can now make a move through the just freed square, and check if the rook in the "to" square is going to make blind some piece. There are other issues, eg if the rook "removes" some pinned piece...

This seems the same idea of the "incremental move generation" idea that has been done several years ago when the move generation phase cost was very high compared to search cost.

[Tennison]

Thanks Natale for your response.

You also seems not to cover discovery moves: in the case of a rook move for example you have to check if a bishop can now make a move through the just freed square, and check if the rook in the "to" square is going to make blind some piece. There are other issues, eg if the rook "removes" some pinned piece...

I think I cover all this with this bitboard :
- for the "from" and the "to" you have all diagonals, lines,files and knight moves. So this covers discovery, pinned and so on.
(if I'm not wrong)

So if you want to generate now the moves you only have to modify the moves of the pieces in the X. All pièces outside the X aren't affected.

[xmas79]

Ah yes I see. But other issues I see with this approach is:

Suppose we are in your example #1. The move is Re3-e7. Suppose a queen (yours) on a7. Since that queen is on an x square you know have to calculate moves for that piece. How do you remove from the previous move list all the moves of the queens like Qe7 Qf7 Qg7 Qf7? Then have to add Qf2 and Qg1... If the queen is an opponent one, then you have to simply add Rxa7. And if there's a piece on b7 then that queen on a7 would not be on an x square, as the rook ray stops at b7. So you always have to evaluate all the moves from the "to" square. If you have sorted you move list then all this stuff is pretty bad... Do you really want to traverse the move list? Very expensive... Or do you use the previous ply queen bitboard and mask? It's a lot easier (simpler code is enough for me) to evaluate it again IMO, since the major cost is traversing the bitset of the bitboard, so you won't gain anything at all, always in IMHO.

Regards,
Natale.

[cdani]

I do this on Andscacs for calculating attacks after every move. Is not null move related, is for every move done. I don't use magic boards, just plain calculations with array of bytes and Bitboards with some precaltulations. The attacks are just overwritten, so there is no problem with this approach.
If someone wants I can put the code here.
I think also that using this idea for move generation will be very expensive.