A Qsearch idea

[Fguy64]

OK, I just wanted to toss around a qSearch idea I had. It came about because I was really struggling to understand what was going on in my qSearch, collecting PV was not so cut and dry (for me at least). My qSearch does seem to work as far as I can see, but...

in my engine, there is a single external call to alphaBeta, so there is no separate "root search". I pass '1' to alphaBeta as the ply, then my stop condition is if( ply > maxPly ) return qSearch( 1, alpha, beta ) etc. Then there is a separate qSearch function. This plan of calling a separate search function when the maximum search depth is reached in "normal search" is pretty much "de rigeur" as far as I know.

What about this...

instead of having a separate qSearch function, when maxPly is reached why not just call a separate moveGen function that generates only captures, and cointinue to use the alphaBeta method. As far as I can see the only adjustment one should have to make is how to handle the situation where moveCOunt is zero. Instead of testing for checkmate or stalemate, you would just return alpha if the maxPly had been exceeded.

Do people do things like this, or is there some fatal flaw in my idea that has escaped me?

[mjlef]

OK, I just wanted to toss around a qSearch idea I had. It came about because I was really struggling to understand what was going on in my qSearch, collecting PV was not so cut and dry (for me at least). My qSearch does seem to work as far as I can see, but...

in my engine, there is a single external call to alphaBeta, so there is no separate "root search". I pass '1' to alphaBeta as the ply, then my stop condition is if( ply > maxPly ) return qSearch( 1, alpha, beta ) etc. Then there is a separate qSearch function. This plan of calling a separate search function when the maximum search depth is reached in "normal search" is pretty much "de rigeur" as far as I know.

What about this...

instead of having a separate qSearch function, when maxPly is reached why not just call a separate moveGen function that generates only captures, and cointinue to use the alphaBeta method. As far as I can see the only adjustment one should have to make is how to handle the situation where moveCOunt is zero. Instead of testing for checkmate or stalemate, you would just return alpha if the maxPly had been exceeded.

Do people do things like this, or is there some fatal flaw in my idea that has escaped me?

This could be done and in fact was done in an old version of my program. The changes between the full width and qsearch are normally:

a. Different sets of moves generated
b. qsearch assumes (as long as the side to move is not in check) that the side to move can either take the current eval, and make no move, or optionally the score returned from one of its moves. So most programs handle this by setting the best score on entry to the eval.
c. in the qsearch, you also check if the current eval is >=beta and if so, return that score (or beta). Since under b above, we accept the right to use the current score, then if it is high enough it is a fail high.

note that b and c are not doing in the main search.

Mark

[Fguy64]

OK, I just wanted to toss around a qSearch idea I had. It came about because I was really struggling to understand what was going on in my qSearch, collecting PV was not so cut and dry (for me at least). My qSearch does seem to work as far as I can see, but...

in my engine, there is a single external call to alphaBeta, so there is no separate "root search". I pass '1' to alphaBeta as the ply, then my stop condition is if( ply > maxPly ) return qSearch( 1, alpha, beta ) etc. Then there is a separate qSearch function. This plan of calling a separate search function when the maximum search depth is reached in "normal search" is pretty much "de rigeur" as far as I know.

What about this...

instead of having a separate qSearch function, when maxPly is reached why not just call a separate moveGen function that generates only captures, and cointinue to use the alphaBeta method. As far as I can see the only adjustment one should have to make is how to handle the situation where moveCOunt is zero. Instead of testing for checkmate or stalemate, you would just return alpha if the maxPly had been exceeded.

Do people do things like this, or is there some fatal flaw in my idea that has escaped me?

This could be done and in fact was done in an old version of my program. The changes between the full width and qsearch are normally:

a. Different sets of moves generated
b. qsearch assumes (as long as the side to move is not in check) that the side to move can either take the current eval, and make no move, or optionally the score returned from one of its moves. So most programs handle this by setting the best score on entry to the eval.
c. in the qsearch, you also check if the current eval is >=beta and if so, return that score (or beta). Since under b above, we accept the right to use the current score, then if it is high enough it is a fail high.

note that b and c are not doing in the main search.

Mark

right that seems clear enough.

so instead of starting my alphaBeta method with

Code: Select all

if( ply > maxPly ) return qsearch(alpha,beta)

I start with

Code: Select all

if( ply > maxPly ) {
	eval = evaluate();
	if( eval >= beta ) return beta;
	if( eval > alpha ) alpha = eval;
	capGen();
}
else moveGen();

and at the end replace

Code: Select all

if( count == 0 ) {
	if( inCheck() ) return -(100000-ply+2);
	else return 0;
}
return alpha;

with

Code: Select all

if( ply<=maxPly && count==0 ) {
	if( inCheck() ) return -(100000-ply+2);
	else return 0;
}
return alpha;

or something very much like that.

Thanks

[MattieShoes]

Yeah, you've got it. You can't do a standard captures-only alpha-beta instead of q-search because it would force the sides to make stupid captures (like QxP resulting in PxQ, etc), thereby totally hosing the score.

Essentially, Q-search is alpha beta with different rules for cutting off the search. Alpha beta ends when depth hits zero, but q-search ends when the side to move elects not to capture a piece.

[Fguy64]

Thanks Matt.

OK, that went well enough. There still remains the challenge of knowing two things...

1. How deep the search goes in the principal variation.
2. How deep the maximum achieved depth was.

I suppose that is easy, just increment a variable at each successive call to search until there is either a beta cutoff ( in one of two places: regular or stand pat ) or when we reach a moveCount of 0 ( either mate or no more captures. The variable would need to be initialized for each move at the root node, and I guess stored with each change in the principal variation (i.e. each alpha update).

Anyways, the whole point of this exercise is that it makes it easier for me to manage the principal variation. Although I suppose it may complicate the situation when it comes to any kind of advanced pruning strategy other than alphaBeta, which is not likely to happen any time soon.

[hgm]

Joker uses the same routine for QS and main search. It just calls a different move generator. Micro-Max even calls the same move generator. (Well, not really calls, as Search() basically is the move generator; there is only a single function (apart from main()) in micro-Max.) It decides if it wants to search the generated move afterwards, based on if it is a capture or not.

The initial value of bestScore is chosen as Eval() in QS, and as -INFINITY at other depth. In both cases it is tested if it is >= beta, in order to produce a cutoff. This gives automatic mate-distance pruning if -INFINITY >= beta.

[Fguy64]

This has all turned out rather well, everything works, except when it comes time to collecting the principal variation, I am forced to concede I haven't a clue. And I could use a little help.

The idea is to collect and display a full PV, I am not trying to use it yet, just display it What is happening is that PV is collected properly for the full width portion of the search, but for the Q portion of the search the reported PV is garbage. But Q works.

ok I have something called maxDepth which is the maximum of full width search and qSearch combined. Then I have something called maxPly, which is my full width search depth. Ok in my initial call to search '1' is passed as the recursion variable ply, and when ply > maxPly, the capture generator kicks in.

my Principal value array is defined as PV[maxDepth+1][maxDepth+1]. The zero indices are never used, and PV[1][1] is returned as the optimal move.

here us the code that is used to display the PV after it is collected...

Code: Select all

int j=0;
int src, dest;
while( ( ++j <= maxDepth ) && ( PV[1][j] != 0 ) ) {
	src = (PV[1][j] >> 8) & 127;
	dest = (PV[1][j] >> 15) & 127;
	pvBuf.append( Utils1.toAlg.get(src) +"-" +Utils1.toAlg.get(dest) +" " );
}
pvBuf.append("\n");

And here is my search method. I won't try to explain right away, but if someone takes a look and has any questions about how I want it to work, I'm ready to respond. I can also make complete source code and/ or a runnable java applet on request.

Code: Select all

int search( int ply, int alpha, int beta ) {

	if( ply > maxDepth ) return evaluate();

	int eval;

	if( ply > maxPly ) {
		if( qS ) {
			eval = evaluate();
			if( eval >= beta ) return beta;
			if( eval > alpha ) alpha = eval;
			qGen(ply);
		}
		else return evaluate();
	}
	else moveGen( ply );
	
	int count=0;
	State gs1 = new State();
	int m, p0, p1;
		
	for( int i=(mPtr[ply-1]+1); i<=mPtr[ply]; i++ ) {

		m = mList[i];

		p0 = posn[(m>>8)&127]; p1 = posn[(m>>15) & 127];
		copyState( gs, gs1 );

		makeMove( m );

		if( gs.isLegal ) {
			count++;
			
			eval = -search( ply+1, -beta, -alpha );
			
			unmakeMove( m, p0, p1 );
			copyState( gs1, gs );

			if( eval >= beta ) {
				if( ply == 1 ) {
					PV[1][1] = m;
					Arrays.fill( PV[1], 2, maxDepth+1, 0 );
				}
				return beta;
			}
			if( eval > alpha ) { 
				alpha = eval; 
				PV[ply][ply] = m;
				Arrays.fill( PV[ply], ply+1, maxDepth+1, 0 );
				if( ply < maxDepth ) System.arraycopy( PV[ply+1], ply+1, PV[ply], ply+1, maxDepth-ply );
			}
		}
		else {
			unmakeMove( m, p0, p1 );
			copyState( gs1, gs );
		}
	}
	
	if( ply <= maxPly && count == 0 ) {
	
		Arrays.fill( PV[ply], ply, maxDepth+1, 0 );
		if( inCheck() ) return -(100000-ply+2);
		else return 0;
	}

	return alpha;

}

[MattieShoes]

You might want to look at the code of TSCP. It's fairly small (2000 lines or so?) so you don't get lost in the code, and it stores the PV.

[Alessandro Damiani]

You just have to "close" the PV in quiescence search through "PV[ply][ply] = 0":

Code: Select all

	if( ply > maxDepth ) {
		PV[ply][ply] = 0;
		return evaluate();
	}

Code: Select all

	if( ply > maxPly ) {
		PV[ply][ply] = 0;
		if( qS ) {
			eval = evaluate();
			if( eval >= beta ) return beta;
			if( eval > alpha ) alpha = eval;
			qGen(ply);
		}
		else return evaluate();
	}
	else moveGen( ply );

[Fguy64]

Thanks, Alessandro, I figured it had to be something like you suggested, but when I tried your ideas, it didn't seem to make much, if any, difference.

I eventually tried the following modification to the code block that handles alpha updates, with no other changes to my original search posted above and it appears to have resolved the issues, although my tests have not been exhaustive.

Code: Select all

if( eval > alpha ) { 
    alpha = eval; 
    PV[ply][ply] = m;
    if( ply < maxDepth ) {
        System.arraycopy( PV[ply+1], ply+1, PV[ply], ply+1, maxDepth-ply );
        Arrays.fill( PV[ply+1], ply+1, maxDepth+1, 0 );
    }
}