Newbie with a question about debugging move generation...

[dsharp]

I've been working on a chess program off-and-on for a few months now, and I've reached the point where I really need to debug my move generation.

I've implemented perft() and divide(), but I've run into an issue where perft() returns a different total number of nodes than divide.

perft("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1",2); yields 2053 nodes

divide("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1",2); yields a total of 2039 nodes.

I happen to know that the 2039 is the correct number. but I have no idea how to figure out why perft() is overcounting by 14 nodes, especially since divide() calls perft().

here is my perft() code:

Code: Select all

    public static void perft(int depth,Game game, long[] stats,boolean verbose)
    {
        Color color = game.getBoard().getColorToMove();
        Color enemy = color.getEnemy();
        Collection<Move> moves = game.getBoard().getMoves(color, false);
        if (depth == 0)//divide may call perft 0;
        {
            ++stats[0];
        }
        else for(Move move : moves)
        {
            game.applyMove(move);
//            System.out.println("Applied " + move);
            if (!game.getBoard().inCheck(color))
            {
                if(verbose)
                {
                    for(int i=0;i<(3-depth);++i)
                    {
                        System.out.printf("   ");
                    }
                    System.out.print("+>" + move);
                    if (depth == 1)
                        System.out.print("\t (" + stats[0] + ")");
                    else
                        System.out.print(" <" + game.getBoard().getMoves(color, false).size() + ">" + " " + color.toString());
                    System.out.println();
                }

                if (move.isCapturingMove()) ++stats[1];
                if (move instanceof EnpassantMove) ++stats[2];
                if (move instanceof CastleMove) ++stats[3];
                if (move instanceof PromotionMove) ++stats[4];
                if (game.getBoard().inCheck(enemy))
                {
                    ++stats[5];
                    if (game.getBoard().getMoves(enemy, false).size() == 0) ++stats[6];
                }
                
                if (depth == 1) ++stats[0]; //avoid recursive call
                else perft(depth - 1, game,stats,verbose);


            }
//            System.out.println("Undoing " + move);
            game.undoMove();
        }

Here is my divide() code:

Code: Select all

    public static void divide(int depth, Game game, boolean verbose)
    {
        Board board = game.getBoard();
        long[] stats = new long[7];
        Color color = game.getBoard().getColorToMove();
        Collection<Move> legalMoves = game.getBoard().getMoves(color, false);
        for(Move move : legalMoves)
        {
            if (verbose) System.out.println("start:" + move);
            long[] localStats = new long[7];
            game.applyMove(move);
            if (verbose) System.out.println(board);
            if (!game.getBoard().inCheck(color))
            {
                perft(depth-1,game,localStats,verbose);
                for(int i=0;i<localStats.length;++i)
                {
                    stats[i]+=localStats[i];
                }
                if (move instanceof PromotionMove)
                {
                    PromotionMove pmove = (PromotionMove) move;
                    System.out.println(locationString(pmove.getStartLocation()) + locationString(pmove.getEndLocation()) + pmove.getNewType().toString(Color.WHITE) + " " + localStats[0]);
                }
                else
                {
                    System.out.println(locationString(move.getStartLocation()) + locationString(move.getEndLocation()) + " " + localStats[0]);
                }
            }
            game.undoMove();
        }
        System.out.println("Nodes: " + stats[0]);
        System.out.println(game.getBoard());
    }

If anyone sees any obvious errors, I would appreciate the help.

Thanks,
Dave

[Robert Pope]

One thing to check is if they always return the same number. Do you get the same numbers if you do perft, then divide, as you do with divide, then perft?

I had a problem with unmake once, so when I did perft/divide the second time, I would get a different result than the first time, because the board position was corrupted.

[Kempelen]

Well, I am not an expert in C++, but I think your are calling new to allocate size for variables and then you dont assign them to 0 in order to propertly inicializate. This happend with "long[] stats = new long[7]; ". It could take any initial values. Also with localStats. Also I think you must call delete to release memory allocated. Only a tip that maybe is not the solution.....

[ilari]

Well, I am not an expert in C++, but I think your are calling new to allocate size for variables and then you dont assign them to 0 in order to propertly inicializate. This happend with "long[] stats = new long[7]; ". It could take any initial values. Also with localStats. Also I think you must call delete to release memory allocated. Only a tip that maybe is not the solution.....

The code is obviously Java, not C++. The garbage collector will delete any dynamically allocated data when it's not needed, and I believe that even primitive data types get assigned a default value (0).

[dsharp]

Edit:
I found the bug in under a minute thanks to your hint. I was setting the color to move to the opposite of what it needed in my undo() logic.

Again, many thanks!
---

One thing to check is if they always return the same number. Do you get the same numbers if you do perft, then divide, as you do with divide, then perft?

You sir, are a genius. There does indeed appear to be a problem with my undo logic. Now that I think about it, it makes sense. About a month ago, I introduced an AbstractMove base class that imposes a default make/undo lifecycle with phases to be overridden by child move classes as needed.

Heh, all that was supposed to make the code more modular and easier to understand. Time to whip my lazy butt into shape and write some unit tests for each move class's make/unmake logic.

Thanks a bunch!
Dave

[Robert Pope]

You sir, are a genius.

Heh, if that were true, Beaches wouldn't still be a 1700 engine. I just decided to try 0x88 instead of rotated bitboards, and now have a very clean program that runs half as fast as the original slow one. Oh, well.

[dsharp]

Heh, if that were true, Beaches wouldn't still be a 1700 engine. I just decided to try 0x88 instead of rotated bitboards, and now have a very clean program that runs half as fast as the original slow one. Oh, well.

Hah! I know *exactly* how you feel. I switched from a simply array representation to 0x88 and it took a lot of work to get a speed-up. Method invocation overhead was killing me, so I ended up switching to direct member access from getter/setter.

Now I'm maybe 30% faster than my array-based engine, but still only running about 3% of the speed of a non-java engine (roce38). Perft on my engine gets around 2M nodes/sec on my 27" iMac. Roce gets over 60M nodes/sec.

I'm hoping that raw move generation speed won't be an issue once I get better search algorithms implemented.

Right now I'm using plain-old Negamax, without a transposition table, and a relatively simple heuristic function.

It can beat the Chess program included with Mac OS, if I turn the settings down.

How do you find your engine's rating?[/quote]

[Robert Pope]

Heh, if that were true, Beaches wouldn't still be a 1700 engine. I just decided to try 0x88 instead of rotated bitboards, and now have a very clean program that runs half as fast as the original slow one. Oh, well.

Hah! I know *exactly* how you feel. I switched from a simply array representation to 0x88 and it took a lot of work to get a speed-up. Method invocation overhead was killing me, so I ended up switching to direct member access from getter/setter.

Now I'm maybe 30% faster than my array-based engine, but still only running about 3% of the speed of a non-java engine (roce38). Perft on my engine gets around 2M nodes/sec on my 27" iMac. Roce gets over 60M nodes/sec.

I'm hoping that raw move generation speed won't be an issue once I get better search algorithms implemented.

Right now I'm using plain-old Negamax, without a transposition table, and a relatively simple heuristic function.

It can beat the Chess program included with Mac OS, if I turn the settings down.

How do you find your engine's rating?

[/quote]
Ask for it to be entered in WBEC Ridderkerk. Leo does very thorough competitions involving over 100 engines.