Newbie programmer: weird bug in perft, node count changing

[aquaPlane]

I have just started in chess programming (and I don't have much experience with programming in general), so please be patient with me since I'll probably have a lot of trivial( ) or downright silly questions, which I could not find the answer to elsewhere.

My first attempt at a chess program, after over a month of reading up and programming, resulted in a very weak program that plays to the standard of a weakish club player. Once in a while it even drops a piece, presumably due to some bug in the code. Even the move generator for this first program could only churn out a measly 2million nps in perft (for kiwiPete) - and the program is written in (very bad) c++.

My second attempt at a chess program has now run into a strange problem. In the kiwiPete position, http://chessprogramming.wikispaces.com/Perft+Results, I found the node count to be incorrect for depth 4. Thus I used divide and found one of the problematic branches. At depth 1 in the branch, the problem was still there. Then, after I identified a problematic sub-branch and used divide/perft at depth 2, the total node count for this subbranch is actually correct and not the same as the node count for this subbranch from one level up! I checked this for all branches, and it was the same result.

For all the branches that I can see are wrong from divide, once I manually makeMove(), and go into them the node counts inexplicably change to the correct ones. The problem of course is that the original perft is still bugged - but how do I debug the program now? My function verifyBoard() also returns no problems after each unmakeMove(), so I'm stumped. Has anyone ever encountered a similar bug?

[Ajedrecista]

Hello:

I have just started in chess programming (and I don't have much experience with programming in general), so please be patient with me since I'll probably have a lot of trivial( ) or downright silly questions, which I could not find the answer to elsewhere.

My first attempt at a chess program, after over a month of reading up and programming, resulted in a very weak program that plays to the standard of a weakish club player. Once in a while it even drops a piece, presumably due to some bug in the code. Even the move generator for this first program could only churn out a measly 2million nps in perft (for kiwiPete) - and the program is written in (very bad) c++.

My second attempt at a chess program has now run into a strange problem. In the kiwiPete position, http://chessprogramming.wikispaces.com/Perft+Results, I found the node count to be incorrect for depth 4. Thus I used divide and found one of the problematic branches. At depth 1 in the branch, the problem was still there. Then, after I identified a problematic sub-branch and used divide/perft at depth 2, the total node count for this subbranch is actually correct and not the same as the node count for this subbranch from one level up! I checked this for all branches, and it was the same result.

For all the branches that I can see are wrong from divide, once I manually makeMove(), and go into them the node counts inexplicably change to the correct ones. The problem of course is that the original perft is still bugged - but how do I debug the program now? My function verifyBoard() also returns no problems after each unmakeMove(), so I'm stumped. Has anyone ever encountered a similar bug?

I am not a programmer so I can hardly help you. I think that your topic is more related with programming and technical discussions so a moderator should move this thread to that subforum.

This thread can probably help you:

REPORT: wrong perft result by qperft.

If I am not wrong, that problem is similar to yours and it had to do with a hash bug, but it is better that you read the whole thread.

I recommend you some perft counters to check your results on more positions (not only those positions at CPW). For example JetChess and gperft. A good collection of positions is found here. Good luck!

Regards from Spain.

Ajedrecista.

[tpetzke]

Hi,

welcome at chess programming.

Probably there is a bug in your make/unmake move code.

When you do a divide in general you just generate all moves for the root and for each move you make the move and generate the sub perft (this is your divide result for the move). Then undo the move and make the next move.

Code: Select all

   TDivideMoveList *dml;
	TMoveList *ml;
	int i;
	int64 subPerft;

	dml = new TDivideMoveList();
	ml = getAllMoves();

	for (i=0;i<ml->moveCnt;i++)
	{
		makeMove(ml->moves[i]);
		subPerft = perft(depth-1);
		unmakeMove(ml->moves[i]);

		dml->add(ml->moves[i],subPerft);
	}

	delete ml;
	return dml;

So if you now only make the move that showed a wrong perft and now it suddenly is correct, try simulating divide by making/perft/unmaking all the other moves too before you perft the suspicious one.

Probably one of the previous sub-perfts will then show you an error.

There are a lot of engines available that implement perft and divide (including iCE) so you can use them as reference for correct sub perfts and positions also for ones you don't find in the wiki.

Good luck with your engine!

[aquaPlane]

Thanks for the reply - you're quite right, this thread should probably be moved to programming discussions.

I have read the thread your suggested, but unfortunately I'm not using hashing in the move generator or perft, so it can't be that. My move generator uses the oldschool mailbox approach with a piecelist to speed up move generation. A further array is used to convert from the position of a piece on the board to its relevant position in the piecelist. My verifyBoard() function checks that these three parts are consistent after each unmake() in my perft function, and it is not throwing up any errors, so this is why I find the problem so perplexing.

[aquaPlane]

Yep, there is definitely something wrong with my make/unmake; I tried using the correct make/unmake from a previous version, and the problem disappeared.

Thanks for the suggestion - it looks like I'll have to simulate divide by hand. In fact I also thought of something along those lines, though I was putting it off, since it's such a daunting task with how messy my code is

EDIT: BTW Thomas, the Elo progress you have made with iCE over the past year or so is incredible (over 200 points right) - may I ask what features you have added to it that strengthened it so much?

[tpetzke]

The ELO gain from iCE 0.3 to iCE 1.0 came mainly from simple tuning.

I would distribute them
50 ELO by adding/changing/removing eval terms
80 ELO by tuning the evaluation terms
60 ELO by tuning the parameters that control the search (LMR and stuff)
50 ELO by producing an x64 binary (iCE 0.3 was 32 bit only)

iCE 0.3 was basically not tuned at all. All values were just set at a number that I thought makes sense. So there was a lot to gain there.

[Sven]

Yep, there is definitely something wrong with my make/unmake; I tried using the correct make/unmake from a previous version, and the problem disappeared.

Thanks for the suggestion - it looks like I'll have to simulate divide by hand. In fact I also thought of something along those lines, though I was putting it off, since it's such a daunting task with how messy my code is

Hi,

you might also have a counting error. Have you changed anything regarding node counting for perft recently?

Sven

[hMx]

Yep, there is definitely something wrong with my make/unmake; I tried using the correct make/unmake from a previous version, and the problem disappeared.

Thanks for the suggestion - it looks like I'll have to simulate divide by hand. In fact I also thought of something along those lines, though I was putting it off, since it's such a daunting task with how messy my code is

Here, I would try to print out the complete move trees and compare them to find the first difference. That may give a strong hint.

Cheers, Heiner

[jswaff]

I would recommend that you take a step back and write some basic unit testing around your make and unmake functions. Perft is more of a functional test. Debugging using perft will get you there eventually, but by the time you do that, you should already have some confidence that things will work.

One thing you might do is set up a test where you make a move (say, e4 from the initial position), then assert the value of the e.p. square, move counter, fifty move counter, player to move, etc. Then undo the move and do an equality check-- the position you have now should be exactly equal to the position before you started.

You could set up similar tests for any type of special (problematic) moves, such as castling, captures, ep captures, promotions, capturing promotions...

If your data structure has the possibility of redundant data becoming inconsistent (e.g. a special member that holds the value of a king square, even though you could loop over squares to find it), then set up a verification routine that checks that all these things are consistent. Call it via an assert() so that it's only triggered on DEBUG builds. If you do find an issue, go back and set up a failing unit test, then fix the bug.

--
James

[Bloodbane]

I had a bug like this long ago, it was caused by faulty updating of castling rights in unmake. Basically the program messed the rights up when getting out of one part of the tree and it affected the counts in the others. When divide was done the part of the tree which messed the right up was no longer there so everything was fine. Of course in your case it might not be castling rights but given the position it seems like it's the most likely explanation.