question about search depth

[cyberfish]

Hi,
I have just started my chess engine, currently consisting of alpha-beta, QS on all captures and promotions with MVV/LVA ordering, and a transposition table.

It works fine (although very weak) as far as I can tell. However, the ply count that it reaches worries me.

In mid-game situations, it can only do (with iterative deepening) about 2-3 plies full width alpha-beta. The node count looks okay to me (~1e6 nps on 32-bit Linux on 2ghz Core 2) though. Does that number look normal? Or is there a serious bug somewhere?

Thank you

[hgm]

Sounds like your alpha-beta is not working...

Or it might be ineffective because you ar not using a good move ordering in main search.

Count QS nodes and and main-search nodes separately, and you will get a better idea where the problems ly. Also do statistics on beta cutoffs, how many of those occr through the 1st, 2nd and 3d move, and how many by later moves.

[Dann Corbit]

You could do 5 plies of pure mini-max, so something is crazy.

If you have any extensions, remove them.

Start with alpha-beta that has no null move or anything.

You should have a branching factor of about 6 (as high as 8 might be OK if you have bad move ordering). You can calculate it by the average of how long it takes to go from ply to ply when you complete them (or node count increase).

Once your simple alpha-beta is working, then go on to refining it.

[cyberfish]

Thanks for your reply, I think it is a move ordering issue. I am currently only ordering captures by MVV/LVA, and promotions, followed by everything else in random order.

I will give your suggestions a try. Thanks.

[cyberfish]

Count QS nodes and and main-search nodes separately, and you will get a better idea where the problems ly. Also do statistics on beta cutoffs, how many of those occr through the 1st, 2nd and 3d move, and how many by later moves.

I have collected the data:
for this position: rnb1kbnr/ppp2ppp/8/3qp3/3P4/5N2/PPP2PPP/RNBQKB1R b KQkq - 0 4
(sorry I can't seem to figure out how to post FENs)

Ply 0:
ABnodes: 0 Qnodes: 779581. 1074375 NPS. Num cutoffs: 294010.
Ply 1:
ABnodes: 47 Qnodes: 23828467. 1123194 NPS. Num cutoffs: 8403833.
Ply 2:
patience overflowed

Seems like the numbers for Qnodes are way too high. However, I cannot make much sense of it as this is my first chess engine and I don't know what normal values would be. Can someone please take a look at it for me? Or maybe shoot a wild guess or two as to what might be wrong?

The transposition table is disabled.

Also, I am currently not ordering moves except captures and promotions. How should I order regular moves? I have PV-first ordering too when the transposition table is enabled (I track my PV with the TT).

Thank you very much.

[Edsel Apostol]

There must be something wrong with your quiescent search.

Have you tried adding a perft function to determine if you are generating moves correctly?

Are you returning the eval score for the quiescent search position if it is greater than or equal to beta?

Check your iterative deepening.

Check also your extensions. Maybe you are extending indefinitely in the qsearch.

The best idea is to post your quiescent search code here in this forum and I assure that there will be a lot of programmers that will help you solve your problem.

[Uri Blass]

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

rnb1kbnr/ppp2ppp/8/3qp3/3P4/5N2/PPP2PPP/RNBQKB1R b KQkq - 0 4

It is clear that something is wrong and the best way to find is simply to print the first 100 nodes of your qsearch

Uri

[hgm]

Clearly your QS is defective. Probably beta cutoff is not working there. Make also sure you look for beta cutoff after calculating the evaluation, before searching any moves.

[cyberfish]

Thanks for the help.

Have you tried adding a perft function to determine if you are generating moves correctly?

all the positions here:
http://www.albert.nu/programs/sharper/perft.htm
have being solved correctly.

Are you returning the eval score for the quiescent search position if it is greater than or equal to beta?

yes, I believe so.

Check your iterative deepening.

It currently just calls minimax with increasing depth. So I don't exactly know what to check for.

Check also your extensions. Maybe you are extending indefinitely in the qsearch.

I am only extending on captures and promotions.

The best idea is to post your quiescent search code here in this forum and I assure that there will be a lot of programmers that will help you solve your problem.

That would be great. Except the code is still very messy at this point, and I have alpha-beta and Q in the same function. I am also doing vanilla alpha-beta instead of negamax because I find it easier logically this way. But anyways, here it is:

Code: Select all

Score miniMax(int depth, Score lowerBound, Score higherBound) {

	checkTimeCounter--;
	if ((checkTimeCounter == 0) || (!depthFinished)) {
		checkTimeCounter = checkTimePeriod;
		if (current_time() > allocatedEndTime) {
			if (currentDepth != 0) { //never abort ply 0 search
				depthFinished = false;
				return 0;
			}
		}
	}
	//end time checking code

	if (depth <= 0) {
		Qcount++;
	} else {
		ABcount++;
	}

	Score tableResult;
	if ((tableResult = probeTable(depth, lowerBound, higherBound)) != UNKNOWN) { //this is disabled right now to simplify the matter. probeTable always returns UNKNOWN
		return tableResult;
	}

	vector<Move> *pseudoMoves;
	if (depth <= 0) {
		pseudoMoves = genViolentMoves();
	} else {
		pseudoMoves = genMoves();
	}

	if (pseudoMoves == NULL) { //last move was illegal
		return INVALID_SCORE;
	}

	bool legalMoveFound = false;

	Score staticScore = staticEval();

	if (depth <= 0) {
		printNode(0, staticScore, depth);
		if (moving_side == engine_side) { //maximize
			if (staticScore > higherBound) {
				Cutoffcount++;
				delete pseudoMoves;
				recordEntry(depth, AT_LEAST, staticScore, 0);
				return staticScore;
			}
			if (staticScore > lowerBound) {
				lowerBound = staticScore;
			}
		} else { //minimize
			if (staticScore < lowerBound) {
				Cutoffcount++;
				delete pseudoMoves;
				recordEntry(depth, AT_MOST, staticScore, 0);
				return staticScore;
			}
			if (staticScore < higherBound) {
				higherBound = staticScore;
			}
		}
	}

	orderMoves(*pseudoMoves);
	Score extremeScore;

	Move bestMove = 0;

	Uint8 hash_type;

	if (moving_side == engine_side) { //maximize
		hash_type = AT_MOST;
		for (unsigned int i = 0; i < pseudoMoves->size(); ++i) {
			applyMove((*pseudoMoves)[i]);
			Score thisScore = miniMax(depth-1, lowerBound, higherBound);

			if (thisScore == INVALID_SCORE) {
				undoMove();
				continue;
			}

			adjustTerminalScore(thisScore);
			legalMoveFound = true;

			if (thisScore > higherBound) {
				Cutoffcount++;
				undoMove();
				delete pseudoMoves;
				recordEntry(depth, AT_LEAST, thisScore, 0);
				return thisScore;
			}

			if (thisScore > lowerBound) {
				lowerBound = thisScore;
				bestMove = (*pseudoMoves)[i];
				hash_type = EXACT;
			}

			undoMove();
		}

		extremeScore = lowerBound;
	} else { //minimize
		hash_type = AT_LEAST;
		for (unsigned int i = 0; i < pseudoMoves->size(); ++i) {
			applyMove((*pseudoMoves)[i]);

			Score thisScore = miniMax(depth-1, lowerBound, higherBound);

			if (thisScore == INVALID_SCORE) {
				undoMove();
				continue;
			}

			adjustTerminalScore(thisScore);
			legalMoveFound = true;

			if (thisScore < lowerBound) {
				Cutoffcount++;
				undoMove();
				delete pseudoMoves;
				recordEntry(depth, AT_MOST, thisScore, 0);
				return thisScore;
			}

			if (thisScore < higherBound) {
				higherBound = thisScore;
				bestMove = (*pseudoMoves)[i];
				hash_type = EXACT;
			}

			undoMove();
		}
		extremeScore = higherBound;
	}

	if (!legalMoveFound) {

		if (depth <= 0) {
			delete pseudoMoves;
			recordEntry(depth, EXACT, staticScore, 0);
			return staticScore;
		}

		Uint32 kingAt;
		if (moving_side == WHITE) {
			kingAt = ctzll(board_desc[WK]);
		} else {
			kingAt = ctzll(board_desc[BK]);
		}
		if (underAtk(kingAt)) {
			if (engine_side == moving_side) {
				delete pseudoMoves;
				recordEntry(depth, EXACT, LOSE_SCORE, 0);
				return LOSE_SCORE;
			} else {
				delete pseudoMoves;
				recordEntry(depth, EXACT, WIN_SCORE, 0);
				return WIN_SCORE;
			}
		} else {
			delete pseudoMoves;
			recordEntry(depth, EXACT, DRAW_SCORE, 0);
			return DRAW_SCORE;
		}

	} else {
		delete pseudoMoves;
		recordEntry(depth, hash_type, extremeScore, bestMove);
		return extremeScore;
	}
}

It is clear that something is wrong and the best way to find is simply to print the first 100 nodes of your qsearch

Thanks for the suggestion, I will try doing that.

Clearly your QS is defective. Probably beta cutoff is not working there. Make also sure you look for beta cutoff after calculating the evaluation, before searching any moves.

I believe I am already doing that.

Thanks again for your great helps.

[hgm]

One remark:

You should take cutoffs if thisScore >= upperBound (or <= loweBound), not just > or <. This might ause you to mess many cutoffs. It is difficult to judge how bad this is; it depends on the finess of your evaluation.