Page 1 of 1
Negamax questions
Posted: Tue Jun 02, 2015 11:33 pm
by thevinenator
A question and a problem.
Assumption: The code generates LEGAL moves, not pseudo legal, so if the move generator returns 0 moves, it does mean checkmate or stalemate.
TheGame.StartDepth is the original "depth" from the start of the search.
Evaluate() calculates the game from WHITES (=1) perspective.
MATESCORE is big, but not as big as INFSCORE.
GetNextMove() handles the move ordering returning the next best move to try.
TheGame has the position info. everything is updated incrementally when doing make/unmake moves.
MOVES is an array of MOVE structures with some additional housekeeping info.
the move/unmove code passes all PERFT tests i've thrown at it.
i removed some code not associated with the problem such as the history heuristic update in the Alpha/Beta comparison.
given the following negamax() framework:
Code: Select all
int NegaMax(int depth, int Alpha, int Beta)
{
MOVES ms;
MOVE *m;
int NumMoves;
int BestValue;
int Value;
NumMoves = TheGame.GenerateLegalMoves(&ms);
if (NumMoves == 0) {
if (ms.IsInCheck == true)
return (-MATESCORE + (TheGame.StartDepth - depth));
else
return (0); // draw
}
else {
if (depth == 0)
return (TheGame.Evaluate() * TheGame.GetSideToMove());
}
BestValue = -INFSCORE;
m = ms.GetNextMove();
while (m != NULL) {
TheGame.MakeMove(m);
Value = -NegaMax(depth - 1, -Beta, -Alpha);
TheGame.UnMakeMove(m);
BestValue = max(Alpha, Value);
Alpha = max(Alpha, Value);
if (Alpha >= Beta)
break;
m = ms.GetNextMove();
}
return (BestValue);
}
question: is the code to check for the mate value correct?
-MATESCORE + (TheGame.StartDepth - depth)
i've seen so many variations during my research that i can't tell which is correct.
also, i saw some code that is used to modify Alpha/Beta when a mate is detected. Should that code be placed in the same code block prior to returning the mate value?
Re: Negamax questions
Posted: Wed Jun 03, 2015 12:13 am
by hyatt
that looks awkward.
Typically depth is a value that counts down as you advance toward the tips. Ply is a variable that typically counts up from the root. The traditional value is MATE - ply. If you are going to return it, then -MATE + ply. If your "depth" means something different than the usual value, it might work, but it looks wrong to my eye with traditional "depth" meaning. A mate score is an absolute thing. "depth" goes up and down as extensions and reductions are applied, which is what makes this look wrong.
Re: Negamax questions
Posted: Wed Jun 03, 2015 12:17 am
by hyatt
that looks awkward.
Typically depth is a value that counts down as you advance toward the tips. Ply is a variable that typically counts up from the root. The traditional value is MATE - ply. If you are going to return it, then -MATE + ply. If your "depth" means something different than the usual value, it might work, but it looks wrong to my eye with traditional "depth" meaning. A mate score is an absolute thing. "depth" goes up and down as extensions and reductions are applied, which is what makes this look wrong.
Re: Negamax questions
Posted: Wed Jun 03, 2015 1:12 am
by thevinenator
hyatt wrote:Typically depth is a value that counts down as you advance toward the tips.
depth is correct, it counts down...see the embedded recursive call.
I didn't want to carry another counter on the stack and since i know the StartDepth, i was trying to convert the combination of the two to "ply".
so, for example if i do a 3-ply search, StartDepth is set to 3 along with depth.
the first recursive call, depth = 2, and (StartDepth - depth) will = 1. isn't that what ply should be ? each recursive call and depth goes down by one and ply will be one greater.
The traditional value is MATE - ply. If you are going to return it, then -MATE + ply.
so then my -MATE + (calculated ply) should be right?
i can try to add another parameter (ply) to the call and see if i get the same results.
if what i have read is correct, you always return the mate as being BAD for the side to move, hence the (-)MATE, correct?
Vince
Re: Negamax questions
Posted: Wed Jun 03, 2015 3:26 am
by hyatt
thevinenator wrote:hyatt wrote:Typically depth is a value that counts down as you advance toward the tips.
depth is correct, it counts down...see the embedded recursive call.
I didn't want to carry another counter on the stack and since i know the StartDepth, i was trying to convert the combination of the two to "ply".
so, for example if i do a 3-ply search, StartDepth is set to 3 along with depth.
the first recursive call, depth = 2, and (StartDepth - depth) will = 1. isn't that what ply should be ? each recursive call and depth goes down by one and ply will be one greater.
The traditional value is MATE - ply. If you are going to return it, then -MATE + ply.
so then my -MATE + (calculated ply) should be right?
I don't see how it could be right, because depth doesn't change at every ply by -1, assuming you do extensions and reductions. So it will represent the wrong value. You must have a "ply" or something I would think, but if you don't, I don't see how what you are doing can work, because a mate score is relative to the distance from the root of the tree to the position where there are no legal moves. But depth might not change at all. Suppose you do check extensions AND one-legal-reply-to-check extensions. If the first three moves for white are checks, and the first two moves by black are one legal reply positions, depth would not have changed, and you couldn't derive a mate score from that number...
i can try to add another parameter (ply) to the call and see if i get the same results.
if what i have read is correct, you always return the mate as being BAD for the side to move, hence the (-)MATE, correct?
Vince
Re: Negamax questions
Posted: Thu Jun 04, 2015 6:56 pm
by H.G.Muller
By using 'depth' instead of 'ply' the engine would prefer to mate the opponent through a sequence of moves that trigger more extensions, rather than the branch that has the fewest moves. That is a funny way to do it, which would surely lead to lots of complains of users, but it would not really have any adverse effects on the engine's Elo.
An even better way to do it would be to also subtract the material evaluation. Then the engine would prefer to be checkmated with most material left, even if that would mean in fewer moves. So it would refrain from totally silly sacrifices, like throwing its Queen at the opponent's King fortress to deliver a spite check that delays the mate one move. So that when the opponent does not see the mate, it will not have a totally lost position. It only makes sense to make such sacrifices if the DTM after in is indeed larger than the DTM before it, because you hand the first move of the mating sequence to the opponent for free (as he will of course accept the sac, even if he had no idea there even was a mate). So it would make sense to count a Pawn for two moves.
Re: Negamax questions
Posted: Wed Jun 10, 2015 3:24 pm
by thevinenator
I found a bug elsewhere which was causing my problems. I think my code will work as long as, as pointed out, i don't change what depth is (extensions, etc). i will try adding a 'ply' value and try it again, though
two new questions along the same line.
1. i saw a comment on another web page where it indicated that the mate value must be adjusted when it is stored and retrieved from the TT. i haven't been able to find any good examples of how that is accomplished. Can someone point me to a good write up or example solution?
2. How are mates handled in Quiescent search extensions. I am working on adding a "capture" extension search and it is possible that a capture can cause mate. in the examples of Q-searches I've seen, most don't carry a depth value so how do you score the mate in these situations?
Re: Negamax questions
Posted: Wed Jun 10, 2015 6:10 pm
by hyatt
thevinenator wrote:I found a bug elsewhere which was causing my problems. I think my code will work as long as, as pointed out, i don't change what depth is (extensions, etc). i will try adding a 'ply' value and try it again, though
two new questions along the same line.
1. i saw a comment on another web page where it indicated that the mate value must be adjusted when it is stored and retrieved from the TT. i haven't been able to find any good examples of how that is accomplished. Can someone point me to a good write up or example solution?
2. How are mates handled in Quiescent search extensions. I am working on adding a "capture" extension search and it is possible that a capture can cause mate. in the examples of Q-searches I've seen, most don't carry a depth value so how do you score the mate in these situations?
question 1. Think about it in this way. In the search. a MATE score always represents mate-in-N moves from the ROOT position. Say you have the following PV: m1, m2, m3, m4, m5, m6, m7#. That would be considered mate in 4 moves (or better mate in 8 plies from the root (mate in 8 because at ply=8 you are checkmated with no legal moves.
If you store the position at ply=5, which would represent ONLY the sequence m5, m6, m7# you can't store "mate in 8 plies" as that is wrong. Given this position, it is mate in 4 plies. What you do is take the score at ply 5, which is "mate in 8 plies) and adjust it by -4 to make it "mate in 4 plies" and store this.
Now suppose you get a hash hit later after the move sequence: n1, n2 and you pull up this entry. It says "mate in 4 from this position, but you are two plies into the tree, so you add the 2 back in and make it mate in 6 plies. If you transpose the original moves, so that you search m3, m4, m1, m2 you get a hit on this same position. You pull mate in 4 plies from ttable entry, but since you are 4 plies into the tree, you add that 4 in, and you are back to (again) the correct mate score (mate in 8 plies from the root).
Hope that helps.