Staged move generation???

[Ras]

Yes, my engine gained 39 ELO.

That's strange. Assuming 70 Elo per speed doubling, this means a 47% speedup. Even if assuming that the move generation doesn't take any time at all after the optimisation, it means that before, it must have taken 32% of the total time. That's a lower bound estimation because the move generation still takes time now, so it would have been closer to 40%. That would be extremely high, so I don't think the Elo gain can be attributed to the speedup alone. There should also be some improvement on the move ordering to explain that much Elo.

Also, most nodes are spent in quiescence, so the staged move generation in main search won't have any large impact anyway.

[Desperado]

Yes, my engine gained 39 ELO.

That's strange. Assuming 70 Elo per speed doubling, this means a 47% speedup. Even if assuming that the move generation doesn't take any time at all after the optimisation, it means that before, it must have taken 32% of the total time. That's a lower bound estimation because the move generation still takes time now, so it would have been closer to 40%. That would be extremely high, so I don't think the Elo gain can be attributed to the speedup alone. There should also be some improvement on the move ordering to explain that much Elo.

Also, most nodes are spent in quiescence, so the staged move generation in main search won't have any large impact anyway.

The biggest speed gain would happen if someone would generate all moves in qs and skip the search for the quiet moves. If someone already splits the movegeneration into quiets and capture part from the beginning, then 10% (-20%) speed gain is realistic too. This can make a big difference with hyperfast (<10s) testing games and if the engine level is still in the range of 2000 Elo.

The next thing is, that move ordering because of history heuristic might change and that can have another impact on strength.
Quiet moves get (can have) another history score in staged move generation than in a "one run" implementation because the time when
you check the scores is different. When reengineering the move picker properly (producing the same node counts for example) you will realize issues like that.

I can say that changing to staged move generation can result in 15 Elo only because of the combination speed, testing conditions and engine level.

Finally i agree that 39 Elo is a lot, maybe there was some bug fixing on the fly too.

[emadsen]

Finally i agree that 39 Elo is a lot, maybe there was some bug fixing on the fly too.

It's possible the change included other bug fixes, though I'm usually disciplined about mentioning other changes (than those implied by the post title) in my blog posts, and I see no mention of anything but staged move generation. I made the change before I migrated my code from Subversion to Git / GitHub, so finding the exact diff between blog posts is more difficult than with more recent changes. I'm too lazy to install Subversion and search my archives for the diff. So I'll leave it to the OP to report back how much ELO he gains from staged move generation.

[emadsen]

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.

Adding a KillerMoves stage to my move generator has been on my To Do list for a while now, I just haven't gotten around to it yet. Meaning, play the two killer moves directly from the KillerMoves[ply][0 or 1] cache prior to generating moves. I've already written an extensive move validity function- I hardened it when I was experimenting with storing partial Zobrist keys in cache entries. I should add logic, for sliders, to verify no pieces are in between the From and To Squares (I already have bit masks for this related to pin detection code), add a metric to track how often a killer move is invalid, then run some tests...

[mvanthoor]

Adding a KillerMoves stage to my move generator has been on my To Do list for a while now, I just haven't gotten around to it yet. Meaning, play the two killer moves directly from the KillerMoves[ply][0 or 1] cache prior to generating moves.

I've been looking into something like this for the TT Move. So you actually do mean:

- check legality for TTMove / Killer / PVMove (whatever)
- run make( move )
- if make reports "legal", do "eval = qsearch(...)"
- If eval >= beta: immediately return this
- If not returned, undo move and just proceed with normal move generation / sorting / playing

That would be easy to implement...

[emadsen]

I've been looking into something like this for the TT Move. So you actually do mean:

- check legality for TTMove / Killer / PVMove (whatever)
- run make( move )
- if make reports "legal", do "eval = qsearch(...)"
- If eval >= beta: immediately return this
- If not returned, undo move and just proceed with normal move generation / sorting / playing

Not quite. I'm referring to move generation in the main search, not qsearch. I mean this: (not a complete listing of search logic, just what's relevant to this thread)

1. Fetch best move from cache, validate it*, test legality, if legal play it.
2. Call Search(), UndoMove(), and take beta cutoff if eval >= beta.
3. Fetch killer move 1 from killer cache, validate it*, test legality, if legal play it.
4. Call Search(), UndoMove(), and take beta cutoff if eval >= beta.
5. Fetch killer move 2 from killer cache, validate it*, test legality, if legal play it.
6. Call Search(), UndoMove(), and take beta cutoff if eval >= beta.
7. Generate and sort captures. For each capture...
8. Call Search(), UndoMove(), and take beta cutoff if eval >= beta.
9. Generate and sort non-captures. For each non-capture...
10. Call Search(), UndoMove(), and take beta cutoff if eval >= beta.

After move generation, I ensure I don't search the best move from cache a second time. I'll need to ensure the same with killer 1 & 2 once I add a move generation stage for killers.

The ELO benefit comes from delaying move generation until step 7.

* Move validation is a sanity test: Is there a piece on the From square? Of the correct color? Can it reach the To square? Not a capture of a king or own piece? etc. Testing legality means does move leave own king in check?

[hgm]

Note that killers should be non-captures, and should only be searched after the captures (or at least the good captures) have been searched. I suppose that with "best move from cache" you mean the hash move from the Transposition Table?

The hash move can only be invalid if there is a key collision; otherwise it would be from the same position as you are in now. Key collisions are extremely rare (unless you hashing scheme is badly broken). So any test on it that isn't strictly necessary to prevent an engine crash is basically a waste of time. What exactly can crash your engine depends on the implementation. Possible dangers are moving opponent piece or empty squares, or capturing friendly pieces or enemy Kings. If the hash move doesn't do any of that, you can safely play it.

If you take care to clear the killer slots of ply+1 when you enter the node at ply, the only thing that can be wrong with a killer is that the piece was captured, or the move is blocked. This happens quite often, so you do have to test for that. Otherwise the killer must be pseudo-legal.

I just search the best move a second time. That is much faster than trying to fish it out of the move list. It will produce a hash hit, with a score that will fail low, as you have already seen that score in the node before.

[emadsen]

Note that killers should be non-captures, and should only be searched after the captures.

Doh! I wrote my previous post quickly and made a dumb mistake. You are correct, HG. Killers should be searched after captures- and killers are non-capture moves. That's how it it's done in my engine. Actually killers are searched after best move from cache, captures, and promotions. I just made a mistake when writing my previous post.

I suppose that with "best move from cache" you mean the hash move from the Transposition Table?

Correct.

[emadsen]

I just search the best move a second time.

I don't because I've designed my perft function to execute the same call stack as search does. So correct perft counts give me confidence search is examining all the moves it should (exempting pruning). Searching the best move twice would produce a different move count, breaking my perft tests.

[Joost Buijs]

I just search the best move a second time. That is much faster than trying to fish it out of the move list. It will produce a hash hit, with a score that will fail low, as you have already seen that score in the node before.

I can't imagine that playing the best move twice will be faster, you have to do at least a redundant hash probe (which is slow) and probably you have to do some other things too. In a multi-threading environment there is a big chance that the entry has already been overwritten. It doesn't sound like a very safe way of doing things.