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?
Staged move generation???
Moderators: hgm, Rebel, chrisw
-
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
-
- Posts: 434
- Joined: Thu Apr 26, 2012 1:51 am
- Location: Oak Park, IL, USA
- Full name: Erik Madsen
Re: Staged move generation???
Yes, my engine gained 39 ELO. See my Staged Move Generation blog post.
I only use three stages:
I only use three stages:
- Best Move
- Captures
- Non-Captures
My C# chess engine: https://www.madchess.net
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Staged move generation???
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.
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.
-
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
Re: Staged move generation???
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:emadsen wrote: ↑Wed Mar 10, 2021 10:19 pm Yes, my engine gained 39 ELO. See my [url=https://www.madchess.net/2018/12/15/mad ... eneration/]Staged
- Hash move / PV move
- Good or equal captures
- Quiets sorted by killers, countermoves and lastly history
- Losing captures
-
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
Re: Staged move generation???
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.hgm wrote: ↑Thu Mar 11, 2021 9:26 am 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.
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
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: Staged move generation???
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.
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.
-
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
Re: Staged move generation???
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;
}
Code: Select all
if (futility_pruning && !capture && !gives_check && SPECIAL(move) != PROMOTION && SPECIAL(move) != ENPASSANT) {
continue;
}
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.
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.
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: Staged move generation???
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.
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.
Last edited by Henk on Thu Mar 11, 2021 11:13 am, edited 1 time in total.
-
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Staged move generation???
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.