how to continue

[tcusr]

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 one ply deeper your 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'll know exactly what's going on.

i see you quoted my unedited post. i tested it again and i can assure that it plays random moves if i remove "+ ply"

But by searching one ply deeper your 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.

yes, if depth > 1 it is able to find mate. am i supposed to check for checkmate in my evaluation function? i didn't know it
i only added the check extensions because it wasn't able to find mate if the depth is 1 (since i pass depth - 1 (0) it calls eval<C>(board) without going to the "if (no_moves)" at the end of negamax)

[Mergi]

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?

Yes, that is completely normal. Just making a move isn't enough to deduce that the opponent is mated. You also need to see if they have any responses available to your move. For mate in X plies, you always need to search X + 1 plies deep (= generate all the available responses and see that there's exactly 0 of them).

[lithander]

i see you quoted my unedited post. i tested it again and i can assure that it plays random moves if i remove "+ ply"

The only odd thing I can see in the code you posted above is that you have a beta cutoff in the root (how could a root move ever be too good?) and I think you could safely remove it. I have the hunch that it is responsible for your random moves. If it helps I can explain to you why exactly... but let's try that first.

yes, if depth > 1 it is able to find mate. am i supposed to check for checkmate in my evaluation function? i didn't know it

You can do whatever you want. But most engines only call the static evaluation on quiet positions where no captures are possible anymore. I was just surprised that you added check extensions (which I still don't have in my engine) before quiescence search. But if you want to see the mate without searching the next iteration it gets the job done.

[tcusr]

The only odd thing I can see in the code you posted above is that you have a beta cutoff in the root (how could a root move ever be too good?) and I think you could safely remove it. I have the hunch that it is responsible for your random moves. If it helps I can explain to you why exactly... but let's try that first.

tbf i copied it from algerbrex code (it seemed off to me too, i just kept it because i was desperate), i removed it now and it still finds mate if depth > 1 as before, thank you for that.
but still, if i remove "+ ply" it gives me random moves, only check extensions solve this

I was just surprised that you added check extensions (which I still don't have in my engine) before quiescence search.

i don't understand, why? check extensions is literally one statement. to add quiescence i have to first implement MVV/LVA ordering otherwise i will get a "quiescence explosion" which slows down search massively.

You can do whatever you want. But most engines only call the static evaluation on quiet positions where no captures are possible anymore

so you check for checkmate in the quiescence search?

[tcusr]

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?

Yes, that is completely normal. Just making a move isn't enough to deduce that the opponent is mated. You also need to see if they have any responses available to your move. For mate in X plies, you always need to search X + 1 plies deep (= generate all the available responses and see that there's exactly 0 of them).

i only saw this now, thanks for telling me, i feel better now
should i keep check extensions though? since, in my understanding, i will solve this problem of not finding mate at depth 1 with a quiescence search

[lithander]

but still, if i remove "+ ply" it gives me random moves, only check extensions solve this

I'm still not sure if I understand the extent of your problem: On the simple mate in 1 position do you always get random positions regardless of the depth you search (which would be of course hinting at a bug) or do you only get random positions when searching at depth 1? The latter would be expected. You need one ply to create the check and another ply to realize that there are no legal moves possible after that. So, as Mergi said: just search to depth 2 or greater if you want to find a mate in 1.

i don't understand, why? check extensions is literally one statement. to add quiescence i have to first implement MVV/LVA ordering otherwise i will get a "quiescence explosion" which slows down search massively.

so you check for checkmate in the quiescence search?

Quiescence has other advantages too namely dealing with the horizon effect. And as it makes moves until the position is quiet (and a checked position isn't quite) it prevents the static eval to be called on a checked position.

[tcusr]

I'm still not sure if I understand the extent of your problem: On the simple mate in 1 position do you always get random positions regardless of the depth you search (which would be of course hinting at a bug)

basically in my original function i just return -MAX_EVAL when there's a checkmate and, regardless of the depth, it sometimes gave me the mating move or the first possible move (the least significant bit of the attacks mask) or rarely a move by the king.
with algerbrex suggestion to use + ply it solved this problem and now it always gives me the mating move. i'm not worried about not finding mate at depth 1 because i will do it in quiescence as you said, which i will eventually implement.
i'm as confused as you, i have no explanation on why it doesn't give the mating move if i return a general -MAX_EVAL.
this is the code that behaves correctly

Code: Select all

template<int C>
int negamax(Board& board, int depth, int ply, int alpha, int beta)
{
        // i removed check extensions which would happen here
	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()) {
			board.undo_move<C>(*m);
			continue;
		}

		no_moves = false;
		score = -negamax<C ^ 1>(board, depth - 1, ply + 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 + ply : 0;

	return alpha;
}

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);
	end = generate_quiet<C>(board, end);

	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, 0, -beta, -alpha);
		board.undo_move<C>(*m);

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

	return best_move;
}

[algerbrex]

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.

True, that's a good point. I've always thought it easier to just let the engine naturally find the shortest mate by adjusting the mate score, but you're right it's perfectly fine to return the same mate score is fine, you just need to take care not to waste time searching deeper.

I thought it easier though to go with the later option, especially given what OP already has written.

[tcusr]

you just need to take care not to waste time searching deeper.

to do that you would need to check if alpha is equal to infinity in your iterative deepening loop?
does your engine work correctly if you remove + ply? i'm afraid i may have a bug, which is sad since my whole search module is the code i posted 2 posts above

[Mergi]

I'll dare to venture a guess. The reason why for others disregarding the ply might work is because they use iterative deepening. So for each particular depth, if they find a mate, they can keep track of it, and then they can select the shortest one overall. But in your case, it appears that you dont use iterative deepening (?), meaning that you search every single move to a fixed depth. Now if the first move leads to a mate in 5, from your engine's point of view it's the same as if another move lead to mate in 2. So the move returned is a mating move, just perhaps it will shuffle the king back and forth 4 times before delivering the mate, instead of doing it immediately.