move scoring

Discussion of chess software programming and technical issues.

Moderator: Ras

JohnWoe
Posts: 529
Joined: Sat Mar 02, 2013 11:31 pm

Re: move scoring

Post by JohnWoe »

Luecx wrote: Tue Feb 15, 2022 12:48 pm
JohnWoe wrote: Tue Feb 15, 2022 11:12 am 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. :roll: 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.
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: move scoring

Post by 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. :D
User avatar
lithander
Posts: 915
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: move scoring

Post by lithander »

mvanthoor wrote: Tue Feb 15, 2022 8:56 am 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)
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: move scoring

Post by 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).
User avatar
mvanthoor
Posts: 1784
Joined: Wed Jul 03, 2019 4:42 pm
Location: Netherlands
Full name: Marcel Vanthoor

Re: move scoring

Post by mvanthoor »

lithander wrote: Tue Feb 15, 2022 11:35 pm ...
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.
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL
tcusr
Posts: 325
Joined: Tue Aug 31, 2021 10:32 pm
Full name: tcusr

Re: move scoring

Post by tcusr »

lithander wrote: Tue Feb 15, 2022 11:35 pm
mvanthoor wrote: Tue Feb 15, 2022 8:56 am 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?
User avatar
mvanthoor
Posts: 1784
Joined: Wed Jul 03, 2019 4:42 pm
Location: Netherlands
Full name: Marcel Vanthoor

Re: move scoring

Post by mvanthoor »

JohnWoe wrote: Tue Feb 15, 2022 9:48 pm 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.)
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: move scoring

Post by 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.
User avatar
lithander
Posts: 915
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: move scoring

Post by lithander »

tcusr wrote: Wed Feb 16, 2022 3:14 pm 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)
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess