Sven Schüle wrote:bob wrote:rob wrote:I put a copy of my negamax ab + TT implementation online, with just a bit of simplification, removal of some unnecessary details (like how draw by 3-fold repetition is detected).
It's essentially a clone of Tony Marsland's recipe given in Figure 7 of his paper "A Review of Game Tree Pruning".
negamax_ab_TT
Rob
One thing that certainly looks wrong, for starters, is your mate score. Mates are measured in plies from the root, not from the tips. Most would do something like this:
if (checkmate)
return INFINITY - ply;
which turns into a value that represents the distance to mate from the root. Depth is usually "distance from here to the tip (assuming there are no extensions/reductions applied)", which really doesn't belong in the mate score computation, unless I misread your use of depth.
-(INFINITY - (max_depth - depthleft))
would intrinsically be the same as
-(INFINITY - distance_from_root)
if either no extensions/reductions are used, or max_depth grows and shrinks with each extension or reduction. I agree that using distance_from_root (or "ply") is the much better solution on the long term (requiring another parameter of the search function which is trivial of course). But if we assume that no extensions/reductions are used in the current testing stage of the OP then this is not yet the explanation of his bug but "only" a valid improvement.
Think about that again. depth-left is continually changed. It can INCREASE due to a check. It can be reduced by LMR. That's not going to give you distance from the root any significant percentage of the time. "depth" is the wrong value. Distance from the root is a value that changes by exactly one for each move played beyond the root. Depth-remaining has no such relationship except when a program does zero reductions and zero extensions, not to mention zero null-move searches and such...
If he is not extending or reducing anywhere, he can get away with this, but only until he adds his first extension, where he starts to debug inconsistent mate scores once again.
Some of what I saw I didn't understand, such as "don't update bounds or score (I don't remember the exact comment now) in selective search." No idea what that is about.
I really wasn't proposing the above as a reason for his inverted score bug. But I wanted to understand his code and what he thought it was doing as I worked through it. I've always been of the mindset that I am not going to debug through a clear problem and continue, because that problem certainly results in an issue and I don't really want to debug the interaction between different bugs, but rather want to eliminate every bug I see, when I encounter it.
My first test were this my program would be to get a known working program and compare results for known forced mates. In Crafty, one could disable extensions and reductions by simple command-line arguments, to see what it does with a given forced mate. Until I matched Crafty with these positions, I would not add anything new...
It is definitely a necessary fix for the OP's program to use "ply" instead of his current implementation, although that will most probably not fix his current bug yet.