Illegal moves in PV stack

[niel5946]

Hi.

I have noticed my engine making illegal moves over the past few days and I can't seem to figure out why. When I play a 200 game tournament - I have tested with time controls of 4s+0.1s, 12s+0.12s and 1min - between the current and the old version, at least two of those games are lost (by the current) because of playing an illegal move. It is usually because the engine recommends the opponents response to the actual best move (for example if e2e4, e7e5 is the best line for white, the engine sometimes gives the UCI-command "bestmove e7e5"), but the confusing/infuriating thing is that it is not reproducible... Everytime I see a position where it has made an illegal move, I paste in the FEN and make the engine search, but then magically, it actually gives the best (legal) move.. I have also tried loading the FENs for each position it searched during the game, run the search for the time cutechess has noted it searched for, but this still doesn't show any illegal moves..
For PV storing I use a PV-stack like the one on https://www.chessprogramming.org/Principal_Variation.
PV stack:

Code: Select all

struct SearchPv {
	int length = 0;
	int pv[MAXDEPTH] = { 0 };

	void clear() {
		std::fill(std::begin(pv), std::end(pv), 0);
		length = 0;
	}
};

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

	// Here we copy the PV that the child node found into the parent while keeping the parent's first move as "move"
	std::copy(std::begin(child->pv), std::begin(child->pv) + child->length, std::begin(parent->pv) + 1);
}

Aspiration windows:

Code: Select all

	// Calls search_root with aspiration windows
	int aspiration_search(SearchThread_t* ss, int depth, int estimate, SearchPv* line) {
		/* Set up alpha beta apsiration windows... */
	asp_loop:
		line->clear();
		score = search_root(ss, depth, alpha, beta, line);

		/* adjust alpha and beta if score is outside the bounds */

		return score;
	}

The root search function:

Code: Select all

// Root alpha beta
	int search_root(SearchThread_t* ss, int depth, int alpha, int beta, SearchPv* pvLine) {
		assert(depth > 0);

		ss->info->nodes++;

		pvLine->length = 0;
		SearchPv line;

		/* TT probing and other initialization */

		// Now we'll loop through the move list.
		for (int m = 0; m < moves->size(); m++) {

			ss->pickNextMove(m, moves);
			
			int move = (*moves)[m]->move;
			

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

			
			// Print move, move number and such to the command line.
			if (ss->thread_id == 0) {
				uci_moveinfo(move, depth, legal);
			}

			// PVS
			if (!raised_alpha) {
				score = -alphabeta(ss, depth - 1, -beta, -alpha, true, &line);
			}
			else {
				score = -alphabeta(ss, depth - 1, -alpha - 1, -alpha, true, &line);

				if (score > alpha) {
					score = -alphabeta(ss, depth - 1, -beta, -alpha, true, &line);
				}
			}


			ss->pos->undo_move();


			if (score > best_score) {
				best_score = score;

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

					raised_alpha = true;

					ChangePV(best_move, pvLine, &line); // Change PV when raising alpha
				}
				else if (legal == 1) {  // Make sure that we have at least some pv if we fail low.
					ChangePV(move, pvLine, &line);
				}
			}

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

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

				ChangePV(move, pvLine, &line); // Change PV when failing high.

				delete moves;

				return beta;
			}

		}

		/* Checkmate detection and tt-storing */
	
		return alpha;
	}

and the alpha beta function itself:

Code: Select all

int alphabeta(SearchThread_t* ss, int depth, int alpha, int beta, bool can_null, SearchPv* pvLine) {
		assert(beta > alpha);

		// Reset pv
		pvLine->length = 0;


		SIDE Us = ss->pos->side_to_move;
		SIDE Them = (Us == WHITE) ? BLACK : WHITE;

		ss->info->nodes++;

		/* Transposition table probing here */

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

		/* Repetition and 50-move check */

		int score = -INF;
		int best_score = -INF;

		bool raised_alpha = false;
		int best_move = NOMOVE;

		int reduction = 0; // Only used in moves_loop

		int new_depth;

		// We are in a PV-node if we aren't in a null window.
		// In a null window, beta = alpha + 1, which means that beta - alpha = 1, so if this isn't true, we're not in a null window.
		bool is_pv = (beta - alpha == 1) ? false : true;

		// Create a new PV
		SearchPv line;

		// Idea from stockfish: Are we improving our static evaluations over plies? This can be used for pruning decisions.
		bool improving = false;

		// Determine if we're in check or not.
		bool in_check = ss->pos->in_check();



		/* Mate distance pruning here */

		// Step 4. Static evaluation.
		if (in_check) {
			// If we're in check, we'll go directly to the moves since we don't want this branch pruned away.
			ss->static_eval[ss->pos->ply] = VALUE_NONE;
			improving = false;

			goto moves_loop;
		}
		
		ss->static_eval[ss->pos->ply] = Eval::evaluate(ss->pos);
		improving = (ss->pos->ply >= 2) ? (ss->static_eval[ss->pos->ply] >= ss->static_eval[ss->pos->ply - 2] || ss->static_eval[ss->pos->ply - 2] == VALUE_NONE) :
			false;

		assert(!in_check);


		/* Null move pruning here */



		/* Enhanced futility pruning here */


		/* Reverse futility pruning here */


		/* Razoring here */


		moves_loop:

		MoveList* moves = ss->generate_moves();


		/* Internal Iterative deepening here */

		int move = NOMOVE;
		int legal = 0;
		int moves_searched = 0;

		for (int m = 0; m < moves->size(); m++) {
			ss->pickNextMove(m, moves);

			move = (*moves)[m]->move;
			bool capture = (ss->pos->piece_list[Them][TOSQ(move)] != NO_TYPE) ? true : false;

			reduction = 0;
			int extensions = 0;


			/* Exstensions */

			if (!ss->pos->make_move((*moves)[m])) { // Make the move
				continue;
			}
			
			// Increment legal when we've made a move. This is used so as to not prune potential checkmates or stalemates.
			legal++;

			bool gives_check = ss->pos->in_check();			



			/* Late move pruning here */
			


			/* Futility pruning here */
			
			
			new_depth = depth + extensions - 1;
		
			/* Late move reductions here */
			

			re_search:

			// Step 14. Principal Variation Search.
			if (!raised_alpha) {
				score = -alphabeta(ss, new_depth, -beta, -alpha, true, &line);
			}
			else {
				score = -alphabeta(ss, new_depth, -alpha - 1, -alpha, true, &line);

				if (score > alpha) {
					score = -alphabeta(ss, new_depth, -beta, -alpha, true, &line);
				}
			}


			// If we raise alpha on a reduced search, re-search the move at full depth.
			if (reduction > 0 && score > alpha) {
				reduction = 0;
				new_depth = depth - 1;

				re_searches++;

				goto re_search;
			}


			ss->pos->undo_move();

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

			if (score >= beta) {
				if (moves_searched == 1) {
					ss->info->fhf++;
				}
				ss->info->fh++;

				/* Update move ordering heuristics here */

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

				// Change the PV even when failing high
				ChangePV(move, pvLine, &line);

				delete moves;

				return beta;
			}


			if (score > best_score) {
				best_score = alpha;
				best_move = move;

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

					// Change PV
					ChangePV(move, pvLine, &line);
				}
			}


		}

		delete moves;

		/* TT-storing and checkmate/stalemate detection here */


		return alpha;
	}

For completeness sake, here are the full search.cpp code: https://github.com/BimmerBass/Loki/blob ... search.cpp

I know the illegal moves aren't caused by the move generator since I have done perft tests on the positions in which they happened and verified with Stockfish's perft function.

Is there anything weird or erroneous about the way I store the PV?

Any help is much appreciated!

[jdart]

It's a bug, no easy way to tell where I think.

You could add a check for illegal moves at the point where it's storing the PV. Run it in the debugger and see when that is triggered.

It's also generally a good idea to run a sanity check with a bounds checker (use -fsanitize-bounds-strict and -fsanitize-address on the compile and link lines for GCC). That will show any array overflow problems you might have.

[hgm]

Since you appear to take the move to play from the PV, how do you get that PV? Normally the root search would construct a new PV from a move that raised alpha, followed by the PV returned by the child node. And normally it would only search move for the player on move. So how could the first move of a PV ever be an opponent move? Do you search moves in the root that were not generated by the move generator (e.g. hash, killers)?

[niel5946]

Since you appear to take the move to play from the PV, how do you get that PV? Normally the root search would construct a new PV from a move that raised alpha, followed by the PV returned by the child node. And normally it would only search move for the player on move. So how could the first move of a PV ever be an opponent move? Do you search moves in the root that were not generated by the move generator (e.g. hash, killers)?

I get the PV exactly the way you're explaining, and I have checked that there are no moves made before calling root_search (which would make it search the opponent moves).
I do not search moves returned by the TT or killers, but I do score them accordingly which I do by looping through the move list to to see if they're there.

[Sven]

@Niels:
1) I suggest not to change the PV if score <= alpha or score >= beta. In that case you will restart the root search with a different aspiration window anyway (or you run out of time so you play the best move from previous iteration) so you do not need a PV (and it would also be misleading).
2) Furthermore, in root search you do a "delete moves" right before returning beta, is that intended? You don't do that further down when returning alpha ... but I can't see from your code snippet where you allocate the root move list (I would have guessed that you do that outside of your root search function?).
Both points do not really sound like an explanation for illegal moves, though ...

[Ronald]

if the search is stopped before the alfabeta search is finished (ss->info->stopped) you have to make sure you don't use any results of the last search. You seem to do that in alphabeta() but I don't see it in search_root(). This means that the current search results are stored in your PV and also in the hashtable.

Code: Select all

ss->pos->undo_move();

// stop code here

if (score > best_score) {

I didn't check the main search loop.

The results of a stopped search are usually bogus, from experience I know that if you use that info it sometimes results in very "interesting" moves played....

[niel5946]

@Niels:
1) I suggest not to change the PV if score <= alpha or score >= beta. In that case you will restart the root search with a different aspiration window anyway (or you run out of time so you play the best move from previous iteration) so you do not need a PV (and it would also be misleading).
2) Furthermore, in root search you do a "delete moves" right before returning beta, is that intended? You don't do that further down when returning alpha ... but I can't see from your code snippet where you allocate the root move list (I would have guessed that you do that outside of your root search function?).
Both points do not really sound like an explanation for illegal moves, though ...

1. That makes sense. I agree that this does not explain illegal moves, but thanks for the suggestion
2. I think that I've just deleted the part of the code for this post. In the full function, moves gets deleted before returning alpha