A Qsearch idea

[Fguy64]

OK, after much ripping of hair and gnashing of teeth, i think I have finally nailed down the collection of PV from qSearch. I had it working before, when my search code was doing double duty for both full-width and qSearch, but eventually decided that approach had its own set of problems and it was better to separate the two.

Below is my qSearch method. As usual I come up with something that seems correct, my test results look ok, I'm just not sure how to prove the point, so I was hoping someone could give it a quick eyeball and let me know if they see anything obviously wrong.

OK, in full width search I now have a recursion variable (depth remaining) that decrements to 0. In the initial call to qSearch, when depth = 0 in alphaBeta, I pass 0 as a ply recursion variable. You can see that in Q my recursion variable is incremented. This is used only to index/enumerate the PV and possible moves arrays in Q. There is no explicit stop conditionj. maxPly is my full width search depth, maxDepth repreents the total of the full width search depth and the maximum possible qSearch depth. I think the biggest problem I had before was in putting the PV[ply][ply] = 0 statement in the wrong place. The alpha update code is the same for both regular and Q search.

Code: Select all

private int qSearch( int qPly, int alpha, int beta ) {

    int eval = evaluate();
    if( eval >= beta ) return beta;
    if( eval > alpha ) alpha = eval;
	
    State gs1 = new State();
    int m, p0, p1;	// move, moved piece, captured piece
    int ply = maxPly + qPly;
    PV[ply][ply] = 0;

    qGen( qPly );
	
    int start = (qPly>0) ? qPtr[qPly-1]+1 : 0;
    for( int i = start; i <= qPtr[qPly]; i++ ) {
        m = qList[i];

        p0 = posn[(m>>8)&127]; p1 = posn[(m>>15) & 127];
        copyState( gs, gs1 );
		
        makeMove( m );
		
        if( gs.isLegal ) {
		
            eval = -qSearch( qPly+1, -beta, -alpha );
			
            unmakeMove( m, p0, p1 );
            copyState( gs1, gs );
			
            if( eval >= beta ) return beta;
            if( eval > alpha ) {
                alpha = eval;
                PV[ply][ply] = m;
                System.arraycopy( PV[ply+1], ply+1, PV[ply], ply+1, maxDepth - (ply+1) );
            }
        }
        else {
            unmakeMove( m, p0, p1 );
            copyState( gs1, gs );
        }
    }
	
    return alpha;
}