Move ordering

[hgm]

Conventional move ordering is something like
1) Null move
2) Hash move
3) Good and equal captures (ordered by SEE, MVV/LVA or mixed)
4) Killers
5) Non-Captures (perhaps ordered by history scores)
6) Bad captures

Now it seems to me that this ordering is often obviously sub-optimal, as it more or less ignores defensive moves. If my Queen is just put under attack by a Pawn, moves that don't do anything about this are doomed. And the moves that do something about it, like moving the Queen away to a safe square, do come pretty late in the standard ordering. Unless it is the hash move, of course, but in nodes were the hash move is good, move ordering is not really an issue, as we don't even get to generating moves there in the first place. And if the hash move, saving the Queen, turns sour on increasing search depth, we have to fall back on the move ordering to find a better way to save the Queen.

Trying good and equal captures on Knights and Bishops is an obvious waste of time, in such a situation. Moves that save the Queen are unlikely to be killers, as they become necessary only in reply to the previous (Pawn) move, while killer slots tend to be taken by moves that are general refutations of all moves that do not address an existing threat. So the killer heuristic helps you to quickly find the refutation to all the moves that did not save the Queen (and where you thus were wasting your time on), where the killer at the next level will be PxQ. But it doesn't help you to save the Queen in the current ply.

So except where capturing the offending Pawn was possible, you would have to wait for the non-captures, and even if the history scores would help you to avoid withdrawals of the Queen to unsafe squares, there might be many offensive moves with other pieces that in general are better. A forced withdrawal is not that likely to be a good move. And if equal capture of the Pawn was possible, you would like it to be tried before good captures of other, minor pieces, both in violation of MVV and SEE ordering.

Standard move ordering thus is very ill suited to solve such a situation. Nevertheless, the situation is often very obvious, and easily recognized. If the null move fails low when CurEval >= Beta, the move that refutes it identifies a threat (usually the worst threat if there are more, the MVV or SEE ordering of captures in the reply node will see to that). So in cases were the null move is refuted by a capture, and you have to start searching real moves, an obvious measure would be to sort the threat evasions more in front. If the threatend piece is really valuable, the evasions might even have to go in front of the good captures.

Now classical evasions are withdrawal, capture of the attacker, interposing or defending. Capture of the attacker, when possible, seems the preferable solution, and the SEE value of it could be increased by the value of the threat. (This value could be verified by a SEE on the threatened piece, if we don't trust the upper bound given by the null-move score.) Similarly, the 'SEE value' of moves with the threatened piece should also be increased with the value of the threat, and be sorted with the good captures even if they are non-captures. Their own SEE value would have to be calculated as well, to make sure they go to a safe square, even if you don't do that normally for non-captures, because the move now is likely to get sorted so much in front that you really want to make sure it is a good one.

The witdrawal and capture evasions are easy to recognize, and require only a small modification to the normal sorting of the captures (adding the threat value if the piece is the threatened one or the victim is the attacker). The main difference occurs when you have finished searching all moves that with these modifications had SEE scores above the threat value. At that point you would want to try the non-losing non-capture withdrawals (requiring you to identify and SEE them), before continuing with the less-important winning captures.

It seems advisable to search a non-losing non-capture evasion as soon as you find it. There can't be any better non-captures. Only if the withdrawal also loses the piece (based on SEE), but perhaps with better compensation, you would want to make sure there are no better evasions before searching it, and sort it between the remaining captures based on how much it softens the loss.

We might be a little cautious, though. A strong piece (Q or R) might have many non-losing withdrawals, but when one of them doesn't work (after search) the reason why it doesn't work often generalizes to a large part of them. E.g. the piece might be (soft) pinned, or tied in defense to another piece. It might be advantageous to recognize this. If the refutation goes over the FromSquare, don't try any other withdrawals that do not stay on that ray. If the refutation captures a piece that was defended by the withdrawn piece, do not consider any other withdrawals that do not keep that piece defended. If the refutation captures a piece that was not defended by the withdrawn piece, you might even specifically look for a withdrawal that does defend it!

Now unfortunately, interposing and defending moves are a lot harder to recognize. But considering the effort we take sorting these early moves (calculating SEE scores) the tests needed to find them do not seem overly expensive. Defending of course only helps if the threatened piece was not of higher value than the attacker. Otherwise we don't have to consider it. But if defendng is an option (and we are out of withdrawals) going through the move list to find moves that defend or interpose, and try them immediately if the have a non-losing SEE, and sort them with the remaining captures otherwise, seems very worthwile.

Does anyone use techniques like this? If so, what is your experience? Do they help?

[FrancoisK]

Funnily enough, i have very recently tried something along this lines, as i also thought that, as for good captures, in the "big piece attacked by weak piece" situations, some good answers are obvious, at least at low depth.
It was a one-shot crude attempt that did the following :

After general IID (which in BugChess2 comes after my good captures and HMove if no legal move was found before and if Remaining Depth > 3),

If last move attacked ONLY one stronger piece (i wanted to keep the situation simple)
And no good capture was found on the attacking figure (last ordering phase),
And not in check
And no hash move nor IID move
And remaining depth <= 3

Then skip killers (as this is supposed to be a very local situation), put N moves leaving the attacked square OR checks, both with SEE >= 0 in front (i tried N = 2 and 5 if i remember well).
Then History moves and all remaining moves.

This first attemps gave a small increase in nodes at fixed depth (thus even not considering the -probably negligible- time overhead) on my 1200 position test set (with hash cuts disabled). (adding cheking moves improved the situation a little but not enough to call this an improvement).

BUT this is not enough for me draw conclusions as on the one hand i only tested with classical test suites,
not with my "real life BugChess2 game positions" test suite, a bad habit. And i had no time nor courage to try and find why and where i was losing nodes. As I feared it seems that even at low depth, in many of this situations my avoid moves were not the best moves (maybe because they are buggy )
On the other hand this first attempt can be refined a lot, maybe
- try not to skip killers : if the threat is negligible as compared to other things going on on the board, killers are better (and cheaper in term of time) than history moves.
- some avoiding moves might be better than other good captures as you suggested
- i had in mind to first only try this at ReaminingDepth <= 3 because these avoiding moves were more likely to be the right move at shallow depth.
I exected my IID to cheaply make this move go up if it was indeed a good move at bigger depth and find a better one if it was not.
Maybe it is a mistake as my IID is rather naive for now.
- try other interesting refinements you suggest.

I remain convinced that there is something to gain, but it will not be so easy, and the gain will be tiny (at least in my program).
I have put this aside for now, i think i can find easier improvements elsewhere, but i am not done with this.
I think Ed Shroder does give a little bonus for move escaping attacks in Pro Deo.
I would also be interested in reading about other experiments on this subject, hopefully more fruitful.

François

[ed]

I think Ed Shroder does give a little bonus for move escaping attacks in Pro Deo.

Since I evaluate every node I can do some static tricks, moves that escape from attacks are pushed upwards, moves that give away material are pushed downwards in the move list. It helps but not as much as one would expect.

Ed

[ed]

It's not so bad as you might think, after the queen is taken by the pawn alpha-beta works optimal because only a very small sub-tree is generated. I am not saying you should not try to improve this kind of situations, I am saying that you won't get a super speed-up improvement.

Ed

Conventional move ordering is something like
1) Null move
2) Hash move
3) Good and equal captures (ordered by SEE, MVV/LVA or mixed)
4) Killers
5) Non-Captures (perhaps ordered by history scores)
6) Bad captures

Now it seems to me that this ordering is often obviously sub-optimal, as it more or less ignores defensive moves. If my Queen is just put under attack by a Pawn, moves that don't do anything about this are doomed. And the moves that do something about it, like moving the Queen away to a safe square, do come pretty late in the standard ordering. Unless it is the hash move, of course, but in nodes were the hash move is good, move ordering is not really an issue, as we don't even get to generating moves there in the first place. And if the hash move, saving the Queen, turns sour on increasing search depth, we have to fall back on the move ordering to find a better way to save the Queen.

Trying good and equal captures on Knights and Bishops is an obvious waste of time, in such a situation. Moves that save the Queen are unlikely to be killers, as they become necessary only in reply to the previous (Pawn) move, while killer slots tend to be taken by moves that are general refutations of all moves that do not address an existing threat. So the killer heuristic helps you to quickly find the refutation to all the moves that did not save the Queen (and where you thus were wasting your time on), where the killer at the next level will be PxQ. But it doesn't help you to save the Queen in the current ply.

So except where capturing the offending Pawn was possible, you would have to wait for the non-captures, and even if the history scores would help you to avoid withdrawals of the Queen to unsafe squares, there might be many offensive moves with other pieces that in general are better. A forced withdrawal is not that likely to be a good move. And if equal capture of the Pawn was possible, you would like it to be tried before good captures of other, minor pieces, both in violation of MVV and SEE ordering.

Standard move ordering thus is very ill suited to solve such a situation. Nevertheless, the situation is often very obvious, and easily recognized. If the null move fails low when CurEval >= Beta, the move that refutes it identifies a threat (usually the worst threat if there are more, the MVV or SEE ordering of captures in the reply node will see to that). So in cases were the null move is refuted by a capture, and you have to start searching real moves, an obvious measure would be to sort the threat evasions more in front. If the threatend piece is really valuable, the evasions might even have to go in front of the good captures.

Now classical evasions are withdrawal, capture of the attacker, interposing or defending. Capture of the attacker, when possible, seems the preferable solution, and the SEE value of it could be increased by the value of the threat. (This value could be verified by a SEE on the threatened piece, if we don't trust the upper bound given by the null-move score.) Similarly, the 'SEE value' of moves with the threatened piece should also be increased with the value of the threat, and be sorted with the good captures even if they are non-captures. Their own SEE value would have to be calculated as well, to make sure they go to a safe square, even if you don't do that normally for non-captures, because the move now is likely to get sorted so much in front that you really want to make sure it is a good one.

The witdrawal and capture evasions are easy to recognize, and require only a small modification to the normal sorting of the captures (adding the threat value if the piece is the threatened one or the victim is the attacker). The main difference occurs when you have finished searching all moves that with these modifications had SEE scores above the threat value. At that point you would want to try the non-losing non-capture withdrawals (requiring you to identify and SEE them), before continuing with the less-important winning captures.

It seems advisable to search a non-losing non-capture evasion as soon as you find it. There can't be any better non-captures. Only if the withdrawal also loses the piece (based on SEE), but perhaps with better compensation, you would want to make sure there are no better evasions before searching it, and sort it between the remaining captures based on how much it softens the loss.

We might be a little cautious, though. A strong piece (Q or R) might have many non-losing withdrawals, but when one of them doesn't work (after search) the reason why it doesn't work often generalizes to a large part of them. E.g. the piece might be (soft) pinned, or tied in defense to another piece. It might be advantageous to recognize this. If the refutation goes over the FromSquare, don't try any other withdrawals that do not stay on that ray. If the refutation captures a piece that was defended by the withdrawn piece, do not consider any other withdrawals that do not keep that piece defended. If the refutation captures a piece that was not defended by the withdrawn piece, you might even specifically look for a withdrawal that does defend it!

Now unfortunately, interposing and defending moves are a lot harder to recognize. But considering the effort we take sorting these early moves (calculating SEE scores) the tests needed to find them do not seem overly expensive. Defending of course only helps if the threatened piece was not of higher value than the attacker. Otherwise we don't have to consider it. But if defendng is an option (and we are out of withdrawals) going through the move list to find moves that defend or interpose, and try them immediately if the have a non-losing SEE, and sort them with the remaining captures otherwise, seems very worthwile.

Does anyone use techniques like this? If so, what is your experience? Do they help?

[Gerd Isenberg]

Conventional move ordering is something like
1) Null move
2) Hash move
3) Good and equal captures (ordered by SEE, MVV/LVA or mixed)
4) Killers
5) Non-Captures (perhaps ordered by history scores)
6) Bad captures

My current move-generation and move-picking scheme is a bit different.

In a pre-hash-probe step I determine all attacks, double attacks (disjoint pawn attacks are always cheap to determine on the fly) and a kind of a fixed sized movelist, aka 16-bitboards (plus some bytes for minor-promotions and castles) with all legal move-targets for all 16 directions (including the none-moves of sliding attacks to own pieces for some xray-tricks) plus one bitboard with all real move-targets ored together. If this bitboard is empty, it is either mate or stalemate.

Using sets of hanging pieces (not defended) and for the most simple cases even pieces en-prise (a kind of setwise SEE) of both sides is a matter of storing some once computed stuff to use it later during move-generation. I consider attacking and defending aspects inside my getmove, implemented as a finite state-machine traversing statefull sets, "generating" and picking one "most plausible" move per call. One state is for instance - move an attacked, hanging white bishop - or a double- or pawn attacked white bishop - to a "safe" square in north-west direction, but not "diagonal behind" an own pawn. Safe squares are squares not attacked at all - or only attacked once (but not by pawn) and defended. States oscillate beween considering more attacking or defending aspects.

I don't use other movelists any longer in this fillbased and setwise approach, except for the root. Beside some initial move-generation-states related to full/medium/qsearch-layer, there are options to consider node-types like pv, (weak, strong) cut or all, to eventually shortcut some states to traverse more general from- and "statefull" to-sets. Putting an en-prise queen to some safe square at expected cut-nodes with no hash-move near the tips seems a good idea imho, while it likely don't cares in futile all-nodes.

Does anyone use techniques like this? If so, what is your experience? Do they help?

Still a lot of work to finish - but I believe in it

[Aleks Peshkov]

I don't use other movelists any longer in this fillbased and setwise approach, except for the root.

What is special with rooks?

[Gerd Isenberg]

I don't use other movelists any longer in this fillbased and setwise approach, except for the root.

What is special with rooks?

Nothing. En-prise rooks are handled similar after en-prise queen state and before bishops/knights.

I mean the root-node. Moves generated once into a single list and sorted after each iterative deepening.

[Michael Sherwin]

Since iterative deepening is used, is not a move that will avoid the PxQ move going to be the hash move most of the time except at the leaf nodes? So would just altering the normal move ordering at the leaf nodes give the most benifit? However, it is really fast and efficient by qsearch to dismiss moves that do not save the Queen isn't it? Taking the time to find the situation beforehand seems like trading a dollar for three quarters.

[hgm]

Yes, IID helps to ameliorate such problems. But it still cannot do everything:

1) Most nodes are leave nodes! Being totally unaware of defensive moves might make you discover on the average the cut-move only at the 10th try. (If you have 40 moves, a Queen is responsible for quite a lot of them, so chances that you pick a withdrawal don't seem so bad. But you systematically sort other moves, that are not withdrawals, in front of it.) This means you waste work on a search of 9 moves that fail low before you get the one that fails high. This is simply 10 times as much work in any node where it happens. And situations where the opponent happens to attack one of your pieces are not that uncommon.

2) IID might pick out a move that saves the Queen at d=1. But even if you sort cut-moves permanently in front, rather than just making them hash move, the nature of IID is such that you revisit an inner node several times (because of the deepening at nodes below it, and eventually at the root). And if you come back to the node at higher depth all information about the move sorting is forgotten. You try the hash move, which will be a withdrawal. But if you are close to the PV score, it might be essential to pick the best evasion, and the which of the evasions is best is likely to be dominated by moves that follow the withdrawal. It is thus quite likely that you will have to switch to other evasions, perhaps a few times, before your search stabilizes. And on each switch you would fall back on the standard move ordering. It would then really help if all the evasions were tried before any moves that simply blunder away the Queen. Although it is true that these blunders are easy to refute, as Queen captures are tried first, it is also a fact that refuting by a capture can be more expensive than refuting by a null move.

3) In all-nodes IID doesn't help at all, as even the reasonable moves fail low.In situations where an all node reverts to a cut-node at high depth (because the opponent was merely stalling an unavoidable loss, which can be just an positional catch-up if you are close to the PV), the first cut-move will appear at quite high search depths. It would be convenient if you tried the moves first that at least have a chance to become cut-moves (i.e. don't have blundered away the Queen already on the fiirst ply).

In cases where CurEval < Beta (which is the common situation in all-nodes, so case (3)) you usually don't do null move, though. And even if you do, it is easily refuted by another null move (a legitimate one...), so you don't learn a lot of it. So it might be smarter not to rely on the result of the null-move score (which is only a bound anyway), but really look for threats against your own pieces through SEEing all enemy captures.

[Michael Sherwin]

I would suggest then to look for the condition of PxQ and it's evasions only after returning from making a leaf node move, where the score returned, failed low plus a margine. That should save a lot of work and be quite efficient.