Question about checkmate and beta cutoffs

[Sven]

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.

Before commenting on some of the points above, I would like to add one general remark. The misunderstandings regarding terminology like "depth" and "ply" are quite typical and occur frequently. I think they are caused by our lazyness to use proper words within discussions or verbal descriptions of programming concepts. Instead, much too often we are tempted to just use variable names from our own programs. But these are in fact the most ambiguous things I can ever think of since there is no standard at all, and everyone uses similar words but with different meanings. It would be much better, for instance, if we could agree on a slightly improved vocabulary for discussions, like:
- "remaining depth" or "depth left" for the number of plies that are left to play from the current node until reaching the full search horizon;
- "height" for the number of plies that have been played from the root node to the current node (the height of the tree until here);
- "maximum search depth" for the number of plies from the root node to the horizon, for the current iteration.

The word "ply" originally means nothing else than a "half move". Using it for any of the concepts above when discussing with others seems to cause too many ambiguities. However, "ply" may still be a good choice as a variable name. But sometimes it is also used for the number of plies having been played since the beginning of the whole game.


Regarding mate and beta cutoff: A mate in one is always the optimal value the side to move can reach from a legal position. So if the goal of the search is to find the best move and its evaluation, finding a move at the root that immediately delivers checkmate means that you have found an optimal move, you can't improve anymore on it. And the mechanism to get this done automatically is to set beta for the root search to VALUE_OF_MATE_IN_ONE_PLY. If you don't do this and find a mate in one, the search will continue and check all other root moves but none of them will return with a better move and value, so it is wasted effort since the usual rule is to select the first of possibly several moves with the same value returned by the search.

Regarding the maximum search depth you need to detect a mate in N: This is about terminology again. "Mate in 2" means the moving side needs to make two moves until checkmate. Since the moving side (at the root) makes the first but also the last move, the total length of each forced mating sequence starting at a given node (here: root) is always an odd number. "Mate in N" with N > 0 means exactly "Mate in (2*N-1) plies". A similar rule is valid for "Checkmated in N", this always means that an even number of plies is needed, so you have "Mate in 2*N plies".

Sven

[jesper_nielsen]

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.

The mate is detected at a node at ply = 3 depth. (Where the root has ply = 0. So maybe it is a numbering thing! ) So disregarding extensions and reductions and whether or not you can go to q-search when you are in check, you do need a depth 4 search to spot it.
It has to be a node where you try to call AlphaBeta, not one where you call Eval.

Now the whole "mate-in-1 should give a beta-cutoff" issue:
I do not have +INF equal to the "Mate-in-1" value. Therefore I do not have any special early cutoff in that case. This is because of the way I handle the root node.

I like to complete the root search iteration before returning a value.

The number of nodes you save are minuscule, since it is very fast to complete the depth = 1 search anyway. So in my opinion, it doesn't matter which strategy you select. Just go with what you think is the simplest to implement/understand.

The amount of time spend at the root node is simply close to nothing compared to the millions of nodes searched below the root.

I my case, I handle the "break early because of mate score" option completly outside the root search, in the iterative deepening part. It makes sense to me, but that might just be because that was the way I wrote it originally.

Kind regards,
Jesper

[Fguy64]

Noted, Jesper your answer tells me we agree on how it works, but we used different ways to describe the situation. Is Sven pointed out, this is often a source of probloems.

Anyways, as H.G. suggested, It seems the source of my uncertainty about where actually the beta cutoff occurs was a problem with my checkmate scoring in search. Here is my old code...

Code: Select all

if( count == 0 ) {
    if( inCheck(pStr) ) {
        alpha = -(100000-(ply-depth) );
        if( depth == ply ) move = new Move("Checkmate", false);
    }
    else {
        alpha = 0;
        if( depth == ply ) move = new Move("Stalemate", false);
    }
}

by changing the one line to read...

Code: Select all

alpha = -(100000-(ply-depth) +1 );

it seems to have resolved all my issues.

[bob]

Noted, Jesper your answer tells me we agree on how it works, but we used different ways to describe the situation. Is Sven pointed out, this is often a source of probloems.

Anyways, as H.G. suggested, It seems the source of my uncertainty about where actually the beta cutoff occurs was a problem with my checkmate scoring in search. Here is my old code...

Code: Select all

if( count == 0 ) {
    if( inCheck(pStr) ) {
        alpha = -(100000-(ply-depth) );
        if( depth == ply ) move = new Move("Checkmate", false);
    }
    else {
        alpha = 0;
        if( depth == ply ) move = new Move("Stalemate", false);
    }
}

by changing the one line to read...

Code: Select all

alpha = -(100000-(ply-depth) +1 );

it seems to have resolved all my issues.

I don't like the use of "depth" in the mate score. Depth is dynamically variable with both extensions and reductions making its value somewhat clouded.

If you get to ply=N in your search, and find you have no legal moves, and you are in check, why not simply return MATE - ply? Where MATE is some constant that is larger than any possible normal score you can return, and which is also less than "+infinity" so that you can get a real score returned rather than just a beta cutoff.

From Crafty's search.c:


value = (Check(wtm)) ? -(MATE - ply) : DrawScore(wtm);

Here I realize that I have no legal moves, and I am either mated or stalemated depending on whether I am in check or not. I therefore return -(MATE - ply) (which turns into MATE-ply at the previous ply, a good score) or else DrawScore() which may be zero or something else depending on how you want to handle draw scores.

A mate score must be relative to the distance from the root position. Hence the MATE-ply computation. I don't see why depth has anything to do with this.

[Fguy64]

Noted, Jesper your answer tells me we agree on how it works, but we used different ways to describe the situation. Is Sven pointed out, this is often a source of probloems.

Anyways, as H.G. suggested, It seems the source of my uncertainty about where actually the beta cutoff occurs was a problem with my checkmate scoring in search. Here is my old code...

Code: Select all

if( count == 0 ) {
    if( inCheck(pStr) ) {
        alpha = -(100000-(ply-depth) );
        if( depth == ply ) move = new Move("Checkmate", false);
    }
    else {
        alpha = 0;
        if( depth == ply ) move = new Move("Stalemate", false);
    }
}

by changing the one line to read...

Code: Select all

alpha = -(100000-(ply-depth) +1 );

it seems to have resolved all my issues.

I don't like the use of "depth" in the mate score. Depth is dynamically variable with both extensions and reductions making its value somewhat clouded.

If you get to ply=N in your search, and find you have no legal moves, and you are in check, why not simply return MATE - ply? Where MATE is some constant that is larger than any possible normal score you can return, and which is also less than "+infinity" so that you can get a real score returned rather than just a beta cutoff.

From Crafty's search.c:


value = (Check(wtm)) ? -(MATE - ply) : DrawScore(wtm);

Here I realize that I have no legal moves, and I am either mated or stalemated depending on whether I am in check or not. I therefore return -(MATE - ply) (which turns into MATE-ply at the previous ply, a good score) or else DrawScore() which may be zero or something else depending on how you want to handle draw scores.

A mate score must be relative to the distance from the root position. Hence the MATE-ply computation. I don't see why depth has anything to do with this.

Well, I certainly want to be consistent with accepted use of terminology, that would save a lot of headaches, but I was just following Bruce Moreland's alphaBeta pseudo-code. And depth is the name of the variable that he uses in the alphaBeta function header, and he uses depth-1 in the recursive call. So what else would I use in my mate score but depth? Are you saying that Moreland's pages are not the accepted usage of the words?

I can adapt, but It seems to me there is not a generally accepted usage even among the experts.

[Sven]

by changing the one line to read...

Code: Select all

alpha = -(100000-(ply-depth) +1 );

it seems to have resolved all my issues.

I don't like the use of "depth" in the mate score. Depth is dynamically variable with both extensions and reductions making its value somewhat clouded.

If you get to ply=N in your search, and find you have no legal moves, and you are in check, why not simply return MATE - ply? Where MATE is some constant that is larger than any possible normal score you can return, and which is also less than "+infinity" so that you can get a real score returned rather than just a beta cutoff.

From Crafty's search.c:


value = (Check(wtm)) ? -(MATE - ply) : DrawScore(wtm);

Here I realize that I have no legal moves, and I am either mated or stalemated depending on whether I am in check or not. I therefore return -(MATE - ply) (which turns into MATE-ply at the previous ply, a good score) or else DrawScore() which may be zero or something else depending on how you want to handle draw scores.

A mate score must be relative to the distance from the root position. Hence the MATE-ply computation. I don't see why depth has anything to do with this.

Bob,

your "ply" variable has a different meaning than his "ply". For Crafty it is the distance to the root while for his engine it is the maximum search depth, which is a constant value during the whole search. Therefore his "ply - depth", with "depth" being the remaining depth until horizon, is the same as your "ply".

Read what I wrote here yesterday, which is just a few posts above in this thread.

Sven

[Sven]

Well, I certainly want to be consistent with accepted use of terminology, that would save a lot of headaches, but I was just following Bruce Moreland's alphaBeta pseudo-code. And depth is the name of the variable that he uses in the alphaBeta function header, and he uses depth-1 in the recursive call. So what else would I use in my mate score but depth? Are you saying that Moreland's pages are not the accepted usage of the words?

I can adapt, but It seems to me there is not a generally accepted usage even among the experts.

Confusion came from the name of your "ply" variable, I guess. "depth" is frequently used for the depth left to horizon, as in your code. But "ply" often has a similar meaning as in Crafty.

Maybe you should think about tracking your distance from the root node differently. At the moment you are relying on the constant value "ply" to calculate that distance via "ply - depth". But as soon as you introduce the first extension or reduction, the full search horizon becomes flexible and your "ply" can't help you anymore to find the distance from the root. So maybe you just count it up and down, starting with zero at the root.

Also I don't know yet why you made this change into:

Code: Select all

alpha = -(100000-(ply-depth) +1 );

Why the +1?

Sven

[bob]

Noted, Jesper your answer tells me we agree on how it works, but we used different ways to describe the situation. Is Sven pointed out, this is often a source of probloems.

Anyways, as H.G. suggested, It seems the source of my uncertainty about where actually the beta cutoff occurs was a problem with my checkmate scoring in search. Here is my old code...

Code: Select all

if( count == 0 ) {
    if( inCheck(pStr) ) {
        alpha = -(100000-(ply-depth) );
        if( depth == ply ) move = new Move("Checkmate", false);
    }
    else {
        alpha = 0;
        if( depth == ply ) move = new Move("Stalemate", false);
    }
}

by changing the one line to read...

Code: Select all

alpha = -(100000-(ply-depth) +1 );

it seems to have resolved all my issues.

I don't like the use of "depth" in the mate score. Depth is dynamically variable with both extensions and reductions making its value somewhat clouded.

If you get to ply=N in your search, and find you have no legal moves, and you are in check, why not simply return MATE - ply? Where MATE is some constant that is larger than any possible normal score you can return, and which is also less than "+infinity" so that you can get a real score returned rather than just a beta cutoff.

From Crafty's search.c:


value = (Check(wtm)) ? -(MATE - ply) : DrawScore(wtm);

Here I realize that I have no legal moves, and I am either mated or stalemated depending on whether I am in check or not. I therefore return -(MATE - ply) (which turns into MATE-ply at the previous ply, a good score) or else DrawScore() which may be zero or something else depending on how you want to handle draw scores.

A mate score must be relative to the distance from the root position. Hence the MATE-ply computation. I don't see why depth has anything to do with this.

Well, I certainly want to be consistent with accepted use of terminology, that would save a lot of headaches, but I was just following Bruce Moreland's alphaBeta pseudo-code. And depth is the name of the variable that he uses in the alphaBeta function header, and he uses depth-1 in the recursive call. So what else would I use in my mate score but depth? Are you saying that Moreland's pages are not the accepted usage of the words?

I can adapt, but It seems to me there is not a generally accepted usage even among the experts.

That would be fine if there were no extensions. But think about this. Suppose you extend the search at ply=1 with a check, and at ply=3 with a check, and at ply=5 with a check, and your opponent is mated at ply 7. What is your mate score? Since you extended 3 times, and assuming this is a 10 ply search, we start off with depth=10, and by the time we get to 7 we have reduced depth 7 times, and increased it 3. So this would say we have a mate in 4 plies. And that would be wrong.

I pass both "depth" and "ply" thru my recursive calls. Depth is the remaining depth left to search before I drop into a q-search, ply is incremented once at each level of the tree so it always tells me _exactly_ how far I am from the root. Since the mate score should be based on distance from root, rather than distance from the tips, ply is the right value to use.

[bob]

by changing the one line to read...

Code: Select all

alpha = -(100000-(ply-depth) +1 );

it seems to have resolved all my issues.

I don't like the use of "depth" in the mate score. Depth is dynamically variable with both extensions and reductions making its value somewhat clouded.

If you get to ply=N in your search, and find you have no legal moves, and you are in check, why not simply return MATE - ply? Where MATE is some constant that is larger than any possible normal score you can return, and which is also less than "+infinity" so that you can get a real score returned rather than just a beta cutoff.

From Crafty's search.c:


value = (Check(wtm)) ? -(MATE - ply) : DrawScore(wtm);

Here I realize that I have no legal moves, and I am either mated or stalemated depending on whether I am in check or not. I therefore return -(MATE - ply) (which turns into MATE-ply at the previous ply, a good score) or else DrawScore() which may be zero or something else depending on how you want to handle draw scores.

A mate score must be relative to the distance from the root position. Hence the MATE-ply computation. I don't see why depth has anything to do with this.

Bob,

your "ply" variable has a different meaning than his "ply". For Crafty it is the distance to the root while for his engine it is the maximum search depth, which is a constant value during the whole search. Therefore his "ply - depth", with "depth" being the remaining depth until horizon, is the same as your "ply".

Read what I wrote here yesterday, which is just a few posts above in this thread.

Sven

OK, I didn't catch that. Sort of an unusual way of expressing a search, since you really do need things for each ply (and assuming you are not doing the ugly and creating a new search object at each new ply (too much overhead) and having the "ply" value as an index into an array of these things is really simple to deal with.

[Fguy64]

Well, I certainly want to be consistent with accepted use of terminology, that would save a lot of headaches, but I was just following Bruce Moreland's alphaBeta pseudo-code. And depth is the name of the variable that he uses in the alphaBeta function header, and he uses depth-1 in the recursive call. So what else would I use in my mate score but depth? Are you saying that Moreland's pages are not the accepted usage of the words?

I can adapt, but It seems to me there is not a generally accepted usage even among the experts.

Confusion came from the name of your "ply" variable, I guess. "depth" is frequently used for the depth left to horizon, as in your code. But "ply" often has a similar meaning as in Crafty.

Maybe you should think about tracking your distance from the root node differently. At the moment you are relying on the constant value "ply" to calculate that distance via "ply - depth". But as soon as you introduce the first extension or reduction, the full search horizon becomes flexible and your "ply" can't help you anymore to find the distance from the root. So maybe you just count it up and down, starting with zero at the root.

Also I don't know yet why you made this change into:

Code: Select all

alpha = -(100000-(ply-depth) +1 );

Why the +1?

Sven

About +1, well it is hard to explain, but it has something to do with the fact that I need maxPly = 4 to solve mate in 2. All I know is, without the +1 I wasn't getting an immediate cutoff when mate was found. I would get the "cursory search of subsequent nodes" that I spoke about. Which gets back to the original point of this thread.

For mate in n I need maxPly = 2n, because it is at the 2nth play, where no moves are found, that the mate score is applied. And I think somewhere therein lies the reason for the +1.

How about this. I have the ability to turn qSearch on and off from my GUI. I can tell you that this has no effect on the number of ply needed to solve a checkmate problem. In fact turning off qSearch only speeds up the search for checkmate. Does that shed any light?