PV change when changed from minmax to alphaBeta?

[macsmol]

Hi everyone! This is my first post. I've been doing my own UCI chess engine for some time. Only recently switched from minmax to alphabeta search.
I was surprised that search for fixed depth=5 yielded different best move (one with a worse score) from bare minimax. I was under the impression that alphabeta gives the same score as minimax but faster.
I'm wondering if it's due to some bug that I fail to see or maybe it's due to the fact that my evaluation is very simplistic (only material and mobility for all pieces)?
Here are the actual results (from starting position).
Minimax yields:

Code: Select all

go depth 5
info pv a2a3 e7e6 e2e3 d8g5 d1g4
...
info nodes 4865609 pv e2e4 e7e6 d1f3 f7f5 f3h5 time 6057 depth 5 nps 803291 score cp 185 pvUpdates 1170856
bestmove e2e4

alpha beta:

Code: Select all

go depth 5
...
info nodes 305537 pv e2e3 e7e6 d1f3 f7f5 f3h5 time 687 depth 5 nps 444461 score cp 180 pvUpdates 85387
bestmove e2e3

And here's the commit that introduced the change
https://github.com/macsmol/machess/comm ... d603b5dd20

Thanks for any help!

[Brian Richardson]

The best move should be the same for both.
See:
https://www.chessprogramming.org/Alpha-Beta

[macsmol]

Hmmm. I'm pretty sure there is no bug here. Intuitively I think that same pv is not guarranteed. It comes from the fact that alpha-beta is not an exhaustive search so it might not bother to descend into branches that do not look promising at first but indeed can turn out better after all. And this is especially in the case of such a simplistic evaluation function.

Today I spent some time debugging it. I realized that 1. e2e4 e7e6 2. d1f3 f7f5 3. f3h5 is considered but later it's overwritten several times and eventually the 1. e2e4 branch returns with score lower than that for 1. e2e3. (which would be in favor or missing good continuations theory)
Generally speaking setting breakpoints in recursive functions looks very daunting . I can't really wrap my head around it.

Also just read this paragraph here https://www.chessprogramming.org/Mate_Search that sometimes shorter lines to mate are pruned which pretty much confirms my theory.

[H.G.Muller]

If you have no hash table or fancy pruning techniques like null move. minimax and alpha-beta should give exactly the same score. The PV could only change if there happen to be several PVs with exactly the same score. So I suspect indeed a bug.

The way I always debug such thing is by printing an overview of all searched moves and their scores (and best score so far) in selected nodes. (E.g. selected by specifying the move sequence that leads to them. Like you say, unconditional debug info is pretty useless in something as heavily recursive as a chess program.) In minimax you should have the exact score of every move; in alpha-beta most scores would be upper- or lower-bounds. But by comparing the two cases for the same node (starting with the root node) you can see which bound or exact score in the a-b case is in disagreement with that of minimax, and then print the move lists in the daughter node after that move, etc., until you arrive at the point where the difference originates. This is usually a place where a move is pruned because it was assumed it could not affect the root score, while in fact it did. But it could also be that evaluations for the same position differ, e.g. because you use an uninitialized variable which happens to get a different value in the two cases.

Once you have set up the necessary infra-structure in your program to do that (e.g. remembering the moves that lead to the current node in a global array, and an if(PATH) printf(...) statement after the return of the recursive call, where you can easily define variant PATH conditions), finding the source of a bug is often just a matter of minutes. If the problem is reproducible, that is.

[macsmol]

Hi! Thanks for the in-depth answer! So just to make sure that I understand you correctly I'll use the analogy to perft and perft-divide (described here http://rocechess.ch/perft.html).
So what you advise me to do relates to minimax and alphabeta like perft-divide relates to perft. Except in perft we compare different engines and here we compare search functions.

[macsmol]

Hi. I figured it out! It looks embarrassingly simple now. The fault was a mechanism I created long time ago that made the engine prefer choosing earlier checkmates (without it the engine tended to change it's mind every turn as horizon was changing and new mate lines would show up). The mechanism was simple: every score returned from subtree was multiplied by some positive number smaller than one.
The problem was that it did for all nodes not only the terminal ones. The fix was to pass ply count (the thing that increments as depth goes to zero) to function that calculates terminal node scores.
Anyway the infrastructure suggested by H.G. Muller will be useful tool to debug some blunders that I see my engine is making ...and it was the reason why I added ply count param to alphabeta() in the first place! So thanks!