out of check move ordering

[Don]

Any secrets here for out of check move ordering? I'm experimenting with this now.

Komodo keeps separate out of check killers, but a recent experiment seems to indicate that this may actually hurt the performance slightly.

We are only talking about a fraction of a percent node reduction probably, but I'm trying to squeeze and I have never given this issue much attention.

Right now we do:

1. hash table move
2. good captures
3. killers ?? (probably not)
4. history ordering
5. bad captures.

The history ordering is not particularly valid for out of check moves, but it appears to be better than doing nothing.

I want to experiment with putting king moves at the end of the list next.

[hgm]

A good capture (necessarily of the checker) should definitely go first after the hash. For the rest it is very hard to guess. Of the legal moves,only interpositions and withdrawal are left. Interposition is often preferable (if it is a solidly defended piece of low value, or a piece that counter-attacks the checker), but equally often disastrous (if it is not defended, or walks into a dangerous pin). Withdrawal is preferable if you can withdraw to a safer square, disastrous if it is an unsafer square.

Why not make a new heuristic for this? For every (from,to) pair of the check, keep an evasion killer, which stores the last succesful evasion out of that check? That seems to make sense, as a human I prepare for possible invasions of my King fortress by planning an escape route in advance. The path through which you flee to safety should be quite constant through the entire tree.

If you do pseudo-legal move generation it might also help to get an instant evasion, before generating moves and testing all of them for legality. Just take the evasion killer corresponding to the check, and test that for legality.

[Don]

A good capture (necessarily of the checker) should definitely go first after the hash. For the rest it is very hard to guess. Of the legal moves,only interpositions and withdrawal are left. Interposition is often preferable (if it is a solidly defended piece of low value, or a piece that counter-attacks the checker), but equally often disastrous (if it is not defended, or walks into a dangerous pin). Withdrawal is preferable if you can withdraw to a safer square, disastrous if it is an unsafer square.

the current move ordering always puts losing moves at the end of the list for out of check and it always tries captures first (after hash table move) in the standard MVV/LVA order. A legal king move can never be losing, but I'm now trying putting the king moves last and trying interpositions immediately after the captures. These will of course be non-losing interpositions since losing move go to the end.

Why not make a new heuristic for this? For every (from,to) pair of the check, keep an evasion killer, which stores the last succesful evasion out of that check? That seems to make sense, as a human I prepare for possible invasions of my King fortress by planning an escape route in advance. The path through which you flee to safety should be quite constant through the entire tree.

That sounds like a reasonable idea - I will give it a try.

If you do pseudo-legal move generation it might also help to get an instant evasion, before generating moves and testing all of them for legality. Just take the evasion killer corresponding to the check, and test that for legality.

Komodo always tries to not generate moves - it tries any type of killer before generating moves and of course the hash table move is tried before proceeding beyond this. So this fits naturally into the structure of Komodo.

[hgm]

A legal king move can never be losing, but I'm now trying putting the king moves last and trying interpositions immediately after the captures. These will of course be non-losing interpositions since losing move go to the end.

The problem is that even 'non-losing' interpositions can be immediately losing, because you are voluntarily walking into a pin. Like 1. Qa4+ Nc6 2. d5! (2. Qxc6? bxc6). So in general interposition is suspect, as it always creates a pin, while King moves do not. To qualify as 'safe' an interposition should not only be SEE-safe, but either be Pawn defended by Pawn, or counter-attack the checker (1. Qa4+ Bd2 is more than OK). In a purely static ordering (without the benefit of collected search stats) I would expect it to pay off to make that difference. First (good) counter-attacking interpositions, then Pawn defended by Pawn, then King stepping into the corner (if not open file), then other King moves, then other good interpositions, then losing captures, then losing interpositions.

[bob]

Any secrets here for out of check move ordering? I'm experimenting with this now.

Komodo keeps separate out of check killers, but a recent experiment seems to indicate that this may actually hurt the performance slightly.

We are only talking about a fraction of a percent node reduction probably, but I'm trying to squeeze and I have never given this issue much attention.

Right now we do:

1. hash table move
2. good captures
3. killers ?? (probably not)
4. history ordering
5. bad captures.

The history ordering is not particularly valid for out of check moves, but it appears to be better than doing nothing.

I want to experiment with putting king moves at the end of the list next.

I only do (1), then (2), and then rest of moves. I have tried several schemes but nothing really helped beyond those. I haven't used history ordering for 10+ years now as I found it to be of no help at the depths being searched today...

[mcostalba]

Right now we do:

1. hash table move
2. good captures
3. killers ?? (probably not)
4. history ordering
5. bad captures.

It is like we do in SF apart from the killers the we don't use in evasions. I think any improvement in this area is at best a second order improvement, but these days I agree it is better than nothing

I want to experiment with putting king moves at the end of the list next.

Instead I will do the opposite because I have the feeling that king moves are better than interpositions

[Don]

Right now we do:

1. hash table move
2. good captures
3. killers ?? (probably not)
4. history ordering
5. bad captures.

It is like we do in SF apart from the killers the we don't use in evasions. I think any improvement in this area is at best a second order improvement, but these days I agree it is better than nothing

I want to experiment with putting king moves at the end of the list next.

Instead I will do the opposite because I have the feeling that king moves are better than interpositions

My reasoning is that king moves are almost always blunders if you have not get castled. Most opening theory has checks answered by interpositions. Also, interpositions are never blunders as I apply see() to the out of the check moves, so these are usually going to be safe interpositions.

However, you could be right, in my mind I was only focused on these cases but it's also true that interposing produces a self-pin. And in the ending it's likely a king move is the way to go.

But I generally try things in many combinations, the way I think it should be, the way I don't think it should be, because my intuition is often incorrect.

[michiguel]

Right now we do:

1. hash table move
2. good captures
3. killers ?? (probably not)
4. history ordering
5. bad captures.

It is like we do in SF apart from the killers the we don't use in evasions. I think any improvement in this area is at best a second order improvement, but these days I agree it is better than nothing

I want to experiment with putting king moves at the end of the list next.

Instead I will do the opposite because I have the feeling that king moves are better than interpositions

My reasoning is that king moves are almost always blunders if you have not get castled.

Not in the endgame. A king moves towards the center has good chances to be a good move.

Miguel

Most opening theory has checks answered by interpositions. Also, interpositions are never blunders as I apply see() to the out of the check moves, so these are usually going to be safe interpositions.

However, you could be right, in my mind I was only focused on these cases but it's also true that interposing produces a self-pin. And in the ending it's likely a king move is the way to go.

But I generally try things in many combinations, the way I think it should be, the way I don't think it should be, because my intuition is often incorrect.

[Don]

Right now we do:

1. hash table move
2. good captures
3. killers ?? (probably not)
4. history ordering
5. bad captures.

It is like we do in SF apart from the killers the we don't use in evasions. I think any improvement in this area is at best a second order improvement, but these days I agree it is better than nothing

I want to experiment with putting king moves at the end of the list next.

Instead I will do the opposite because I have the feeling that king moves are better than interpositions

My reasoning is that king moves are almost always blunders if you have not get castled.

Not in the endgame. A king moves towards the center has good chances to be a good move.

Miguel

Most opening theory has checks answered by interpositions. Also, interpositions are never blunders as I apply see() to the out of the check moves, so these are usually going to be safe interpositions.

However, you could be right, in my mind I was only focused on these cases but it's also true that interposing produces a self-pin. And in the ending it's likely a king move is the way to go.

But I generally try things in many combinations, the way I think it should be, the way I don't think it should be, because my intuition is often incorrect.

Yes, that's why I said in the ending king moves is the way to go.

But given a choice, you generally want to optimize middle game performance, since you don't even get to the endgame if you walk your king out to the center. If you increase your middlegame ELO 20 ELO the program is almost 20 ELO stronger. If you increase your endgame ELO by 20, you have increased the overall playing strength perhaps only 5 ELO at most.

So one possibility is to use the piece square table appropriate the stage of the game for ordering king moves - and hopefully get the best of both worlds.

Don

[hgm]

If you have castling rights, it is a different matter. But during most of the game you will not, and when you have a book, you will virtually never search a position where you have castling rights. So focusing on this is even worse than optimizing for the end-game, which at least you might reach...

A castled King does not lose rights when moving, nor does it necessarily move towards the center. Kc3-b3 is a quite sound move after Q-side castling, Kg8-h8 is played in many games. You still seem to ignore my point that SEE-safe interpositions can be horrible blunders. Again, that in opening theory it is sometimes good, should be of little concern when you use book. During most of the game you don't have a large supply of pieces that weren't doing anything because they were not yet developed, so that getting them pinned does not make the situation much worse.Especially as the opponent is also not yet developed enough topunish you for it.