how to continue

[tcusr]

i rewrote the search function and now the engine seems to be working correctly consistently, it solves lichess puzzles if i give enough depth to see the combination (i'm only evaluating material for now).
now i'm going to add:
1) move ordering (i'll start with MVV/LVA because it is the simplest)
2) PSQT tables to improve strength
3) quiescence search

i have one question, is MVV ordering basically running a sort function on all the captures using the value of the piece on the "to" square to compare? and LVA just sorting in descending order using the value of the piece on the "from" square? this is the case for me because i use this enum

Code: Select all

enum {
	KING = 1,
	PAWN,
	KNIGHT,
	BISHOP,
	ROOK,
	QUEEN
};

Not quite. The way I've usually seen MVV/LVA implemented is using a two-dimensional array. Here's how Blunder does MVV-LVA move ordering:

Code: Select all

// An array that maps move scores to attacker and victim piece types
// for MVV-LVA move ordering: https://www.chessprogramming.org/MVV-LVA.
var MvvLva [7][6]int16 = [7][6]int16{
	{16, 15, 14, 13, 12, 11}, // victim Pawn
	{26, 25, 24, 23, 22, 21}, // victim Knight
	{36, 35, 34, 33, 32, 31}, // victim Bishop
	{46, 45, 44, 43, 42, 41}, // vitcim Rook
	{56, 55, 54, 53, 52, 51}, // victim Queen

	{0, 0, 0, 0, 0, 0}, // victim King
	{0, 0, 0, 0, 0, 0}, // No piece
}

...

// Score the moves given
func (search *Search) scoreMoves(moves *MoveList, ttBestMove Move, ply uint8) {
	for index := 0; index < int(moves.Count); index++ {
		move := &moves.Moves[index]
		captured := &search.Pos.Squares[move.ToSq()]
		moved := &search.Pos.Squares[move.FromSq()]
		move.AddScore(MvvLva[captured.Type][moved.Type])
	}
}

...

// Order the moves given by finding the best move and putting it
// at the index given.
func orderMoves(index int, moves *MoveList) {
	bestIndex := index
	bestScore := moves.Moves[bestIndex].Score()

	for index := bestIndex; index < int(moves.Count); index++ {
		if moves.Moves[index].Score() > bestScore {
			bestIndex = index
			bestScore = (*moves).Moves[index].Score()
		}
	}

	tempMove := moves.Moves[index]
	moves.Moves[index] = moves.Moves[bestIndex]
	moves.Moves[bestIndex] = tempMove
}

And here's how "scoreMoves" and "orderMoves" are called in negamax:

Code: Select all

// Score the moves
search.scoreMoves(&moves, ttBestMove, ply)

for index := 0; index < int(moves.Count); index++ {
	// Order the moves to get the best moves first.
	orderMoves(index, &moves)
	move := moves.Moves[index]

         ...
}

thank you for explaining, now i get it.
i have another problem now, i thought my search functions worked but i changed something and now i don't know what's going on.
even though i don't know Go i looked at your code and i think i'm doing the same thing but the engine gives me random moves even for simple positions like this k7/8/K7/8/8/8/8/2R5 w - - 0 1or k7/8/K3q3/3P4/8/8/8/8 w - - 0 1 (moves that my material-only evaluation functions could easily find)

Code: Select all

template<int C>
int negamax(Board& board, int depth, int alpha, int beta)
{
	if (depth == 0)
		return eval<C>(board);

	Move list[250], *end;
	int score;
	bool no_moves = true;

	end = generate_noisy<C>(board, list);
	end = generate_quiet<C>(board, end);

	for (Move *m = list; m != end; ++m) {
		board.make_move<C>(*m);

		if (board.move_was_legal()) {
			no_moves = false;
			score = -negamax<C ^ 1>(board, depth - 1, -beta, -alpha);
		}

		board.undo_move<C>(*m);

		if (score >= beta)
			return beta;

		if (score > alpha)
			alpha = score;
	}

	if (no_moves)
		return board.in_check() ? -MAX_EVAL : 0;

	return alpha;
}

// root negamax
template<int C>
Move search(Board& board, int depth)
{
	Move list[250], *end;
	Move best_move;

	int alpha = -MAX_EVAL;
	int beta = MAX_EVAL;
	int score;

	end = generate_noisy<C>(board, list); // eventually order these
	end = generate_quiet<C>(board, end);

	for (Move *m = list; m != end; ++m) {
		board.make_move<C>(*m);

		if (board.move_was_legal())
			score = -negamax<C ^ 1>(board, depth - 1, -beta, -alpha);

		board.undo_move<C>(*m);

		if (score == beta) {
			alpha = beta;
			best_move = *m;
			break;
		}

		if (score > alpha) {
			alpha = score;
			best_move = *m;
		}
	}

	return best_move;
}

[tcusr]

i'm starting to get depressed, it struggles to find mate in one but in this position (r3k2r/ppp1n1pp/2pq1p2/2b1p2b/4P3/3PBN1P/PPPN1PP1/R2Q1RK1 w kq - 5 10) it finds this, how?
the number on the left is depth searched
1: e3c5
2: e3c5
3: d2c4
4: d2c4
5: d2c4
6: d2c4
7: d2c4
8: d2c4
9: d2c4
10: d2c4
meanwhile here k7/8/K7/8/8/7R/8/8 w - - 0 1 it gives
1: h3h1
2: a6a5
3: h3h8
4: a6a5
5: a6a5
6: h3h8
7: h3h8
8: h3h8
9: a6a5
10: a6a5

[Mergi]

By the way, your score is unitialized. What if the first attempted move is illegal? Then you have random garbage in your score variable and might make some unexpected beta cutoffs.

The way you check for legality and then unmake the move will make your code very messy later on, when your engine has more features. I'd recommend using the more canonical way to do negamax with pseudo legal moves:

Code: Select all

	int score; // can be left unitialized
	
	for (Move *m = list; m != end; ++m) {
		board.make_move<C>(*m);

		if (!board.move_was_legal()) {
			board.undo_move<C>(*m);
			continue;
		}
		score = -negamax<C ^ 1>(board, depth - 1, -beta, -alpha);
		board.undo_move<C>(*m);
		no_moves = false;

		if (score >= beta)
			return beta;

		if (score > alpha)
			alpha = score;
	}
	

[tcusr]

By the way, your score is unitialized. What if the first attempted move is illegal? Then you have random garbage in your score variable and might make some unexpected beta cutoffs.

The way you check for legality and then unmake the move will make your code very messy later on, when your engine has more features. I'd recommend using the more canonical way to do negamax with pseudo legal moves:

Code: Select all

	int score; // can be left unitialized
	
	for (Move *m = list; m != end; ++m) {
		board.make_move<C>(*m);

		if (!board.move_was_legal()) {
			board.undo_move<C>(*m);
			continue;
		}
		score = -negamax<C ^ 1>(board, depth - 1, -beta, -alpha);
		board.undo_move<C>(*m);
		no_moves = false;

		if (score >= beta)
			return beta;

		if (score > alpha)
			alpha = score;
	}
	

ok thanks, i changed it.
but still, my engine is able to find tactics (even 5 moves long) but struggles with checkmate (in one)
can someone more experienced check it please? i noticed many engines return -INFINITY + ply but i just return -INFINITY, maybe this is the cause?
for example here k2p4/3R4/K7/8/8/8/8/8 w - - 0 1 it gives d7d8 as the best for ALL the depth i give. but without the pawn it doesn't find it

[algerbrex]

By the way, your score is unitialized. What if the first attempted move is illegal? Then you have random garbage in your score variable and might make some unexpected beta cutoffs.

The way you check for legality and then unmake the move will make your code very messy later on, when your engine has more features. I'd recommend using the more canonical way to do negamax with pseudo legal moves:

Code: Select all

	int score; // can be left unitialized
	
	for (Move *m = list; m != end; ++m) {
		board.make_move<C>(*m);

		if (!board.move_was_legal()) {
			board.undo_move<C>(*m);
			continue;
		}
		score = -negamax<C ^ 1>(board, depth - 1, -beta, -alpha);
		board.undo_move<C>(*m);
		no_moves = false;

		if (score >= beta)
			return beta;

		if (score > alpha)
			alpha = score;
	}
	

ok thanks, i changed it.
but still, my engine is able to find tactics (even 5 moves long) but struggles with checkmate (in one)
can someone more experienced check it please? i noticed many engines return -INFINITY + ply but i just return -INFINITY, maybe this is the cause?
for example here k2p4/3R4/K7/8/8/8/8/8 w - - 0 1 it gives d7d8 as the best for ALL the depth i give. but without the pawn it doesn't find it

Hi Pier, I think you've hit your issue right on the head!

You're correct that you need to return -INFINITY + ply and not just -INFINITY. The reason why is pretty simple. You don't want to reward the engine the same for finding mate in 1, and say, mate 8. Right? If you do, you run into the frustrating problem where the engine sees mate, but it probably won't deliver it, since it sees no difference in the reward between giving mate and seeing mate.

What you need to do to coax the engine into delivering mate once it sees it is to reward it more the closer it gets to mate and reward it fully once it delivers mate. So you need to encourage it to continue making moves leading to the shortest mate.

Probably the reason you're engine was able to find mate for the position:

[fen]k2p4/3R4/K7/8/8/8/8/8 w - - 0 1[/fen]

with the pawn, is because it naturally sees d7d8 as the best move since it wins material, and delivers mate, which means it sees the mate in 1 as being better than any other mate.

The easiest way to adjust the mate score is to use the ply of the current search to add to the negative mate score. That way, the engine will be penalized for finding long, often pointless mate sequences, the deeper and deeper it goes. Here's how I adjust the mate score returned in Blunder:

Code: Select all

// If we don't have any legal moves, it's either checkmate, or a stalemate.
if legalMoves == 0 {
	if inCheck {
		// If its checkmate, return a checkmate score of negative infinity,
		// with the current ply added to it. That way, the engine will be
		// rewarded for finding mate quicker, or avoiding mate longer.
		return -Inf + int16(ply)
	} else {
		// If it's a draw, return the draw value.
		return search.contempt()
	}
}

You can ignore "search.contempt()" and think of it as a constant DRAW_VALUE = 0.

And the way I find the ply, is simply by calling negamax like this in my root negamax:

Code: Select all

score := -search.negamax(depth-1, 0, -beta, -alpha, ...)

And then calling it recursively like so in the main negamax function:

Code: Select all

score := -search.negamax(depth-1, ply+1, -beta, -alpha, ...)

Hopefully this helps.

[algerbrex]

Also, I noticed you were starting to get pretty frustrated, and I can identify with that. I'm dealing with some bugs myself currently while trying to make Blunder stronger.

But think about the progress you've made so far, and think back to how you probably felt like you'd never finish debugging the move generator or some other part of the engine, but you eventually got it working. And try to use that perspective to keep persevering in squashing search and evaluation bugs.

[tcusr]

By the way, your score is unitialized. What if the first attempted move is illegal? Then you have random garbage in your score variable and might make some unexpected beta cutoffs.

The way you check for legality and then unmake the move will make your code very messy later on, when your engine has more features. I'd recommend using the more canonical way to do negamax with pseudo legal moves:

Code: Select all

	int score; // can be left unitialized
	
	for (Move *m = list; m != end; ++m) {
		board.make_move<C>(*m);

		if (!board.move_was_legal()) {
			board.undo_move<C>(*m);
			continue;
		}
		score = -negamax<C ^ 1>(board, depth - 1, -beta, -alpha);
		board.undo_move<C>(*m);
		no_moves = false;

		if (score >= beta)
			return beta;

		if (score > alpha)
			alpha = score;
	}
	

ok thanks, i changed it.
but still, my engine is able to find tactics (even 5 moves long) but struggles with checkmate (in one)
can someone more experienced check it please? i noticed many engines return -INFINITY + ply but i just return -INFINITY, maybe this is the cause?
for example here k2p4/3R4/K7/8/8/8/8/8 w - - 0 1 it gives d7d8 as the best for ALL the depth i give. but without the pawn it doesn't find it

Hi Pier, I think you've hit your issue right on the head!

You're correct that you need to return -INFINITY + ply and not just -INFINITY. The reason why is pretty simple. You don't want to reward the engine the same for finding mate in 1, and say, mate 8. Right? If you do, you run into the frustrating problem where the engine sees mate, but it probably won't deliver it, since it sees no difference in the reward between giving mate and seeing mate.

What you need to do to coax the engine into delivering mate once it sees it is to reward it more the closer it gets to mate and reward it fully once it delivers mate. So you need to encourage it to continue making moves leading to the shortest mate.

Probably the reason you're engine was able to find mate for the position:

[fen]k2p4/3R4/K7/8/8/8/8/8 w - - 0 1[/fen]

with the pawn, is because it naturally sees d7d8 as the best move since it wins material, and delivers mate, which means it sees the mate in 1 as being better than any other mate.

The easiest way to adjust the mate score is to use the ply of the current search to add to the negative mate score. That way, the engine will be penalized for finding long, often pointless mate sequences, the deeper and deeper it goes. Here's how I adjust the mate score returned in Blunder:

Code: Select all

// If we don't have any legal moves, it's either checkmate, or a stalemate.
if legalMoves == 0 {
	if inCheck {
		// If its checkmate, return a checkmate score of negative infinity,
		// with the current ply added to it. That way, the engine will be
		// rewarded for finding mate quicker, or avoiding mate longer.
		return -Inf + int16(ply)
	} else {
		// If it's a draw, return the draw value.
		return search.contempt()
	}
}

You can ignore "search.contempt()" and think of it as a constant DRAW_VALUE = 0.

And the way I find the ply, is simply by calling negamax like this in my root negamax:

Code: Select all

score := -search.negamax(depth-1, 0, -beta, -alpha, ...)

And then calling it recursively like so in the main negamax function:

Code: Select all

score := -search.negamax(depth-1, ply+1, -beta, -alpha, ...)

Hopefully this helps.

since i'm still at the beginning of my engine i thought i could implement later a way to find the shortest mate possible, thank you a lot for your help

Also, I noticed you were starting to get pretty frustrated, and I can identify with that. I'm dealing with some bugs myself currently while trying to make Blunder stronger.

But think about the progress you've made so far, and think back to how you probably felt like you'd never finish debugging the move generator or some other part of the engine, but you eventually got it working. And try to use that perspective to keep persevering in squashing search and evaluation bugs.

yeah, that's because it's the second time i encounter this problem (after my failed first engine), but now i finally solved it thanks to you!

one question, i noticed that my engine doesn't find checkmate if depth is 1 (i think this happens because it calls the evaluation function immediately since i pass depth-1 from the root, which is zero). in your engine i've seen that you increase depth if the king is in check, i guess this is the reason why, right?

[lithander]

You're correct that you need to return -INFINITY + ply and not just -INFINITY. The reason why is pretty simple. You don't want to reward the engine the same for finding mate in 1, and say, mate 8. Right? If you do, you run into the frustrating problem where the engine sees mate, but it probably won't deliver it, since it sees no difference in the reward between giving mate and seeing mate.

since i'm still at the beginning of my engine i thought i could implement later a way to find the shortest mate possible, thank you a lot for your help

Just returning the same score for all mates is fine. All released versions of MMC do it like that. I think even Amanj's Zahak does it like that and it's much stronger than our engines.

The only thing with that setup that you have to keep in mind is that it doesn't make sense to continue searching deeper after the PV leads to mate. Because algerbrex is right: there's just no incentive to prefer shorter mates. It might even find longer mate sequences when you increase the depth further and prefer those.

[tcusr]

You're correct that you need to return -INFINITY + ply and not just -INFINITY. The reason why is pretty simple. You don't want to reward the engine the same for finding mate in 1, and say, mate 8. Right? If you do, you run into the frustrating problem where the engine sees mate, but it probably won't deliver it, since it sees no difference in the reward between giving mate and seeing mate.

Just returning the same score for all mates is fine. All released versions of MMC do it like that. I think even Amanj's Zahak does it like that and it's much stronger than our engines.

The only thing with that setup you have to keep in mind is that it doesn't make sense to continue searching after the PV leads to mate. Because algerbrex is right, there's just no incentive to prefer shorter mates.

for me it doesn't work, if i remove "+ ply" it starts playing random moves again

[lithander]

i guess the important thing is that i added

Code: Select all

if (board.in_check()) ++ depth;

before checking if depth is equal to zero

You mean you implemented check extensions because your eval would otherwise not catch a mated position?

But by searching just one ply deeper your normal search should have caught it, right? If it doesn't you probably still have a bug somewhere and the check extensions are just covering it up.

If your engine has problem to find trivial mates like "k7/8/K7/8/8/8/8/2R5 w - - 0 1" you can just debug it by hand. Connect a debugger, step through the code. It's only a handful of moves and c1c8 should come back as a mate and if it doesn't you step through it one instruction after another and you'll know exactly what's going on.