🚀 go-pugleaf

Joel Rivat (rivat@univ-lyon1.fr) wrote:

: >There can be a slight improvement made to the zero window searching
: >that is carried out in gnuchess.  There are 2 places where a zero window
: >search is done.  The first is when NULLMOVE is defined and a null move
: >search is carried out.  Here a window of (beta, beta+1) is being used.
: >It turns out that we can use a window of (beta, beta).  Now if a score
: >of beta+1 is obtained, we have a beta cut whereas in the former case, this
: >will not give a cut.  This 1 point change makes a difference because
: >in the hashtable, a lowerbound is stored as beta+1.  What this means is
: >that when a lowerbound entry of beta+1 is found in the hashtable, a cut is
: >obtained whereas in the former, it would not be identified as a cut.

: >Similarly, during zero window searching in PVS, instead of using a
: >window of (alpha, alpha+1), a window of (alpha, alpha) can be used.

: >Several experimental runs shows an improvement of 2-3% in the number of
: >nodes searched.


: >Kong Sian


:   This does not seem correct to me:

: as far as I know the correct definition of the PVS is:

: int PVS(int alpha,int beta,...)
: {
: int v;
: ...
: return v;
: }

: and we have the 3 following properties:
: * if (v<=alpha)     then (V<=v)  upperbound
: * if (alpha<v<beta) then (V==v)  exact value
: * if (v>=beta)      then (V>=v)  lowerbound
: where V is the "true" value...

: Hence it is always v that we put in the transposition table.

: the condition for a cut off in the search is (v>=beta)

: the idea of the minimal window search (best,best+1)
: is to know very fast that the current move has a value<=best,
: or that value>=(best+1).

: if you call PVS with a window(best,best) and it returns best,
: you don't know wether the value is <= or > than best...

: This is also true for NULLMOVE search...

: When reading your post I think that the hash tables are
: incorrect in gnuchess, and PVS has to be checked...

:     Joel Rivat


I agree with your analysis.  The thing is that in gnuchess, the alpha-beta
implementation is such that a beta cut is obtained when score > beta
instead of the more traditional score >= beta.  Hence my suggestion does
seems to be okay.

Perhaps it should be changed to following the more traditional alpha,beta
algorithm.

Kong Sian