out of check move ordering

[Don]

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...

I don't based any decisions on the possibility that we might use a book because I think it's important to optimize komodo to play the whole game (even the opening) as well as possible. Even though a good book might make it possible to ignore the opening, we feel that it benefits the program to understand this phase anyway. And yes, we expect in any important game to be using the book but as I say we don't optimize for that.

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.

I don't think you read my post where I admit that my intuition on this could easily be wrong and drew attention to the fact that if you interpose you are putting yourself in a self-pin. So don't get nasty with me, I am sympathetic to your point of view on this. You have said nothing here I don't already understand - I am a fairly strong tournament chess player.

As I said, I almost always try things both ways, because I know that whatever I think is correct has about a 50% chance of being the case. I have discovered that most people who are sure they are correct about something are right about 50% of the time

Don

[bhlangonijr]

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.

For quiet moves I sum up history values with PST deltas (PST(piece,to)-PST(piece,from)) and taking into account the game phase. It seems to help a bit.

Code: Select all

const int hist = history[pieceFrom][move.to];
const GamePhase phase = board.getGamePhase();
const int gain = board.getPieceSquareValue(pieceFrom,move.to,phase)-board.getPieceSquareValue(pieceFrom,move.from,phase);
move.score=hist+gain;

EDIT: It seems SF uses a similar scheme, but only using PST deltas when there is no history value.
Regards,

[Ferdy]

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.

In addition another idea would be to classify the piece checker and act accordingly.

If it is a pawn, then king move in front of a pawn, king move along the file of a pawn blocking it in its path

If a knight checker then king move close to the checker, king move to a color opposite to the color of the checker so that it can not check again, king move to a square where there are more than one safe squares around it for future mobility.

If a bishop checker then king move opposite to the color of the bishop, king moves that goes to same bishop color but hides on pawns or bishop or knight, the king hides because it protects some important squares there.

If a rook checker then king move to a square where it will not be cut off from important zone on the board, a rook cover, a safe pawn, and minor piece cover moves.

If a queen checker, then a safe pawn, bishop and rook counter attack covers, safe queen cover, king move to squares where there are more safe squares around, safe non-counter attack covers.

And of course factor in the number of opp pieces on the board, the number of opp rooks on the board and the number of opp bishops on the board, the number of open files controlled by opp rooks on the board.

[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.

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

Take into account that checks in middlegame are less frequent than in the endgame. But I agree in general with what you say.

Miguel

[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.

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.

I tried the refutation table idea you suggested and get no speedup.

However, the idea of putting king moves first may be a win. It's too early to say for sure, but it appears to be about a 1.5 percent node reduction, as measured by a couple of thousand 8 ply games. I need to see 10 or 20 thousand games to get a clearer picture.

Here is a question for the group - we don't reduce out of check or prune them although I know some program do. So given that I don't, does improving the out of check move ordering improve the strength of the program as measured by a fixed depth search? For example should the results of the 8 ply test be positive or neutral? I have always assumed in such a case that there should be no strength change whatsoever (other than that attributed to any extra speedups). But several recent experiments have consistently indicated otherwise. I seem to be getting a couple of ELO for the versions that have reduced nodes and lose an ELO or 2 for the other version.

It's hard to say for sure because I have only run 60,000 games or so at 8 ply and the error margin makes it still ambiguous, but several tests have seemed to indicate a small difference. It does have a small impact on the order moves get stored and overwritten (or not get stored) in the hash table, so if it helps it could be slightly impactful.

[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.

For quiet moves I sum up history values with PST deltas (PST(piece,to)-PST(piece,from)) and taking into account the game phase. It seems to help a bit.

That seems to be a very sensible things to do. I will probably try that next.

Code: Select all

const int hist = history[pieceFrom][move.to];
const GamePhase phase = board.getGamePhase();
const int gain = board.getPieceSquareValue(pieceFrom,move.to,phase)-board.getPieceSquareValue(pieceFrom,move.from,phase);
move.score=hist+gain;

EDIT: It seems SF uses a similar scheme, but only using PST deltas when there is no history value.
Regards,

[bob]

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.

I think the issue is that you have to address the most common case. And for escaping checks, by far the most common case is after castling rights are gone. Interposing is dangerous because you just walked into an absolute pin where the interposing piece can not not legally move (unless it moves in the direction of the pinning piece).

I experimented with this stuff when I wrote my generate check evasion code. I'd take capturing the checking piece first (assuming SEE agrees), followed by moving the king. If it is a double check, you move the king, period...

[hgm]

It's hard to say for sure because I have only run 60,000 games or so at 8 ply and the error margin makes it still ambiguous, but several tests have seemed to indicate a small difference. It does have a small impact on the order moves get stored and overwritten (or not get stored) in the hash table, so if it helps it could be slightly impactful.

It would be much more effective to take statistics directly from the positions. Just suppress beta cutoffs on check evasions, so you will always search all moves, add some code to classify the moves as King move, counter-attacking SEE-safe interposition, other SEE-safe interposition, losing interposition. And then take statistics of how many times each class was able to achieve the cutoff,and perhaps more importantly, how often it occurred that a move of class A caused a cutoff, while no move of class B caused a cutoff, for every combination of A and B. That should tell you in a much more certain way what class you'd better put your money on than looking for a tiny speedupin games.

Btw, I thought of another way to refute your your argument that it is important that in opening theory you usually interpose:

The point is that interposing puts you in a pin, which you often only can solve by moving the King away later. So in the best case the interposing is just a waste of time. Now in the opening this is often not a problem, becase you planned to move the King anyway, by castling. And you will not be able to do it immediately, because castling out of check is not allowed (and there might still be pieces blocking the castling). So you interpose an undeveloped piece (so it is not a waste of time), and then solve the pin quickly afterwards by castling. So it is really a very special case, that tells you preciously little about what is best in general. This does suggest it wold be useful to take the availability of castling rights (which you presumably would want to use) into account in the classification of evasions.

[Don]

It's hard to say for sure because I have only run 60,000 games or so at 8 ply and the error margin makes it still ambiguous, but several tests have seemed to indicate a small difference. It does have a small impact on the order moves get stored and overwritten (or not get stored) in the hash table, so if it helps it could be slightly impactful.

It would be much more effective to take statistics directly from the positions. Just suppress beta cutoffs on check evasions, so you will always search all moves, add some code to classify the moves as King move, counter-attacking SEE-safe interposition, other SEE-safe interposition, losing interposition. And then take statistics of how many times each class was able to achieve the cutoff,and perhaps more importantly, how often it occurred that a move of class A caused a cutoff, while no move of class B caused a cutoff, for every combination of A and B. That should tell you in a much more certain way what class you'd better put your money on than looking for a tiny speedupin games.

Btw, I thought of another way to refute your your argument that it is important that in opening theory you usually interpose:

There is no need to refute me, I am completely open on this issue.

However, I think this is not so clear cut. I think intuitively your thinking is that when in check a king move is more likely to be the best move. But is that really the issue? There are usually multiple king moves, so unless you classify them, the question is whether a random king move is likely to be better than a random interposition. Most king moves in chess are horrible moves. That may be also true of interpositions, but I think it is important to make sure that you are really thinking correctly on things like that and it's still not obvious to me. The version which orders king moves before interpositions did not prove to be an improvement - so I am back at square one.

The point is that interposing puts you in a pin, which you often only can solve by moving the King away later. So in the best case the interposing is just a waste of time. Now in the opening this is often not a problem, becase you planned to move the King anyway, by castling. And you will not be able to do it immediately, because castling out of check is not allowed (and there might still be pieces blocking the castling). So you interpose an undeveloped piece (so it is not a waste of time), and then solve the pin quickly afterwards by castling. So it is really a very special case, that tells you preciously little about what is best in general. This does suggest it wold be useful to take the availability of castling rights (which you presumably would want to use) into account in the classification of evasions.

[hgm]

- so I am back at square one.

Well, try to take the statistics then. Or just let the search print positions where you are in-check in a cut-node to a file (perhaps with a small probability, to get a bearable number of them, like 1000, after some 100 games), and then look at a few of them to see what you would think the most obvious defence would have been in that case, and if there would be a simple heuristic that could have made the engine see it too. (Or perhaps only print cases where it found the cutmove quite late.)