Perft 25

[sje]

Perft 25 for the well-known Fine #70:

[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Ka2 327999083762531157
Kb1 419736306837795168
Kb2 612315810248920416

Count: 1360051200849246741
Unique position count: 1361183

[Daniel Shawul]

Hmm I was mislead by the title which didn't have the initial position
It seems reasonable for a low branching factor . Maximum branching factor for this position is 8 , considering pawns remain blocked, and that it takes 20 something plies for the first pawn capture IIRC.
That would be then 8^25 = 3.8e22 leaf nodes max. Are you using mutiple cores, hashing or other tricks to get fast perft results?

[sje]

Hah! With current tech, it would take a world full of computers to generate Perft(initial-array, 25) in a reasonable amount of time.

Hashing has been used for the Fine #70 result, but instead of a table, the Lisp program in play uses a ply-indexed vector of position dictionaries. Each dictionary is a pair of binary trees (one for each color, although only one is used per ply) with the position hash used as a node key. The program asks for a minimum of 128 bit long hash codes and with the 32 bit Steel Bank Common Lisp processor, it gets 145 bit codes. (An inspection of the source will explain why this happens.) Each node also contains the movepath count of its chess subtree (not its hash subtree).

Only a single core was used, and the machine was heavily loaded with a Perft(1 e3, 11) calculation among other tasks.

For a perft calculation of depth > 8, the operation should probably be re-defined to include draws by repetition at intermediate ply, something that will reduce the path count. To be fair, perhaps all draws should also be considered.

[Lasse Hansen]

Hi!

Its nice to verify my own move generator to others. Here are my results togheter with H.G.Müller's qpert on my AMD64 box. (I also took the liberty to compare perft speed with qperft on two 'normal' perft positions).

Code: Select all

lasseh@AMD64:~/Downloads$ ./perft.exe 28 H25 "8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1"
Hash-table size = 1ffffff, Starts at 5b7fe020
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - . . . . . . . . - -
 - - k . . . . . . . - -
 - - . . . p . . . . - -
 - - p . . P . p . . - -
 - - P . . P . P . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - K . . . . . . . - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: Hash-table size = 512MB, bulk counting in horizon nodes
perft(1)=3 ( 0.000 sec)
perft(2)=15 ( 0.000 sec)
...
perft(23)=43351968581265298 ( 0.290 sec)
perft(24)=224782969551367613 ( 0.590 sec)
perft(25)=1360051200849246741 ( 0.980 sec)
perft(26)=7077459201934621316 ( 2.390 sec)
perft(27)=5948107044607007921 ( 5.070 sec)
perft(28)=2306730512529876632 (14.020 sec)

// My own perft
perfthash (Hashtable size=448MB)
perft 1=3 t=0.00s 0.00MN/s
perft 2=15 t=0.00s 0.00MN/s
...
perft 23=43351968581265298 t=0.17s 247725539328.00MN/s
perft 24=224782969551367613 t=0.52s 432274931712.00MN/s
perft 25=1360051200849246741 t=1.08s 1261642973184.00MN/s
perft 26=7077459201934621316 t=4.00s 1768038727680.00MN/s
perft 27=18053782842978901169 t=7.41s 2437065736192.00MN/s
perft 28=13547715182446634648 t=32.72s 414037344256.00MN/s

lasseh@AMD64:~/Downloads$ ./perft.exe 7 "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w QKqk -"
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - 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)
perft(3)=8902 ( 0.000 sec)
perft(4)=197281 ( 0.000 sec)
perft(5)=4865609 ( 0.200 sec)
perft(6)=119060324 ( 4.930 sec)
perft(7)=3195901860 (128.720 sec)

// My own perft
perft (no hashing)
perft 1=20 t=0.00s 0.00MN/s
perft 2=400 t=0.00s 0.00MN/s
perft 3=8902 t=0.00s 0.00MN/s
perft 4=197281 t=0.01s 28.18MN/s
perft 5=4865609 t=0.15s 31.59MN/s
perft 6=119060324 t=3.60s 33.11MN/s
perft 7=3195901860 t=88.11s 36.27MN/s

lasseh@AMD64:~/Downloads$ ./perft.exe 6 "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w QKqk - -"
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r . . . k . . r - -
 - - p . p p q p b . - -
 - - b n . . p n p . - -
 - - . . . P N . . . - -
 - - . p . . P . . . - -
 - - . . N . . Q . p - -
 - - P P P B B P P P - -
 - - R . . . K . . R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft(1)=48 ( 0.000 sec)
perft(2)=2039 ( 0.000 sec)
perft(3)=97862 ( 0.000 sec)
perft(4)=4085603 ( 0.160 sec)
perft(5)=193690690 ( 7.360 sec)
perft(6)=8031647685 (317.290 sec)

// My own perft
perft (no hashing)
perft 1=48 t=0.00s 0.00MN/s
perft 2=2039 t=0.00s 0.00MN/s
perft 3=97862 t=0.00s 97.86MN/s
perft 4=4085603 t=0.07s 56.74MN/s
perft 5=193690690 t=2.52s 76.80MN/s
perft 6=8031647685 t=128.23s 62.64MN/s

So for 25 plies the results are confirmed. For 26 qperft and mine agrees, on 27 plies it seems like qperft uses signed int, mine signed. Deeper plies become garbadge.

It also seems like my perft beats H.G's qperft without hashing
But I have not been able to beat his hashing scheme.

BTW, my perft uses popcount at leaf nodes when the legality of moves are known. So this should be even faster on K10 or i7

Regards, Lasse

[sje]

Perft 26: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Ka2 1706910857137266354
Kb1 2184210511941397691
Kb2 3186337832855957271

Count: 7077459201934621316

[sje]

Perft 27: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Ka2 10330993714697377755
Kb1 13219615867581864416
Kb2 19290985609746868982

Count: 42841595192026111153

[sje]

Perft 28: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Ka2 53938997118561111592
Kb1 69016468768716398235
Kb2 100712193509766986197

Count: 223667659397044496024

"Why settle for fixed length integers when you can have Lisp bignums that are arbitrarily long? The Lisp language; it's recommended by four out of five computer memory manufacturers."

"Lisp programmers are a different breed -- they know everything about values but understand nothing about costs."

[sje]

Perft 29: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Ka2 326669429393242838655
Kb1 417827415718852132416
Kb2 610024584339638908057

Count: 1354521429451733879128

[sje]

Perft 30: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Ka2 1710908392584537344313
Kb1 2188204893733437778865
Kb2 3194637422182324560024

Count: 7093750708500299683202

[sje]

Perft 31: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Ka2 10371366973326742232771
Kb1 13252601250407797823413
Kb2 19366999975110719410642

Count: 42990968198845259466826

That's forty-two sextillion nine hundred ninety quintillion nine hundred sixty-eight quadrillion one hundred ninety-eight trillion eight hundred forty-five billion two hundred fifty-nine million four hundred sixty-six thousand eight hundred twenty-six. By contrast, 2^64-1 is less than a thousandth of this at 18446744073709551615 or eighteen quintillion four hundred forty-six quadrillion seven hundred forty-four trillion seventy-three billion seven hundred nine million five hundred fifty-one thousand six hundred fifteen.

The Lisp program in use stores a hash and a count for each unique depth-1 position, so more than four GB were needed to hold the data because of the length of the hash signatures. This was handled by using ccl64, the 64 bit version of Clozure Common Lisp.