request assistance or advice on an obscure bug

[michiguel]

perft simply walks a search tree with a fixed depth, so it's far simpler than even alpha beta with fixed depth and no qsearch


Off the top of my head, here's some pseudocode of the entire perft function.

Code: Select all

//perft calculates the number of leaf nodes in a search tree at a given depth
int perft(int depth)
{
  if(depth==0)
    return 1;
  int leaves = 0;
  genMoves();
  foreach move m in movelist
  {
    makeMove(m);
    leaves += perft(depth-1);
    undoMove();
  }
  return leaves;
}

I don't know what perftdiv is, can somebody enlighten me?

perftdiv x gives you the perft x-1 value after each legal move. It is like advancing one ply on the tree and get the "sub" values. For instance, from the initial position:

Code: Select all

perftdiv 2
   -->    f2-f4          20
   -->    c2-c4          20
   -->    e2-e4          20
   -->    d2-d4          20
   -->    h2-h4          20
   -->    g2-g4          20
   -->    f2-f3          20
   -->    c2-c3          20
   -->    b2-b4          20
   -->    a2-a4          20
   -->    e2-e3          20
   -->    d2-d3          20
   -->    h2-h3          20
   -->    g2-g3          20
   -->    b2-b3          20
   -->    a2-a3          20
   -->   Ng1-f3          20
   -->   Nb1-c3          20
   -->   Ng1-h3          20
   -->   Nb1-a3          20
depth 2: leaves:        400
seconds: 0.00 nps: inf

So, if perft fails, you know which move lead you to a wrong number. Very easy to find the problem.

Miguel

[jwes]

In my experience, the easiest way to find bugs like this is by using perft. If your engine passes perft tests in a variety of positions, you can be much more confident that things like castling rights and en passant are handled correctly in your move generator.

If you're not familiar with perft, more information is available at http://chessprogramming.wikispaces.com/Perft

Thanks, I've tried to figure perftt out a few times. It's on my list. Personally I find the chessprogramming wiki a little too advanced for my needs. I'm just an amateur in this crowd. recursion tends to make my head spin.

Anyways. I knew early on my program wasn't passing the test and I was pretty sure it was castling related, I also thought of unmake move early on, because a move was being made by a non-existent piece. I just didn't spot the typo, even thought I passed over it a few times.

It is refreshing to see someone to attack CC from the ground up. We are cheering for you Fred. Trust me, perft should not be just in your list, perft should be your priority #1. Perftdiv your priority #2.

Miguel

Thanks for the support, duly noted on the perftt. I've certainly heard it often enough. I'll have to give it another go soon.

The program has come a long way in the last year or two, thanks in large part to the help I've received here. I have a ton of ideas for moving ahead, a lot of it is GUI related, database stuff, chess server client, UCI or xBoard standard. gaming website stuff . It's supposed to be a vehicle for learning to program, I have to make sure the chess aspect doesn't take priority.

Perft is actually simpler than things you have been already doing. One way to think of it is as mini-max without an eval. I will try to give an example off the top of my head, so I will skip some details (and probably make some mistakes).

Code: Select all

int perft (int n)
{
  int count =0;
  MOVE movelist[256];
  int nmoves = GenerateMoves(movelist);
  for &#40;i=0;i<nmoves;i++&#123;
    MakeMove&#40;movelist&#91;i&#93;);
    if (!InCheck&#40;)) &#123;  // is it a legal move?
      if &#40;n>0&#41;
        count += perft&#40;n-1&#41;;
      else
        count++;    // count the nodes at the last ply
    &#125;
    UnmakeMove&#40;);
    return count;
&#125;

[Fguy64]

OK thanks to all for the tips. You are right, it doesn't look that hard, I'm not sure what I was thinking of. I suppose I actually use a manual form of it, but what I see it looks like it will make it a lot quicker to zero in on on problem nodes.

I'll see if I can't give it a try maybe this weekend, and let you know,.