Your squeeze/stretch seem to be about the same as my CalcSvUp/CalcSvDn except that you negate the results. If you always prune at the right time when generating a new window one ply down, then I suppose it will work without having the safety range margins.Rein Halbersma wrote:Of course, you have to be careful not to let the search window collapse when one of the bounds crosses over to infinity. This is done by mate distance pruning:sje wrote:When moving one ply down (away from the root), the window bounds are swapped and then shifted down. When moving one ply up (towards the root), the result score is shifted up.
Note: It is possible to get scores better than mate in one or worse than checkmated, so there has to be a safety range between mate in one and +infinity and also between checkmated and -infinity. This safety margin length has to be at least as long as the greatest possible search ply.Code: Select all
// alpha < beta <= +INF implies alpha <= win_min // with equality, any finite score will fail low if (alpha == win_min()) return alpha; // -INF <= alpha < beta implies loss_min <= beta // with equality, any finite score will fail high if (beta == loss_min()) return beta;
Mate score in TT
Moderators: hgm, Rebel, chrisw
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Shifting scores down and up
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: Shifting scores down and up
I used to have a minus sign inside the stretch/squeeze, but I like it better to have the minus side outside. That way, it's slightly easier to search/replace (in the past I did distance to root scoring).sje wrote:Your squeeze/stretch seem to be about the same as my CalcSvUp/CalcSvDn except that you negate the results. If you always prune at the right time when generating a new window one ply down, then I suppose it will work without having the safety range margins.Rein Halbersma wrote:Of course, you have to be careful not to let the search window collapse when one of the bounds crosses over to infinity. This is done by mate distance pruning:sje wrote:When moving one ply down (away from the root), the window bounds are swapped and then shifted down. When moving one ply up (towards the root), the result score is shifted up.
Note: It is possible to get scores better than mate in one or worse than checkmated, so there has to be a safety range between mate in one and +infinity and also between checkmated and -infinity. This safety margin length has to be at least as long as the greatest possible search ply.Code: Select all
// alpha < beta <= +INF implies alpha <= win_min // with equality, any finite score will fail low if (alpha == win_min()) return alpha; // -INF <= alpha < beta implies loss_min <= beta // with equality, any finite score will fail high if (beta == loss_min()) return beta;
The pruning is not just to avoid bogus search windows. It also saves nodes (although the difference is never really big).
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Shifting scores down and up
But how should alpha become better than mate-in-1 or beta worse than checkmated, or vice versa?sje wrote:Example:Sven Schüle wrote:I don't quite understand that part, can you please elaborate a bit more on it? To my current understanding it would be sufficient to have something like "-infinity == checkmated - 1" and "+infinity == (mate in one) + 1", can you show a case where that would cause trouble?sje wrote:Note: It is possible to get scores better than mate in one or worse than checkmated, so there has to be a safety range between mate in one and +infinity and also between checkmated and -infinity. This safety margin length has to be at least as long as the greatest possible search ply.
How can evaluation or search return a score better than mate in one? And why does the greatest possible search ply influence the safety range you are referring to?
The search discovers a a checkmated position that when backed up to the root gets a mate-in-3 score for the corresponding root move. Later in the search and much deeper than the ply where the checkmated position was located, either alpha will be better than mate-in-1 or beta will be worse than checkmated (lose-in-0). So if there isn't some kind of protective pruning, the score values will be incorrect if there is no safety range margin as described above.
In my engines I take care to never let alpha and beta bounds take values outside the interval [checkmated - 1 .. mate-in-1-ply + 1]. The only place where I think this might become an issue is if you use aspiration windows and define bounds for the next iteration after the previous one returned a mate score.
Sven
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Shifting scores down and up
The savings can be large if there are a lot of mate/lose nodes. I've seen this with my dedicated mate finder routine.Rein Halbersma wrote:The pruning is not just to avoid bogus search windows. It also saves nodes (although the difference is never really big).
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Shifting scores down and up
I don't think this is a problem. In fact it is desirable, because it is simply mate-distance pruning.sje wrote:The search discovers a a checkmated position that when backed up to the root gets a mate-in-3 score for the corresponding root move. Later in the search and much deeper than the ply where the checkmated position was located, either alpha will be better than mate-in-1 or beta will be worse than checkmated (lose-in-0). So if there isn't some kind of protective pruning, the score values will be incorrect if there is no safety range margin as described above.
In micro-Max I have no safety margin (except that it counts from King capture rather than mate, so +INF = capture of King, -INF = illegal move, INF-1 = mate-in-1, 1-INF = mated-in-1,etc). The search starts with bestScore = -INF, and when beta <= -INF this gives an immediate stand-pat cutoff even outside QS, whih effects the mate distance pruning. Even giving your King away in 1 move would not be good enough for the opponent here, because he can already force earlier capture of your King in another branch.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Mate score in TT
Yes. You don't store the right value if I read your post correctly. What you want to store is some constant MATE - current ply. This turns the mate in N from the root to "mate in M from the current position." Now when you get that hit, you have to adjust the score again, buy ADDING ply, to convert it from mate in M from the current ply, to mate in N from the root, once again.mcostalba wrote:An almost universal accepted way to storing mate scores in the TT is the following:
In this way we always store in TT the number of moves to mate (to be mated) counted form the root. This is ok as far as root does not change, but suppose I find a mate in 7 for a given position P0, I will store it as (VALUE_MATE - 7). Now I do the move and go to position P1, the opponent replies and goes to position P2 from where I search again. I find a TT hit immediately and I read back the TT value with:Code: Select all
// value_to_tt() adjusts a mate score from "plies to mate from the root" to // "plies to mate from the current ply". Non-mate scores are unchanged. The // function is called before storing a value to the transposition table. Value value_to_tt(Value v, int ply) { if (v >= VALUE_MATE_IN_PLY_MAX) return v + ply; if (v <= VALUE_MATED_IN_PLY_MAX) return v - ply; return v; }
And I read (VALUE_MATE - 7) while instead, because in the meantime I have moved and the opponent has replied the correct value should be (VALUE_MATE - 5) because I am at 5 move to mate, no more 7.Code: Select all
// value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from // the transposition table to a mate score corrected for the current ply. Value value_from_tt(Value v, int ply) { if (v >= VALUE_MATE_IN_PLY_MAX) return v - ply; if (v <= VALUE_MATED_IN_PLY_MAX) return v + ply; return v; }
Am I missing something ?
This works and has always worked flawlessly for me...
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Shifting scores down and up
You gave a couple of the many reasons I always have simply adjusted the score when I store/retrieve, and don't bother adjusting anything otherwise. One also has to deal with adjusting mate bounds that get stored... but it all works out easily enough...sje wrote:When moving one ply down (away from the root), the window bounds are swapped and then shifted down. When moving one ply up (towards the root), the result score is shifted up.
Note: It is possible to get scores better than mate in one or worse than checkmated, so there has to be a safety range between mate in one and +infinity and also between checkmated and -infinity. This safety margin length has to be at least as long as the greatest possible search ply.Code: Select all
function SynthLoseInN(n: Integer): svtype; inline; begin SynthLoseInN := svlosein0 + n end; { SynthLoseInN } function SynthMateInN(n: Integer): svtype; inline; begin SynthMateInN := svmatein1 - n + 1 end; { SynthMateInN } function IsSvLosing(sv: svtype): Boolean; inline; begin IsSvLosing := (sv <> svbroken) and (sv <= svlonglose) end; { IsSvLosing } function IsSvMating(sv: svtype): Boolean; inline; begin IsSvMating := (sv <> svbroken) and (sv >= svlongmate) end; { IsSvMating } function IsSvLosingOrMating(sv: svtype): Boolean; inline; begin IsSvLosingOrMating := (sv <> svbroken) and ((sv <= svlonglose) or (sv >= svlongmate)) end; { IsSvLosingOrMating } function IsSvInRange(sv: svtype): Boolean; inline; begin IsSvInRange := (sv > svlonglose) and (sv < svlongmate) end; { IsSvInRange } function IsSvInfinite(sv: svtype): Boolean; inline; begin IsSvInfinite := (sv = svneginf) or (sv = svposinf) end; { IsSvInfinite } function CalcLosingDistance(sv: svtype): Integer; inline; begin CalcLosingDistance := sv - svlosein0 end; { CalcLosingDistance } function CalcMatingDistance(sv: svtype): Integer; inline; begin CalcMatingDistance := svmatein1 - sv + 1 end; { CalcMatingDistance } function CalcSvDn(sv: svtype): svtype; var myresult: svtype; begin if sv = svbroken then myresult := sv else if IsSvInRange(sv) then myresult := -sv else if IsSvInfinite(sv) then if sv = svneginf then myresult := svposinf else myresult := svneginf else if IsSvLosing(sv) then myresult := SynthMateInN(CalcLosingDistance(sv)) else myresult := SynthLoseInN(CalcMatingDistance(sv) - 1); CalcSvDn := myresult end; { CalcSvDn } function CalcSvUp(sv: svtype): svtype; var myresult: svtype; begin if sv = svbroken then myresult := sv else if IsSvInRange(sv) then myresult := -sv else if IsSvInfinite(sv) then if sv = svneginf then myresult := svposinf else myresult := svneginf else if IsSvLosing(sv) then myresult := SynthMateInN(CalcLosingDistance(sv) + 1) else myresult := SynthLoseInN(CalcMatingDistance(sv)); CalcSvUp := myresult end; { CalcSvUp } procedure WindowShiftDn(var window0, window1: windowtype); inline; begin window1.alfa := CalcSvDn(window0.beta); window1.beta := CalcSvDn(window0.alfa) end; { WindowShiftDn }
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Shifting scores down and up
From the micro-Max code:Sven Schüle wrote:But how should alpha become better than mate-in-1 or beta worse than checkmated, or vice versa?
Code: Select all
Search(alpha, beta)
{
alpha -= alpha < curEval;
beta -= beta <= curEval;
// usual code
...
return bestSore += bestScore < curEval;
}