Perft and en_passant

[Harald]

Hi,

Today I have played with perft after a long absence from chess programming.
I have a problem with

[D]8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -

and the numbers given here: http://chessprogramming.wikispaces.com/Perft+Results

The table gives the numbers for depth 5: 674624 nodes, 52051 captures, 1165 en_passants.
But my numbers are: 674543 nodes, 51970 captures, 1084 en_passants.
I can reproduce the numbers from wikispaces if I deactivate the test if the
king is checked through the captured en_passant pawn, that was 'pinned'.
Which numbers are right?

Here is a part of my logfile with a divided perft.
My perft depth differs by 1 and the mate numbers by another ply.
C=color (0=W, 1=B), P=piece (0=P, N, B, R, Q, K=6), F=from, T=to, (H1=0, A8=63) X=capture, >=promotion.
Sorry, nicer output is on the todo list.

Code: Select all

0089075463: 0000003240: Perft 4
0089075463: 0000003241: Ply   1:   C 0  P 1  F 11  T 19  X 0  > 0
0089075478: 0000006569: Perft divide 4: 45326 nodes, 5417 captures, 73 en_passants, 0 castles, 0 promotions, 3847 checks, 3 checkmates, 0 stalemates
0089075478: 0000006569: Ply   1:   C 0  P 1  F 9  T 17  X 0  > 0
0089075478: 0000007642: Perft divide 4: 14747 nodes, 1545 captures, 19 en_passants, 0 castles, 0 promotions, 880 checks, 0 checkmates, 0 stalemates
0089075478: 0000007642: Ply   1:   C 0  P 1  F 11  T 27  X 0  > 0
0089075494: 0000010584: Perft divide 4: 36889 nodes, 2419 captures, 74 en_passants, 0 castles, 0 promotions, 2600 checks, 2 checkmates, 0 stalemates
0089075494: 0000010584: Ply   1:   C 0  P 1  F 9  T 25  X 0  > 0
0089075510: 0000014530: Perft divide 4: 53895 nodes, 4900 captures, 87 en_passants, 0 castles, 0 promotions, 2070 checks, 3 checkmates, 0 stalemates
0089075510: 0000014530: Ply   1:   C 0  P 4  F 30  T 26  X 1  > 0
0089075510: 0000015180: Perft divide 4: 10774 nodes, 311 captures, 21 en_passants, 0 castles, 0 promotions, 1014 checks, 0 checkmates, 0 stalemates
0089075510: 0000015180: Ply   1:   C 0  P 4  F 30  T 31  X 0  > 0
0089075525: 0000018417: Perft divide 4: 45580 nodes, 3199 captures, 63 en_passants, 0 castles, 0 promotions, 3683 checks, 1 checkmates, 0 stalemates
0089075525: 0000018417: Ply   1:   C 0  P 4  F 30  T 29  X 0  > 0
0089075541: 0000022484: Perft divide 4: 63770 nodes, 6330 captures, 74 en_passants, 0 castles, 0 promotions, 5068 checks, 1 checkmates, 0 stalemates
0089075541: 0000022484: Ply   1:   C 0  P 4  F 30  T 28  X 0  > 0
0089075556: 0000026365: Perft divide 4: 59563 nodes, 5996 captures, 88 en_passants, 0 castles, 0 promotions, 5020 checks, 1 checkmates, 0 stalemates
0089075556: 0000026365: Ply   1:   C 0  P 4  F 30  T 27  X 0  > 0
0089075572: 0000030000: Perft divide 4: 54181 nodes, 4360 captures, 83 en_passants, 0 castles, 0 promotions, 5020 checks, 1 checkmates, 0 stalemates
0089075572: 0000030000: Ply   1:   C 0  P 4  F 30  T 22  X 0  > 0
0089075588: 0000033922: Perft divide 4: 59708 nodes, 2932 captures, 83 en_passants, 0 castles, 0 promotions, 5533 checks, 1 checkmates, 0 stalemates
0089075588: 0000033922: Ply   1:   C 0  P 4  F 30  T 14  X 0  > 0
0089075588: 0000037472: Perft divide 4: 48486 nodes, 2378 captures, 70 en_passants, 0 castles, 0 promotions, 3157 checks, 1 checkmates, 0 stalemates
0089075588: 0000037472: Ply   1:   C 0  P 4  F 30  T 6  X 0  > 0
0089075603: 0000041953: Perft divide 4: 69653 nodes, 2989 captures, 86 en_passants, 0 castles, 0 promotions, 5884 checks, 1 checkmates, 0 stalemates
0089075603: 0000041953: Ply   1:   C 0  P 6  F 39  T 47  X 0  > 0
0089075619: 0000045862: Perft divide 4: 59028 nodes, 4840 captures, 136 en_passants, 0 castles, 0 promotions, 4784 checks, 1 checkmates, 0 stalemates
0089075619: 0000045862: Ply   1:   C 0  P 6  F 39  T 31  X 0  > 0
0089075634: 0000049496: Perft divide 4: 52943 nodes, 4354 captures, 127 en_passants, 0 castles, 0 promotions, 4390 checks, 1 checkmates, 0 stalemates
0089075634: 0000049496: Perft 4: 674543 nodes, 51970 captures, 1084 en_passants, 0 castles, 0 promotions, 52950 checks, 17 checkmates, 0 stalemates
0089075634: 0000049496: Time 171 ms, 3944695 nps

The logfile with wikispace numbers is:

Code: Select all

0089206145: 0000003240: Perft 4
0089206145: 0000003241: Ply   1:   C 0  P 1  F 11  T 19  X 0  > 0
0089206160: 0000006569: Perft divide 4: 45326 nodes, 5417 captures, 73 en_passants, 0 castles, 0 promotions, 3847 checks, 3 checkmates, 0 stalemates
0089206160: 0000006569: Ply   1:   C 0  P 1  F 9  T 17  X 0  > 0
0089206160: 0000007642: Perft divide 4: 14747 nodes, 1545 captures, 19 en_passants, 0 castles, 0 promotions, 880 checks, 0 checkmates, 0 stalemates
0089206160: 0000007642: Ply   1:   C 0  P 1  F 11  T 27  X 0  > 0
0089206176: 0000010584: Perft divide 4: 36889 nodes, 2419 captures, 74 en_passants, 0 castles, 0 promotions, 2600 checks, 2 checkmates, 0 stalemates
0089206176: 0000010584: Ply   1:   C 0  P 1  F 9  T 25  X 0  > 0
0089206176: 0000014530: Perft divide 4: 53895 nodes, 4900 captures, 87 en_passants, 0 castles, 0 promotions, 2070 checks, 3 checkmates, 0 stalemates
0089206176: 0000014530: Ply   1:   C 0  P 4  F 30  T 26  X 1  > 0
0089206192: 0000015180: Perft divide 4: 10776 nodes, 313 captures, 23 en_passants, 0 castles, 0 promotions, 1014 checks, 0 checkmates, 0 stalemates
0089206192: 0000015180: Ply   1:   C 0  P 4  F 30  T 31  X 0  > 0
0089206192: 0000018417: Perft divide 4: 45591 nodes, 3210 captures, 74 en_passants, 0 castles, 0 promotions, 3683 checks, 1 checkmates, 0 stalemates
0089206192: 0000018417: Ply   1:   C 0  P 4  F 30  T 29  X 0  > 0
0089206207: 0000022484: Perft divide 4: 63781 nodes, 6341 captures, 85 en_passants, 0 castles, 0 promotions, 5068 checks, 1 checkmates, 0 stalemates
0089206207: 0000022484: Ply   1:   C 0  P 4  F 30  T 28  X 0  > 0
0089206223: 0000026365: Perft divide 4: 59574 nodes, 6007 captures, 99 en_passants, 0 castles, 0 promotions, 5020 checks, 1 checkmates, 0 stalemates
0089206223: 0000026365: Ply   1:   C 0  P 4  F 30  T 27  X 0  > 0
0089206238: 0000030000: Perft divide 4: 54192 nodes, 4371 captures, 94 en_passants, 0 castles, 0 promotions, 5020 checks, 1 checkmates, 0 stalemates
0089206238: 0000030000: Ply   1:   C 0  P 4  F 30  T 22  X 0  > 0
0089206254: 0000033922: Perft divide 4: 59719 nodes, 2943 captures, 94 en_passants, 0 castles, 0 promotions, 5533 checks, 1 checkmates, 0 stalemates
0089206254: 0000033922: Ply   1:   C 0  P 4  F 30  T 14  X 0  > 0
0089206270: 0000037472: Perft divide 4: 48498 nodes, 2390 captures, 82 en_passants, 0 castles, 0 promotions, 3157 checks, 1 checkmates, 0 stalemates
0089206270: 0000037472: Ply   1:   C 0  P 4  F 30  T 6  X 0  > 0
0089206285: 0000041953: Perft divide 4: 69665 nodes, 3001 captures, 98 en_passants, 0 castles, 0 promotions, 5884 checks, 1 checkmates, 0 stalemates
0089206285: 0000041953: Ply   1:   C 0  P 6  F 39  T 47  X 0  > 0
0089206301: 0000045862: Perft divide 4: 59028 nodes, 4840 captures, 136 en_passants, 0 castles, 0 promotions, 4784 checks, 1 checkmates, 0 stalemates
0089206301: 0000045862: Ply   1:   C 0  P 6  F 39  T 31  X 0  > 0
0089206301: 0000049496: Perft divide 4: 52943 nodes, 4354 captures, 127 en_passants, 0 castles, 0 promotions, 4390 checks, 1 checkmates, 0 stalemates
0089206316: 0000049496: Perft 4: 674624 nodes, 52051 captures, 1165 en_passants, 0 castles, 0 promotions, 52950 checks, 17 checkmates, 0 stalemates
0089206316: 0000049496: Time 156 ms, 4324512 nps

Harald

[Dan Honeycutt]

Hi Harald,

I get 674624 but I don't break it out by capture:

Code: Select all

Cupcake_11b
Error in ini file: Cupcake.ini (The system cannot find the file specified)
16 mb hash table
fen=8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1
depth              perft       time
  1/5                 14 0:00:00.00
  2/5                191 0:00:00.00
  3/5               2812 0:00:00.00
  4/5              43238 0:00:00.04
  5/5             674624 0:00:00.12
moves/second = 5866295

Here are the individual moves:

Code: Select all

e2e3 45326
g2g3 14747
e2e4 36889
g2g4 53895
a5a4 52943
a5a6 59028
b4a4 45591
b4b1 69665
b4b2 48498
b4b3 59719
b4c4 63781
b4d4 59574
b4e4 54192
b4f4 10776

Best
Dan H.

[tpetzke]

Hi,

the wiki numbers are correct. I remember also that my engine has failed that perft initially. Here are the perft numbers and also a divide of the single moves.

perft 5
perft Nodes Time
1 14 0 sec
2 191 0 sec
3 2.812 0 sec
4 43.238 0 sec
5 674.624 0.094 sec

divide 5
Ka5 a4 : 52.943
Ka5 a6 : 59.028
e2 e3 : 45.326
g2 g3 : 14.747
e2 e4 : 36.889
g2 g4 : 53.895
Rb4 b1 : 69.665
Rb4 b2 : 48.498
Rb4 b3 : 59.719
Rb4 a4 : 45.591
Rb4 c4 : 63.781
Rb4 d4 : 59.574
Rb4 e4 : 54.192
Rb4xf4 : 10.776
Total Nodes of 14 moves : 674.624, Time : 0.078 sec

My problem was the pin detection as after the ep capture two pieces are removed at once from a rank. A case I did not take care of.

Thomas...

[JVMerlino]

Hi Harald,

The numbers on wikispaces are correct. Clearly you are missing 81 en-passant captures somewhere, and I'm sure you've figured out that all of them are distributed among the branches created by an initial rook move.

The best way to solve these is to force any one of the rook moves and then use the divide command again with one less depth. It should be easy to narrow down the problem.

jm

[Ajedrecista]

Hello Harald:

Sorry for this extremely long post. I can not say anything about captures and en-passant captures. But I can provide the correct numbers of perft using JetChess 1.0.0.0. You can try to debug your perft because I give you divided results:

[d]8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -

Using 64 MB of hash:

Code: Select all

Total:               14

14 (move pathes after 1 half move).

Time: 0 ms (0:00:00.000).

Code: Select all

  1  Rb4-c4          15
  2  Rb4-d4          15
  3  Rb4-e4          15
  4  Rb4*f4           2
  5  Rb4-a4          15
  6  Rb4-b3          15
  7  Rb4-b2          16
  8  Rb4-b1          16
  9   e2-e3          15
 10   e2-e4          16
 11   g2-g3           4
 12   g2-g4          17
 13  Ka5-a6          15
 14  Ka5-a4          15

Total:              191

191 (move pathes after 2 half moves).

Time: 0 ms (0:00:00.000).

Code: Select all

  1  Rb4-c4         254
  2  Rb4-d4         243
  3  Rb4-e4         228
  4  Rb4*f4          41
  5  Rb4-a4         202
  6  Rb4-b3         248
  7  Rb4-b2         205
  8  Rb4-b1         265
  9   e2-e3         205
 10   e2-e4         177
 11   g2-g3          54
 12   g2-g4         226
 13  Ka5-a6         240
 14  Ka5-a4         224

Total:             2812

2,812 (move pathes after 3 half moves).

Time: 0 ms (0:00:00.000).

Code: Select all

  1  Rb4-c4        3797
  2  Rb4-d4        3622
  3  Rb4-e4        3391
  4  Rb4*f4         606
  5  Rb4-a4        3019
  6  Rb4-b3        3658
  7  Rb4-b2        3328
  8  Rb4-b1        4199
  9   e2-e3        3107
 10   e2-e4        2748
 11   g2-g3        1014
 12   g2-g4        3702
 13  Ka5-a6        3653
 14  Ka5-a4        3394

Total:            43238

43,238 (move pathes after 4 half moves).

Time: 1 ms (0:00:00.001).

Code: Select all

  1  Rb4-c4       63781
  2  Rb4-d4       59574
  3  Rb4-e4       54192
  4  Rb4*f4       10776
  5  Rb4-a4       45591
  6  Rb4-b3       59719
  7  Rb4-b2       48498
  8  Rb4-b1       69665
  9   e2-e3       45326
 10   e2-e4       36889
 11   g2-g3       14747
 12   g2-g4       53895
 13  Ka5-a6       59028
 14  Ka5-a4       52943

Total:           674624

674,624 (move pathes after 5 half moves).

Time: 11 ms (0:00:00.011).

Code: Select all

  1  Rb4-c4     1027199
  2  Rb4-d4      957108
  3  Rb4-e4      860971
  4  Rb4*f4      174919
  5  Rb4-a4      745667
  6  Rb4-b3      941129
  7  Rb4-b2      818501
  8  Rb4-b1     1160678
  9   e2-e3      745505
 10   e2-e4      597519
 11   g2-g3      271220
 12   g2-g4      892781
 13  Ka5-a6      968724
 14  Ka5-a4      868162

Total:         11030083

11,030,083 (move pathes after 6 half moves).

Time: 104 ms (0:00:00.104).

Code: Select all

  1  Rb4-c4    17400108
  2  Rb4-d4    15996777
  3  Rb4-e4    14187097
  4  Rb4*f4     3069955
  5  Rb4-a4    11996400
  6  Rb4-b3    15482610
  7  Rb4-b2    12755330
  8  Rb4-b1    19481757
  9   e2-e3    11427551
 10   e2-e4     8853383
 11   g2-g3     4190119
 12   g2-g4    13629805
 13  Ka5-a6    16022983
 14  Ka5-a4    14139786

Total:        178633661

178,633,661 (move pathes after 7 half moves).

Time: 670 ms (0:00:00.670).

------------------------

Using 256 MB of hash:

Code: Select all

  1  Rb4-c4   289779152
  2  Rb4-d4   266036026
  3  Rb4-e4   232884804
  4  Rb4*f4    50536497
  5  Rb4-a4   203399342
  6  Rb4-b3   255227951
  7  Rb4-b2   220200673
  8  Rb4-b1   334490114
  9   e2-e3   193737630
 10   e2-e4   147565227
 11   g2-g3    76036362
 12   g2-g4   229512485
 13  Ka5-a6   270960314
 14  Ka5-a4   239427816

Total:       3009794393

3,009,794,393 (move pathes after 8 half moves).

Time: 4.694 s (0:00:04.694).

Code: Select all

  1  Rb4-c4  4966212754
  2  Rb4-d4  4521736449
  3  Rb4-e4  3920504030
  4  Rb4*f4   885894814
  5  Rb4-a4  3399463489
  6  Rb4-b3  4258569600
  7  Rb4-b2  3576462883
  8  Rb4-b1  5688812201
  9   e2-e3  3087382842
 10   e2-e4  2321736882
 11   g2-g3  1220138764
 12   g2-g4  3628220761
 13  Ka5-a6  4580161609
 14  Ka5-a4  4031452737

Total:      50086749815

50,086,749,815 (move pathes after 9 half moves).

Time: 25.585 s (0:00:25.585).

------------------------

Using 1 GB of hash:

Code: Select all

  1  Rb4-c4  84426671210
  2  Rb4-d4  76806392133
  3  Rb4-e4  65752177844
  4  Rb4*f4  14697335274
  5  Rb4-a4  58844057449
  6  Rb4-b3  72444943767
  7  Rb4-b2  62742842587
  8  Rb4-b1  99664021346
  9   e2-e3  53139628960
 10   e2-e4  39545420719
 11   g2-g3  22000709906
 12   g2-g4  62054876516
 13  Ka5-a6  78703269883
 14  Ka5-a4  69500254715

Total:      860322602309

860,322,602,309 (move pathes after 10 half moves).

Time: 142.680 s (0:02:22.680).

Code: Select all

  1  Rb4-c4  1463151281937
  2  Rb4-d4  1324944943461
  3  Rb4-e4  1126470725027
  4  Rb4*f4   258287648492
  5  Rb4-a4  1008655489960
  6  Rb4-b3  1228179918985
  7  Rb4-b2  1049413031768
  8  Rb4-b1  1716821664250
  9   e2-e3   872169979347
 10   e2-e4   646956903053
 11   g2-g3   362361958827
 12   g2-g4  1007073431028
 13  Ka5-a6  1355148667403
 14  Ka5-a4  1201827680136

Total:      14621463323674

14,621,463,323,674 (move pathes after 11 half moves).

Time: 777.324 s (0:12:57.324).

I seriously recommend you (and everybody) JetChess when you have doubts about perft() and/or divide(); one warning: always input the castling rights in FEN string in alphabetic order to JetChess. I mean, you must use KQkq instead of QKqk (the last choice will produce wrong numbers due to a small bug in FEN parsing). Good luck fixing your bug!

Regards from Spain.

Ajedrecista.

[Daniel Shawul]

Which numbers are right?

The nerve ! Ofcourse wiki.

[Harald]

Thank you all. I found the error. And of course the wiki is right.

I really did the test of pins through the moved and captured pawns.
But I did not remove the ep captured pawns from one of the bitboards
in a temporary test in the move generator. Then I used a generic attack
function to avoid problems with complicated ep moves. This function
saw a king in check by the ghostly pawn.

Harald