Collecting the principal Variation

[Desperado]

Hello Fred,

Code: Select all

...

if( count == 0 ) {
    PV[ply][ply] = 0; 
    for&#40; int j=ply+1; j<=maxPly; j++ ) &#123; 
        PV&#91;ply&#93;&#91;j&#93; = 0; 
    &#125; 
    if&#40; inCheck&#40;gs&#41; ) return -&#40;100000-ply+2&#41;;
    else return 0;
&#125;

...

let s see if i understand correctly what happens there.

- if no legalMove available (count==0) cleanup successors,
beginning at current ply.
After cleanup return mate/stalemate score.
- on ply-1, if returned value is a pvValue and you copy the pv
you are now able to detect, that there arent any successors.

ok, if i understood this is doing the job principal, but
there several things to think about.

analyse
=================

1:
you dont have to loop the "successors". it is enough to set
the PV[ply][ply] = noMove (0).

Because on ply-1 ...

Code: Select all

    PV[ply][ply] = m; 
    for&#40; int j=ply+1; j<=maxPly && PV&#91;ply+1&#93;&#91;j&#93;; j++ ) &#123; 
        PV&#91;ply&#93;&#91;j&#93; = PV&#91;ply+1&#93;&#91;j&#93;; 

... the copyProcess is stopped anyway. (PV[ply+1][j]==0)

so now your code may look like this.

Code: Select all

if( count == 0 ) { 
    PV[ply][ply] = 0; 
    /*noLoop*/
    if( inCheck(gs) ) return -(100000-ply+2); 
    else return 0; 
} 

2: the cleanupProcess(PV[ply][ply]=0) is done (maybe only)
depending on the mate/stalemate recognition. Of course there is
no move, but there are several other searchstates, where also no
move is available. In all this cases you have to set the pv[ply][ply]
to noMove(0) before returning a value !? (hope you will never forget
).

So my proposal is: clean the PV[ply][ply] on entering the search.

Code: Select all

SCORE_T search(params)
{ 
 PV[ply][ply] = 0;
 
  ...further code...
 return(alpha / score ) //failHard/failSoft
}

So if the slot will not be filled by a move it is automatic null.You can
simple return the score you found.

2a: make sure that after any kind of shallow search/ nullmoveSearch
... you reset PV[ply][ply] again, if the search continues or the
pvSlot has no valid move.(to be on the safe side).

3:

what is left now ?! (only detecting mate/stalemate!)

Code: Select all

if( count == 0 ) 
{ 
    //done on entering the search
    //and because no move is available
    //it cannot be overwritten, and is kept 0
    /*PV[ply][ply] = 0;*/ 

    /*noLoop*/

    if( inCheck(gs) ) return -(100000-ply+2); 
    else return 0; 
} 

well, i dont really understand your mateScore.
an easy mateScore statement could look like this:

return(LOBOUND+ply)

4: return values & failhard/faillow

as long as your engine doesnt profit enormously from failsoft framework,
i also would propose to use the failard framework. It is much easier
to follow what happens in the search.

FAILHARD: Alpha <= Score <= Beta

First i never thought about fhard/fsoft, but short time ago i tried to understand. So, if you use this framework you only have to make
sure you

never return a value < alpha (as i understand)

which leads to the following statements.

Code: Select all

SCORE_T search(...params...)
{
 ...
 ...
 ...
 return&#40;bestscore < alpha ? alpha &#58; bestscore&#41;
&#125;

//especially for you mate/stalemate scheme

if&#40;count==0&#41;
&#123; 
 if&#40;inCheck&#41; return&#40;MATESCORE < alpha ? alpha &#58; MATESCORE&#41;
 else return&#40; 0 < alpha ? alpha &#58;  0 )
&#125;

the effect is:

Scenario1:

PLY : score >= beta(cut)
PLY-1: score < alpha (which is upvalued at the end to alpha)

Scenario2:

PLY : score < alpha (upvalue score to alpha)
PLY-1: score==beta (cut)


regards, Michael

[Fguy64]

Thanks Michael, It'll take some time to properly digest your post. I'm not sure if a lot of it is currently relevant to my simplistic engine, right now it's just plain old vanilla alphabeta. But there is some good material here I hope to do it justice in the next few days.

Anyways, if you are interested, you can see from my alphaBeta code that it's a pretty basic engine. http://fchess.pastebin.com/f1c534288

and you can see the results here

http://fchess.uuuq.com/fchess2/fchess2b.htm

Actually the positional eval is switched off at the moment, so it plays like crap, I do that when I want to focus on the alphaBeta.

[Don]

OK, I am trying to do collect the PV, and it is just not happening.

Just to set the stage, I am working with just alphabeta search, no qSearch, no iterative deepening, no hash table.
I use the terms maxPly to denote the initial search depth, and the term ply to denote the decreasing search depth at each call to alphaBeta, so ply goes from maxPlay to 0, at which point eval() is called. Finally, I am working with a single external non-recursive call to alphaBeta.

The PV moves are being stored in an array PV of length maxPly. Each time alpha is updated, a copy of the move being evaluated is saved in PV[maxPly-ply].

So anyways, the first move PV[0] is always the final move chosen, after that things are pretty much garbage. I imagine I am missing the point somewhere.

Any suggestions would be welcome.

Here is what I do

Code: Select all

    int search(  ....,    move_t  *pv )
    {


    }

when you call search you pass in a move_t array of size 32 (or however long you want it.) i.e.

move_t pv[32];
search( ...., pv );


Inside the search I have another array I call subPV which is the same

Code: Select all

    int search( ....,   move_t  *pv) 
    {
         move_t  subPV[32];

         pv[0] = NO_MOVE;   // make sure garbage isn't here

         // call search recursively
         sc = -search( x, y, z,  subPV );

         if move is best then {
               pv[0] = current move;
               memcpy( pv + 1,  subPV,  sizeof(move_t) * 31 );
         }
    }

Make sure that you always have some end of PV sentinal such as the null move or something so that when you display the pv you know where to stop.

At the very begining of the search you should set the pv to the sentinal:

pv[0] = NO_MOVE;

In quies this would mark the end of the list.

does that make sense?

- Don