Strange negamax behaviour

[niel5946]

I have been struggling with a weird behaviour with my search function for some time now, and I have looked through all the search functions multiple times, but can't seem to see the problem.
I am using negamax alpha-beta with principal variation search. There are no pruning methods, reductions or extensions implemented yet since I want to untangle this mess first.
My alpha-beta function looks like this:

Code: Select all

int alphabeta(SearchThread_t* ss, int depth, int alpha, int beta, SearchPv* pvLine) {
		SIDE Us = ss->pos->side_to_move;

		ss->info->nodes++;

		SearchPv line;
		pvLine->length = 0;

		if (depth == 0) {
			return quiescence(ss, alpha, beta);
		}


		// Return zero for a drawn position
		if ((is_repetition(ss->pos) || ss->pos->fiftyMove >= 100) && ss->pos->ply > 0) {
			return 0;
		}

		if (ss->pos->ply > MAXDEPTH - 1) {
			return Eval::evaluate(ss->pos);
		}


		int score = -INF;
		int best_move = NOMOVE;
		bool raised_alpha = false;

		// When doing principal variation search, we are in a PV node if beta - alpha != 1 since we're then not in a null window
		bool is_pv = (beta - alpha != 1) ? true : false;


		/*
		TRANSPOSITION TABLE PROBING:
			- We'll check to see if the position has been reached before and saved in the transposition table.
		*/
		bool ttHit = false;
		TT_Entry* ttEntry = tt->probe_tt(ss->pos->posKey, ttHit);

		int ttScore	= (ttHit) ? ttEntry->data.score	: -INF;
		int ttMove	= (ttHit) ? ttEntry->data.move	: NOMOVE;
		int ttDepth	= (ttHit) ? ttEntry->data.depth	: 0;
		int ttFlag	= (ttHit) ? ttEntry->data.flag	: NO_FLAG;

		if (ttScore >= MATE) { ttScore -= ss->pos->ply; }
		else if (ttScore <= -MATE) { ttScore += ss->pos->ply; }


		// If ttHit is true, the pointer is a valid entry for the position. We just need to check if the depth is satisfactory.
		if (ttHit && ttDepth >= depth && !is_pv) {
			switch (ttFlag) {
			case ALPHA:
				if (ttScore <= alpha) {
					return alpha;
				}
				break;
			case BETA:
				if (ttScore >= beta) {
					return beta;
				}
				break;
			case EXACT:
				return score;
			}
		}



		// Check if we need to stop, and drop out if we do.
		if ((ss->info->nodes & 2047) == 0) {
			CheckUp(ss);
		}

		if (ss->info->stopped) {
			return 0;
		}


		// Generate all moves for the position
		MoveList* moves = ss->generate_moves();

		int legal = 0;
		
		// If our transposition table probing returned a move, this will be scored the highest.
		if (ttHit && ttMove != NOMOVE) {
			for (int m = 0; m < moves->size(); m++) {
				if ((*moves)[m]->move == ttMove) {
					(*moves)[m]->score = 100000000;
					break;
				}
			}
		}


		int move = NOMOVE;

		// Now we begin searching the moves.
		for (int m = 0; m < moves->size(); m++) {
			ss->pickNextMove(m, moves);

			move = (*moves)[m]->move;

			// piece captured will be used for killer moves and history heuristic
			int piece_captured = ss->pos->piece_list[(Us == WHITE) ? BLACK : WHITE][TOSQ(move)];

			// The new_depth will be where we add the extensions and reductions
			int new_depth = depth - 1;

			if (!ss->pos->make_move((*moves)[m])) {
				continue;
			}
			legal++;

			/*
			PRINCIPAL VARIATION SEARCH
			*/
			if (!raised_alpha) {
				score = -alphabeta(ss, new_depth, -beta, -alpha, &line);
			}
			else {
				score = -alphabeta(ss, new_depth, -alpha - 1, -alpha, &line);
				
				// If we somehow still raise alpha with a move we thought was bad, we need to re-search it.
				// But if it also beats beta (score > beta) we dont need to do anything
				if (score > alpha) {
					score = -alphabeta(ss, new_depth, -beta, -alpha, &line);
				}
			}


			ss->pos->undo_move();

			if (ss->info->stopped) { return 0; }

			if (score > alpha) {
				raised_alpha = true;
				best_move = move;

				if (score >= beta) {

					if (legal == 1) {
						ss->info->fhf++;
					}
					ss->info->fh++;

					// Since we've beaten beta, we'll check if it is a quiet move. If it is, we'll add it to the killer and history heurstic
					if (piece_captured == NO_TYPE && SPECIAL(move) != PROMOTION) {
						ss->setKillers(ss->pos->ply, (*moves)[m]->move);
						ss->history[FROMSQ(move)][TOSQ(move)] += depth * depth;
					}



					tt->store_entry(ss->pos, best_move, score, depth, BETA);

					return beta;
				}

				ChangePV(best_move, pvLine, &line);

				alpha = score;
			}

		}

		delete moves;

		// If we had zero legal moves, we're either in checkmate or stalemate.
		if (legal == 0) {
			if (ss->pos->in_check()) {
				return -INF + ss->pos->ply;
			}
			else {
				return 0;
			}
		}

		// If we raised alpha, we're in a PV-node, otherwise we're in an all node
		if (raised_alpha) {
			tt->store_entry(ss->pos, best_move, alpha, depth, EXACT);
		}
		else {
			tt->store_entry(ss->pos, best_move, alpha, depth, ALPHA);
		}

		return alpha;
	} // alphabeta

And my quiescence search:

Code: Select all

	// At the moment quiescence only searches captures and promotions. FIXME: Should this also contain checks and check evasions?
	int quiescence(SearchThread_t* ss, int alpha, int beta) {
		SIDE Us = ss->pos->side_to_move;
		
		ss->info->nodes++;

		// Check if we need to stop, and drop out if we do.
		if ((ss->info->nodes & 2047) == 0) {
			CheckUp(ss);
		}

		if (ss->info->stopped) {
			return 0;
		}

		
		// Return zero for a drawn position, or if we have reached our maximum search depth.
		if ((is_repetition(ss->pos) || ss->pos->fiftyMove >= 100) && ss->pos->ply > 0) {
			return 0;
		}

		int stand_pat = Eval::evaluate(ss->pos);

		if (ss->pos->ply > MAXDEPTH - 1) {
			return stand_pat;
		}

		// If the static evaluation beats beta, we can do a cutoff
		if (stand_pat >= beta) {
			return beta;
		}

		else if (stand_pat > alpha) {
			alpha = stand_pat;
		}

		// Only generate tatical moves in quiescence
		MoveList* ml = ss->generate_moves(true);

		int legal = 0; // Amount of legal moves. We need to know if they are zero, so we can return a mate score or stalemate score

		int score = -INF;

		for (int m = 0; m < ml->size(); m++) {

			if (!ss->pos->make_move((*ml)[m])) {
				continue;
			}
			legal++;

			score = -quiescence(ss, -beta, -alpha);

			ss->pos->undo_move();

			// Return if we have been told to stop the search.
			if (ss->info->stopped) { return 0; }

			if (score > alpha) {
				alpha = score;

				if (score >= beta) {
					// If this is the first move, and it beats beta, we failed high on the first move i.e. good move ordering.
					if (legal == 1) {
						ss->info->fhf++;
					}
					ss->info->fh++;

					return beta;
				}
			}
		}

		if (legal == 0) {
			if (ss->pos->in_check()) {
				return -INF + ss->pos->ply;
			}
			else {
				return 0;
			}
		}

		delete ml;

		return alpha;
	} // quiescence

All of this is run inside an iterative deepening loop, and I have tested my eval to make sure it isn't unbalanced (it only consists of material and psqt at the moment though). The SearchThread_t class is:

Code: Select all

// SearchThread_t is a structure that holds all information local to a thread. This includes static evaluations, move ordering etc..
struct SearchThread_t {
	GameState_t* pos = new GameState_t;
	SearchInfo_t* info = new SearchInfo_t;

	int history[64][64] = { {0} };
	int killers[MAXDEPTH][2] = { {0} };

	int static_eval[MAXDEPTH] = { 0 };

	int thread_id = 0;


	void setKillers(int ply, int move);
	void pickNextMove(int index, MoveList* ml);

	MoveList* generate_moves(bool qsearch = false);
	~SearchThread_t() {
		delete pos;
		delete info;
	}

private:
	void score_moves(MoveList* ml);
};

Even though the engine is multithreaded with Lazy SMP, I still get problems with only one thread searching. It gives outright blunderous lines like:
[pgn]1. Nc3 Nf6 2. e4 Nxe4 3. Nxe4 Rg8 4. Nf3 h6 5. d4 *[/pgn]

Can anyone see what I am doing wrong?

Any help is very much appreciated!

[IanKennedy]

If that is a PV issued can you post your ChangePV function?

[hgm]

I have been struggling with a weird behaviour with my search function for some time now, and I have looked through all the search functions multiple times, but can't seem to see the problem.

Just a general remark: looking through code is not a good way to trace bugs; if these could be recognized that way you would not have made them in the first place.

If you see some obviously wrong behavior that is reproducible, just run the same position again while printing diagnostics that tells you how the engine came to that decision. Then you never have to "struggle with anything for some time", but instead decisively zoom in to the source of the problem in a matter of minutes.

In particular, it helps to print the list of moves and the score they got (perhaps together with alpha and beta) in every node of an erroneous line. You can then start at the root, and follow the moves with the wrong score to the child, where you then also must have moves with a wrong score (or moves that were not searched at all), which you can follow further.

[niel5946]

If that is a PV issued can you post your ChangePV function?

I initially used the method from https://www.chessprogramming.org/Principal_Variation which is:

Code: Select all

pvLine->pv[0] = best_move;
memcpy(pvLine->pv + 1, line.pv, line.length * sizeof(int));
pvLine->length = line.length + 1;

So to make sure this wasn't causing the problem, I looked through some other implementations and found one in Laser (https://github.com/jeffreyan11/laser-chess-engine), which gives exactly the same PV:

Code: Select all

void ChangePV(int move, SearchPv* parent, SearchPv* child) {
	parent->pv[0] = move;

	for (int i = 0; i < child->length; i++) {
		parent->pv[i + 1] = child->pv[i];
	}
	parent->length = child->length + 1;
}

[Ras]

I saw some other issues instead:
I'd enter quiescence if depth<=0, not ==0. That's more robust once you add reductions later.
The draw check for the 50 moves rule ignores checkmate. If ply 100 delivers checkmate, that has priority over the 50 moves.
Upon returning due to timeout, you return 0 instead of alpha.
Be aware that the legal==0 check may see wrong stalemates once you add futility pruning.

[Nomis]

Code: Select all

		if (ss->pos->ply > MAXDEPTH - 1) {
			return Eval::evaluate(ss->pos);
		}

What is that supposed to do ?

I never call eval() in the search, except for pruning purposes.

[Karlo Bala]

I have been struggling with a weird behaviour with my search function for some time now, and I have looked through all the search functions multiple times, but can't seem to see the problem.
I am using negamax alpha-beta with principal variation search. There are no pruning methods, reductions or extensions implemented yet since I want to untangle this mess first.
My alpha-beta function looks like this:

Code: Select all

int alphabeta(SearchThread_t* ss, int depth, int alpha, int beta, SearchPv* pvLine) {
		SIDE Us = ss->pos->side_to_move;

		ss->info->nodes++;

		SearchPv line;
		pvLine->length = 0;

		if (depth == 0) {
			return quiescence(ss, alpha, beta);
		}


		// Return zero for a drawn position
		if ((is_repetition(ss->pos) || ss->pos->fiftyMove >= 100) && ss->pos->ply > 0) {
			return 0;
		}

		if (ss->pos->ply > MAXDEPTH - 1) {
			return Eval::evaluate(ss->pos);
		}


		int score = -INF;
		int best_move = NOMOVE;
		bool raised_alpha = false;

		// When doing principal variation search, we are in a PV node if beta - alpha != 1 since we're then not in a null window
		bool is_pv = (beta - alpha != 1) ? true : false;


		/*
		TRANSPOSITION TABLE PROBING:
			- We'll check to see if the position has been reached before and saved in the transposition table.
		*/
		bool ttHit = false;
		TT_Entry* ttEntry = tt->probe_tt(ss->pos->posKey, ttHit);

		int ttScore	= (ttHit) ? ttEntry->data.score	: -INF;
		int ttMove	= (ttHit) ? ttEntry->data.move	: NOMOVE;
		int ttDepth	= (ttHit) ? ttEntry->data.depth	: 0;
		int ttFlag	= (ttHit) ? ttEntry->data.flag	: NO_FLAG;

		if (ttScore >= MATE) { ttScore -= ss->pos->ply; }
		else if (ttScore <= -MATE) { ttScore += ss->pos->ply; }


		// If ttHit is true, the pointer is a valid entry for the position. We just need to check if the depth is satisfactory.
		if (ttHit && ttDepth >= depth && !is_pv) {
			switch (ttFlag) {
			case ALPHA:
				if (ttScore <= alpha) {
					return alpha;
				}
				break;
			case BETA:
				if (ttScore >= beta) {
					return beta;
				}
				break;
			case EXACT:
				return score;
			}
		}



		// Check if we need to stop, and drop out if we do.
		if ((ss->info->nodes & 2047) == 0) {
			CheckUp(ss);
		}

		if (ss->info->stopped) {
			return 0;
		}


		// Generate all moves for the position
		MoveList* moves = ss->generate_moves();

		int legal = 0;
		
		// If our transposition table probing returned a move, this will be scored the highest.
		if (ttHit && ttMove != NOMOVE) {
			for (int m = 0; m < moves->size(); m++) {
				if ((*moves)[m]->move == ttMove) {
					(*moves)[m]->score = 100000000;
					break;
				}
			}
		}


		int move = NOMOVE;

		// Now we begin searching the moves.
		for (int m = 0; m < moves->size(); m++) {
			ss->pickNextMove(m, moves);

			move = (*moves)[m]->move;

			// piece captured will be used for killer moves and history heuristic
			int piece_captured = ss->pos->piece_list[(Us == WHITE) ? BLACK : WHITE][TOSQ(move)];

			// The new_depth will be where we add the extensions and reductions
			int new_depth = depth - 1;

			if (!ss->pos->make_move((*moves)[m])) {
				continue;
			}
			legal++;

			/*
			PRINCIPAL VARIATION SEARCH
			*/
			if (!raised_alpha) {
				score = -alphabeta(ss, new_depth, -beta, -alpha, &line);
			}
			else {
				score = -alphabeta(ss, new_depth, -alpha - 1, -alpha, &line);
				
				// If we somehow still raise alpha with a move we thought was bad, we need to re-search it.
				// But if it also beats beta (score > beta) we dont need to do anything
				if (score > alpha) {
					score = -alphabeta(ss, new_depth, -beta, -alpha, &line);
				}
			}


			ss->pos->undo_move();

			if (ss->info->stopped) { return 0; }

			if (score > alpha) {
				raised_alpha = true;
				best_move = move;

				if (score >= beta) {

					if (legal == 1) {
						ss->info->fhf++;
					}
					ss->info->fh++;

					// Since we've beaten beta, we'll check if it is a quiet move. If it is, we'll add it to the killer and history heurstic
					if (piece_captured == NO_TYPE && SPECIAL(move) != PROMOTION) {
						ss->setKillers(ss->pos->ply, (*moves)[m]->move);
						ss->history[FROMSQ(move)][TOSQ(move)] += depth * depth;
					}



					tt->store_entry(ss->pos, best_move, score, depth, BETA);

					return beta;
				}

				ChangePV(best_move, pvLine, &line);

				alpha = score;
			}

		}

		delete moves;

		// If we had zero legal moves, we're either in checkmate or stalemate.
		if (legal == 0) {
			if (ss->pos->in_check()) {
				return -INF + ss->pos->ply;
			}
			else {
				return 0;
			}
		}

		// If we raised alpha, we're in a PV-node, otherwise we're in an all node
		if (raised_alpha) {
			tt->store_entry(ss->pos, best_move, alpha, depth, EXACT);
		}
		else {
			tt->store_entry(ss->pos, best_move, alpha, depth, ALPHA);
		}

		return alpha;
	} // alphabeta

And my quiescence search:

Code: Select all

	// At the moment quiescence only searches captures and promotions. FIXME: Should this also contain checks and check evasions?
	int quiescence(SearchThread_t* ss, int alpha, int beta) {
		SIDE Us = ss->pos->side_to_move;
		
		ss->info->nodes++;

		// Check if we need to stop, and drop out if we do.
		if ((ss->info->nodes & 2047) == 0) {
			CheckUp(ss);
		}

		if (ss->info->stopped) {
			return 0;
		}

		
		// Return zero for a drawn position, or if we have reached our maximum search depth.
		if ((is_repetition(ss->pos) || ss->pos->fiftyMove >= 100) && ss->pos->ply > 0) {
			return 0;
		}

		int stand_pat = Eval::evaluate(ss->pos);

		if (ss->pos->ply > MAXDEPTH - 1) {
			return stand_pat;
		}

		// If the static evaluation beats beta, we can do a cutoff
		if (stand_pat >= beta) {
			return beta;
		}

		else if (stand_pat > alpha) {
			alpha = stand_pat;
		}

		// Only generate tatical moves in quiescence
		MoveList* ml = ss->generate_moves(true);

		int legal = 0; // Amount of legal moves. We need to know if they are zero, so we can return a mate score or stalemate score

		int score = -INF;

		for (int m = 0; m < ml->size(); m++) {

			if (!ss->pos->make_move((*ml)[m])) {
				continue;
			}
			legal++;

			score = -quiescence(ss, -beta, -alpha);

			ss->pos->undo_move();

			// Return if we have been told to stop the search.
			if (ss->info->stopped) { return 0; }

			if (score > alpha) {
				alpha = score;

				if (score >= beta) {
					// If this is the first move, and it beats beta, we failed high on the first move i.e. good move ordering.
					if (legal == 1) {
						ss->info->fhf++;
					}
					ss->info->fh++;

					return beta;
				}
			}
		}

		if (legal == 0) {
			if (ss->pos->in_check()) {
				return -INF + ss->pos->ply;
			}
			else {
				return 0;
			}
		}

		delete ml;

		return alpha;
	} // quiescence

All of this is run inside an iterative deepening loop, and I have tested my eval to make sure it isn't unbalanced (it only consists of material and psqt at the moment though). The SearchThread_t class is:

Code: Select all

// SearchThread_t is a structure that holds all information local to a thread. This includes static evaluations, move ordering etc..
struct SearchThread_t {
	GameState_t* pos = new GameState_t;
	SearchInfo_t* info = new SearchInfo_t;

	int history[64][64] = { {0} };
	int killers[MAXDEPTH][2] = { {0} };

	int static_eval[MAXDEPTH] = { 0 };

	int thread_id = 0;


	void setKillers(int ply, int move);
	void pickNextMove(int index, MoveList* ml);

	MoveList* generate_moves(bool qsearch = false);
	~SearchThread_t() {
		delete pos;
		delete info;
	}

private:
	void score_moves(MoveList* ml);
};

Even though the engine is multithreaded with Lazy SMP, I still get problems with only one thread searching. It gives outright blunderous lines like:
[pgn]1. Nc3 Nf6 2. e4 Nxe4 3. Nxe4 Rg8 4. Nf3 h6 5. d4 *[/pgn]

Can anyone see what I am doing wrong?

Any help is very much appreciated!

It could be just the PV pollution. What is the eval at the end of the PV?

Since the error is in the middle of the PV it is probably not due to qSearch. Could be also a bug in the eval if pawn and knight are of the same value. From my experience, the majority of bugs are hidden in the TT.

What I would do:

1.Disable TT
2.Open AB windows to max
3.Disable beta cutoff
4.Start search after 1. Nc3 Nf6 2. e4 (best through a debugger)

[niel5946]

I have been struggling with a weird behaviour with my search function for some time now, and I have looked through all the search functions multiple times, but can't seem to see the problem.
I am using negamax alpha-beta with principal variation search. There are no pruning methods, reductions or extensions implemented yet since I want to untangle this mess first.
My alpha-beta function looks like this:

Code: Select all

int alphabeta(SearchThread_t* ss, int depth, int alpha, int beta, SearchPv* pvLine) {
		SIDE Us = ss->pos->side_to_move;

		ss->info->nodes++;

		SearchPv line;
		pvLine->length = 0;

		if (depth == 0) {
			return quiescence(ss, alpha, beta);
		}


		// Return zero for a drawn position
		if ((is_repetition(ss->pos) || ss->pos->fiftyMove >= 100) && ss->pos->ply > 0) {
			return 0;
		}

		if (ss->pos->ply > MAXDEPTH - 1) {
			return Eval::evaluate(ss->pos);
		}


		int score = -INF;
		int best_move = NOMOVE;
		bool raised_alpha = false;

		// When doing principal variation search, we are in a PV node if beta - alpha != 1 since we're then not in a null window
		bool is_pv = (beta - alpha != 1) ? true : false;


		/*
		TRANSPOSITION TABLE PROBING:
			- We'll check to see if the position has been reached before and saved in the transposition table.
		*/
		bool ttHit = false;
		TT_Entry* ttEntry = tt->probe_tt(ss->pos->posKey, ttHit);

		int ttScore	= (ttHit) ? ttEntry->data.score	: -INF;
		int ttMove	= (ttHit) ? ttEntry->data.move	: NOMOVE;
		int ttDepth	= (ttHit) ? ttEntry->data.depth	: 0;
		int ttFlag	= (ttHit) ? ttEntry->data.flag	: NO_FLAG;

		if (ttScore >= MATE) { ttScore -= ss->pos->ply; }
		else if (ttScore <= -MATE) { ttScore += ss->pos->ply; }


		// If ttHit is true, the pointer is a valid entry for the position. We just need to check if the depth is satisfactory.
		if (ttHit && ttDepth >= depth && !is_pv) {
			switch (ttFlag) {
			case ALPHA:
				if (ttScore <= alpha) {
					return alpha;
				}
				break;
			case BETA:
				if (ttScore >= beta) {
					return beta;
				}
				break;
			case EXACT:
				return score;
			}
		}



		// Check if we need to stop, and drop out if we do.
		if ((ss->info->nodes & 2047) == 0) {
			CheckUp(ss);
		}

		if (ss->info->stopped) {
			return 0;
		}


		// Generate all moves for the position
		MoveList* moves = ss->generate_moves();

		int legal = 0;
		
		// If our transposition table probing returned a move, this will be scored the highest.
		if (ttHit && ttMove != NOMOVE) {
			for (int m = 0; m < moves->size(); m++) {
				if ((*moves)[m]->move == ttMove) {
					(*moves)[m]->score = 100000000;
					break;
				}
			}
		}


		int move = NOMOVE;

		// Now we begin searching the moves.
		for (int m = 0; m < moves->size(); m++) {
			ss->pickNextMove(m, moves);

			move = (*moves)[m]->move;

			// piece captured will be used for killer moves and history heuristic
			int piece_captured = ss->pos->piece_list[(Us == WHITE) ? BLACK : WHITE][TOSQ(move)];

			// The new_depth will be where we add the extensions and reductions
			int new_depth = depth - 1;

			if (!ss->pos->make_move((*moves)[m])) {
				continue;
			}
			legal++;

			/*
			PRINCIPAL VARIATION SEARCH
			*/
			if (!raised_alpha) {
				score = -alphabeta(ss, new_depth, -beta, -alpha, &line);
			}
			else {
				score = -alphabeta(ss, new_depth, -alpha - 1, -alpha, &line);
				
				// If we somehow still raise alpha with a move we thought was bad, we need to re-search it.
				// But if it also beats beta (score > beta) we dont need to do anything
				if (score > alpha) {
					score = -alphabeta(ss, new_depth, -beta, -alpha, &line);
				}
			}


			ss->pos->undo_move();

			if (ss->info->stopped) { return 0; }

			if (score > alpha) {
				raised_alpha = true;
				best_move = move;

				if (score >= beta) {

					if (legal == 1) {
						ss->info->fhf++;
					}
					ss->info->fh++;

					// Since we've beaten beta, we'll check if it is a quiet move. If it is, we'll add it to the killer and history heurstic
					if (piece_captured == NO_TYPE && SPECIAL(move) != PROMOTION) {
						ss->setKillers(ss->pos->ply, (*moves)[m]->move);
						ss->history[FROMSQ(move)][TOSQ(move)] += depth * depth;
					}



					tt->store_entry(ss->pos, best_move, score, depth, BETA);

					return beta;
				}

				ChangePV(best_move, pvLine, &line);

				alpha = score;
			}

		}

		delete moves;

		// If we had zero legal moves, we're either in checkmate or stalemate.
		if (legal == 0) {
			if (ss->pos->in_check()) {
				return -INF + ss->pos->ply;
			}
			else {
				return 0;
			}
		}

		// If we raised alpha, we're in a PV-node, otherwise we're in an all node
		if (raised_alpha) {
			tt->store_entry(ss->pos, best_move, alpha, depth, EXACT);
		}
		else {
			tt->store_entry(ss->pos, best_move, alpha, depth, ALPHA);
		}

		return alpha;
	} // alphabeta

And my quiescence search:

Code: Select all

	// At the moment quiescence only searches captures and promotions. FIXME: Should this also contain checks and check evasions?
	int quiescence(SearchThread_t* ss, int alpha, int beta) {
		SIDE Us = ss->pos->side_to_move;
		
		ss->info->nodes++;

		// Check if we need to stop, and drop out if we do.
		if ((ss->info->nodes & 2047) == 0) {
			CheckUp(ss);
		}

		if (ss->info->stopped) {
			return 0;
		}

		
		// Return zero for a drawn position, or if we have reached our maximum search depth.
		if ((is_repetition(ss->pos) || ss->pos->fiftyMove >= 100) && ss->pos->ply > 0) {
			return 0;
		}

		int stand_pat = Eval::evaluate(ss->pos);

		if (ss->pos->ply > MAXDEPTH - 1) {
			return stand_pat;
		}

		// If the static evaluation beats beta, we can do a cutoff
		if (stand_pat >= beta) {
			return beta;
		}

		else if (stand_pat > alpha) {
			alpha = stand_pat;
		}

		// Only generate tatical moves in quiescence
		MoveList* ml = ss->generate_moves(true);

		int legal = 0; // Amount of legal moves. We need to know if they are zero, so we can return a mate score or stalemate score

		int score = -INF;

		for (int m = 0; m < ml->size(); m++) {

			if (!ss->pos->make_move((*ml)[m])) {
				continue;
			}
			legal++;

			score = -quiescence(ss, -beta, -alpha);

			ss->pos->undo_move();

			// Return if we have been told to stop the search.
			if (ss->info->stopped) { return 0; }

			if (score > alpha) {
				alpha = score;

				if (score >= beta) {
					// If this is the first move, and it beats beta, we failed high on the first move i.e. good move ordering.
					if (legal == 1) {
						ss->info->fhf++;
					}
					ss->info->fh++;

					return beta;
				}
			}
		}

		if (legal == 0) {
			if (ss->pos->in_check()) {
				return -INF + ss->pos->ply;
			}
			else {
				return 0;
			}
		}

		delete ml;

		return alpha;
	} // quiescence

All of this is run inside an iterative deepening loop, and I have tested my eval to make sure it isn't unbalanced (it only consists of material and psqt at the moment though). The SearchThread_t class is:

Code: Select all

// SearchThread_t is a structure that holds all information local to a thread. This includes static evaluations, move ordering etc..
struct SearchThread_t {
	GameState_t* pos = new GameState_t;
	SearchInfo_t* info = new SearchInfo_t;

	int history[64][64] = { {0} };
	int killers[MAXDEPTH][2] = { {0} };

	int static_eval[MAXDEPTH] = { 0 };

	int thread_id = 0;


	void setKillers(int ply, int move);
	void pickNextMove(int index, MoveList* ml);

	MoveList* generate_moves(bool qsearch = false);
	~SearchThread_t() {
		delete pos;
		delete info;
	}

private:
	void score_moves(MoveList* ml);
};

Even though the engine is multithreaded with Lazy SMP, I still get problems with only one thread searching. It gives outright blunderous lines like:
[pgn]1. Nc3 Nf6 2. e4 Nxe4 3. Nxe4 Rg8 4. Nf3 h6 5. d4 *[/pgn]

Can anyone see what I am doing wrong?

Any help is very much appreciated!

It could be just the PV pollution. What is the eval at the end of the PV?

Since the error is in the middle of the PV it is probably not due to qSearch. Could be also a bug in the eval if pawn and knight are of the same value. From my experience, the majority of bugs are hidden in the TT.

What I would do:

1.Disable TT
2.Open AB windows to max
3.Disable beta cutoff
4.Start search after 1. Nc3 Nf6 2. e4 (best through a debugger)

I have just tried your recommendations, but with no success. I decided to test alphabeta without quiescence search, and it actually began giving more reasonable lines like:
[pgn]1. Nc3 Nf6 2. e4 e5 3. Nf3 Bb4 4. Ne2 Nxe4 *[/pgn]

Although this is far from optimal, I think it is a huge improvement since it really doesn't loose material the same way, and doesn't give away material as black. Therefore, i think all of this is an error in quiescence search after all, and the mistakes in the above PGN are a mixture between very minimal evaluation and shallow search depth.
What do you think? Could quiescence be the culprit?

[hgm]

It is not unusual that the searched tree completely changes even by a minor change in the evaluation. By searching without QS you will most certainly search a completely different tree. And alpha-beta always only searches a very small part of the minimax tree. So it is very likely that whatever caused the error will not be in the tree anymore, after a tiny change that had nothing to do with the error.

Without proper debugging search errors are typically impossible to find. To establish there is a bug in QS you would have to show there is a QS that returns an incorrect score.

[Desperado]

Code: Select all

		if (ss->pos->ply > MAXDEPTH - 1) {
			return Eval::evaluate(ss->pos);
		}

What is that supposed to do ?

I never call eval() in the search, except for pruning purposes.

It guards the data structure. Many arrays are limited to MAXDEPTH (MAXPLY).
If such a limit is reached you can not go deeper in the tree, so you return the static eval.