A Qsearch idea

[hgm]

The bad capture is not in the PV, because it is not the best move. (Better is not to do the capture, that is why we call it bad.) By definition the PV contains only best moves. A move that does not raise alpha cannot be on a branch of only best moves (if you do no aspiration in the root). That is the basis of alpha-beta. If it does not raise alpha, it is either because in the same node a move before it raised alpha to a higher value than the current move's score, and so the latter is not the best. (It could be a tie, though; we are not wasting time on finding out if we have a tie, in alpha-beta.) Or it is because earlier along the branch you had a move that was better, so that you are already a few ply long working on a non-PV branch.

If stand-pat is the best move, there could be equal captures that score the same. But we try stand-pat first, as it is cheaper in case we get a cutoff. (When we are not on the PV.) Eventually you have to do a stand-at at the end of any branch that does not end in mate or stalemate (or rep-draws, if you detect them). Cheaper to do it immediately.

If you would not allow stand-pat, you would:
1) score each position without captures as stalemate, because you have nothing you can do and are not in check.
2) Be forced to sac all your material in bad captures like it was giveway, once you reach QS.

A giveaway engine indeed cannot stand pat until there are no captures. Stand-pat symbolizes the best non-capture, with the assumption that you usually do have a non-capture that will not give away anything.

[Fguy64]

much appreciated. I think I'm in pretty good shape. I was gonna say, why is it that the final echange of rooks is done in a full width 6-ply search, but eventually decided that is because move ordering made it the first move searched and the absence of a positional evaluation or more favorable exchange makes that exchange a given.

[Fguy64]

Recently I have been posting a lot about getting started with hash tables, and collecting PV from qSearch, and also usng the same alphaBeta code for both full width and quiescent search. Everything seems to have come together nicely, it all seems to work, touch wood. The only question mark is proving conclusively that my PV is as it should be, especially that from Q. I acknowledge that my testing capabilities aren't the best, for now I just have to paste a fen string, set my search depth, and eyeball the results.

OK, my full width search is fixed depth, which means no iterative deepening. I am collecting PV but not using it except for display purposes. My Qsearch is a full capture search with MVV/LVA move ordering. My current evaluate() just does a material balance using traditional piece values. My engine is currently supporting Queen promoton only, and does not deal with 50 move rule or repetition. maxPly represents the full width search depth, and maxDepth represents the max depth of full width and Q combined. Whch means at the moment that as my full width search depth increases, the maximum Qsearch depth decreases.

I would like to be able to paste a fen string, set the depth for my full width search, and eyeball the results. I guess am looking for test material that says "if you set your fixed depth search depth to this, you should get that PV. And the number of PV moves that exceed the fixed search depth must of course be Q moves.

For example, with WAC.003 position, 5rk1/1ppb3p/p1pb4/6q1/3P1p1r/2P1R2P/PP1BQ1P1/5RKN w - - , If I set my full width search depth to 2, I get the following PV, e3-g3 g5-g3 h1-g3 f4-g3 with a material balance of +1 for white. There looks to be a lot of good materal on WAC positions at a site such as http://www.jakob.at/steffen/hossa/testsuites/wac.html , but it is not clear how I can apply it given my current fixed depth, non-iterative full-width search.

Anyways, a java applet of my current program is here. The default test2 mode uses qsearch and material eval only. http://fchess.uuuq.com/test1/fchess3.htm If people have the interest to try one or two positions as I have described, that would be a bonus.

Here is my alphaBeta. I concede that my data structure for hashing is not the usual method, but I think it should be ok. If t seems a little long, it is because I have combned my hash reads and writes, and qSearch, into alphaBeta.

finally, my hash index uses 21 bits, so there are 2,097,151 entries (buckets?)

Code: Select all

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

//	if( !checkLists() ) { 
//		System.out.println("Houston we have a problem entering search at ply = " +ply);
//		System.exit(0);
//	}

	int eval;
	
	// hash probe
	int hI = (int) (zKey & 2097151L);
	if( (zKey == hKey[hI]) && (maxPly-ply <= hPly[hI]) ) {
		if( hType[hI] == 0 ) return hVal[hI];	// exact
		if( (hType[hI] == 1) && (hVal[hI]<=alpha) ) return alpha;
		if( (hType[hI] == 2) && (hVal[hI]>=beta) ) return beta;
	}

	byte hashType = 1;	// type alpha
	

	if( ply > maxPly ) {
		eval = evaluate();
		if( ply > maxDepth ) {
			hKey[hI] = zKey; hType[hI] = 0; hPly[hI] = (byte) 0; hVal[hI] = (short) eval;
			return eval;
		}
		PV[ply][ply] = 0;
		if( qS ) {
			if( eval >= beta ) return beta;
			if( eval > alpha ) alpha = eval;
			qGen(ply);
		}

		else {
			hKey[hI] = zKey; hType[hI] = 0; hPly[hI] = (byte) 0; hVal[hI] = (short) eval;
			return eval;
		}
	}
	else moveGen(ply);
	
	int count=0;
	State gs1 = new State();
	int m, p0, p1;
	long zBU;

	for( int i=(cPtr[ply-1]+1); i<=cPtr[ply]; i++ ) {
	
		m = cList[i];

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

		makeMove( m );

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

			if( eval >= beta ) {
				if( ply == 1 ) {
					PV[1][1] = m;
					PV[1][2] = 0;
				}
				hKey[hI] = zKey; hType[hI] = 2; hPly[hI] = (byte) (maxPly-ply); hVal[hI] = (short) beta;
				return beta;
			}
			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 );
				hashType = 0;	// exact
			}
		}
		else {
			unmakeMove( m, p0, p1 );
			copyState( gs1, gs );
			zKey = zBU;
		}
	}

	if( ply <= maxPly ) {
		
	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 );
		zBU = zKey;	

		makeMove( m );

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

			if( eval >= beta ) {
				if( ply == 1 ) {
					PV[1][1] = m;
					PV[1][2] = 0;
				}
				hKey[hI] = zKey; hType[hI] = 2; hPly[hI] = (byte) (maxPly-ply); hVal[hI] = (short) beta;
				return beta;
			}
			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 );
				hashType = 0;	// exact
			}
		}
		else {
			unmakeMove( m, p0, p1 );
			copyState( gs1, gs );
			zKey = zBU;
		}
	}
	
	if( count == 0 ) {
		PV[ply][ply] = 0;
		if( inCheck() ) return -(10000-ply+2);
		else return 0;
	}
	
	}
	
	hKey[hI] = zKey; hType[hI] = hashType; hPly[hI] = (byte) (maxPly-ply); hVal[hI] = (short) alpha;
	
	return alpha;
}

[Fguy64]

p.s. there are two main code blocks in search. The first one is for captures, the second one, executed when ply<=maxPly, is non captures.

[hgm]

If you do MVV/LVA there should be no danger in setting maxDep to a ridiculously high value that can never be reached. (An all-capture search can never be deeper than 30 ply, before you are left with bare Kings.)

The problem you are facing is that with material-only, there are very many lines with the same score. Because of this degeneracy there usually is no unique PV. Which one you get is very much dependent on move ordering. And every engine does that differently, which makes it meaningless to compare.

[Fguy64]

If you do MVV/LVA there should be no danger in setting maxDep to a ridiculously high value that can never be reached. (An all-capture search can never be deeper than 30 ply, before you are left with bare Kings.)

The problem you are facing is that with material-only, there are very many lines with the same score. Because of this degeneracy there usually is no unique PV. Which one you get is very much dependent on move ordering. And every engine does that differently, which makes it meaningless to compare.

I see your point. However right now my main motivation is to prove that my algorithm can find a clearly best solution when there is one to be found, regardless of move ordering. So I test using the WAC positons which as far as I know all have a provably best solution. And under those circumstances I suppose it shouldn't be too hard to eyeball the PV, but it can be a little time consuming.

Once I get this nailed down solid. Then can start devoting some energy to developing a more sophisticated positional evaluation.

[hgm]

I suppose they only have a unique solution as to the first move. Once it is established that you will lose a pawn/piece, there are usually many ways to defend and end with the same loss. Especially in a fixed-depth search, wher you can simply sac a piece (e.g. do NxP somewhere) to push the problem that it is all about over the horizon.

[Fguy64]

I suppose they only have a unique solution as to the first move. Once it is established that you will lose a pawn/piece, there are usually many ways to defend and end with the same loss. Especially in a fixed-depth search, wher you can simply sac a piece (e.g. do NxP somewhere) to push the problem that it is all about over the horizon.

OK, I see your point. I should also mention that eval plays a significant role in my testing. So while it may be that PV is not unique, one should still be unable to find as better one.

Generally my strategy with a WAC posn is as follows. Usually I try several attempts without Q, increasing the depth until it s clear that the central idea is played, and a deeper search won't significantly change the score. At this pont my best move is compared to that which is known. Then I'll turn on Q, and see if the same eval can be found at a lower ply, which would imply that the original "non-Q" PV ended with exchanges. I'll also scritunize the sequence myself to verify visually.

In my "non-iterative" engine, if I get a PV from a six ply search for example. Then I can step through that PV one move at a time, playng both sides and reducing the search depth by 1 at each turn. Using this approach to "verify" PV has turned up a a bug or three.

So the method itself is sound enough, as long as I use it properly. It's possible for me to overlook a problem in one or two positions. But far less likely that a problem will go undiscovered through several dozen positions. Imagine there might b a better way to prove my algorithms before moving on to iterative deepening and positional evals, but then then that begs the question, it's the reason for my post.

[Fguy64]

OK, here is an example where I could use a little help with understanding the PV that my engine collects.

first of all the relevant features of my engine.

Piece values Q=90, R=50, B=30, N=29, P=10
Piece/square values WKg1=3, WPe4=2, WPd4=2, WNf3=3, WNc3=3, WBc4=3, WBf4=3, WQe2=2, WQd2=2
same values for corresponing piece/squares for black

fixed depth +Q, no iterative deepening.

position being searched - rnbqkb1r/pppp1ppp/8/4P3/6n1/7P/PPPNPPP1/R1BQKBNR b KQkq -

here are the various search results. The central theme is the mate that results if the knight is captured on e3.

6-ply, quiescence and piece/square tables disabled
PV: g4-e3 e5-e6 e3-d1 e6-d7 b8-d7 e1-d1
eval = 51 for Black this is +BQ -WN -WP

6-ply, quiescence disabled, piece/square enabled
PV: g4-e3 d2-f3 e3-d1 e1-d1 b8-c6 c1-f4
eval = 48 The difference is the WN on f3

ok this second line makes sense considering that piece/square has been turned on. But when Q and piece/square are both turned on, the situation gets cloudy

6-ply, Q & piece/square turned on
g4-e3 e5-e6 e3-d1 e6-f7 e8-f7 e1-d1
eval = 51 for black, same as the first.

Noticed that in the third case, no Q moves show up in PV, what don't understand is why 2.d2-f3 doesn't show up in PV like it does in the 2nd case. One might think there is a bug, but previous tests have all produced explainable results. This result might still have an explanation, I just can't see it.

I can make the engine source code, and a java applet available if it will help.

[Fguy64]

OK, here is an example where I could use a little help with understanding the PV that my engine collects.

first of all the relevant features of my engine.

Piece values Q=90, R=50, B=30, N=29, P=10
Piece/square values WKg1=3, WPe4=2, WPd4=2, WNf3=3, WNc3=3, WBc4=3, WBf4=3, WQe2=2, WQd2=2
same values for corresponing piece/squares for black

fixed depth +Q, no iterative deepening.

position being searched - rnbqkb1r/pppp1ppp/8/4P3/6n1/7P/PPPNPPP1/R1BQKBNR b KQkq -

here are the various search results. The central theme is the mate that results if the knight is captured on e3.

6-ply, quiescence and piece/square tables disabled
PV: g4-e3 e5-e6 e3-d1 e6-d7 b8-d7 e1-d1
eval = 51 for Black this is +BQ -WN -WP

6-ply, quiescence disabled, piece/square enabled
PV: g4-e3 d2-f3 e3-d1 e1-d1 b8-c6 c1-f4
eval = 48 The difference is the WN on f3

ok this second line makes sense considering that piece/square has been turned on. But when Q and piece/square are both turned on, the situation gets cloudy

6-ply, Q & piece/square turned on
g4-e3 e5-e6 e3-d1 e6-f7 e8-f7 e1-d1
eval = 51 for black, same as the first.

Noticed that in the third case, no Q moves show up in PV, what don't understand is why 2.d2-f3 doesn't show up in PV like it does in the 2nd case. One might think there is a bug, but previous tests have all produced explainable results. This result might still have an explanation, I just can't see it.

I can make the engine source code, and a java applet available if it will help.

OK ended up answering my own question, I think. In the situation where both qSearch and piece/square us enabled, there is no line where White can force a more favourable evaluation than -51.

if White does play 2.d2-f3, then 2...e3-d1 3.e1-d1 f8-c5 and the score is still -51 wth one white move left in regular search. White can't use it to favourably change the eval because his f-pawn is hanging, which would get snapped up in Q.

So all is still well.