Staged move generation???

[hgm]

The hash probe will be fast, because the entry will be in cache, since the initial hash probe has brought it there. Only for nodes close to the root there is a chance it has been flushed out of the caches. But there are so few of those, that it doesn't matter at all how slow things are there.

And of course the hash move usually gives a cutoff the first time you try it. Then there won't be a second time.

I have little experience with multi-threading. But it seems unusual that the target position of the hash move would be overwritten with something you cannot use. You only do the retry if the first try failed low, and if it fails high the second time, it could correct a faulty result for the current node. Which might have a net positive effect despite the fact that it took some extra time.

[Joost Buijs]

Well, I don't agree. Removing the best move from the move-list is nothing more than 1 extra integer comparison for each move you play at that particular node. If the best move didn't fail-high and the hash-entry has been overwritten, either because it is close to the root or by another thread, it will have an detrimental effect on the branching factor and that is something you don't want. So you lose both ways.

[hgm]

Just measure how often that happens. With a proper replacement scheme entries close to the root should never be overwritten, because their depth protects them from that. If it is close to the leaves, the time between the visits is so short that there also is virtually no chance that it will be overwrittent between the visits. But it is not useful to argue about this, without actually measuring the numbers.

[Joost Buijs]

It could be that this is not a very big issue for a single-threaded engine, but when you run on 16, 32 or even more threads (like most engines nowadays do), hash-entries will get overwritten very frequently and then it will become an issue.

[emadsen]

Removing the best move from the move-list is nothing more than 1 extra integer comparison for each move you play at that particular node.

That's my assessment too. I'll gladly "buy" a correct node count for the price of 1 ulong comparison (well, there's some bit masking involved too). Especially because in my engine the move generator used by perft is the same move generator used by search. I recently refactored pin detection code and was glad to be assured correct perft node counts after the refactoring guaranteed unaltered search trees. I'll gladly buy that for 1 ulong comparison at each cut node.

[emadsen]

I re-read what I wrote this morning. Apparently the coffee hadn't kicked in, because I didn't express myself clearly. I meant to say:

"I'll gladly buy that for 1 ulong comparison per move at each all node."

[niel5946]

I have worked on implementing a staged move generation the last days, but I haven't seen any significant elo gains (+7 elo, but with a +-25 error margin, so it is not even statistically safe to draw conclusions...). It works with the following move ordering/staging scheme:

1. Hash move
2. Generate and score captures using MvvLva and SEE
3. Search good or equal captures.
4. Search the killers if they are deemed to be pseudo-legal
5. Generate and sort the rest of the quiet moves.
6. Search the remaining quiets.
7. Search the losing captures

I don't think there are any bugs (since bugs in move generation would probably result in extreme elo losses), but it is more likely that the implementation is just too inefficient. It might also be because my first movegen implementation - just generating and scoring the entire list at once - was fast enough so that no significant increase can be expected from generating moves in stages. But this is weird since generating less moves would most certainly increase the nps. I think that I've just "moved" the inefficiency from scoring moves that won't be used, to fetching moves generated in stages.
The slow-downs in this implementation is probably mainly due to the SMG constructor and the fetch_next method.

I really can't see a way to make it so much faster that it will gain up to 40 elo...

The code for the pseudo-legal check can be found here: https://github.com/BimmerBass/Loki/blob ... sition.cpp (everything after line 973)
The code for the staged move generation class: https://github.com/BimmerBass/Loki/blob ... movepick.h and https://github.com/BimmerBass/Loki/blob ... vepick.cpp