Question about checkmate and beta cutoffs

[bob]

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?

One golden rule. Do NOT go forward with unexplained results, you need to understand exactly why something works or fails. "just working" is a good way to spend a lot of time debugging later when you change something.

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

One golden rule. Do NOT go forward with unexplained results, you need to understand exactly why something works or fails. "just working" is a good way to spend a lot of time debugging later when you change something.

well yeah, but that kind of begs the question don't it?.

Nothing is failing. I can solve any checkmate or tactical problem. With all the lack of consensus on ply and whatever, I didn't give a whole lot of thought to the extra ply thing, I just chalked it up to semantics. Well now I'm starting to see maybe there's more to it than that, and someone tells my I broke the golden rule. I certainly have made my code available every step of the way, through all of these discussions, so if something is failing, then I ain't the only one who hasn't noticed.

Anyways I'll take that as a yes to my question. Back to the drawing board.

regards.

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

Assuming that the code you have published is the current version we are talking about, here is what I think you are doing. Here I refer to the version prior to your '+1' change.

You create an Engine object with 'ply = 4' in order to perform a full-width search to a maximum depth of 4 later on. 'ply' is stored as private member of the Engine object (perhaps better call it 'maxPly'?).

You call Engine::getBestMove() with the current position to start the (4-ply) search. This in turn calls Engine::alphaBeta() with 'depth' initially set to 'ply' and 'alpha' and 'beta' set to -100000 and +100000.

Let's further assume that A is to move at the root and B is the opponent.

Within the tree search, you arrive at a node three plies below the root and call alphaBeta() with depth=1 and some alpha/beta window. This alphaBeta() does not find any legal move, detects B is in check, and returns the mate score '-(100000-(4-depth))' = -99997. For A at the level above (at root distance 2) this becomes a +99997. All other legal moves of B at level 1 are immediately answered by a checkmate, too, so -99997 is returned from level 1 and backed up to the root as +99997 which is the value of the move that starts the mating sequence for A.

Now we are at your alpha/beta window settings at the root. You have beta=+100000 so a +99997 will not cause a beta cutoff. Nor does your '+1' change cause that, since in this case '-(100000-(4-depth)+1)'=-99998 would be returned from the mate detecting node and propagated to the root as +99998.

Here I want to point out that it is indeed not *critical* whether you get this beta cutoff with a mate score at the root, or not. I am only trying to help finding an *explanation* of what happens in your case.

If you like the idea of getting this beta cutoff when finding a score at root that can't be improved any further then your initial setting of beta would have to be different, something like '100000-(ply-1)' using your "ply" terminology.

Now you say that without your '+1' in the mate score formula you get different behaviour than with it. So there may be something wrong, either in your program or in my logic or somewhere else And as Bob already stated: you should find it before proceeding!

Sven

[bob]

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?

One golden rule. Do NOT go forward with unexplained results, you need to understand exactly why something works or fails. "just working" is a good way to spend a lot of time debugging later when you change something.

well yeah, but that kind of begs the question don't it?.

Nothing is failing. I can solve any checkmate or tactical problem. With all the lack of consensus on ply and whatever, I didn't give a whole lot of thought to the extra ply thing, I just chalked it up to semantics. Well now I'm starting to see maybe there's more to it than that, and someone tells my I broke the golden rule. I certainly have made my code available every step of the way, through all of these discussions, so if something is failing, then I ain't the only one who hasn't noticed.

Anyways I'll take that as a yes to my question. Back to the drawing board.

regards.

your "nothing is failing" is not exactly correct. If you need to add a +1, for unexplained reasons, then you have to either work to explain why _exactly_ or else work to get rid of the +1. It is those "unexplained" behaviours that lead to significant debugging issues later.