debugging my search function

[talkchessAccount]

hello everyone, this is my first time posting here, if did anything wrong please let me know.
I'm currently writing my first chess engine and the code below is what i use to find the best move.
it is able to solve lichess puzzles up to 1800 elo but i have many questions regarding its functionality
1) i used other people's code to write so i don't even know if i implemented it correctly
2) even though i get perft 6 in 4.5 seconds (no bulk-counting) it becomes incredibly slow after depth 3 (i assume this is because i don't order the moves)
3) i did some hacky things to get it working, they are described in the comments
4) it only gives the best move only if the depth is odd, otherwise it gives the best move to favor the other side

Code: Select all

#define WORST_EVAL -1e4
#define BEST_EVAL 1e4

// code adapted from TSCP
// eval_board is this code https://www.chessprogramming.org/PeSTO%27s_Evaluation_Function

static int quiesce(Board *board, int alpha, int beta)
{
	int eval = eval_board(board);

	if (eval >= beta)
		return beta;

	if (eval > alpha)
		alpha = eval;

	int movelist[MAX_MOVES];
	// pseudo-legal
	int n = generate_captures(board, movelist);
	bool legals = false;

	for (int i = 0; i < n; ++i) {
		move = movelist[i];
		int play_move(board, move);

		if (!move_was_legal(board)) {
			undo_move(board, move);
			continue;
		}

		legals = true;
		eval = -quiesce(board, -beta, -alpha);
		undo_move(board, move);

		if (eval >= beta)
			return beta;

		if (eval > alpha)
			alpha = eval;
	}

	// no legal moves found, either checkmate or stalemate
	if (!legals)
		return king_in_check(board) ? WORST_EVAL : 0;

	return alpha;
}

static int alphabeta(Board *board, int alpha, int beta, int depth)
{
	if (depth == 0)
		return quiesce(board, alpha, beta);

	int movelist[MAX_MOVES];
	int n = generate_all(board, movelist);
	bool legals = false;

	int move, eval;

	for (int i = 0; i < n; ++i) {
		move = movelist[i];
		play_move(board, move);

		if (!move_was_legal(board)) {
			undo_move(board, move);
			continue;
		}

		legals = true;
		eval = -alphabeta(board, -beta, -alpha, depth - 1);
		undo_move(board, move);

		if (eval >= beta)
			return beta;

		if (eval > alpha)
			alpha = eval;
	}

	if (!legals)
		return king_in_check(board) ? WORST_EVAL : 0;

	return alpha;
}

int search(Board *board, int depth)
{
	// moves are encoded as integers
	int movelist[MAX_MOVES];
	// number of pseudo-legal moves
	int n = generate_all(board, movelist);
	int move, result, score;

	score = WORST_EVAL;

	// i do this because after i get the best score
	// how am i supposed to know which move it is attached to?
	for (int i = 0; i < n; ++i) {
		int move = movelist[i];
		play_move(board, move);

		if (!move_was_legal(board)) {
			undo_move(board, move);
			continue;
		}

		// putting a '-' for some reason fixed it
		if ((result = -alphabeta(board, WORST_EVAL, BEST_EVAL, depth)) > score) {
			score = result;
			// here i know move has the best score
		}

		// if a checkmate is found stop trying other moves
		if (score >= BEST_EVAL) {
			undo_move(board, move);
			return score;
		}

		undo_move(board, move);
	}

	return score;
}

[oriyonay]

Hi there, and welcome to talkchess This is my first reply to a post, so we're both in the same boat!
I'll start with the comment in your code in your search function - how to know which move is associated with the highest score? I had the same question when I first got started, and there are two basic fixes for this. The first is the one that I use in my engine and is one that is very commonly used: once we collect the principal variation, the best move is just the first move in the PV. The other way is to just keep a global variable for the best move that you update whenever you find a better move.

Your implementation looks correct to me, though any problems you may have could very well also come from your implementation of move making/unmaking. My first engine also had that problem and could only play as black?? I've found that even though my perft was working perfectly, I was still missing stupid bugs that caused my search to be weird.

The reason you needed a negative sign in the alphabeta call in your search function is that your search function acts like the first layer of your alphabeta search. It's essentially the same function as your alphabeta, so you don't really need it (I know from experience, I did the same thing ). If you use either of the ways above you won't need that function (which you can just replace with an iterative deepening function).

You're 100% right in your assumption that your search gets slow because you don't order the moves, but also because you don't do much pruning. In computer chess, deeper is better than broader, assuming you're still considering the best moves. Even basic LVV/MVA move ordering will get you far!!

I hope this helped!
- Ori

[Ras]

This one in quiescence doesn't make sense to me:

Code: Select all

	// no legal moves found, either checkmate or stalemate
	if (!legals)
		return king_in_check(board) ? WORST_EVAL : 0;

Check evasions: what if the only legal answers are quiet moves? You will wrongly detect a mate here because you don't look at quiet moves in quiescence.
Stalemates: quiescence will capture and recapture until there are no more captures. If it's not check at this point, you will wrongly conclude stalemate because you don't consider quiet moves.