Question about checkmate and beta cutoffs

[Fguy64]

OK i 'm not sure about my terminology here. So first a description. Consider the situation where we have a single external call to alphabeta. And the first level is where depth = ply, we are iterating through the list of moves that the engine might make in the actual game.

It seems to me that the only situation where a beta cutoff can occur at this first level is if the engine has an immediate checkmate. Even then, it seems it will only happen when the mate node is searched, no legal moves are found at the 2nd level, and the mate score returned to the first level is equal to the original beta.

Now I think that good programming practice frowns upon a mate score assigned in search, as opposed to eval, where the value returned is equal to the original beta. So it follows that when a mate is found, that each subsequent move at the same level receives a cursory search, and an immediate beta cutoff occurs at the 2nd level.

Do I have this right?

[jesper_nielsen]

OK i 'm not sure about my terminology here. So first a description. Consider the situation where we have a single external call to alphabeta. And the first level is where depth = ply, we are iterating through the list of moves that the engine might make in the actual game.

It seems to me that the only situation where a beta cutoff can occur at this first level is if the engine has an immediate checkmate. Even then, it seems it will only happen when the mate node is searched, no legal moves are found at the 2nd level, and the mate score returned to the first level is equal to the original beta.

Now I think that good programming practice frowns upon a mate score assigned in search, as opposed to eval, where the value returned is equal to the original beta. So it follows that when a mate is found, that each subsequent move at the same level receives a cursory search, and an immediate beta cutoff occurs at the 2nd level.

Do I have this right?

I am not sure i follow you completely.

In my terminology depth is "remaining depth in the search" and "ply" is "number of plies from root".

There are three cases where a mate value is assigned in my program.

1. In the search, where a position is found with no legal moves. Then if the side to move is in check, I return a mate value, based upon "ply" i.e. how deep from the root are we.

Code: Select all

return -9999 + ply;

2. If a mate value is found in a tablebase lookup, it is returned like a normal hit, after a conversion of the value to the current ply.

3. In the recognizor code for the simple endgame positions.

There is the whole "storing mate values in the hashtable" discussion lurking here, but that is another matter!

AlphaBeta is called to find a best guess as to the value of the current position. If the search reveals the position to be checkmate or stalemate, the value of the position is 100% exactly known. Therefore there are no reasons for calling eval(). In this case AlphaBeta simply returns the exact value.

Now the node above the "exact" node receives the value just like any other calls to AlphaBeta. And it treats it is exactly the same way. If the value is above beta, then a beta cutoff occurs, etc.

So in short: Search reveals exact mate values. Evaluation takes a best guess at the current postition, when the "depth remaining" dictates that we do not wan't to search any deeper at this time.

Kind regards,
Jesper

[Fguy64]

OK i 'm not sure about my terminology here. So first a description. Consider the situation where we have a single external call to alphabeta. And the first level is where depth = ply, we are iterating through the list of moves that the engine might make in the actual game.

It seems to me that the only situation where a beta cutoff can occur at this first level is if the engine has an immediate checkmate. Even then, it seems it will only happen when the mate node is searched, no legal moves are found at the 2nd level, and the mate score returned to the first level is equal to the original beta.

Now I think that good programming practice frowns upon a mate score assigned in search, as opposed to eval, where the value returned is equal to the original beta. So it follows that when a mate is found, that each subsequent move at the same level receives a cursory search, and an immediate beta cutoff occurs at the 2nd level.

Do I have this right?

I am not sure i follow you completely.

In my terminology depth is "remaining depth in the search" and "ply" is "number of plies from root".

There are three cases where a mate value is assigned in my program.

1. In the search, where a position is found with no legal moves. Then if the side to move is in check, I return a mate value, based upon "ply" i.e. how deep from the root are we.

Code: Select all

return -9999 + ply;

2. If a mate value is found in a tablebase lookup, it is returned like a normal hit, after a conversion of the value to the current ply.

3. In the recognizor code for the simple endgame positions.

There is the whole "storing mate values in the hashtable" discussion lurking here, but that is another matter!

AlphaBeta is called to find a best guess as to the value of the current position. If the search reveals the position to be checkmate or stalemate, the value of the position is 100% exactly known. Therefore there are no reasons for calling eval(). In this case AlphaBeta simply returns the exact value.

Now the node above the "exact" node receives the value just like any other calls to AlphaBeta. And it treats it is exactly the same way. If the value is above beta, then a beta cutoff occurs, etc.

So in short: Search reveals exact mate values. Evaluation takes a best guess at the current postition, when the "depth remaining" dictates that we do not wan't to search any deeper at this time.

Kind regards,
Jesper

I think your step 1 shows we are in agreement, allow me to elaborate.

I will rephrase without use of the terms depth or ply. Our design is such that there is a single external call to alphaBeta. We call Level1 that level where we are iterating through the list of possible moves that the engine might make in the actual game. Also, we can limit this to fixed depth search, the answer to my question can be easily extrapolated to iteratie deepening. Ok that sets the stage.

Ok suppose the engine has a choice of 20 possible moves

now suppose, due to move ordering, that the very first move in the aforementioned 1st level iteration delivers immediate checkmate. What I am trying to establish is that the nature of beta cutoffs mean that the remaining 19 1st level iterations still get executed. as follows.

1. the checkmate node gets searched (i.e passed to level2), the 2nd level generates 0 legal replies, a mate score ( a score slightly less than the original beta ) is returned to level1.

2. even though move1 was checkmate, the loop continues to look at the remaining 19 moves. the resulting position is searched, and as long as that node generates a legal reply, then it is that reply to the subsequent level1 non checkmate move that generates the cutoff.

In other words, even when we have an immediate checkmate, the remaining moves get a cursory search. An attempt to sidestep this requirement will likely mean that the engine will play the first move that leads to a checkmate within the given depth, even when a faster checkmate exists. And that leaves open the possibility that the engine will continue to play mate in two moves when a mate in one exists.

Anyways, I'm just thinking out loud here, to solidify that which has been bouncing around in my head.

regards.
Fred.

[jesper_nielsen]

Aha, I see what you mean!

Yes all moves are searched, but your assumption that a mate in two is played if it is searched first is not true. (At least it is not, if you give a ply dependant mate score)

The mate in two will be found at ply = 3.
I move, You move, I move MATE!

This gives a value of 9996 i my case ( - - - ( - 9999 + 3)) with -9999 as mate score.

The mate in one will give 9998 ( - ( -9999 + 1)) since it is found at ply = 1.

Therefore the mate in one is played, because is has the highest value.

Now if there are more than one mate in one moves, then the first one searched is indeed always played.

It is important not to terminate the search when the first mate in two is found, because then the engine coudl stumble into a draw by repetition because it constinues to play a mate in two, when a mate in one is actually possible. EDIT: Like you describe above.

Kind regards,
Jesper

[hgm]

If your first move in the root is mate-in-1, it gives an immediate cutoff, not? No other moves are searched. The root window is (-INF,INF), and the score of mate-in-1 is +INF, as no higher score is possible. So the first (mating) move returns beta, which produces a beta cutoff in the root.

[bob]

OK i 'm not sure about my terminology here. So first a description. Consider the situation where we have a single external call to alphabeta. And the first level is where depth = ply, we are iterating through the list of moves that the engine might make in the actual game.

It seems to me that the only situation where a beta cutoff can occur at this first level is if the engine has an immediate checkmate. Even then, it seems it will only happen when the mate node is searched, no legal moves are found at the 2nd level, and the mate score returned to the first level is equal to the original beta.

Now I think that good programming practice frowns upon a mate score assigned in search, as opposed to eval, where the value returned is equal to the original beta. So it follows that when a mate is found, that each subsequent move at the same level receives a cursory search, and an immediate beta cutoff occurs at the 2nd level.

Do I have this right?

Where do you get that "I think" conclusion? I _only_ recognize mates in the search, _never_ in the evaluation code. I recognize a mate when I complete the search of some node in the tree, and noticed that (a) I found no legal moves to search and (b) I am in check.

[Fguy64]

Aha, I see what you mean!

Yes all moves are searched, but your assumption that a mate in two is played if it is searched first is not true. (At least it is not, if you give a ply dependant mate score)
...

Kind regards,
Jesper

Yes, I agree with you. That is the whole point of my post. A ply dependant mate score (i.e not equal to the original beta) will prevent the situation of a mate in two being played when a shorter one exists at a later iteration.

And as for my original point, it is this ply dependant mate score that prevents a beta cutoff from happening at all "at the first level". as I defined 1st level. Saying no 1st level beta cutoff is just my way of saying "all moves are searched".

My Hyatt, my "I think" remark referred to the fact that anything other than a ply dependant mate score ( i.e do not use the original beta) in search seems to be asking for trouble. I also detect mate in search as you describe, always have. I don't see how it could be otherwise. So my reference to eval was kind of careless, but not really the point.

regards.

[hgm]

And as for my original point, it is this ply dependant mate score that prevents a beta cutoff from happening at all "at the first level". as I defined 1st level. Saying no 1st level beta cutoff is just my way of saying "all moves are searched".

Well, if a mate-in-one does not produce a beta cutoff, you did not set beta properly. It is as simple as that. It makes no sense at all to search other moves after finding a mate-in-one...

[Fguy64]

And as for my original point, it is this ply dependant mate score that prevents a beta cutoff from happening at all "at the first level". as I defined 1st level. Saying no 1st level beta cutoff is just my way of saying "all moves are searched".

Well, if a mate-in-one does not produce a beta cutoff, you did not set beta properly. It is as simple as that. It makes no sense at all to search other moves after finding a mate-in-one...

OK well that makes sense. SO I guess I am wrong, and I also misinterpreted Jesper's remark.

Somehow we are not on the same page. We differ, but I'm not sure why. I suspect some differences in how we define ply and depth.

Jesper remarks that mate in 2 needs a 3 ply search, but I need ply=4 becuase it is at the 4th ply that determines that there are no possible moves. always mate in n moves requires ply = 2n.

I suspect somehow I may not be as efficient as I could be in my algorithm. I have no problem solving any checkmate, but ...

I need to return to the drawing board with this question, I'll be back later.

[hgm]

Well, it depends when exactly your engine detects the mate. Micro-Max, for instance, detects the mate only when the King is actually captured. So it needs d=2 to see mate in one. But that still means that you could set beta in the root to the mate-in-one score there, whatever it is.