Staged move generation???

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
niel5946
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Staged move generation???

Post by niel5946 » Wed Mar 10, 2021 8:48 pm

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?
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

User avatar
emadsen
Posts: 319
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Re: Staged move generation???

Post by emadsen » Wed Mar 10, 2021 9:19 pm

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).
My C# chess engine: https://www.madchess.net

User avatar
hgm
Posts: 26576
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Staged move generation???

Post by hgm » Thu Mar 11, 2021 8: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.

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
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Staged move generation???

Post by niel5946 » Thu Mar 11, 2021 8:59 am

emadsen wrote:
Wed Mar 10, 2021 9:19 pm
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 :D . 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!
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

niel5946
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Staged move generation???

Post by niel5946 » Thu Mar 11, 2021 9:10 am

hgm wrote:
Thu Mar 11, 2021 8: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.
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 :D
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

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

Re: Staged move generation???

Post by Henk » Thu Mar 11, 2021 9:22 am

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
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Staged move generation???

Post by niel5946 » Thu Mar 11, 2021 9:38 am

Henk wrote:
Thu Mar 11, 2021 9:22 am
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.
Henk wrote:
Thu Mar 11, 2021 9:22 am
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.
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

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

Re: Staged move generation???

Post by Henk » Thu Mar 11, 2021 10:09 am

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.
Last edited by Henk on Thu Mar 11, 2021 10:13 am, edited 1 time in total.

niel5946
Posts: 159
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Staged move generation???

Post by niel5946 » Thu Mar 11, 2021 10:13 am

Henk wrote:
Thu Mar 11, 2021 10:09 am
ok. You don't futility prune captures.
Exactly :D
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

User avatar
hgm
Posts: 26576
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Staged move generation???

Post by hgm » Thu Mar 11, 2021 10:34 am

Henk wrote:
Thu Mar 11, 2021 9:22 am
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.

Post Reply