Next steps for my engine?

[plattyaj]

As for your second point. I think I understand, either kind of cutoff would cause the same issue of missing a desireable underpromotion. Which is why I have already decided to proceed with the way I originally had it, for now, which is don't update alpha until after all four promotion nodes are searched. I can always change it later.

As for mate score, a couple of posts ago I described how mate is currently handled. As long as that works, I'll stick with it and look for improvements like you have suggested later.

regards.

I agree - get there in your own time but don't forget, as you search deeper and deeper, that if the promotion is near the root of the tree, that could be thousands of nodes you are searching because you aren't cutting off at the first one.

I really struggled to understand alpha-beta when I first wrote an engine. In fact I refused to believe it really worked until I had proved it myself. I sense you have the same underlying disbelief but it's really quite simple. If your promotion to a Queen causes a cutoff (> beta) you should get out immediately because it really doesn't matter what score another promotion is going to give - none of these moves are going to be played because the opponent (e.g. the side not to move for the ply you are searching) will not make this move since they have already found a better one.

Andy.

[Fguy64]

As for your second point. I think I understand, either kind of cutoff would cause the same issue of missing a desireable underpromotion. Which is why I have already decided to proceed with the way I originally had it, for now, which is don't update alpha until after all four promotion nodes are searched. I can always change it later.

As for mate score, a couple of posts ago I described how mate is currently handled. As long as that works, I'll stick with it and look for improvements like you have suggested later.

regards.

I agree - get there in your own time but don't forget, as you search deeper and deeper, that if the promotion is near the root of the tree, that could be thousands of nodes you are searching because you aren't cutting off at the first one.

I really struggled to understand alpha-beta when I first wrote an engine. In fact I refused to believe it really worked until I had proved it myself. I sense you have the same underlying disbelief but it's really quite simple. If your promotion to a Queen causes a cutoff (> beta) you should get out immediately because it really doesn't matter what score another promotion is going to give - none of these moves are going to be played because the opponent (e.g. the side not to move for the ply you are searching) will not make this move since they have already found a better one.

Andy.

Hmm ok a light is starting to glimmer. As I am doing it, I think, a Queen promo that leads to a mate won't cause a cutoff until alpha gets updated, i.e. it will search the other three promo nodes anyways. But I don't want a Queen promo to cause a cutoff for any other reason besides mate. So It is not so clear to me that val >= beta implies checkmate. Maybe I should be looking at some other type of conditional expression?

[Aaron Becker]

But I don't want a Queen promo to cause a cutoff for any other reason besides mate.

A full alpha-beta search is guaranteed to give the same result as searching the full tree. Given this fact, you should never reject legitimate cutoffs, because the algorithm has proved that you don't need to consider any of the nodes in that subtree. It sounds to me like you're taking legitimate concerns about risky but often beneficial maneuvers like forward pruning and depth reductions and mis-applying them to the completely safe and always beneficial case of alpha-beta cutoffs.

[xsadar]

As for your second point. I think I understand, either kind of cutoff would cause the same issue of missing a desireable underpromotion. Which is why I have already decided to proceed with the way I originally had it, for now, which is don't update alpha until after all four promotion nodes are searched. I can always change it later.

As for mate score, a couple of posts ago I described how mate is currently handled. As long as that works, I'll stick with it and look for improvements like you have suggested later.

regards.

I agree - get there in your own time but don't forget, as you search deeper and deeper, that if the promotion is near the root of the tree, that could be thousands of nodes you are searching because you aren't cutting off at the first one.

I really struggled to understand alpha-beta when I first wrote an engine. In fact I refused to believe it really worked until I had proved it myself. I sense you have the same underlying disbelief but it's really quite simple. If your promotion to a Queen causes a cutoff (> beta) you should get out immediately because it really doesn't matter what score another promotion is going to give - none of these moves are going to be played because the opponent (e.g. the side not to move for the ply you are searching) will not make this move since they have already found a better one.

Andy.

Hmm ok a light is starting to glimmer. As I am doing it, I think, a Queen promo that leads to a mate won't cause a cutoff until alpha gets updated, i.e. it will search the other three promo nodes anyways. But I don't want a Queen promo to cause a cutoff for any other reason besides mate. So It is not so clear to me that val >= beta implies checkmate. Maybe I should be looking at some other type of conditional expression?

Let's consider an example. Let's say that in the following position, your engine's playing black, and it's your engine's turn.
[d]4q3/5P1k/8/7K/8/8/8/B5R1 b - - 0 1
Now your engine begins by searching captures and promotions, so it considers 1...Qxf7+, and finds that it gives you a decent advantage (let's say +5.00).
Now we start considering non-captures, including Qd4, which gives the following position with a beta of -5.00 (meaning the best your opponent can do is -5.00 because your engine can get a score of +5.00 with Qxf7+ if Qd4 doesn't work out):
[d]8/5P1k/8/7K/4q3/8/8/B5R1 w - - 0 1
Now we consider the move 2. f8=Q which gives a stalemate (score of 0.00) with Qh4+ 3. Kxh4. Since 0.00 is greater than our beta of -5.00 we return without considering any more moves. We don't need to consider the underpromotion 2. f8=N# even though it's mate because the draw is bad enough. We already know 1...Qd4 (the move that brought us to this position) is not as good as what we've found before (1...Qxf7+), even without considering the mate.

[Fguy64]

But I don't want a Queen promo to cause a cutoff for any other reason besides mate.

A full alpha-beta search is guaranteed to give the same result as searching the full tree. Given this fact, you should never reject legitimate cutoffs, because the algorithm has proved that you don't need to consider any of the nodes in that subtree. It sounds to me like you're taking legitimate concerns about risky but often beneficial maneuvers like forward pruning and depth reductions and mis-applying them to the completely safe and always beneficial case of alpha-beta cutoffs.

Duly noted, I accept the first part or your paragraph but not sure about the second part. At this point I think I must be misinterpreting something fundamental about cutoffs. I'm not worried, I think I'm pretty close it'll come.

Here's the concern restated..

If in my search function as shown there is a return statement after the search on the queen promo and before the search on the other three promos, then it better be because the Queen promo leads to a forced mate.

I've already explained why it is I'm dealing with promotion in my search function. I don't see that that should interfere with proper functioning of alpha-beta, but if it is then I have some work to do.

regards.

edit: p.s. to Mike thanks I'll address your post tomorrow.

[Aaron Becker]

If in my search function as shown there is a return statement after the search on the queen promo and before the search on the other three promos, then it better be because the Queen promo leads to a forced mate.

This is where you run into problems. Finding a forced mate is one reason to stop searching a node, but it's not the only reason, or the most important reason. The more important reason to stop searching a node is because it is irrelevant, because getting to that node requires either us or our opponent to play bad moves. So the question becomes "how do we identify the irrelevant nodes?"

In the case of alpha-beta search, the answer is that a node is irrelevant if it has any child node with a score higher than beta, or if all of its child nodes have scores lower than alpha.

The idea that we throw out nodes when we see a score that's too high is not the most intuitive--after all, we're looking for high scores. However, the algorithm is designed so that we always know that with best play on both sides, the final score will end up somewhere between alpha and beta. Therefore if we get a result outside that range, we know it's the result of suboptimal play, and that the resulting score is irrelevant.

[Fguy64]

If in my search function as shown there is a return statement after the search on the queen promo and before the search on the other three promos, then it better be because the Queen promo leads to a forced mate.

This is where you run into problems. Finding a forced mate is one reason to stop searching a node, but it's not the only reason, or the most important reason. The more important reason to stop searching a node is because it is irrelevant, because getting to that node requires either us or our opponent to play bad moves. So the question becomes "how do we identify the irrelevant nodes?"

In the case of alpha-beta search, the answer is that a node is irrelevant if it has any child node with a score higher than beta, or if all of its child nodes have scores lower than alpha.

The idea that we throw out nodes when we see a score that's too high is not the most intuitive--after all, we're looking for high scores. However, the algorithm is designed so that we always know that with best play on both sides, the final score will end up somewhere between alpha and beta. Therefore if we get a result outside that range, we know it's the result of suboptimal play, and that the resulting score is irrelevant.

Well ok. If that is true, then either the way I am dealing with promotion, or the way I am dealing with mate, must be incompatible with full alpha-beta search, otherwise your remark leaves open the possibility of missing a forced mate by underpromotion. And that is not a problem that I had with my "not quite alpha-beta" search that I started out this thread with.

We are not on the same page. We can't be. Probably I am misusing the terminology. I don't think I mean stop searching a node the way you mean it. I'm talking about not missing a forced mate by stopping or pruning or whatever at the wrong time. If you say that won't happen then that is more evidence that we are talking at cross purposes. Lets leave it for now. I'm gonna play with this code and see what happens. We'll come back to this soon.

[Aaron Becker]

I suspect this is a miscommunication about what is meant by stopping the search and cutting off. Taking a beta cutoff will never miss a forced mate. The fact that one of the possible moves led to a score above beta means that somewhere in between the root of the search and the current node, there is a sub-optimal move. Therefore, the current line is not forcing at all--it's refuted by an alternative move at some parent of the current node. The fact that there are other moves available at the current node doesn't matter, whether they are promoting moves or not. Regardless of what the other available moves are, once we've seen a score above beta we know that the current node is not in the principal variation. In the case where there is a forced mate possible, beta is always at least as high as the score for the forced mate, and no beta cutoff will occur.

[Evert]

This is where you run into problems. Finding a forced mate is one reason to stop searching a node, but it's not the only reason, or the most important reason. The more important reason to stop searching a node is because it is irrelevant, because getting to that node requires either us or our opponent to play bad moves. So the question becomes "how do we identify the irrelevant nodes?"

In the case of alpha-beta search, the answer is that a node is irrelevant if it has any child node with a score higher than beta, or if all of its child nodes have scores lower than alpha.

The idea that we throw out nodes when we see a score that's too high is not the most intuitive--after all, we're looking for high scores. However, the algorithm is designed so that we always know that with best play on both sides, the final score will end up somewhere between alpha and beta. Therefore if we get a result outside that range, we know it's the result of suboptimal play, and that the resulting score is irrelevant.

I learned about alpha-beta years ago, and the explanation given for why it works is that if we find a beta cut-off, then our position is so now so good (we should not expect to do better than beta) that the opponent has made a blunder and would never allow us this good position, therefore we back out. It came with nice diagrams of the mini-max tree showing why this worked.

That's fine, but it required some mental gymnastics at the time. Recently, it occurred to me that there might be a more intuitive explanation for what it does and why it works, or at least an explanation that seems more natural and intuitive to me, and maybe easier for someone who is new to the concept.

First, we need to think slightly differently about the search.
The purpose of the search is not to find good moves per se (as it's usually explained), but to eliminate bad ones. Many people here probably do think that way, but this is not how the idea is usually presented in tutorials. To identify a blunder, we need to find a refutation. That's why we try hash moves, killer moves and winning captures before other moves: they tend to refute blunders by the opponent. Once we've found a refutation (i.e. a move with a score > beta), we're done and we don't need to search any further. It doesn't matter if there's more than one refutation, or even if the one we found is the best one, because we only need one to expose the blunder.

At the very least I think it's good conceptually to switch from one view to the other now and then (we search to find good moves / we search to eliminate bad moves) because it makes some things a bit clearer.

Anyway, hope that contributed something to the discussion.

[Fguy64]

OK I think I see what the problem is. I think that the way I am dealing with checkmate is compatible with my old way of pruning, but incompatible with full alpha-beta pruning. And I think people have not recognized that I am not dealing with checkmate properly, because I haven't shown my qSearch() function, which at this point is just an eval().

Under the old method, it was my search function that was dealing with checkmate. It did this by virtue of the fact that checkmate positions were being searched and finding no legal moves, therefore the initial seed value of best=-10000 was being undisturbed. Esthetically this appealed to me as a way of making extra use of my search function. The operative word here is efficiency. Now if we accept for the purpose of discussion that my old method of checkmate is ok, then the search function I posted a little earlier was incomplete because there was no mechanism to distinguish between checkmate and stalemate, a mechanism that would not have been necessary anyway if I had been dealing with mate in my eval().

I can't say exactly how, but intuitively I think proper alpha-beta cutoffs are interfering with this. By changing things so that checkmate is handled by my eval() function, and thus a score is explicitly assigned to mate, I feel the impasse we find ourselves at will be resolved.

make sense?

regards.

p.s. to Evert. Thanks for that. yes I do believe your remarks about the purpose of search are very relevant, if I am correct in my diagnosis in this post.