Weird perft logic

[leanchess]

I'm trying to implement perft from scratch.

I'm not sure if my approach is anything new (it's definitely not the most efficient), but the wiki doesn't mention it.

I'm using a "quazi-legal" move generator:

Code: Select all

move_t* gen_all(move_t* moves);

which returns NULL when it finds a king capture.

Code: Select all

int64_t perft(move_t* moves, uint8_t depth) {
	move_t *pCurr, *pEnd;
	int64_t count = 0, n;
	if (!depth)
		return 1;
	if (!(pEnd = gen_all(moves)))
		return -1;
	for (pCurr = moves; pCurr != pEnd; ++pCurr) {
		make(*pCurr);
		n = perft(pEnd, depth - 1);
		unmake(*pCurr);
		if (n < 0)
			return 0;
		count += n;
	}
	return count;
}

perft(3) for startpos returns 8890, which is exactly 12 less than right.

Could you please help me find the bug?

[dangi12012]

I'm trying to implement perft from scratch.

I'm not sure if my approach is anything new (it's definitely not the most efficient), but the wiki doesn't mention it.

I'm using a "quazi-legal" move generator:

Code: Select all

move_t* gen_all(move_t* moves);

which returns NULL when it finds a king capture.

Code: Select all

int64_t perft(move_t* moves, uint8_t depth) {
	move_t *pCurr, *pEnd;
	int64_t count = 0, n;
	if (!depth)
		return 1;
	if (!(pEnd = gen_all(moves)))
		return -1;
	for (pCurr = moves; pCurr != pEnd; ++pCurr) {
		make(*pCurr);
		n = perft(pEnd, depth - 1);
		unmake(*pCurr);
		if (n < 0)
			return 0;
		count += n;
	}
	return count;
}

perft(3) for startpos returns 8890, which is exactly 12 less than right.

Could you please help me find the bug?

Its easy to find bugs with this tool:
https://github.com/jniemann66/juddperft

It has a "Test-External" command which expects your main() to take a fen and a number and return success if they match.
Then it will show you the 1 position where perft differs.

A performance hint:
if (!depth) return 1;
Take it a level higher and do if (depth == 1) return 1; Because then your processor doesnt need to go a stacklevel deeper just to return 1.

[dangi12012]

Code: Select all

for (pCurr = moves; pCurr != pEnd; ++pCurr) {
		make(*pCurr);
		n = perft(pEnd, depth - 1);
		unmake(*pCurr);
		if (n < 0)
			return 0;
		count += n;
	}

Becomes:

Code: Select all

pCurr = moves;
while(pCurr++ != pEnd) {
		make(*pCurr);
		count += perft(pEnd, depth - 1);
		unmake(*pCurr);
}

The if statement with n<0 is redundant. (except if you use -1 as signalling which is bad in this case)

[leanchess]

I have the performance in mind, but I believe correctness should be the priority.

[dangi12012]

I have the performance in mind, but I believe correctness should be the priority.

Simple code is easier to debug.

[Ras]

Code: Select all

for (pCurr = moves; pCurr != pEnd; ++pCurr) {
	make(*pCurr);
	n = perft(pEnd, depth - 1);
	unmake(*pCurr);
	if (n < 0)
		return 0;
	count += n;
}

So if you make an illegal move that leads to a king capture, you cancel not only the result from that move, but the whole node? That doesn't look right. I'd guess it could work like this:

Code: Select all

for (pCurr = moves; pCurr != pEnd; ++pCurr) {
	make(*pCurr);
	n = perft(pEnd, depth - 1);
	unmake(*pCurr);
	if (n > 0)
		count += n;
}

[leanchess]

I have the performance in mind, but I believe correctness should be the priority.

Simple code is easier to debug.

Yes, as simple as possible, but not simpler. perft(1) is sometimes 0 with my approach.

[Sven]

I think you need to generate moves at depth 0 as well to check whether a leaf node was reached by an illegal move. Currently you always return 1 there.
Additionally, I would simply return 0 in all illegal positions. That should work magically for mate/stalemate as well.
So:
if (!gen_all()) return 0;
if (depth == 0) return 1;
n = 0;
for all moves:
n += perft(move, depth - 1 ...)
return n;

[Sven]

perft(3) for startpos returns 8890, which is exactly 12 less than right.

Since White can't make any illegal move two plies from startpos there must be a movegen/make/unmake bug unrelated to your perft function itself.

[leanchess]

So if you make an illegal move that leads to a king capture, you cancel not only the result from that move, but the whole node? That doesn't look right. I'd guess it could work like this:

Code: Select all

for (pCurr = moves; pCurr != pEnd; ++pCurr) {
	make(*pCurr);
	n = perft(pEnd, depth - 1);
	unmake(*pCurr);
	if (n > 0)
		count += n;
}

Thank you, that must be it; cannot verify right now due to a bug in the move generator.