move ordering especially ordering&searching of root move

[Lyudmil Tsvetkov]

I guess a major flaw of standard move-ordering techniques as found in engines, is that they rely too much on previous performance of a move (history tables, etc.), and too little of the objective quality of the move in the new setting at a bigger depth. relying on previous performance means relying on eval scores throughout different depths, which migth not be the perfect approach taken into account engines' far from perfect eval.

as I see it currently, modern top engines use too few flags to order their moves, and there are, of course, much much more important patterns than whether a move is a capture, winning capture, simply quiet move, etc. for example, it matters very much if the move is close to the enemy king or far from it, whether it creates some threat, though not executing it, etc., etc. Top engines seem to not quite take this into account, at least that is what I see from SF's choice of moves.

What you have to remember is that most move sequences considered by engines are blunders. When they hang a queen, you want to capture it immediately. That's why you have to sort captures (especially winning captures) first.
Once you're past that, you need some way to sort moves that are not obviously good (because they win you a queen). There are two approaches:
1. Hard code all patterns that you can think of. This requires a lot of work, and a lot of testing for special cases (I mean the code needs to do a lot of tests, not that it needs to be heavily tuned, though that is also true).
2. Use general guidelines and allow the code to figure out what works and what doesn't during search.

The first approach is like you suggest. This is not scalable and a maintenance nightmare. It's also slow because it needs to do a lot of work. The second is what most (all?) programs do, using things like killer tables and history. Good programs are good not in spite of doing (2) instead of (1), but because they don't waste time doing (1) when (2) will do.

Now, you probably could write a neural network that aims to do (1). I think Giraffe might have that? The issue is setting up and training said network.

problem is that (2) does not quite do very satisfactorily. at least from what I see in SF, it misses an awful lot of good moves, just because it orders them very low or does not consider at all; once the move is shown to the engine, it understands it value immediately, so its eval is sufficient in this case.

I suppose all engines do use some kind of neural network, though most of those networks are quite primitive. Once you manage to create a sufficiently ample network and tune its parameters appropriately, the engine should play at a quite acceptable level.

one thing I noticed about eval in the recent months while playing some engine matches, and that should certainlt be also true of move ordering, is that even as few as 3cps matter. I have always known this, but while watching engine games and see how a factor worth just 3 cps really makes a distinction and decides the game further on, is really striking.

so, I suppose, that the old assumption that, maybe, many best moves are just a matter of style, there migth be couple of first moves with almost equal scores, is a pure illusion. There seems to always be one single best move, significantly better than the rest, and this one best move could only be found by very refined eval, including very refined move ordering, otherwise you are more or less searching not entirely beneficial nodes.

[cdani]

problem is that (2) does not quite do very satisfactorily. at least from what I see in SF, it misses an awful lot of good moves, just because it orders them very low or does not consider at all; once the move is shown to the engine, it understands it value immediately, so its eval is sufficient in this case.

I know you have shown some examples already, but can you collect a few examples of this? Will be useful to test a few different search techniques or variations.
Thanks.

[Evert]

problem is that (2) does not quite do very satisfactorily. at least from what I see in SF, it misses an awful lot of good moves, just because it orders them very low or does not consider at all; once the move is shown to the engine, it understands it value immediately, so its eval is sufficient in this case.

Well, if you can write up an algorithm that actually does as you suggest (not a general description, but a full description of what it needs to test, including all exceptions), then perhaps someone can test it. What you suggest is too vague to translate into code. Note that I said algorithm, not code.

To get you started: I'm ordering moves, and the move under consideration is not a capture, promotion, castling or checking move. For kicks, let's say it is also not a killer move. How do you propose to order it?
I would order it based on counter-move, history, and plain centralisation, in that order.

so, I suppose, that the old assumption that, maybe, many best moves are just a matter of style, there migth be couple of first moves with almost equal scores, is a pure illusion. There seems to always be one single best move, significantly better than the rest, and this one best move could only be found by very refined eval, including very refined move ordering, otherwise you are more or less searching not entirely beneficial nodes.

Another caveat to consider for you: it's pretty easy to make an engine more efficient in a given position. That usually does not translate to better performance in actual games.

[PK]

Move ordering often behaves in counter-intuitive ways. For example, I recently observed no gain from the code that mixed piece/square score (adjusted to the game phase) with history score. Mixing history with crude centralization for everything but the king worked better.

Another strange thing is that I have never gained from the obvious idea of increasing score of piece moves that escape from a pawn capture and don't run into one. Probably history counters are good enough to detect such obvious escapes.

Yet another: I can gain a bit by sorting refutation moves higher or by escaping from a capture that refuted null move in the same node - but last time I tried, mixing those techniques resulted in a net loss.

[Ras]

1-what is the best ordering method for root moves ?

Dunno whether it's the "best", but it works fine:

a) order the root move list by MVV-LVA for captures/promotions, some special value for castling and some kind of centralisation/attack logic for the rest. Same as in the ID search.

b) if the opponent has replied with the expected PV move, put the PV answer move to the top of the list and shift the rest down by one.

c) perform each root move of the list and do a simple alpha-beta-minimax (plus QS at the leaves) with remaining depth=2 (this is total depth=3). Record the score for every root move in a temporary array.

d) sort the root move list by the scores of the score array.

e) repeat step b.

f) store the best move from the move list as failsafe move in case you run out of time before you can complete the regular ID at depth=3.

You can also use the temporary array with the scores to recognise easy moves. That will save precious thinking time in games with tournament or game-in time controls, and it avoids giving the opponent thinking time for a clear ponder hit.

Btw, how do you do your move list sorting? Do you actually sort, or do you have a selection sort called when fetching the next move from the list?

3-and should the root moves be ordered by a different technique before the first iteration of the ID ?

see item 1.

4-in the first iteration after making the root move (I use a different function for the IDLoop&rootSearch separate from the Main AlphaBeta ) , should the search descend directly into Qsearch (Call alphabeta with depth=0) or should it call alphabeta with search = 1 ?

After the pre-sorting from item 1, you can start directly with search depth=3 (plus QS). Actually, depth=3 has already been searched, but the idea is to get hash tables and PV recording involved, that gives quicker cutoffs at depth=4+.

5-Who are Capture-Promotion moves scored according to the MVV-LVA ?

As per the resulting material. Means, if you promote while capturing a knight, then you loose a pawn and win a knight plus a queen, and that is how the move should be regarded.

6-can the average effective branching factor during multiple games a good be used as indicative of the quality of move ordering ?

Not directly - because there are a lot of other factors that also have influence on the branching factor. Effectiveness of hash table management, various kinds of search pruning and search extensions for example.

[Lyudmil Tsvetkov]

Move ordering often behaves in counter-intuitive ways. For example, I recently observed no gain from the code that mixed piece/square score (adjusted to the game phase) with history score. Mixing history with crude centralization for everything but the king worked better.

Another strange thing is that I have never gained from the obvious idea of increasing score of piece moves that escape from a pawn capture and don't run into one. Probably history counters are good enough to detect such obvious escapes.

Yet another: I can gain a bit by sorting refutation moves higher or by escaping from a capture that refuted null move in the same node - but last time I tried, mixing those techniques resulted in a net loss.

precisely; best results are obtained, when redundancy=0. Tord once suggested that redundancy should be very low, but it is best if it is zero altogether. redundancy not only of eval, but of eval, move ordering and search, as the 3 are basically part and parcel of the same puzzle of evaluating the position as best as possible.

redundancy=0 does not mean we should have few parameters, even with 10 terms those migth well be redundant with gross definitions, but, having 1000 terms and taking care that almost no term is redundant to another in any way is the rigth approach, I think.

[Lyudmil Tsvetkov]

problem is that (2) does not quite do very satisfactorily. at least from what I see in SF, it misses an awful lot of good moves, just because it orders them very low or does not consider at all; once the move is shown to the engine, it understands it value immediately, so its eval is sufficient in this case.

I know you have shown some examples already, but can you collect a few examples of this? Will be useful to test a few different search techniques or variations.
Thanks.

I do not know what you mean exactly. if you mean some algorithm for ordering moves, I already have one for the engine that one day in the future migth see the day, but would like to first test first hand, before publishing.

the move ordering scheme is just a couple of pages pseudo-code, and, besides captures/history/killers, basically flags all moves in terms of not 3 or 4, but 20-30 different flags, underlining what moves are valuable: moves that are central, moves that are advanced, moves that are close to the enemy king, moves that create some threats, moves that gain some signifivant positional advantages, etc. when you assign those flags some scores, the best move should pop up rigth at the top, as an advanced central move will combine the central and advanced flags, it will further add check or capture bonus, if it also a capture, etc.

have not still tried this in practice, and it is very important that you find the correct values for the different flags, but I think the main idea is pretty sound, at least such an approach should see the moves SF does not see...

[cdani]

problem is that (2) does not quite do very satisfactorily. at least from what I see in SF, it misses an awful lot of good moves, just because it orders them very low or does not consider at all; once the move is shown to the engine, it understands it value immediately, so its eval is sufficient in this case.

I know you have shown some examples already, but can you collect a few examples of this? Will be useful to test a few different search techniques or variations.
Thanks.

I do not know what you mean exactly. if you mean some algorithm for ordering moves, I already have one for the engine that one day in the future migth see the day, but would like to first test first hand, before publishing.

the move ordering scheme is just a couple of pages pseudo-code, and, besides captures/history/killers, basically flags all moves in terms of not 3 or 4, but 20-30 different flags, underlining what moves are valuable: moves that are central, moves that are advanced, moves that are close to the enemy king, moves that create some threats, moves that gain some signifivant positional advantages, etc. when you assign those flags some scores, the best move should pop up rigth at the top, as an advanced central move will combine the central and advanced flags, it will further add check or capture bonus, if it also a capture, etc.

have not still tried this in practice, and it is very important that you find the correct values for the different flags, but I think the main idea is pretty sound, at least such an approach should see the moves SF does not see...

I mean chess positions that once the move is shown Stockfish see it as good

[Lyudmil Tsvetkov]

problem is that (2) does not quite do very satisfactorily. at least from what I see in SF, it misses an awful lot of good moves, just because it orders them very low or does not consider at all; once the move is shown to the engine, it understands it value immediately, so its eval is sufficient in this case.

I know you have shown some examples already, but can you collect a few examples of this? Will be useful to test a few different search techniques or variations.
Thanks.

I do not know what you mean exactly. if you mean some algorithm for ordering moves, I already have one for the engine that one day in the future migth see the day, but would like to first test first hand, before publishing.

the move ordering scheme is just a couple of pages pseudo-code, and, besides captures/history/killers, basically flags all moves in terms of not 3 or 4, but 20-30 different flags, underlining what moves are valuable: moves that are central, moves that are advanced, moves that are close to the enemy king, moves that create some threats, moves that gain some signifivant positional advantages, etc. when you assign those flags some scores, the best move should pop up rigth at the top, as an advanced central move will combine the central and advanced flags, it will further add check or capture bonus, if it also a capture, etc.

have not still tried this in practice, and it is very important that you find the correct values for the different flags, but I think the main idea is pretty sound, at least such an approach should see the moves SF does not see...

I mean chess positions that once the move is shown Stockfish see it as good

well, if presumably SF sees the best move in 1/2 of all positions (I guess the ration is more 1/4 to 1/8, as SF sees the very best move only rarely), in half of them the reason should be search issues, in the other half bad/insufficient eval. Just take any 4th random position, and SF will fail to see the best move due to search issues, where move ordering will play no small part.

I guess it pays off to slow your move generator and search a bit less nodes, provided that the engine uses some more time to order its moves appropriately.

one way or another, progress will come only slowly, I guess engines have made quite some progress in recent years. Most of the positions engines fail to solve are indeed difficult positions, requiring deeper search and more refined eval. and when it comes to closed positions, most of those (excluding building a fortress, which is the simplest position anyway) are on average around 3 times more difficult and require around 3 times deeper search and much more refined eval than even the most complicated open/semi-open position. so, it is only very natural that engines have most problems with the most complicated positions, I guess engines will fully see closed position patterns in only some 20-30 years on.

one way or another, there are more urgent problems with engines, for example, if one knows how to place the 4 central pawns in the opening, or even only the 2 central pawns closer to the kings in the opening, one should be able to win every single game against current tops. so, I guess, only knowledge about central pawn placement (all patterns worth more than 50cps) should win around 300-400 elo or more.