Pls help a poor beginner, Moves generator

[Marcus9]

Despite my weak programming knowledge,
since I'm a computer chess fan,
I decided to create a simple chess engine.

I have already created the legality function
and a simple recursive function that generates moves
at a depth chosen at will.

By inserting a simple counting variable I get the following results:
From start position:
ply 1: 20
ply 2: 400
ply 3: 8982
ply 4: 182685

These are the number of positions sought.
The problem is that, I read somewhere that
after 4 ply there are 197742 different lines.
My concern is that some legal move is mistakenly considered illegal.

Anyone know a trick to find the problem?
Or do you know a chess engine that counts all the lines with established depth?

[hgm]

There are many engines, as well as dedicated programs that produce these so-called 'perft' counts. The standard technique to identify errors is to use 'split perft', i.e. split out the total count by move, or even by series of moves. Then you can identify the series of moves (and thus the position) where the error occurs, which usually makes it clear immediately what the error is.

E.g. when you use qperft you can split up to any depth of the tree with a -N argument:

Code: Select all

$ ../../perft/qperft 4 -2
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft( 1)=           20 ( 0.000 sec)
perft( 2)=          400 ( 0.000 sec)
2. h2h3 moves =        380 ( 0.000 sec)
2. h2h4 moves =        420 ( 0.000 sec)
2. g2g3 moves =        420 ( 0.000 sec)
2. g2g4 moves =        421 ( 0.000 sec)
2. f2f3 moves =        380 ( 0.000 sec)
2. f2f4 moves =        401 ( 0.000 sec)
2. e2e3 moves =        599 ( 0.000 sec)
2. e2e4 moves =        600 ( 0.000 sec)
2. d2d3 moves =        539 ( 0.000 sec)
2. d2d4 moves =        560 ( 0.000 sec)
2. c2c3 moves =        420 ( 0.000 sec)
2. c2c4 moves =        441 ( 0.000 sec)
2. b2b3 moves =        420 ( 0.000 sec)
2. b2b4 moves =        421 ( 0.000 sec)
2. a2a3 moves =        380 ( 0.000 sec)
2. a2a4 moves =        420 ( 0.000 sec)
2. g1f3 moves =        440 ( 0.000 sec)
2. g1h3 moves =        400 ( 0.000 sec)
2. b1a3 moves =        400 ( 0.000 sec)
2. b1c3 moves =        440 ( 0.000 sec)
perft( 3)=         8902 ( 0.000 sec)
2. h2h3 moves =       8457 ( 0.000 sec)
2. h2h4 moves =       9329 ( 0.000 sec)
2. g2g3 moves =       9345 ( 0.000 sec)
2. g2g4 moves =       9328 ( 0.000 sec)
2. f2f3 moves =       8457 ( 0.000 sec)
2. f2f4 moves =       8929 ( 0.000 sec)
2. e2e3 moves =      13134 ( 0.000 sec)
2. e2e4 moves =      13160 ( 0.000 sec)
2. d2d3 moves =      11959 ( 0.000 sec)
2. d2d4 moves =      12435 ( 0.000 sec)
2. c2c3 moves =       9272 ( 0.000 sec)
2. c2c4 moves =       9744 ( 0.000 sec)
2. b2b3 moves =       9345 ( 0.000 sec)
2. b2b4 moves =       9332 ( 0.000 sec)
2. a2a3 moves =       8457 ( 0.000 sec)
2. a2a4 moves =       9329 ( 0.000 sec)
2. g1f3 moves =       9748 ( 0.000 sec)
2. g1h3 moves =       8881 ( 0.000 sec)
2. b1a3 moves =       8885 ( 0.000 sec)
2. b1c3 moves =       9755 ( 0.000 sec)
perft( 4)=       197281 ( 0.000 sec)

[zullil]

Your ply 3 is also wrong. Read about perft/divide to debug.

Stockfish can give numbers from a command line, like this:

position fen 1rb2r1k/3p1pp1/p3p2p/1p2P3/4q3/1N2B1R1/PPP1N1P1/2KR1B2 w - - 0 1
go perft 6
a2a3: 48375495
c2c3: 45116632
a2a4: 54745564
c2c4: 47626243
b3a1: 47021849
b3d2: 40586189
b3d4: 35641216
b3a5: 50047864
b3c5: 56853907
e2g1: 57319672
e2c3: 62211301
e2d4: 42187698
e2f4: 54405597
e3g1: 49666893
e3d2: 39869027
e3f2: 52451758
e3d4: 35151424
e3f4: 38516366
e3c5: 57786433
e3g5: 47339817
e3b6: 56017295
e3h6: 43650109
e3a7: 51490876
g3f3: 57481168
g3h3: 60482288
g3g4: 57274241
g3g5: 52797192
g3g6: 52722758
g3g7: 44074135
d1e1: 40262929
d1d2: 46413917
d1d3: 52624870
d1d4: 43478234
d1d5: 49038421
d1d6: 52665461
d1d7: 61343809
c1b1: 60594051
c1d2: 40401983

Nodes searched: 1885734682

[Terje]

https://github.com/TerjeKir/weiss/blob/ ... tsuite.epd

Here's a file with positions and their perft counts up to depth 6. The 3rd is a very good position as it will test most special cases.

[zullil]

https://github.com/TerjeKir/weiss/blob/ ... tsuite.epd

Here's a file with positions and their perft counts up to depth 6. The 3rd is a very good position as it will test most special cases.

[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

./perft
FEN string = r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
Depth = 5
Leaf nodes = 193690690
Time taken = 2415 ms

./perft
FEN string = r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
Depth = 6
Leaf nodes = 8031647685
Time taken = 93828 ms

Looks like my generator is OK on this one.

[MOBMAT]

I've found that most of my mistakes when creating a new move generator is en passant (EP) and castling issues. I would suggest setting up very simple positions that have the scenarios that you want to test. For example, to test EP, set up a position that only has the two kings and one pawn for each side. You can use a GUI such as Arena to set them up, then feed your code the FEN and it should be easy to debug.

Just be sure your FEN to board conversion is working correctly and sets all the appropriate flags for castling and/or EP.

It is very satisfying to get a new move generator working correctly.

[bob]

By FAR, the most common issue revolves around en passant pawn captures. It just happens to take 4 plies + captures from the initial position. IE 1. e4 c5, 2. e5 d5 and now white can capture on d6 en passant. Whenever I see someone that breaks around depth = 4/5, that is always a likely candidate. Next most common deals with pawn promotions.

To debug you need to find a position that produces an error with the smallest number of nodes possible. IE from the starting position, perf is over 170K nodes which is really difficult to deal with. One suggestion is to move forward two plies, and start there. See if Perf 2 is still wrong. MUCH easier to debug that small number of moves.