Weird perft logic

[Sven]

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.

*That* sounds weird ... You need to fix your perft function first to be able to verify that your movegen changes work well.

[leanchess]

Code: Select all

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

Thanks again, Ras!

As for "quazi-legal", is that something new? Perhaps it deserves a mention on the wiki?

[Sven]

Code: Select all

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

Thanks again, Ras!

As for "quazi-legal", is that something new? Perhaps it deserves a mention on the wiki?

Did you notice any of my replies on this topic? The code above still has the same problem that I already mentioned:

Code: Select all

	if (!depth)
		return 1;
	if (!(pEnd = gen_all(moves)))
		return 0;

does also count leaves resulting from an illegal move. Example: perft(4), e.g. 1.e4 d6 2.Bb5+ Kd7, you don't call gen_all() there so you miss that Bxd7 captures the king, instead you count it as a "valid leaf node".

Reversing the order:

Code: Select all

	if (!(pEnd = gen_all(moves)))
		return 0;
	if (!depth)
		return 1;

would not. It is slower but you can't get around that with a king-capture algorithm ...

[leanchess]

Did you notice any of my replies on this topic? The code above still has the same problem that I already mentioned:

Code: Select all

	if (!depth)
		return 1;
	if (!(pEnd = gen_all(moves)))
		return 0;

does also count leaves resulting from an illegal move. Reversing the order:

Code: Select all

	if (!(pEnd = gen_all(moves)))
		return 0;
	if (!depth)
		return 1;

would not. It is slower but you can't get around that with a king-capture algorithm ...

You are correct, of course.

Code: Select all

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

Now all that's left is find the bug in make/unmake...

[Sven]

After that change, what does your perft return now for depth=2, 3, 4 from startpos?

[Sven]

Watch out for bishop captures

[leanchess]

After that change, what does your perft return now for depth=2, 3, 4 from startpos?

perft(2)= 400
perft(3)= 9176
perft(4)=209700

I am growing frustrated. My branch-free make/unmake looked so promising...

[dangi12012]

After that change, what does your perft return now for depth=2, 3, 4 from startpos?

perft(2)= 400
perft(3)= 9176
perft(4)=209700

I am growing frustrated. My branch-free make/unmake looked so promising...

Enpassant not working? its mostly something to do with the edges of the board.
Are you using Juddperft Test-External?

[leanchess]

So as not to completely lose my sanity, I started over using C# (and even got it to look not too ugly):

Code: Select all

        ulong Perft(Move* start, int depth)
        {
            Move* end = start;
            if (!AddMoves(ref end))
                return 0;
            if (depth == 0)
                return 1;
            ulong count = 0;
            for (Move* curr = start; curr != end; ++curr)
            {
                Make(*curr);
                count += Perft(end, depth - 1);
                Unmake(*curr);
            }
            return count;
        }

That works, but is obviously very slow.

However, as soon as I try to do it by the book (see? I even named the function the same!):

Code: Select all

        ulong Perft(Move* start, int depth)
        {
            Move* end = start;
            if (depth == 0)
                return 1;
            AddMoves(ref end);
            ulong count = 0;
            for (Move* curr = start; curr != end; ++curr)
            {
                Make(*curr);
                if (!IsInCheck())
                    count += Perft(end, depth - 1);
                Unmake(*curr);
            }
            return count;
        }

I am again getting perft(3) = 8890.

[Sven]

After that change, what does your perft return now for depth=2, 3, 4 from startpos?

perft(2)= 400
perft(3)= 9176
perft(4)=209700

I am growing frustrated. My branch-free make/unmake looked so promising...

I do not understand why perft(3) now returns a bigger number than before. The correction in perft() should only have affected perft(4) and higher since there are no pseudo-legal but illegal moves within the first three plies. So probably you made more changes?