perft conflict...

[ibid]

I've been experimenting with magic in my engine, using i-perft for some verification, and came up with the following:

Code: Select all

i-perft 8 "rnbqkbnr/pppppppp/8/8/8/P7/1PPPPPPP/RNBQKBNR b KQkq - 0 1"

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


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

perft 1           20     0.00s    1.$ mnps 2080.8 ticks/op
perft 2          380     0.00s    1.$ mnps   52.7 ticks/op
perft 3         8457     0.00s    1.$ mnps   32.3 ticks/op
perft 4       181046     0.00s    1.$ mnps   31.8 ticks/op
perft 5      4463267     0.05s   95.0 mnps   29.1 ticks/op
perft 6    106743106     1.00s  107.0 mnps   30.2 ticks/op
perft 7   2863411653    24.95s  114.8 mnps   28.0 ticks/op
perft 8  74950759747   673.47s  111.3 mnps   28.9 ticks/op

perft 8 differs from what I get, and after spending some time bug hunting, I ran oliperft:

Code: Select all

oliperft 8 "rnbqkbnr/pppppppp/8/8/8/P7/1PPPPPPP/RNBQKBNR b KQkq - 0 1"
 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

 1     0      0          20
 2     0      0         380
 3     0      0        8457
 4     0      0      181046
 5     0      4     4463267
 6     0     60   106743106
 7     0    981  2863411653
 8     0  22768 74950758099

Which agrees with what I got.

I am just using the executables from the two web sites here as I don't have a compiler installed on this machine. Does i-perft have some known issue? Or are oliperft and my engine making the same error? Or am I doing something stupid in the way I am running i-perft? :)

[hgm]

qperft also agrees with you.

Code: Select all

$ ./qperft 8 H20 "rnbqkbnr/pppppppp/8/8/8/P7/1PPPPPPP/RNBQKBNR b KQkq - 0 1"
Hash-table size = fffff, Starts at 4e0040,section = 1ffff
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - 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: Hash-table size = 32MB, bulk counting in horizon nodes

perft( 1)=           20 ( 0.000 sec)
perft( 2)=          380 ( 0.000 sec)
perft( 3)=         8457 ( 0.000 sec)
perft( 4)=       181046 ( 0.000 sec)
perft( 5)=      4463267 ( 0.070 sec)
perft( 6)=    106743106 ( 1.041 sec)
perft( 7)=   2863411653 (15.913 sec)
perft( 8)=  74950758099 (281.935 sec)

[Ajedrecista]

Hello Paul:

I post the values from Perft(1) to Perft(8) of this position; all are divided into the subsequent moves (except Perft(1) result) to see if you can detect where the error comes from.

[d]

Code: Select all

Perft(1):
Total:               20
20   (move pathes after 1 half move).
Time: 0 ms.

Perft(2):
  1  nb8-a6          19
  2  nb8-c6          19
  3  ng8-f6          19
  4  ng8-h6          19
  5   a7-a6          19
  6   a7-a5          19
  7   b7-b6          19
  8   b7-b5          19
  9   c7-c6          19
 10   c7-c5          19
 11   d7-d6          19
 12   d7-d5          19
 13   e7-e6          19
 14   e7-e5          19
 15   f7-f6          19
 16   f7-f5          19
 17   g7-g6          19
 18   g7-g5          19
 19   h7-h6          19
 20   h7-h5          19
Total:              380
380   (move pathes after 2 half moves).
Time: 0 ms.

Perft(3):
  1  nb8-a6         380
  2  nb8-c6         418
  3  ng8-f6         418
  4  ng8-h6         380
  5   a7-a6         361
  6   a7-a5         399
  7   b7-b6         399
  8   b7-b5         400
  9   c7-c6         399
 10   c7-c5         419
 11   d7-d6         512
 12   d7-d5         532
 13   e7-e6         569
 14   e7-e5         570
 15   f7-f6         361
 16   f7-f5         381
 17   g7-g6         399
 18   g7-g5         400
 19   h7-h6         361
 20   h7-h5         399
Total:             8457
8,457   (move pathes after 3 half moves).
Time: 0 ms.

Perft(4):
  1  nb8-a6        8163
  2  nb8-c6        8960
  3  ng8-f6        8936
  4  ng8-h6        8142
  5   a7-a6        7754
  6   a7-a5        8551
  7   b7-b6        8568
  8   b7-b5        8573
  9   c7-c6        8499
 10   c7-c5        8934
 11   d7-d6       10963
 12   d7-d5       11402
 13   e7-e6       12103
 14   e7-e5       12129
 15   f7-f6        7754
 16   f7-f5        8189
 17   g7-g6        8568
 18   g7-g5        8551
 19   h7-h6        7754
 20   h7-h5        8553
Total:           181046
181,046   (move pathes after 4 half moves).
Time: 14 ms.

Perft(5):
  1  nb8-a6      182327
  2  nb8-c6      215405
  3  ng8-f6      213990
  4  ng8-h6      181930
  5   a7-a6      165948
  6   a7-a5      199263
  7   b7-b6      197301
  8   b7-b5      198797
  9   c7-c6      203960
 10   c7-c5      219841
 11   d7-d6      300892
 12   d7-d5      331473
 13   e7-e6      371069
 14   e7-e5      373372
 15   f7-f6      163919
 16   f7-f5      181945
 17   g7-g6      199099
 18   g7-g5      196185
 19   h7-h6      165963
 20   h7-h5      200588
Total:          4463267
4,463,267   (move pathes after 5 half moves).
Time: 56 ms.

Perft(6):
  1  nb8-a6     4364503
  2  nb8-c6     5124341
  3  ng8-f6     5117838
  4  ng8-h6     4362016
  5   a7-a6     3992557
  6   a7-a5     4783817
  7   b7-b6     4749927
  8   b7-b5     4766122
  9   c7-c6     4838649
 10   c7-c5     5241384
 11   d7-d6     7211846
 12   d7-d5     7937327
 13   e7-e6     8810309
 14   e7-e5     8852893
 15   f7-f6     3937829
 16   f7-f5     4374714
 17   g7-g6     4782149
 18   g7-g5     4684513
 19   h7-h6     3993007
 20   h7-h5     4817365
Total:        106743106
106,743,106   (move pathes after 6 half moves).
Time: 779 ms.

Perft(7):
  1  nb8-a6   107844586
  2  nb8-c6   133202829
  3  ng8-f6   131987450
  4  ng8-h6   107864025
  5   a7-a6    95428595
  6   a7-a5   121920765
  7   b7-b6   119122930
  8   b7-b5   120839805
  9   c7-c6   128404510
 10   c7-c5   140664908
 11   d7-d6   203100295
 12   d7-d5   240777757
 13   e7-e6   276949789
 14   e7-e5   280003885
 15   f7-f6    91135870
 16   f7-f5   106932395
 17   g7-g6   121572224
 18   g7-g5   116424319
 19   h7-h6    95405446
 20   h7-h5   123829270
Total:       2863411653
2,863,411,653   (move pathes after 7 half moves).
Time: 8.837 s.

Perft(8):
  1  nb8-a6  2824555170
  2  nb8-c6  3466228615
  3  ng8-f6  3456100831
  4  ng8-h6  2828682884
  5   a7-a6  2514928818
  6   a7-a5  3208279697
  7   b7-b6  3143606039
  8   b7-b5  3171786731
  9   c7-c6  3332998273
 10   c7-c5  3676418704
 11   d7-d6  5334050927
 12   d7-d5  6299558646
 13   e7-e6  7212087063
 14   e7-e5  7267927912
 15   f7-f6  2394075148
 16   f7-f5  2808489770
 17   g7-g6  3197493200
 18   g7-g5  3040643369
 19   h7-h6  2513530492
 20   h7-h5  3259315810
Total:      74950758099
74,950,758,099   (move pathes after 8 half moves).
Time: 125.004 s.

I run JetChess 1.0.0.0 with 64 MB of hash from Perft(1) to Perft(7), and 256 MB of hash for this Perft(8).

Maybe en passant captures and/or promotions with captures are guilty of bringing wrong results. AFAIK JetChess is totally correct because I calculated Perft(9) of Petrov defence and the result was the same as Mr. Edwards one. So, your engine and also oliperft should be correct (also qperft, as Muller stated). Please read posts of this thread that may contain valuable info.

I want to ask you something: are you going to calculate Perft(13) as you said in a former post two months ago? Thanks in advance.

Regards from Spain.

Ajedrecista.

[John Major]

In i-perft check evasions are wrong:

Code: Select all

user@dell:~/i-perft$ wine i-perft.exe -divide 1 "rn1qkbnr/p1pppppp/b7/8/1p2P3/P7/1PPPKPPP/RNBQ1BNR w kq - 2 4"

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


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

--divide--------------
Ng1xe2              1
Bf1xe2              1
Qd1xe2              1
Ke2f3               1
Ke2e3               1
Ke2e1               1
----------------------
total               6  (0.00 seconds)

[ibid]

In i-perft check evasions are wrong:

Ah, ouch. I'm somewhat surprised it got as deep as it did without issues. I will avoid i-perft for my verifications; debugging my own code is, er, entertaining enough -- I will leave i-perft alone. :)

Thanks,
-paul

[hgm]

In i-perft check evasions are wrong:

Interesting. It captures its own King rather than the checker. I guess that resolves the check too!

The less funny thing is that I discovered a bug in qperft too,by following up a bug reported here in 2009, which I had so far never looked at, because I assumed it was an acidental key collision. This would have been extremely unlucky, but such things can happen. The latest qperft uses longer key, though, and the error was still there. SoI fugured I'd better take a look again.

Turns out now that the stm key was the same as that for white K-side castling rights, so that it could collide a position that had spoiled the castling rights with that of the opposite side to move. Now this normally doesn't happen, because other side to move must mean other depth. But when the perfts are iteratively deepened as qperft normally does, you can get a hit on an entry from perft(4) while doing perft(5).

I changed the key for stm, and now it gives the correct value even with hashing. Note that this was for

[d] 7r/8/8/8/8/8/7P/4K2R w K - 0 1

where it is easy to spoil the castling rights by Rg1, Rh1, and still castle within the depth. From the opening position you barely reach castling even with perft(8), leaving no time to spoil the rights first.

[ibid]

OK, let me try this again. My last attempt at responding apparently went to /dev/null because I took to long to type it and got logged out. :(

Maybe en passant captures and/or promotions with captures are guilty of bringing wrong results. AFAIK JetChess is totally correct because I calculated Perft(9) of Petrov defence and the result was the same as Mr. Edwards one. So, your engine and also oliperft should be correct (also qperft, as Muller stated). Please read posts of this thread that may contain valuable info.

Looks like i-perft has been outvoted. Thank you and Muller for running this position for me. I'll leave the i-perft bug hunt to someone else. I generate enough of my own to keep me occupied. :) I've been converting my engine to magic bitboards and since I've been doing the magic from scratch, there was the possibility of some nasty hard-to-find bug lurking if a bit had been misplaced somewhere.

I want to ask you something: are you going to calculate Perft(13) as you said in a former post two months ago? Thanks in advance.

Absolutely.

At first I was pausing because the long-running betting pool thread seemed to indicated folks were having fun predicting the result. No need to spoil that with an actual number. :)

More recently, I have become distracted by magic. The good news is that between the conversion from a dubious rotated bitboard setup to magic and converting the bulk-counting routine for that last ply from losers chess to actual chess, the perft routine is about 40% faster. A recent recompute of perft 12 took only 48258 seconds. Although really it was not that fast, because first I had to compute the unique positions at 10 ply which is done by a painfully slow single-thread program and took 4 days. That uniq 10 data will be reused for perft 13 though, which I currently estimate at perhaps 18 days.

Mostly I have not been rushing due to the nature of my program. It is was set up from the start to produce one number as quickly as I can. You get the perft, but no other information, making it impossible for others to verify parts of the computation. And while the program is now fast enough to reasonably run it twice to reduce the odds of hardware issues I would still not be 100% confident in the result until Steven Edwards' program finishes, which is still some months off.

Looking ahead a little further, perft 14 would take 18-24 months using the current setup. Using uniq 11 instead of 10 would reduce that by a factor of 3 or so, but that uniq 11 computation would itself take months (and a lot more disk space than I have available). A modified setup doing the uniq 11 in parts is possible, but I would still estimate 8-10 months -- plus one badly abused hard drive. :) I think for now perft 14 is a bit out of reach, but perhaps in a couple of years...

-paul

[Ajedrecista]

Hello Paul:

I run Perft(9) of the same position for verification purposes in the case you want to run Perft(9) searching more bugs:

[d]

Code: Select all

JetChess 1.0.0.0 with 1024 MB of hash.

Perft(9):

  1  nb8-a6   75825266241
  2  nb8-c6   96471209843
  3  ng8-f6   95079908947
  4  ng8-h6   76048713693
  5   a7-a6   65773102227
  6   a7-a5   88102077062
  7   b7-b6   84784371144
  8   b7-b5   86632491711
  9   c7-c6   94966340141
 10   c7-c5  105291176660
 11   d7-d6  154735616958
 12   d7-d5  199055467042
 13   e7-e6  232397881843
 14   e7-e5  235974794600
 15   f7-f6   59681730538
 16   f7-f5   74388751472
 17   g7-g6   87426746127
 18   g7-g5   80887662502
 19   h7-h6   65675044593
 20   h7-h5   90278802883

Total:      2149477156227

2,149,477,156,227   (move pathes after 9 half moves).

Time: 2637.616 s.

I also have values of Perft(10) and Perft(11) of this position, although was Mr. Edwards who calculated it (or at least I picked up these numbers from his web):

Code: Select all

Perft(10) = 60,403,292,887,824
Perft(11) = 1,825,396,176,881,632

Good luck with everything (18 days for computing whole Perft(13) seems outstanding!) and thanks for your quick answer.

Regards from Spain.

Ajedrecista.

[sje]

Symbolic says:

Code: Select all

[] df
rnbqkbnr/pppppppp/8/8/8/P7/1PPPPPPP/RNBQKBNR b KQkq - 0 1
[] emptran 8
Nh6 2,828,682,884
Na6 2,824,555,170
Nf6 3,456,100,831
Nc6 3,466,228,615
a6 2,514,928,818
b6 3,143,606,039
a5 3,208,279,697
b5 3,171,786,731
c5 3,676,418,704
c6 3,332,998,273
d6 5,334,050,927
d5 6,299,558,646
f5 2,808,489,770
f6 2,394,075,148
g5 3,040,643,369
g6 3,197,493,200
h5 3,259,315,810
h6 2,513,530,492
e5 7,267,927,912
e6 7,212,087,063
Depth: 8   Count: 74,950,758,099   Elapsed: 55.2945  (1.35548e+09 Hz / 7.37744e-10 s)

[JuLieN]

At its own slow pace, Prédateur confirms the figures most of us yet found:

Code: Select all

perft 8
a7a6 : 2514928818
a7a5 : 3208279697
b7b6 : 3143606039
b7b5 : 3171786731
c7c6 : 3332998273
c7c5 : 3676418704
d7d6 : 5334050927
d7d5 : 6299558646
e7e6 : 7212087063
e7e5 : 7267927912
f7f6 : 2394075148
f7f5 : 2808489770
g7g6 : 3197493200
g7g5 : 3040643369
h7h6 : 2513530492
h7h5 : 3259315810
b8a6 : 2824555170
b8c6 : 3466228615
g8f6 : 3456100831
g8h6 : 2828682884
Nombre de noeuds : 74950758099 ; Temps : 20361.952s ; vitesse : 3680922 nps