Move Ordering

[theturk1234]

Hi all,
My name is David and I've been working on a chess engine for some time now. I'd estimate it's about 1700-1800 strength.
I have a question about move ordering:
Right now, I'm doing move ordering at the root based on previous scores(the root moves are stored in a vector, updated after each is searched and after each ply at the root, the vector is sorted based on move score) and also in quiescence search. In quiescence I'm assigning each move a score based on the formula: Score = CapturedType - MovedType where queen = 9, pawn = 1, etc. I do not look at any captures that have a score of less than 0 by the formula as they are a waste of time. Should I do anything different? Which moves do you order first in quiescence search?
That brings me to the final question:
Should I be ordering moves in alpha-beta? I tried it, but it REALLY slowed down the engine(both nps and depth). What do you recommend?

Thanks for your thoughts,
David Cimbalista

[konsolas]

YES!

Alpha-beta is where your move ordering will turn out to be most useful. A typical approach is to generate your move list, and then loop through your moves and assign each one a score (based on capture val, etc.)

Then, instead of running a full sort (which is slow), simply pick the move with the largest score. Move ordering in alpha-beta is essential to get quick beta cutoffs for moves that end up hanging pieces, etc.

When you have capture move ordering working, I suggest you look into the https://chessprogramming.wikispaces.com ... +Heuristic and https://chessprogramming.wikispaces.com ... +Heuristic to start ordering non-captures.

[jdart]

If using PVS you do not have scores that mean anything except for the first move. All others were searched with a zero window.

You can do some initial ordering based on static exchange evaluation (SEE) or you can search the first few plies with a non-zero window and use the scores from that for an initial ordering.

But after that, if using a zero window the simplest approach at the root is just to take the best move at each iteration, swap it into the first position, and push all other moves down in the list. Then the top few moves will be moves that previously were the best in some prior iteration.

You can also use history, countermove and/or killer moves to improve ordering but all these are just heuristics and only on average over the whole tree will give a better than random ordering. I currently don't use them for root move ordering.

--Jon

[hgm]

Note that captures like QxB are not a waste of time at all, because the Bishop can be unprotected (and usually is). So itis amistakeoprune them. For this reason people usually order captures ot by victimValue - attackerValue, but by something like 16*victimValue - attackerValue (MVV/LVA). Whether a HxL capture is worth searching depends on how the piece is protected, and if there are other attackers. Even Q x protected P can be profitable if the only protector is Q and you have K as a second attacker. You should either calculate exactly whether a capture loses material (Static Exchange Evaluation) before pruning it, or be sure it loses material (value protector + victim < value attacker).

In full-width nodes it is also good to search the captures first (after hash move).

[smatovic]

...but it REALLY slowed down the engine(both nps and depth). What do you recommend?

This happened to my engine when i sorted moves in ascending and not descending order...

--
Srdja

[kbhearn]

A minimal move ordering that should save time for alpha-beta:
1) TT move (if you use iterative deepening, your evaluation is reasonably complete, and you have quiescence search implemented this should cutoff at a high % rate)
2) (good) captures sorted by MVV-LVA - the most common refutation needed in the tree. a surprisingly high number of moves searched will be the side that just moved dropping their pieces. you can omit bad captures (SEE < 0) from this if you have SEE implemented. where those bad captures get added back into the move order is something you can experiment with (except at perhaps low depth they shouldn't just be pruned).

after this you have killers and then some heuristics for general moves not yet considered (history tables, PST values, can also filter SEE < 0 noncaptures in general to the end of the list) but with just the TT move and capture ordering you should already be saving nodes and the time spent on move ordering.

[theturk1234]

Thanks guys for all the ideas! I had no idea move ordering was so complicated!
I'll be posting here frequently when I have questions that I'm stuck on.
Keep up the good work guys!

David Cimbalista