Singular extension ... again

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
xr_a_y
Posts: 388
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Singular extension ... again

Post by xr_a_y » Tue Feb 19, 2019 8:44 pm

In Xiphos, one can read

Code: Select all

    // singular extensions
    if (depth >= SE_DEPTH && !skip_move && _m_eq(move, hash_move) &&
        !root_node && !_is_mate_score(hash_score) &&
        hash_data.bound == HASH_LOWER_BOUND && hash_data.depth >= depth - 3)
    {
      beta_cut = hash_score - depth;
      score = pvs(sd, 0, 0, beta_cut - 1, beta_cut, depth >> 1, ply, 0, move);
      if (score < beta_cut)
        new_depth ++;
}
The "beta_cut" is hash_score - depth

In Stockfish

Code: Select all

 Value singularBeta = std::max(ttValue - 2 * depth / ONE_PLY, -VALUE_MATE);
In Ethereal

Code: Select all

 int rBeta = MAX(ttValue - depth, -MATE);
I don't get the "- N * depth" thing. What means a beta of TTscore minus N times depth ? In a pvs framework, what is the difference between score-2 or score-5 or score-10 ...
If it was ttscore - depth*pawnValue, i'll get it better...

can someone help ?

Ras
Posts: 1087
Joined: Tue Aug 30, 2016 6:19 pm
Contact:

Re: Singular extension ... again

Post by Ras » Tue Feb 19, 2019 10:11 pm

Maybe that's a re-adjustment of the score? Some engines give a bonus for delaying bad positions and a malus for delaying good positions, so that's how a depth and a score could be tied together.
Rasmus Althoff
https://www.ct800.net

User avatar
Eelco de Groot
Posts: 4028
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Singular extension ... again

Post by Eelco de Groot » Wed Feb 20, 2019 4:43 am

I read it a bit like this. If you are close to the horizon, ttValue is correlated more highly with the static evaluation of the position, your best estimate of a precise value now. But as depth goes up and you get back the result of a nullwindow search with a lower bound, the lower bound becomes more trustworthy if depth goes up, but you don't know the actual evaluation as well anymore, depending on where you are in the tree. You want to compare other moves with the actual evaluation of the best move, because especially if it is a positional decision you are making, it is about small differences and you are not asking if other moves are alpha or lower, but if they are worse than the precise evaluation of the ttMove, which you presume is best. Because also if ttValue is the result of testing against an old alpha, you don't know the precise evaluation. This is far less an issue if you got back the result of an 'exact' search, a result that lies within a small alpha-beta window. If it is a lowerbound only, you actually don't know anything about all the other moves, combined with the effect that you only know a lower bound for the ttMove.

Because you don't have the exact evaluation if it is just a lower bound, you can push down your singularBeta to get more certainty that everything else is actually worse. Doing so you improve your knowledge of all the other move possible in that node which would otherwise deteriorate, because of the same process of testing only one move against better than some alpha value and stop if that is true. If your best move suddenly proves to be not so good after all, you have a better ordered tree of all the other moves in that node.
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

User avatar
xr_a_y
Posts: 388
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Singular extension ... again

Post by xr_a_y » Wed Feb 20, 2019 6:09 am

But I thought that singular extension aimed at looking if in the current situation there is only one good move (and then extend).
If depth of the tt move is enough, and we trust it, I was thinking that at least ttscore-pawnValue was the bound to use (in a fail soft framework).

Maybe all those very good engines can say the "only good move" is just 10cp above the others, but I guess for less powerfull engine 80 or 100cp is needed no ?

User avatar
Eelco de Groot
Posts: 4028
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Singular extension ... again

Post by Eelco de Groot » Wed Feb 20, 2019 6:58 am

Hi Vivien,

The more nodes in which your engine can find the best move, also if the differences appear small, the better it will play positionally and that wins games, even for someone who is as strong as Morphy. But alpha beta (maybe even more the case for PVS) is geared very much to playing 'not losing' if it does not really understand the position. It will extend the PV as far as it can and if it sees no loss, it thinks it is at least safe for now and then it will check the other moves to see if there maybe some good tactical shot it missed. To be safe, it extends those as far as possible again checking at least if in any line, the opponent appears to have one refutation to most of your moves. If anything goes wrong in this process, you have a tree which is deep, but very sparse. In all the Cut nodes there was only one move, but it proved a wrong one. To build up a new tree can literally take ages because it was ordered the wrong way. You lose on time :) To remedy this a bit, you have to know more about all the other moves, before they become necessary. If you have no move yet or you lost it when putting new things in hash, you do IID. If you have at least one likely move, but nothing more, you do preemptive IID. In PV nodes, you test all moves (unless you there also just want something good enough, but that is not the philosophy of alpha beta. In other ALL nodes, you also test most of the moves. So, the Stockfish singular extension is mostly this preemptive IID, and for PV nodes I think you could try some other things because there preemptive IID is not so necessary.

The original singular extension was for Deep Blue, which did not even have a hash table. It was mostly finding tactical shots because of its very deep searches with it. But it has not so much to do with the modern versions of same name...
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

Karlo Bala
Posts: 299
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Singular extension ... again

Post by Karlo Bala » Wed Feb 20, 2019 10:38 am

xr_a_y wrote:
Wed Feb 20, 2019 6:09 am
But I thought that singular extension aimed at looking if in the current situation there is only one good move (and then extend).
If depth of the tt move is enough, and we trust it, I was thinking that at least ttscore-pawnValue was the bound to use (in a fail soft framework).

Maybe all those very good engines can say the "only good move" is just 10cp above the others, but I guess for less powerfull engine 80 or 100cp is needed no ?
The whole idea of SE is to overcome the horizon effect, therefore SE is less important when the depth is big and more important near the leaves. Also, when the depth is big the cost of the SE is big, that is why the SE margin is wider with bigger depth. The effect is that when the depth is too big, SE is turned off.
Of course, this is just a theory. Some authors say that fixed margin is the best. I doubt there is a significant difference.
Best Regards,
Karlo Balla Jr.

Post Reply