move scoring

[JohnWoe]

Staged movegenerator makes no sense in chess. Very few moves. Propably worth +1 Elo.If your movegenerator is fast. In 10x8 Capablanca/ Shogi maybe with 60+ moves.

Just because yours seems to be bad, you cannot generalize that.

EDIT:

I am actually impressed by your comment history but i assume this comment just sums it up pretty well:

At least +350 Elo stronger than Sapeli 1.92. This proves that handcrafted evaluations are all crap.

I don't understand a word. What is bad? What has Sapeli to do with this?

Anyway you can't just hand wave this. This isn't academia.

Take my engine and replace my MoveGenerator+LazySort() with a staged movegenerator. With same signatures. No added complexity and more SLOC.
Lots of work. Then we will see if it's faster or not.

[hgm]

Of course you could also look at it this way: if speeding up move generation doesn't significantly increase the speed of your engine, the rest of your engine is too slow.

[lithander]

First: you will need to run through the move list anyway to order or pick moves, because you can't know which of the moves in the list are going to be the transposition table move, or are part of the killer moves. (If any, obviously.)

Is there a hash move? Great I play it first. No move generation at all and no iteration over any move list at this point. And the hash move is often already producing a cutoff!
Next... generate just the captures. That's going to be a short list. Lazy picking the best move here is quick because the range is so small.
Next... killers. Why would I need a move list here? I just get the killer move candidate, make sure it's actually playable in the current position and play it.
Finally... quiet moves. But thanks to staged move generation in most nodes we don't get this far and thus most moves that exist in a position have never been generated let alone traversed over in a list.

After searching 300 positions to depth 7 with Leorik (just alpha/beta pruning mostly) this is how often the different stages have been reached in total outside of Qsearch.

Code: Select all

HashMove: 28,105,975, Captures: 19,237,950, Killers: 8,863,512, Quiets: 7,653,768

...and this after searching to depth 8.

Code: Select all

HashMove: 163M Captures: 144M, Killers: 29M, Quiets: 16M

(whether searching even or odd number of plies makes a big difference in the ratios, somehow)

[hgm]

And then most full-width cut-nodes are actually cut by null move. And in many d=1 nodes non-captures will be futile (when currentEval < alpha - MARGIN), so that you would not have to generate these either. So you only rarely get to the non-capture (including killer) stage. In my measurements only 6% of the (non-null) moves played was a non-capture (including QS nodes).

[mvanthoor]

...

Obviously... if you have staged move generation, you're not going to iterate through the move list to find the hash move. If you have move generation, you even don't do half of the move ordering anymore:

- You don't order on the hash move anymore. If it is generated in the captures or quiets you skip it because it was already tried.
- Same for the killers.
- So you order the captures using MVV-LVA (if they are generated) and the quiets by history (if they are generated) and that's about it.

Apart from ordering captures by SEE later, to get the good captures before the bad captures, I don't even see anything else that could improve move ordering because the TT-move + captures almost always generate a cutoff. The rest is jacking around at the fringes compared to that. Same for trying to optimize a fast bitboard move generator even further by making it fully legal using attack maps and pin detection and such. That is stuff for very much later, because saving a few moves, especially in sections that possibly aren't even generated due to the staged move generation is not going to bring a lot of Elo.

[tcusr]

First: you will need to run through the move list anyway to order or pick moves, because you can't know which of the moves in the list are going to be the transposition table move, or are part of the killer moves. (If any, obviously.)

Is there a hash move? Great I play it first. No move generation at all and no iteration over any move list at this point. And the hash move is often already producing a cutoff!
Next... generate just the captures. That's going to be a short list. Lazy picking the best move here is quick because the range is so small.
Next... killers. Why would I need a move list here? I just get the killer move candidate, make sure it's actually playable in the current position and play it.
Finally... quiet moves. But thanks to staged move generation in most nodes we don't get this far and thus most moves that exist in a position have never been generated let alone traversed over in a list.

After searching 300 positions to depth 7 with Leorik (just alpha/beta pruning mostly) this is how often the different stages have been reached in total outside of Qsearch.

Code: Select all

HashMove: 28,105,975, Captures: 19,237,950, Killers: 8,863,512, Quiets: 7,653,768

...and this after searching to depth 8.

Code: Select all

HashMove: 163M Captures: 144M, Killers: 29M, Quiets: 16M

(whether searching even or odd number of plies makes a big difference in the ratios, somehow)

to keep it simple i use gen_all() in negamax search and gen_noisy() in qsearch. 80+ % of nodes are QS nodes so the useless quiet moves generated will give a small overhead (i hope).
just to prove it could you please modify your staged move gen to generate all moves in the noisy stage and measure how long it takes to solve the 300 test positions compared to your current move gen?

[mvanthoor]

Take my engine and replace my MoveGenerator+LazySort() with a staged movegenerator. With same signatures. No added complexity and more SLOC.
Lots of work. Then we will see if it's faster or not.

It doesn't even have to be tested. If playing the hash move creates a beta cutoff in 50% of cases, you don't generate moves AT ALL half of the time. (The actual number is much higher than 50%.) Therefore staged move generator MUST objectively be faster, because you can't be done faster than when doing nothing.

(Granted, the more stages you have, the lower the return on investment will be. That is why most engines stick to TT-move, captures, killers, quiets. You could add capture-promotion, quiet-promotion, and you could even try 3+ killers, but it has been determined that for most engines the difference is minimal to nothing in strength because the gains are too small and infrequent.)

[hgm]

Staged move generation becomes natural when you want to do completely different things during the capture and the non-capture stage. E.g. you sort by a different criterion (MVV/LVA vs history), you might want to use a different sorting algorithm (next-capture extraction vs binning), you might or might not want to subject the moves to SEE and postpone them. And you might even want to generate the moves in an entirely different way (by victim class vs by mover). And even use a different representation for the move list (bitmap vs array). So there are lot of reasons for using separate loops for searching the captures and for searching the non-captures. Skipping the latter after a cutoff (or when non-captures are futile, or in QS) then is an automatic side effect.

[lithander]

just to prove it could you please modify your staged move gen to generate all moves in the noisy stage and measure how long it takes to solve the 300 test positions compared to your current move gen?

I did that quickly and quoting the results wouldn't make sense here because it's misleading and not a fair comparison. For example without extra steps taken now I sort quiets by their MVV-LVA score, meaning I play the quiet moves of high value pieces last. Also killers don't work anymore. I have no easy way to pick them from the list of all moves if they arent their own stage.

But if you'd refactor the current state of Leorik to a non-staged move generator (but keep playing TT moves before generating any moves) I'd expect time to depth to increase by less than 20% which is only a handful of ELO. But I'm using a staged approach now already because I currently lay the foundations for everything that comes later, now. (see hgm's reply)