Chess Combinatorics: Number of legal positions after >2 turns

I've been working on programming my own chess engine for fun, and I've gotten to the point where I'm generating a game tree (which represents all the possible combinations of moves within a certain depth), and I'm not convinced that my code is doing so correctly.  I get 20 possibilities after 1 move, 400 possibilities after 2 moves, but when I generate the game tree for 3 moves I get 8,902 possibilities.   This article states that there are 5,362 "possible positions" after white's second move, and 8,902 "total positions" after 4 moves.  Can someone help me understand the distinction between this article's use of "possible positions" and "total positions?" I feel that the way I'm counting the nodes in my game tree might be off. 

Another article gives similar numbers, saying that there are 5,362 moves after 3 moves, and "The number of chess games that end in exactly  moves - including games that mate in fewer than plies  for n = 3: 8,902"  The fact that the number I'm getting is showing up in other places is promising, but I don't know what about it is wrong. 

Additional info: with a depth of 4 my code finds 197,281 positions, and at depth 5 my code finds: 4865359

Make sure you distinguish between whole moves and half moves(also kbnown as a ply).

Thanks Jabot, I'll think in plies from now on since that's how my code is structured.

Update: found the following breakdown of the 3 ply 5362 number (the number of moves my code find is the 2nd number):

two pawns move 2240, 4480

one white pawn moves twice 326, 326

1 white pawn and 1 white piece play 2416, 3536

1 white knight plays and turns back 20, 80

1 white knight plays twice without coming back 200, 240

2 white knights play 80, 160

1 white knight and 1 white rook play 80, 80

T o t a l 5362, 8902

I tried to compute these by hand to track down where my code might be going wrong, but I found that I actually disagree with several of these numbers. Can someone point out where I'm counting these wrong?

1 knight plays and turns back:

All 4 knights can move on the first move, and black has 20 possible moves following that. There's only one possibility on the 3rd ply move, however, because the knight that moved first has to move, and he only has one square to choose from (the one he started on). I count 4*20*1 = 80 possibilities, not 20.

1 knight plays twice without coming back:

4 possibilities to start out with, Black has 20 possible replies, and then the same knight that moved has to move again. Depending on if the knight moved to a3 or c3, f3 or h3, there are 2 or 4 possibilities respectively. I break this into two sums: (first move to outside files a and h) 2*20*2 + (first move to inside files c and f) 2*20*4 = 80 + 160 = 240

2 white knights play

Each knight has 2 options, so there are 4 possible knight moves at ply 1, then 20 black replies, and then the other knight has to be moved and he has two options. 4*20*2 = 160

I haven't tried to prove or disprove "two pawns move" or "1 pawn and 1 white piece play" since those are larger, and if I can do the simpler cases then I probably can't do the more complex ones. Can someone help me spot where I'm making a mistake with the cases I've tried to explain? It's just hard to understand what my code is doing wrong when I don't even agree with the the accepted number I've seen on several different websites.

I see no one ever answered this question, so I thought I would take a stab at it. I am wondering though if you ever solved the problem?

Anyway, the best way to trouble shoot your move generator is to use perft (performance testing move enumeration). See the wiki: Perft

I think you are on the right track here but let me fill in the correct numbers for the opening position which is:

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

depth 1: 20

depth 2: 400

depth 3: 8902

depth 4: 197281

depth 5: 4865609

These are the LEGAL moves generated only.The breakdown from the root node for each move is:

depth 1:

Move #1.Nb1-a3:1
Move #2.Nb1-c3:1
Move #3.Ng1-f3:1
Move #4.Ng1-h3:1
Move #5.Pa2-a3:1
Move #6.Pa2-a4:1
Move #7.Pb2-b3:1
Move #8.Pb2-b4:1
Move #9.Pc2-c3:1
Move #10.Pc2-c4:1
Move #11.Pd2-d3:1
Move #12.Pd2-d4:1
Move #13.Pe2-e3:1
Move #14.Pe2-e4:1
Move #15.Pf2-f3:1
Move #16.Pf2-f4:1
Move #17.Pg2-g3:1
Move #18.Pg2-g4:1
Move #19.Ph2-h3:1
Move #20.Ph2-h4:1

depth 2:

Move #1.Nb1-a3:20
Move #2.Nb1-c3:20
Move #3.Ng1-f3:20
Move #4.Ng1-h3:20
Move #5.Pa2-a3:20
Move #6.Pa2-a4:20
Move #7.Pb2-b3:20
Move #8.Pb2-b4:20
Move #9.Pc2-c3:20
Move #10.Pc2-c4:20
Move #11.Pd2-d3:20
Move #12.Pd2-d4:20
Move #13.Pe2-e3:20
Move #14.Pe2-e4:20
Move #15.Pf2-f3:20
Move #16.Pf2-f4:20
Move #17.Pg2-g3:20
Move #18.Pg2-g4:20
Move #19.Ph2-h3:20
Move #20.Ph2-h4:20

depth 3:

Move #1.Nb1-a3:400
Move #2.Nb1-c3:440
Move #3.Ng1-f3:440
Move #4.Ng1-h3:400
Move #5.Pa2-a3:380
Move #6.Pa2-a4:420
Move #7.Pb2-b3:420
Move #8.Pb2-b4:421
Move #9.Pc2-c3:420
Move #10.Pc2-c4:441
Move #11.Pd2-d3:539
Move #12.Pd2-d4:560
Move #13.Pe2-e3:599
Move #14.Pe2-e4:600
Move #15.Pf2-f3:380
Move #16.Pf2-f4:401
Move #17.Pg2-g3:420
Move #18.Pg2-g4:421
Move #19.Ph2-h3:380
Move #20.Ph2-h4:420

depth 4:

Move #1.Nb1-a3:8885
Move #2.Nb1-c3:9755
Move #3.Ng1-f3:9748
Move #4.Ng1-h3:8881
Move #5.Pa2-a3:8457
Move #6.Pa2-a4:9329
Move #7.Pb2-b3:9345
Move #8.Pb2-b4:9332
Move #9.Pc2-c3:9272
Move #10.Pc2-c4:9744
Move #11.Pd2-d3:11959
Move #12.Pd2-d4:12435
Move #13.Pe2-e3:13134
Move #14.Pe2-e4:13160
Move #15.Pf2-f3:8457
Move #16.Pf2-f4:8929
Move #17.Pg2-g3:9345
Move #18.Pg2-g4:9328
Move #19.Ph2-h3:8457
Move #20.Ph2-h4:9329

depth 5:

Move #1.Nb1-a3:198572
Move #2.Nb1-c3:234656
Move #3.Ng1-f3:233491
Move #4.Ng1-h3:198502
Move #5.Pa2-a3:181046
Move #6.Pa2-a4:217832
Move #7.Pb2-b3:215255
Move #8.Pb2-b4:216145
Move #9.Pc2-c3:222861
Move #10.Pc2-c4:240082
Move #11.Pd2-d3:328511
Move #12.Pd2-d4:361790
Move #13.Pe2-e3:402988
Move #14.Pe2-e4:405385
Move #15.Pf2-f3:178889
Move #16.Pf2-f4:198473
Move #17.Pg2-g3:217210
Move #18.Pg2-g4:214048
Move #19.Ph2-h3:181044
Move #20.Ph2-h4:218829

If you aren't getting these numbers, then your legal move generator isn't correct. I have a perft test file with about 150 or so positions figured out to depth 5 and 6 that you need to run with your engines move generator. Many of these tests are broken down into small simple chess problems that test your move generator on a certain move. Such as castling, or en passant, or promotions. By loading in all these positions and seeing which ones your engine fails at and which ones your engine completes successfully will allow you to determine where the bugs are in your legal move generator.

If you create a function that prints the board to the screen after each move made and each move that is undone, you can spot the bugs visually and fix what is going wrong.

If you would like help with the coding just ask. I would be happy to share.

I'd like to see the perft file.  Can you please post it?