REPORT: wrong perft result by qperft.

[Ajedrecista]

Hello:

There, bug found and corrected. Now Prédateur agrees with JetChess too. It's quite astonishing to find a bug in the move generation when I thought it was bug free for years!

Maybe I should tell what the bug was, in case someone else has the same problem in his engine?

After going deeper into the tree to see where the node count was starting to diverge, I noticed that when the e pawn was promoted to a rook and that this rook was later captured by the black queen then Prédateur wouldn't consider castling on the king side anymore. So I looked into my MakeMove routine and found a bug there (in pseudocode):

Code: Select all

if (Capture) and (CapturedPiece.type = rook) then begin
  if (Board[to_square] = WhiteRook1) then WhiteQueenCastle := false
  else WhiteKingCastle := false; // This is where the bug is!!!
end;

The commented line is where the bug was: I falsely assumed that the captured rook would be the other one on the starting position board (WhiteRook2), while this rook was actually WhitePawn5 turned into a rook, which wrongly triggered the loss of the king-side castling flag.

The correct pseudo-code is:

Code: Select all

if (Capture) and (CapturedPiece.type = rook) then begin
  if (Board[to_square] = WhiteRook1) then WhiteQueenCastle := false
  else if (Board[to_square] = WhiteRook2) then  WhiteKingCastle := false;
end;

So the missing 1520 moves out of 94 billions were all the king-side castles moves lost that way.

So this position was very interesting because it was a position where:
1- the game is early so the king still hasn't castled but can still do it on both sides;
2- still, a pawn is ready to get promoted.

As the perft procedure up to a depth 7 in this position takes some time, here is a more handy position (a few plies later in the tree) that still matches those two criteria above:

[d]rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8
(Here, a perft 3 is sufficient to detect the class of bugs described above)

Is your perft (with hash) having problems with this position too, HG?

Thanks again for this position, Jesús!

In the second diagram that I posted in the starting post of this topic, I forgot the castling rights (KQkq) in FEN string. The same happened to me at first when running Critter 1.4, until I discovered that I forgot KQkq in FEN. So, Critter results are good in that post, but not the FEN of the second diagram.

Now, trying this position:

[d]rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8

Code: Select all

i-perft -divide 3 "rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8"

i-perft 1.0 (c) 2006-2008 AJ Siemelink


   +---+---+---+---+---+---+---+---+
 8 |*r*|*n*|*b*|*q*|   |*k*|   |*r*|
   +---+---+---+---+---+---+---+---+
 7 |*p*|*p*|   |(P)|*b*|*p*|*p*|*p*|
   +---+---+---+---+---+---+---+---+
 6 |   |   |*p*|   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 5 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 4 |   |   |(B)|   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 3 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 2 |(P)|(P)|(P)|   |(N)|*n*|(P)|(P)|
   +---+---+---+---+---+---+---+---+
 1 |(R)|(N)|(B)|(Q)|(K)|   |   |(R)|
   +---+---+---+---+---+---+---+---+
     a   b   c   d   e   f   g   h

--divide--------------
Ke1g1            1376
d7xc8=Q          1432
d7xc8=N          1573
d7xc8=R          1269
d7xc8=B          1634
a2a3             1344
a2a4             1404
b2b3             1339
b2b4             1369
c2c3             1409
g2g3             1279
g2g4             1308
h2h3             1342
h2h4             1373
Ne2g1            1431
Ne2c3            1564
Ne2g3            1494
Ne2d4            1525
Ne2f4            1526
Nb1d2            1143
Nb1a3            1274
Nb1c3            1436
Bc4b5            1303
Bc4a6            1228
Bc4d5            1345
Bc4e6            1408
Bc4xf7           1301
Bc4d3            1240
Bc4b3            1246
Bc1d2            1337
Bc1e3            1558
Bc1f4            1523
Bc1g5            1395
Bc1h6            1286
Rh1g1            1311
Rh1f1            1364
Qd1d2            1405
Qd1d3            1656
Qd1d4            1722
Qd1d5            1658
Qd1d6            1476
Ke1f1            1445
Ke1xf2           1269
Ke1d2             978
----------------------
total           61298  (0.03 seconds)

i-perft 1.0 does not count well even in Perft(3).

Code: Select all

frcperft-win32

frcperft 1.0, (C) 2008-2011 AJ Siemelink
single threaded, no hashing, mode=FAST, extract=BSF32, count=LOOP

   +---+---+---+---+---+---+---+---+
 8 |*r*|*n*|*b*|*q*|*k*|*b*|*n*|*r*|
   +---+---+---+---+---+---+---+---+
 7 |*p*|*p*|*p*|*p*|*p*|*p*|*p*|*p*|
   +---+---+---+---+---+---+---+---+
 6 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 5 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 4 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 3 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 2 |(P)|(P)|(P)|(P)|(P)|(P)|(P)|(P)|
   +---+---+---+---+---+---+---+---+
 1 |(R)|(N)|(B)|(Q)|(K)|(B)|(N)|(R)|
   +---+---+---+---+---+---+---+---+
     a   b   c   d   e   f   g   h

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
interactive mode, type 'help'+Enter for help
% fen rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8

   +---+---+---+---+---+---+---+---+
 8 |*r*|*n*|*b*|*q*|   |*k*|   |*r*|
   +---+---+---+---+---+---+---+---+
 7 |*p*|*p*|   |(P)|*b*|*p*|*p*|*p*|
   +---+---+---+---+---+---+---+---+
 6 |   |   |*p*|   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 5 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 4 |   |   |(B)|   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 3 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 2 |(P)|(P)|(P)|   |(N)|*n*|(P)|(P)|
   +---+---+---+---+---+---+---+---+
 1 |(R)|(N)|(B)|(Q)|(K)|   |   |(R)|
   +---+---+---+---+---+---+---+---+
     a   b   c   d   e   f   g   h

rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 1
% divide 3
O-O            1376
dxc8=Q         1459
dxc8=N         1607
dxc8=B         1668
dxc8=R         1296
a4             1433
b4             1398
g4             1337
h4             1402
a3             1373
b3             1368
c3             1440
g3             1308
h3             1371
Nd2            1174
Na3            1303
Nbc3           1467
Ng1            1431
Nec3           1595
Ng3            1523
Nd4            1554
Nf4            1555
Bd2            1368
Be3            1587
Bf4            1552
Bg5            1422
Bh6            1312
Bb3            1275
Bd3            1269
Bb5            1332
Bd5            1375
Ba6            1256
Be6            1438
Bxf7           1328
Qd2            1436
Qd3            1685
Qd4            1751
Qd5            1688
Qd6            1500
Rf1            1364
Rg1            1311
Kf1            1445
Kd2             978
Kxf2           1269
-------------------
total         62379
%

Good work of frcperft 1.0.

Code: Select all

qperft 3 "-2" "rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8"
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q . k . r - -
 - - p p . P b p p p - -
 - - . . p . . . . . - -
 - - . . . . . . . . - -
 - - . . B . . . . . - -
 - - . . . . . . . . - -
 - - P P P . N n P P - -
 - - R N B Q K . . R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

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

2. e1g1 moves =       1376 ( 0.000 sec)
2. h2h3 moves =       1371 ( 0.000 sec)
2. h2h4 moves =       1402 ( 0.000 sec)
2. g2g3 moves =       1308 ( 0.000 sec)
2. g2g4 moves =       1337 ( 0.000 sec)
2. c2c3 moves =       1440 ( 0.000 sec)
2. b2b3 moves =       1368 ( 0.000 sec)
2. b2b4 moves =       1398 ( 0.000 sec)
2. a2a3 moves =       1373 ( 0.000 sec)
2. a2a4 moves =       1433 ( 0.016 sec)
2. d7c8 moves =       1459 ( 0.000 sec)
2. d7c8 moves =       1296 ( 0.000 sec)
2. d7c8 moves =       1668 ( 0.000 sec)
2. d7c8 moves =       1607 ( 0.000 sec)
2. b1a3 moves =       1303 ( 0.000 sec)
2. b1c3 moves =       1467 ( 0.000 sec)
2. b1d2 moves =       1174 ( 0.000 sec)
2. e2c3 moves =       1595 ( 0.000 sec)
2. e2d4 moves =       1554 ( 0.000 sec)
2. e2f4 moves =       1555 ( 0.000 sec)
2. e2g3 moves =       1523 ( 0.000 sec)
2. e2g1 moves =       1431 ( 0.000 sec)
2. c4b5 moves =       1332 ( 0.000 sec)
2. c4a6 moves =       1256 ( 0.000 sec)
2. c4d3 moves =       1269 ( 0.000 sec)
2. c4d5 moves =       1375 ( 0.000 sec)
2. c4e6 moves =       1438 ( 0.000 sec)
2. c4f7 moves =       1328 ( 0.000 sec)
2. c4b3 moves =       1275 ( 0.000 sec)
2. c1d2 moves =       1368 ( 0.000 sec)
2. c1e3 moves =       1587 ( 0.000 sec)
2. c1f4 moves =       1552 ( 0.000 sec)
2. c1g5 moves =       1422 ( 0.000 sec)
2. c1h6 moves =       1312 ( 0.000 sec)
2. d1d2 moves =       1436 ( 0.000 sec)
2. d1d3 moves =       1685 ( 0.000 sec)
2. d1d4 moves =       1751 ( 0.000 sec)
2. d1d5 moves =       1688 ( 0.000 sec)
2. d1d6 moves =       1500 ( 0.000 sec)
2. h1g1 moves =       1311 ( 0.000 sec)
2. h1f1 moves =       1364 ( 0.000 sec)
2. e1f1 moves =       1445 ( 0.000 sec)
2. e1f2 moves =       1269 ( 0.000 sec)
2. e1d2 moves =        978 ( 0.000 sec)
perft( 3)=        62379 ( 0.016 sec)

qperft (without hash) is perfect in this position.

Code: Select all

qperft 3 "H20" "-2" "rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8"
Hash-table size = fffff, Starts at 4f0040,section = 1ffff
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q . k . r - -
 - - p p . P b p p p - -
 - - . . p . . . . . - -
 - - . . . . . . . . - -
 - - . . B . . . . . - -
 - - . . . . . . . . - -
 - - P P P . N n P P - -
 - - R N B Q K . . R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: Hash-table size = 16MB, bulk counting in horizon nodes

2. e1g1 moves =       1376 ( 0.015 sec)
2. h2h3 moves =       1371 ( 0.000 sec)
2. h2h4 moves =       1402 ( 0.000 sec)
2. g2g3 moves =       1308 ( 0.000 sec)
2. g2g4 moves =       1337 ( 0.000 sec)
2. c2c3 moves =       1440 ( 0.000 sec)
2. b2b3 moves =       1368 ( 0.000 sec)
2. b2b4 moves =       1398 ( 0.000 sec)
2. a2a3 moves =       1373 ( 0.000 sec)
2. a2a4 moves =       1433 ( 0.000 sec)
2. d7c8 moves =       1459 ( 0.000 sec)
2. d7c8 moves =       1296 ( 0.000 sec)
2. d7c8 moves =       1621 ( 0.000 sec)
2. d7c8 moves =       1621 ( 0.000 sec)
2. b1a3 moves =       1303 ( 0.000 sec)
2. b1c3 moves =       1467 ( 0.000 sec)
2. b1d2 moves =       1174 ( 0.000 sec)
2. e2c3 moves =       1595 ( 0.000 sec)
2. e2d4 moves =       1554 ( 0.000 sec)
2. e2f4 moves =       1555 ( 0.000 sec)
2. e2g3 moves =       1523 ( 0.000 sec)
2. e2g1 moves =       1431 ( 0.000 sec)
2. c4b5 moves =       1332 ( 0.000 sec)
2. c4a6 moves =       1256 ( 0.000 sec)
2. c4d3 moves =       1269 ( 0.000 sec)
2. c4d5 moves =       1375 ( 0.000 sec)
2. c4e6 moves =       1438 ( 0.000 sec)
2. c4f7 moves =       1328 ( 0.000 sec)
2. c4b3 moves =       1275 ( 0.000 sec)
2. c1d2 moves =       1368 ( 0.000 sec)
2. c1e3 moves =       1587 ( 0.000 sec)
2. c1f4 moves =       1552 ( 0.000 sec)
2. c1g5 moves =       1422 ( 0.000 sec)
2. c1h6 moves =       1312 ( 0.000 sec)
2. d1d2 moves =       1436 ( 0.000 sec)
2. d1d3 moves =       1685 ( 0.000 sec)
2. d1d4 moves =       1751 ( 0.000 sec)
2. d1d5 moves =       1688 ( 0.000 sec)
2. d1d6 moves =       1500 ( 0.000 sec)
2. h1g1 moves =       1311 ( 0.000 sec)
2. h1f1 moves =       1364 ( 0.000 sec)
2. e1f1 moves =       1445 ( 0.000 sec)
2. e1f2 moves =       1269 ( 0.000 sec)
2. e1d2 moves =        978 ( 0.000 sec)
perft( 3)=        62346 ( 0.015 sec)

Problems appeared when the hash is used in qperft. Thanks to Muller for detecting where the bug was. Good luck when fixing it!

Code: Select all

JetChess 1.0.0.0 (64 MB of hash):

rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8

  1  Qd1-d2        1436
  2  Qd1-d3        1685
  3  Qd1-d4        1751
  4  Qd1-d5        1688
  5  Qd1-d6        1500
  6  Rh1-g1        1311
  7  Rh1-f1        1364
  8  Bc1-d2        1368
  9  Bc1-e3        1587
 10  Bc1-f4        1552
 11  Bc1-g5        1422
 12  Bc1-h6        1312
 13  Bc4-b5        1332
 14  Bc4-a6        1256
 15  Bc4-d5        1375
 16  Bc4-e6        1438
 17  Bc4*f7        1328
 18  Bc4-d3        1269
 19  Bc4-b3        1275
 20  Nb1-a3        1303
 21  Nb1-c3        1467
 22  Nb1-d2        1174
 23  Ne2-c3        1595
 24  Ne2-d4        1554
 25  Ne2-f4        1555
 26  Ne2-g3        1523
 27  Ne2-g1        1431
 28   a2-a3        1373
 29   a2-a4        1433
 30   b2-b3        1368
 31   b2-b4        1398
 32   c2-c3        1440
 33   g2-g3        1308
 34   g2-g4        1337
 35   h2-h3        1371
 36   h2-h4        1402
 37   d7*c8Q       1459
 38   d7*c8N       1607
 39   d7*c8R       1296
 40   d7*c8B       1668
 41     0-0        1376
 42  Ke1-f1        1445
 43  Ke1-d2         978
 44  Ke1*f2        1269

Total:            62379

62,379 (move pathes after 3 half moves).

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

JetChess is right once again.

Code: Select all

OliPerft -3 "rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8"
 r n b q . k . r
 p p . P b p p p
 . . p . . . . .
 . . . . . . . .
 . . B . . . . .
 . . . . . . . .
 P P P . N n P P
 R N B Q K . . R

Ke1xf2: 1269
Ke1-f1: 1445
Ke1-d2: 978
Pa2-a3: 1373
Pa2-a4: 1433
Pb2-b3: 1368
Pb2-b4: 1398
Pc2-c3: 1440
Pg2-g3: 1308
Pg2-g4: 1337
Ph2-h3: 1371
Ph2-h4: 1402
Pd7xc8q: 1459
Pd7xc8n: 1607
Pd7xc8r: 1296
Pd7xc8b: 1668
Nb1-d2: 1174
Nb1-a3: 1303
Nb1-c3: 1467
Ne2-g1: 1431
Ne2-c3: 1595
Ne2-g3: 1523
Ne2-d4: 1554
Ne2-f4: 1555
Rh1-f1: 1364
Rh1-g1: 1311
Ke1-g1: 1376
Bc1-d2: 1368
Bc1-e3: 1587
Bc1-f4: 1552
Bc1-g5: 1422
Bc1-h6: 1312
Bc4xf7: 1328
Bc4-b3: 1275
Bc4-d3: 1269
Bc4-b5: 1332
Bc4-d5: 1375
Bc4-a6: 1256
Bc4-e6: 1438
Qd1-d2: 1436
Qd1-d3: 1685
Qd1-d4: 1751
Qd1-d5: 1688
Qd1-d6: 1500

Nodes: 62379 cs: 0 knps: 62379

No problems for OliPerft 1.01.

Code: Select all

FireBird 1.1 w32
by Kranium and Sentinel
based on IppoLit
Compiled by KLO
Feb 15 2010 11:59:18

position fen rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8
perft 3
      +---+---+---+---+---+---+---+---+
   8  |<R>|<N>|<B>|<Q>|   |<K>|   |<R>|
      +---+---+---+---+---+---+---+---+
   7  |<P>|<P>| . | P |<B>|<P>|<P>|<P>|
      +---+---+---+---+---+---+---+---+
   6  |   | . |<P>| . |   | . |   | . |
      +---+---+---+---+---+---+---+---+
   5  | . |   | . |   | . |   | . |   |
      +---+---+---+---+---+---+---+---+
   4  |   | . | B | . |   | . |   | . |
      +---+---+---+---+---+---+---+---+
   3  | . |   | . |   | . |   | . |   |
      +---+---+---+---+---+---+---+---+
   2  | P | P | P | . | N |<N>| P | P |
      +---+---+---+---+---+---+---+---+
   1  | R | N | B | Q | K |   | . | R |
      +---+---+---+---+---+---+---+---+
        a   b   c   d   e   f   g   h
rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 0
c4f7 1328/32
e1f2 1269/28
d7c8q 1459/31
e1g1 1376/34
a2a4 1433/34
a2a3 1373/34
b2b4 1398/33
b2b3 1368/34
c2c3 1440/34
g2g4 1337/34
g2g3 1308/34
h2h4 1402/34
h2h3 1371/34
d1d2 1436/34
d1d3 1685/34
d1d4 1751/34
d1d5 1688/35
d1d6 1500/28
h1f1 1364/34
h1g1 1311/34
c1d2 1368/34
c1e3 1587/34
c1f4 1552/34
c1g5 1422/32
c1h6 1312/31
c4b3 1275/34
c4d3 1269/34
c4b5 1332/34
c4d5 1375/35
c4a6 1256/33
c4e6 1438/35
e1f1 1445/34
e1d2 978/34
b1d2 1174/34
b1a3 1303/34
b1c3 1467/34
e2g1 1431/34
e2c3 1595/34
e2g3 1523/34
e2d4 1554/34
e2f4 1555/34
d7c8n 1607/41
d7c8r 1296/31
d7c8b 1668/41
TOTAL 62379  moves 44  time&#58; 47000 us

FireBird 1.1 is right.

Thanks to Julien for providing a position where low plies are enough to see the differences in perft. I suppose that this issue in move generation is not worth a new bugfix version of Prédateur (2.2.2, 2.2.1.1, 2.2.1a...).

When I tested the original position (Perft(7)), I expected that it will be a tricky one due to white castle kingside; I could not expect that the problems will be in black side! Curious...

Just trying to help a little: the order of promotions in qperft is {Q, R, B, N} or {Q, R, N, B} (I suppose the first), but it will be good that Muller could specify it in the output (for example: d7c8q, d7c8r, ...). The only errors are in bishop and knight underpromotions when hash is used in this Perft(3) test.

Congrats to the people that posted here (their results were right, good job!). Also thanks for pointing out the problem: the hash issue.

@Muller: Thank you very much for qperft: it is my second favourite public available dedicated perft programme (after JetChess) due to its speed and the posibility of using hash, which speeds up the run. Good job!

@Julien: I am glad that I have contributed in a modest way to fix your almost perfect move generator. I agree with you: some positions of this topic should be added to any wiki because they will be surely useful for newbie programmers that are starting their move generators. Congratulations and good luck being moderator.

Regards from Spain.

Ajedrecista.

[hMx]

Symbolic says:
[d]rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6[/d]

Code: Select all

[] sf rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6
[] emptran 7
...
Depth: 7   Count: 94,854,874,131   Elapsed: 66.0535  (1.43603e+09 Hz / 6.96364e-10 s)

Chest agrees:

Code: Select all

Time (user) = 2449.68 sec (40.8 min)
dep          #nodes     quot        sum nodes
  0               1 [  0.000]               1
  1              42 [ 42.000]              43
  2            1352 [ 32.190]            1395
  3           53392 [ 39.491]           54787
  4         1761505 [ 32.992]         1816292
  5        70202861 [ 39.854]        72019153
  6      2362704901 [ 33.655]      2434724054
  7     94854874131 [ 40.147]     97289598185

Cheers!

[lucasart]

Symbolic says:
[d]rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6[/d]

Code: Select all

[] sf rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6
[] emptran 7
Bb3 1,816,240,296
Bd2 2,107,363,662
Ba6 1,855,061,374
Bb5 2,130,713,616
Bd3 1,886,965,922
Bd5 2,046,941,872
Be6 2,444,185,312
Be3 3,184,524,390
Bxf7+ 86,568,355
Bf4 2,482,656,228
Bg5 2,400,385,594
Kd2 1,152,858,513
Bh6 2,344,263,758
Kxf2 1,701,268,892
Na3 2,002,068,159
Kf1 2,483,161,986
Nbc3 2,655,487,727
Nd2 1,435,627,351
Nd4 3,061,284,388
Nec3 3,057,530,890
Ng1 2,354,927,176
Nf4 2,949,871,106
Ng3 2,865,273,204
O-O 2,291,266,832
Qd2 2,481,769,422
Qd3 3,719,739,001
Qxd7+ 207,937,563
Qd5 2,815,305,249
Qd4 3,598,056,747
Qd6 2,314,600,161
Rg1 1,983,977,646
Rf1 2,220,729,699
a3 2,245,837,704
b3 2,166,557,328
a4 2,548,648,372
b4 2,263,311,424
c3 2,411,002,727
g3 1,981,011,243
e6 2,461,806,026
h3 2,217,212,927
g4 2,033,046,400
h4 2,387,827,889
Depth: 7   Count: 94,854,874,131   Elapsed: 66.0535  (1.43603e+09 Hz / 6.96364e-10 s)

woaw your code is very fast
it took doublecheck 645 sec with 1gb hash
a very useful test for me. i implemented a hash perft and a normal one. verified equality on few positions but .on hash could never reach such astronomic numbers qjickly. i wanted to be sure my hashing was correct. good news it works

[sje]

To draft 8:

Code: Select all

[] emptran 8
[] sf rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6 
Bb3 62,390,421,333
Bd2 73,815,836,545
Ba6 63,840,917,367
Bb5 73,861,828,455
Bd5 70,615,162,877
Bd3 66,835,913,640
Be6 83,780,119,769
Be3 109,165,077,092
Bxf7+ 2,566,822,408
Bf4 85,213,137,562
Bg5 79,559,611,949
Kd2 40,165,708,509
Bh6 79,210,844,684
Kxf2 50,921,898,957
Kf1 86,847,755,314
Na3 68,733,983,884
Nbc3 91,528,042,446
Nd2 50,539,682,793
Nd4 105,838,273,247
Nec3 105,282,152,818
Ng1 80,984,415,079
Nf4 100,863,022,365
O-O 79,190,258,398
Ng3 97,926,711,928
Qd2 85,309,191,157
Qd3 127,891,776,553
Qxd7+ 7,891,308,529
Qd5 93,643,991,874
Qd6 71,721,175,729
Qd4 122,410,358,073
Rg1 68,226,602,049
Rf1 75,451,133,714
a3 77,459,484,626
b3 74,622,488,189
a4 87,949,986,970
c3 83,690,964,863
b4 76,635,410,589
g3 68,083,657,167
e6 86,810,426,901
h3 76,305,199,742
g4 69,249,377,488
h4 82,338,227,992
Depth: 8   Count: 3,245,368,361,624   Elapsed: 1050.38  (3.08971e+09 Hz / 3.23655e-10 s)

[ibid]

To draft 8:

Code: Select all

[] emptran 8
[] sf rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6 
...
Depth: 8   Count: 3,245,368,361,624   Elapsed: 1050.38  (3.08971e+09 Hz / 3.23655e-10 s)

Agreed...

Code: Select all

$ ./uniq uniq 1
42 unique positions.  0 seconds.
$ ./uniq uniq 2
1352 unique positions.  0 seconds.
$ ./uniq uniq 3
30915 unique positions.  0 seconds.
$ ./uniq uniq 4
635428 unique positions.  1 seconds.
$ ./uniq uniq 5
9611978 unique positions.  10 seconds.
$ ./uniq mperft 7 5 6
94854874131 perft.  7 seconds.
$ ./uniq uniq 6
149129998 unique positions.  137 seconds.
$ ./uniq mperft 8 6 6
3245368361624 perft.  103 seconds.
$ ./uniq mperft 9 6 6
130962926513326 perft.  3718 seconds.

[Ajedrecista]

Hello:

To draft 8:

Code: Select all

[] emptran 8
[] sf rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6 
Bb3 62,390,421,333
Bd2 73,815,836,545
Ba6 63,840,917,367
Bb5 73,861,828,455
Bd5 70,615,162,877
Bd3 66,835,913,640
Be6 83,780,119,769
Be3 109,165,077,092
Bxf7+ 2,566,822,408
Bf4 85,213,137,562
Bg5 79,559,611,949
Kd2 40,165,708,509
Bh6 79,210,844,684
Kxf2 50,921,898,957
Kf1 86,847,755,314
Na3 68,733,983,884
Nbc3 91,528,042,446
Nd2 50,539,682,793
Nd4 105,838,273,247
Nec3 105,282,152,818
Ng1 80,984,415,079
Nf4 100,863,022,365
O-O 79,190,258,398
Ng3 97,926,711,928
Qd2 85,309,191,157
Qd3 127,891,776,553
Qxd7+ 7,891,308,529
Qd5 93,643,991,874
Qd6 71,721,175,729
Qd4 122,410,358,073
Rg1 68,226,602,049
Rf1 75,451,133,714
a3 77,459,484,626
b3 74,622,488,189
a4 87,949,986,970
c3 83,690,964,863
b4 76,635,410,589
g3 68,083,657,167
e6 86,810,426,901
h3 76,305,199,742
g4 69,249,377,488
h4 82,338,227,992
Depth: 8   Count: 3,245,368,361,624   Elapsed: 1050.38  (3.08971e+09 Hz / 3.23655e-10 s)

JetChess also agrees in Perft(8). JetChess 1.0.0.0 (single core, 32-bit) with 1 GB of hash, in an Intel i5-760:

Code: Select all

rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6

  1  Qd1-d2   85309191157
  2  Qd1-d3  127891776553
  3  Qd1-d4  122410358073
  4  Qd1-d5   93643991874
  5  Qd1-d6   71721175729
  6  Qd1*d7    7891308529
  7  Rh1-g1   68226602049
  8  Rh1-f1   75451133714
  9  Bc1-d2   73815836545
 10  Bc1-e3  109165077092
 11  Bc1-f4   85213137562
 12  Bc1-g5   79559611949
 13  Bc1-h6   79210844684
 14  Bc4-b5   73861828455
 15  Bc4-a6   63840917367
 16  Bc4-d5   70615162877
 17  Bc4-e6   83780119769
 18  Bc4*f7    2566822408
 19  Bc4-d3   66835913640
 20  Bc4-b3   62390421333
 21  Nb1-a3   68733983884
 22  Nb1-c3   91528042446
 23  Nb1-d2   50539682793
 24  Ne2-c3  105282152818
 25  Ne2-d4  105838273247
 26  Ne2-f4  100863022365
 27  Ne2-g3   97926711928
 28  Ne2-g1   80984415079
 29   a2-a3   77459484626
 30   a2-a4   87949986970
 31   b2-b3   74622488189
 32   b2-b4   76635410589
 33   c2-c3   83690964863
 34   g2-g3   68083657167
 35   g2-g4   69249377488
 36   h2-h3   76305199742
 37   h2-h4   82338227992
 38   e5-e6   86810426901
 39     0-0   79190258398
 40  Ke1-f1   86847755314
 41  Ke1-d2   40165708509
 42  Ke1*f2   50921898957

Total:      3245368361624

3,245,368,361,624 (move pathes after 8 half moves).

Time: 1197.132 s (0:19:57.132).

I will not comment on the speed of Paul Byrne's programme...; I post a little bonus of the same position (and the same hardware):

JetChess 1.0.0.0 using 80 MB of hash and one step:

Code: Select all

42 (positions after 1 half move).

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

Code: Select all

1,352 (positions after 2 half moves).

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

Code: Select all

30,915 (positions after 3 half moves).

Time: 9 ms (0:00:00.009).

Code: Select all

635,763 (positions after 4 half moves).

Time: 82 ms (0:00:00.082).

Now 320 MB of hash and one step (for not overflow the hash):

Code: Select all

9,611,978 (positions after 5 half moves).

Time: 2.153 s (0:00:02.153).

Now 1280 MB of hash and four steps (for not overflow the hash):

Code: Select all

Count  0:      37321527
Count  1:      37313379
Count  2:      37328875
Count  3:      37313262

Positions:    149277043

149,277,043 (positions after 6 half moves).

Time: 125.880 s (0:02:05.880).

Regards from Spain.

Ajedrecista.

[ibid]

Hello:

JetChess also agrees in Perft(8). JetChess 1.0.0.0 (single core, 32-bit) with 1 GB of hash, in an Intel i5-760:

...

Now 320 MB of hash and one step (for not overflow the hash):

Code: Select all

9,611,978 (positions after 5 half moves).

Time: 2.153 s (0:00:02.153).

Now 1280 MB of hash and four steps (for not overflow the hash):

Code: Select all

Count  0:      37321527
Count  1:      37313379
Count  2:      37328875
Count  3:      37313262

Positions:    149277043

149,277,043 (positions after 6 half moves).

Time: 125.880 s (0:02:05.880).

Regards from Spain.

Ajedrecista.

This last one had me worried, as it different from my result. Turns out
there are just a lot of positions with illegal en passant captures.

JetChess is significantly slower on my windows machine (Phenom 840)...
using your settings, 5 ply took 5.682 seconds and 6 ply took 219.050 seconds.

On this same machine, my program (single core, 64 bit) takes
12 and 163 seconds (I gave the program 7 GB of memory though,
so the 6 ply computation was done in a single step, not four).

-paul

[Ajedrecista]

Hello Paul:

This last one had me worried, as it different from my result. Turns out
there are just a lot of positions with illegal en passant captures.

My bad. Sorry. Thanks for pointing out the en passant issue: I am more used to run perft counts, so when I run a position count, I usually forget to tick the en passant flag in JetChess... it should be ticked at default, but the reality is just the opposite.

640 MB of hash and eight steps (for not overflow the hash):

Code: Select all

rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6

Count  0:      18642653
Count  1:      18642297
Count  2:      18639991
Count  3:      18636857
Count  4:      18645806
Count  5:      18646138
Count  6:      18640190
Count  7:      18636066

Positions:    149129998

149,129,998 (positions after 6 half moves).

Time: 869.586 s (0:14:29.586).

JetChess 1.0.0.0 was ran this time in an Intel Pentium D930 at 3 GHz. The Intel i5-760 was at 2.8 GHz.

So, no need for worry. Thanks for report my failure. I suppose that the count is perfect now.

Regards from Spain.

Ajedrecista.

[Kotlov]

please correct CPW
http://chessprogramming.wikispaces.com/Perft+Results

Position 5
This position was discussed on Talkchess and caught bugs in engines several years old at depth 3.[5]
Depth
Nodes
1 42 - 44!!!
2 1352
3 53392

[bob]

please correct CPW
http://chessprogramming.wikispaces.com/Perft+Results

Position 5
This position was discussed on Talkchess and caught bugs in engines several years old at depth 3.[5]
Depth
Nodes
1 42 - 44!!!
2 1352
3 53392

Looks like it caught a bug in the program used for the Wiki output.