Checks and move ordering

[jwes]

I have been working on my move generator and now I know if a move gives check before I make it. Now I am wondering how I should use this information in move ordering, e.g. should a winning capture that gives check be tried ahead of winning captures that appear to gain more material, or should discoverd checks be tried ahead of all other moves, etc. I would be interested to hear what experiences others have with this.

[Bill Rogers]

Are stopping you search when you find a move that gives check? If check is discovered on the first or second move then I would search a little deeper before I made a determination. If, however, the check was made at the normal end of your search then that is a different question. Do you have a quesient search when discovering checks? One thing to remember by putting a man in check you are limiting the number of replys that your opponent can make which in many cases can be to your advantage.
Try if both ways and play the same game over and over again to see the results.
Bill

[Pradu]

I have been working on my move generator and now I know if a move gives check before I make it. Now I am wondering how I should use this information in move ordering, e.g. should a winning capture that gives check be tried ahead of winning captures that appear to gain more material, or should discoverd checks be tried ahead of all other moves, etc. I would be interested to hear what experiences others have with this.

The way I do it is order good captures first, then order checks that arn't good captures but those that SEE>=0.

[jwes]

My question is which move should I search first, not how deep should I search it.

[Pradu]

My question is which move should I search first, not how deep should I search it.

Good captures should be first regardless of whether they are checks or not. Checks should come later, atleast this is what I do. Of course these moves should SEE>=0.

Code: Select all

#define MOVEORDERING_HASHMOVE   2147483647
#define MOVEORDERING_CAPTURE    2147400000
#define MOVEORDERING_NULLKILLER 2147300002
#define MOVEORDERING_KILLER     2147300001
#define MOVEORDERING_KILLER2    2147300000

#define MOVEORDERING_EQUALCAP   2147200004
#define MOVEORDERING_CHECK      2147200003
#define MOVEORDERING_PASSER     2147200002
#define MOVEORDERING_ATTACKWEAK 2147200001
#define MOVEORDERING_MAXHIST    2147200000

[hgm]

My question is which move should I search first, not how deep should I search it.

These questions are intimately related. It is usually a bad idea to search a move first that is extended, even if it is the best move.

I am just working on equipping Joker with check awareness. After some contemplation, I opted for the following:

Discovered checks are considered captures. This means that non-capture discovered checks are sorted after good captures (as they can only have SEE <= 0). It also means they are searched even in QS. (This might be risky, in connection with perpetual discovered checks. I rely on such perpetuals leading to rapid 3-fold repetition.)

Other checks are not treated special w.r.t. move ordering per se, but they should be exempted from futility pruning.

If checks occur at d<=1 I extend them to d=2 (i.e. the reply to d=1), to avoid stand pat on the check. Other checks are not extended. So there is no reason to sort them behind other non-captures.

I treat 'nearly checks' (one enemy non-Pawn left between 'checker' and enemy King) as checks, as these are on the average just as dangerous: the piece will be attacked and pinned with the same move.

[jwes]

It is usually a bad idea to search a move first that is extended, even if it is the best move.

I don't understand this. The only reason I can think of for not searching the best move first is that you are confident some other move will also fail high, and you won't have to search it at all. If you are that confident, it might be even better to just return a fail high and not search any moves.

[Uri Blass]

My question is which move should I search first, not how deep should I search it.

These questions are intimately related. It is usually a bad idea to search a move first that is extended, even if it is the best move.

I am just working on equipping Joker with check awareness. After some contemplation, I opted for the following:

Discovered checks are considered captures. This means that non-capture discovered checks are sorted after good captures (as they can only have SEE <= 0). It also means they are searched even in QS. (This might be risky, in connection with perpetual discovered checks. I rely on such perpetuals leading to rapid 3-fold repetition.)

Other checks are not treated special w.r.t. move ordering per se, but they should be exempted from futility pruning.

If checks occur at d<=1 I extend them to d=2 (i.e. the reply to d=1), to avoid stand pat on the check. Other checks are not extended. So there is no reason to sort them behind other non-captures.

I treat 'nearly checks' (one enemy non-Pawn left between 'checker' and enemy King) as checks, as these are on the average just as dangerous: the piece will be attacked and pinned with the same move.

Some comments:
1)I disagree that it is usually a bad idea to search a move first that is extended, even if it is the best move..

I have the following comments about it:
a)The question is not if it is extended but how much time do you search it that is close to be proportional to the number of nodes that you expect to search that move.

I do not believe in the thoery that extended moves are searched always for more nodes.

checks limit the number of replies of the opponent so without extending them it is obvious that you can expect less nodes for searching checks.

If you extend them it is not clear that you can expect more nodes after checking moves and one of the questions is how much you extend.

b)even when searching checks is more expensive it is not clear that searching it first is a bad idea because if the check is the best move you save nodes and you may save more than you lose from the case that check is not the best move.

If you search 10% faster with probability of 90% and search 30% slower with probability of 10% you practically save time.

2)I think that your idea not to extend checks when the remaining depth is bigger than 1 is bad.

This idea means simply that checks are searched for less time and I see no reason to use less time for checks.

The reason is that check reduce the number of legal moves of the opponent relative to non checks and make it easier to search to the same depth.

Uri

[hgm]

The object of move ordering is to minimize the tree size. In alpha nodes the move ordering is irrillevant, since eventually you will have to search all moves anyway, and none of the earlier moves affects the window size for the search of the later ones, as they all fail low. So you do the move ordering on the assumption that you are in a beta node.

In a beta node any non-cut-move you search is a waste of time. If there are more cut-nodes, you would like to search the one with the smallest sub-tree. This is, for instance, why you search the null move before the other moves, as the reduction makes it a very cheap move. Of course none of this is known in advance, so you have to gamble.

Uri describes the proper way to evaluate such gambles. Say you have three moves that might be cut moves, and one is twice as likely to be the cut-move as the other (so 50%-25%-25%) but it takes 3 times longe3 to search it (so search times 3-1-1). If you search the most-likely cut move first, you have 50% probability that you are done after 3, 12.5% that you are done after 4, and 1/2*3/4*1/4 = 3/32 that you are done after 5. On the average 1/2*3 + 1/8*4 + 3/32*5 = 48/32 + 16/32 + 15/32 = 79/32. If you search both cheap moves first you will have a probability of 25% that you find a cut-move after 1, 3/4*1/4=3/16 that you find it after 2, and 3/4*3/4*1/2 = 9/32 that you find it after 5, so on the average after 1/4*1 + 3/16*2 + 9/32*5 = 8/32 + 12/32 + 45/32 = 65/32. On the average you will thus spend less search time if you try the less likely, but cheaper cut-move candidates first, as 65 < 79.

This is quite different from not searching any moves at all, and just gamble that you will have a cut-off: in 9 out of 32 cases this would be plain wrong. Sorting the cheaper moves first is never wrong, and on the average even faster (in this example).

So it all depends on how much more expensive it is to search the check, and how much more likely it is to be a cut-move. Now statistically only a very small fraction of the checks are checkmates. As a non-capture check does not gain you any material in the move itself, any gains would have to come from that it is a fork threat. But fork threats are rare. Or the threat would have to exist already, but then you might better try to cash on it first, rather than delaying it with a pointless check.

So it is questionable if checks are so much more likely to be a cut-move, other than through the effect that if you already have a cut-move, you could still do it after the check+evasion. So the question is how much more expensive they are. It is true that the number of moves you have while in check is usually a lot lower than when not in check. But it is usually also larger than one. And if it is two, giving the extension would still double the tree size. (If the check is a cut-move, the evasions will take place in an all node. Even if the check fails low, it is questionable if he would find the cut-move evasion on the first try, as usual move ordering is not tuned to in-check positions. Unless he can capture the checker, of course, but checks with SEE<0 are not really likely cut-move candidates in the first place, and probably sorted with the bad captures.)

So on the average I would expect extended good checks to have about 3 times larger search trees than not-extended moves. The probability that a check would be a cut-move most likely ranks with other useful non-captures such a threat evasions, chasing away opponents pieces or good positional moves. (Bishops or Knights that you attack with lower pieces usually have to move to worse squares, and thus gain you eval points. On the other hand, tha fact that you can give check in the first place already shows that the King was on a poor square, and it is likely to flee to a square with better King safety.) As they are more expensive to search, I would thus sort them behind such other non-captures.

I don't think that one should search something just because it is cheaper than searching something else per unit of depth. What really matters if how much accuracy you gain compared to the number of nodes you invest. I don't see a reason why a line that has a check somewhere close to the root in it would be evaluated less reliably than any other line of the same depth. The reason I extend is that I want to know if it is checkmate. If I search deep enough to recognize that, and still live, it was apparently not a very dangerous check.

Of course you might argue that after the check evasion the King safety might have changed drastically, and a deeper search is needed to find if the King can survive there. But in that case it would be better to extend lines with a bad King safety, (which could have been triggered by many other moves than check). Lines with bad King safety indeed need deeper search to give the same reliability.

[Uri Blass]

In my case finding if the check is checkmate is not a reason to extend
because the first thing that I do after making a check is finding if the move ic checkmate.

If you extend for this purpose you need to generate all moves even in cases that the move is not checkmate.

In this case it is a waste of time and it is better simply to have a simple function that tell you if check is checkmate.

I guess that extending checks is productive for you for other things so replacing extending checks by a function that tell you if a check is checkmate is probably a bad idea.

extending checks help me to find checkmates(often there are some checks before giving checkmate)
extending checks help me to find cases when checks simply delay the loss in some line.

Here is an example

[D]1k6/7p/r7/ppp5/3p4/1B6/PPP5/K6R w - - 0 1

Your program may need more time to avoid Rxh7 because of not extending checks
Uri