Staged move generation???

[niel5946]

Hi.

I am thinking of implementing a staged move generation scheme for my engine, but is it even worth it? I mean even though I save on move generation - which is already very fast due to magic bitboards - in case of a beta cutoff, doesn't this cost a lot in the other end since one has to make sure that the move is at least pseudo-legal?

I believe it wouldn't be safe to not check for pseudo-legality when generating killers, countermoves and ofc the hash/PV move, and I can't really see how this check would make move generation faster than just generating all moves once.

Has anybody had any considerable gains (>15 elo) from switching to staged move generation?

[emadsen]

Yes, my engine gained 39 ELO. See my Staged Move Generation blog post.

I only use three stages:

1. Best Move
2. Captures
3. Non-Captures

I suspect most of the gain comes from avoiding move generation entirely by playing the best move found in the cache- after validating it to guard against rare cache collisions (correct color piece on from square, reachable to square, doesn't attack own piece, etc).

[hgm]

Some stages of move generation can easily be separated without significant overhead. Such as hash move vs captures vs non-captures. To also make killers a separate stage is a bit more cumbersome, because, as you say, one would have to test whether the killer is pseudo-legal in the current position. Note, however, that one always has to test whether killers are pseudo-legal, and that running through the list of generated non-captures to pick them out is not very cheap either. Especially in the case where they are not pseudo-legal, because tyou would only know that when you went through the entire list.

Checking a killer for pseudo-legality is not that expensive. (It does require dedicated code, though, not used for any other purpose.) If you make sure killers are only imported from sibbling nodes, you just have to test if the piece on the from-square is still yours, and (when it was a slider) if the move is not now blocked. Since sibblings are only separated from each other by two oppenent moves (one move, one unmove, actually), it must still be the same piece if the preceding opponent's move did not capture it. So the destination must be valid for that piece type on an empty board, or the sibbling would have designated a non-pseudo-legal move as a killer. The only problem could be that the move is now blocked, either on the from-square of the unmove, or the to-square of the move.

With bitboards it should not be very difficult to test whether the path taken by the killer is blocked. You could store the bitboard of that path in the killer table, and intersect it with the 'occupied' board. That sounds far cheaper than running through the move list to see whether the killer is there. Even when you would not do staged move generation.

[niel5946]

Yes, my engine gained 39 ELO. See my [url=https://www.madchess.net/2018/12/15/mad ... eneration/]Staged

Ahh yes! I totally forgot that I had actually read that blog post a couple of months ago . It looks like a pretty good scheme, and since I have just finished writing my SEE function, I'll try to improve upon it with the following:

• Hash move / PV move
• Good or equal captures
• Quiets sorted by killers, countermoves and lastly history
• Losing captures

This sort of move ordering is what I already do, although both move generation and move ordering in the alphabeta search are quite lazy implementations... But I hope that this, in conjunction with staged move generation will yield good results!

[niel5946]

Some stages of move generation can easily be separated without significant overhead. Such as hash move vs captures vs non-captures. To also make killers a separate stage is a bit more cumbersome, because, as you say, one would have to test whether the killer is pseudo-legal in the current position. Note, however, that one always has to test whether killers are pseudo-legal, and that running through the list of generated non-captures to pick them out is not very cheap either. Especially in the case where they are not pseudo-legal, because tyou would only know that when you went through the entire list.

Now that I think about it... Separating killers from all other quiets seems to be a bit of an over-kill. Especially in the early stages of development. Therefore I will probably just implement a basic staged move generation with: 1. Hash move. 2. Good/equal captures. 3. Sorted quiets. 4. Losing captures, which should be sufficient.

Later on I will try to separate the good quiets (killers, countermoves) so as to try them before all others, but I think that can wait.
Anyways, thank you for the advice! I will definitely keep the pseudo-legality-test method in mind when experimenting with this in the future

[Henk]

Not so sure about these bad captures.
How do you combine that with futility pruning.
Isn't with futility pruning you prune all captures when first capture does not make it.
So bad captures at the end is ok but not when doing futility pruning.

SEE is not cheap.

[niel5946]

Not so sure about these bad captures.
How do you combine that with futility pruning.

My futility pruning implementation is the following:

Code: Select all

/* Before moves loop */
inline int futility_margin(int d, bool i){
	return 110 * depth + ((i) ? 75 : 0);
}

if (depth < 7 && !in_check && !is_pv
	&& abs(alpha) < MATE && abs(beta) < MATE
	&& ss->static_eval[ss->pos->ply] + futility_margin(depth, improving) <= alpha) {
			
	futility_pruning = true;
}

And when searching a move:

Code: Select all

if (futility_pruning && !capture && !gives_check && SPECIAL(move) != PROMOTION && SPECIAL(move) != ENPASSANT) {
	continue;
}

Which means that, when the futility_pruning flag is set, I only prune moves that do not seem tactically significant.
Therefore, with the move ordering scheme I suggested, most of the quiets would simply be skipped, and the losing captures would be searched nearly instantly.

SEE is not cheap.

I know. My plan is to generate all captures, sort them with Mvv/Lva and then do SEE on each one when fetching them to be searched. If SEE < 0, then I'll just push them back and try a new one. I think it was hgm who suggested using SEE this way.

[Henk]

ok. You don't futility prune captures.

By the way my futility pruning only works when lb = ub -1 for when fail low i assume it gets researched.
Although research is slow.

[niel5946]

ok. You don't futility prune captures.

Exactly

[hgm]

Not so sure about these bad captures.
How do you combine that with futility pruning.
Isn't with futility pruning you prune all captures when first capture does not make it.
So bad captures at the end is ok but not when doing futility pruning.

SEE is not cheap.

A proper implementation would extract captures from the move list (or perhaps even geenrated them such in a staged way) in order of decreasing victim value until the next one 'doesn't make it'. And then continue searching the captures you extracted before, but postponed, because they qualified as 'bad'. (E.g. after concluding they were H x L, and then running a SEE on them that came out negative.)

BTW, in classical futility pruning (at d <= 1), not pruning futile captures is of course just a waste of time; the opponent is guaranteed to refute those through standing pat.