LMR at CUT nodes can be arbitrarily bad!

[Daniel Shawul]

Try this for LMR at both ALL/CUT nodes

Code: Select all

    def pvs_LMR(self,alpha,beta,nodetype):
        global count
        count+=1
        if(self.d==0):
            return self.value
        else:
            for i in xrange(0,self.w):
                if nodetype==PV and i==0:
                    s=-self.tree[i].pvs_LMR(-beta,-alpha,PV)
                    if s>=beta:
                        return s
                    elif s>alpha:
                        alpha=s
                else:
                    if nodetype==PV or nodetype==ALL: # if nodetype==PV then  i>0
                        nodetype_child=CUT
                    else:
                        nodetype_child=ALL
                    #Fake LMR
                    if nodetype==ALL:
                        s=rand() # fake result of LMR search
                        if s <= alpha&#58;
                            s=-self.tree&#91;i&#93;.pvs_LMR&#40;-beta,-alpha,nodetype_child&#41;
                    elif nodetype==CUT&#58;
                        s=rand&#40;) # fake result of LMR search
                        if s>=beta&#58;
                            s=-self.tree&#91;i&#93;.pvs_LMR&#40;-beta,-alpha,nodetype_child&#41;
                    elif nodetype==PV&#58;
                       s =-self.tree&#91;i&#93;.pvs_LMR&#40;-alpha-1,-alpha,nodetype_child&#41;
                    else&#58; #no LMR at other node types
                       s =-self.tree&#91;i&#93;.pvs_LMR&#40;-beta,-alpha,nodetype_child&#41;
                    if nodetype==PV and s>alpha&#58; # PVS research
                        # Normally we could raise alpha here
                        # but with our broken LMR this fails
                        ###########################
                        #if s>=beta&#58;
                        #   return s
                        #alpha=s
                        ###########################
                        s=-self.tree&#91;i&#93;.pvs_LMR&#40;-beta,-alpha,PV&#41;
                    if s>=beta&#58;
                        return s;
                    elif s>alpha&#58;
                        alpha=s
                        
            return alpha

[Daniel Shawul]

The premise of LMR according to Tord is to handle fail low nodes hence research when score > alpha.
But I am saying research when the score you got from reduced depth search differs from what you expect from the node type.

Code: Select all

a) Reduce the move and search it 
b) At CUT node, see if the score >= beta, and research if that is the case 
c&#41; At ALL nodes, see if the score <= alpha, and research if that is the case 

instead of

Code: Select all

a)  Reduce the move and search it 
b)  score >= beta, research for all types of nodes 

It looked awesome until I realized researching at an ALL node when it fails low is going to so costly so one might as well don't do reductions there at all. In any case researches should done to those moves that could change the PV in nega-scout search. Then ALL nodes should be researched when they fail low not fail high but it is seems too costly. But I guess it is worth a try since CUT nodes are much more than ALL nodes about CUT/ALL~BF on odd plies. So with that researching all moves in ALL node when they fail low may not be as costly as it first looks.

[Daniel Shawul]

To finish this up I did the following.

a) I added LMR at PV nodes. Guess when we should re-search there at PV nodes? It is same criteria as the ALL node's i.e when score <= alpha or score fails low. This is because a fail high gets researched automatically by PVS so score >= beta are safe. If you check score >= beta at PV nodes it fails because that check is redundant. So this justifies the use of score <= alpha at ALL nodes too. At both PV and ALL we search all moves so this is expected.

b) Second for this and your origianl code to work the NegaScout has to be modified to always do re-searches when score >= alpha!! The correct negascout implementation is to re-search only when score falls in between alpha and beta.

Code: Select all

score > alpha and score < beta

Look at chess wiki . So it was not PVS(negascout) you were using
That is it, done and dusted!

Code: Select all

    def pvs_LMR(self,alpha,beta,nodetype):
        global count
        count+=1
        if(self.d==0):
            return self.value
        else:
            for i in xrange(0,self.w):
                if nodetype==PV and i==0:
                    s=-self.tree[i].pvs_LMR(-beta,-alpha,PV)
                    if s>=beta:
                        return s
                    elif s>alpha:
                        alpha=s
                else:
                    if nodetype==PV or nodetype==ALL: # if nodetype==PV then  i>0
                        nodetype_child=CUT
                    else:
                        nodetype_child=ALL
                        
                    #Fake LMR
                    if nodetype==ALL:
                        s=rand()
                        if s <= alpha&#58;
                            s=-self.tree&#91;i&#93;.pvs_LMR&#40;-beta,-alpha,nodetype_child&#41;
                    elif nodetype==CUT&#58;
                        s=rand&#40;)
                        if s >= beta&#58;
                            s=-self.tree&#91;i&#93;.pvs_LMR&#40;-beta,-alpha,nodetype_child&#41;
                    else&#58; #PV node
                        s=rand&#40;)
                        if s <= alpha&#58;
                            s=-self.tree&#91;i&#93;.pvs_LMR&#40;-alpha-1,-alpha,nodetype_child&#41;

                    #PVS re-search 
                    if nodetype==PV and s>alpha&#58; # NOT a real PVS research! add score < beta for proper negascout
                        s=-self.tree&#91;i&#93;.pvs_LMR&#40;-beta,-alpha,PV&#41;

                    #update bounds
                    if s>=beta&#58;
                        return s;
                    elif s>alpha&#58;
                        alpha=s
                        
            return alpha

[Michel]

Thanks!

I did not try your adaptations yet but I trust it that they do what you write.

So your observation is that in order not to disturb the value at the root it is sufficient to research immediately when the result of the reduced search _matches_ what is predicted by the node type.

But in case your LMR is perfect this would effectively be equivalent to not doing LMR at all at ALL nodes. Indeed the LMRed moves will always fail low and so will always be researched.

[Michel]

The correct negascout implementation is to re-search only when score falls in between alpha and beta.

Yes you are right. I missed this in my PVS implementation (in ordinary PVS
without LMR you can fully trust the bounds given by scout searches).

I will update the script.

[Michel]

I think the results of this discussion can be summarized conveniently as follows.

For PVS to return the minimax value of the tree in the presence of reductions/pruning etc... it is necessary and sufficient that an _upper bound_ returned by a scout search is sane.

As a corollary one obtains that a lower bound returned by a CUT node should be sane and similarly an upper bound returned by an ALL node should be sane.

[Daniel Shawul]

The most interesting aspect of it for me was I was not sure when we should do researches for LMR. Given a reduced depth result, how would you know if the reduction is the cause of a fail high o fail low? It is not so clear whether to do re-searches for score <= alpha or score >= beta. If you take a criteria that "Do re-searches if the result is going to make it to the PV", then you will have something completely opposite done at ALL/CUT nodes. Standard LMR always does a score>alpha but not all moves which update alpha are going to make it to PV. It used to be called "fail low reduction" but I am not sure if it is related to fail low nodes only. Thanks for the code btw , I will use it to test more stuff.
Daniel