Perft(7) test suites just for you

[sje]

Among the 53+ million perft(7) results so far, the mean perft(7) subtotal is about 21,761,466,016. This is about 6.7 times as much as perft(7) from the root, showing how the calculation work increases with ply depth.

[sje]

Bits needed to hold perft(n)

Code: Select all

N   bits
--  ----
 0     1
 1     5
 2     9
 3    14
 4    18
 5    23
 6    27
 7    32
 8    37
 9    42
10    46
11    51
12    56
13    61
14    66 (?)
15    71 (?)

Others are welcome to add entries to the above.

[stegemma]

Bits needed to hold perft(n)

Code: Select all

N   bits
--  ----
 0     1
 1     5
 2     9
 3    14
 4    18
 5    23
 6    27
 7    32
 8    37
 9    42
10    46
11    51
12    56
13    61
14    66 (?)
15    71 (?)

Others are welcome to add entries to the above.

And the delta between nodes are:

Code: Select all

N   bits    delta
--  ----
 0     1     1
 1     5     4
 2     9     4
 3    14    5
 4    18    4
 5    23    5
 6    27    4
 7    32    5
 8    37    5
 9    42    5
10    46   4
11    51   5
12    56   4
13    61   5
14    66   5  (?)
15    71   5 (?)

It seems that more you advance in depth and more the bits required grow by 5. This means from 32 to 63 moves per ply (2^5 to 2^6-1).

[Ajedrecista]

Hello Steven:

Bits needed to hold perft(n)

Code: Select all

N   bits
--  ----
 0     1
 1     5
 2     9
 3    14
 4    18
 5    23
 6    27
 7    32
 8    37
 9    42
10    46
11    51
12    56
13    61
14    66 (?)
15    71 (?)

Others are welcome to add entries to the above.

According to Labelle's estimates, which are indeed very good, I do bits(n) = ceiling{ln[Perft(n)]/ln(2)}. If I am correct:

Code: Select all

 n   bits(n) 
--   -------
 0      1 
 1      5 
 2      9 
 3     14 
 4     18 
 5     23 
 6     27 
 7     32 
 8     37 
 9     42 
10     46 
11     51 
12     56 
13     61 
14     66
15     71
16     76
17     81
18     86
19     91
20     97

Reliable estimates of higher Perft values can be estimated via Montecarlo simulations or other methods and then apply the formula written above.

Regards from Spain.

Ajedrecista.

[ibid]

[...]It took about 67 seconds wall time for the perft(7) calculation.

The above ran on a 2006 dual 2.66 GHz Xeon Mac, a machine about 20% as fast as top end 2015 consumer hardware.
[...]

WOW... 67 seconds???

Of course your is a perft only software (you don't store move, don't sort them and so on) but still it looks very fast. Mine is a I7 4970k but satana is still single core.

67 seconds!!! No I don't believe you. :shock:

One core, no hash tables:

Code: Select all

gperft 1.2d (windows)
Not using hash tables.
Using 1 thread.
Depth is 7.

rnbqk--r
pppp-pp-
----p--n
--b-----  b KQkq -
----Q---
----P---
PPPP-PPP
RNB-KBNR

Bxe3       2,942,810,537
Ng4        3,935,605,279
Nf5        4,028,158,143
Ng8        3,200,797,918
Na6        2,526,661,536
Nc6        3,392,170,798
Ba3        2,337,503,562
Bb4        2,253,211,736
Bd4        2,391,745,630
Bb6        1,970,330,267
Bd6        2,713,619,459
Be7        1,995,684,390
Bf8        1,989,492,762
Qh4        4,071,429,022
Qg5        4,907,287,371
Qf6        4,357,913,153
Qe7        2,992,722,243
Rh7        2,243,962,717
Rf8        2,005,486,351
Rg8        2,161,027,180
e5         2,480,456,841
a6         2,726,177,590
b6         2,880,818,370
c6         2,807,338,986
d6         2,537,662,269
f6         2,150,096,477
g6         2,469,860,577
a5         3,163,227,379
b5         2,902,239,798
d5         3,137,563,064
f5         2,566,461,493
g5         2,107,471,702
Ke7        2,246,915,774
Kf8        2,699,349,280
O-O        2,008,388,929
TOTAL     97,301,648,583
145.532 seconds

Six cores and 4 GB hash tables:

Code: Select all

gperft 1.2d (windows)
Low hash table ready (2048 MB, 2-3 ply).
High hash table ready (2048 MB, 4 ply).
Using 6 threads (split after 3 ply).
Depth is 7.

[...]

TOTAL     97,301,648,583
4.314 seconds

Ultimately I want to get gperft's code connected to my unique positions generator and see how it does. At my current coding speed... I might be in time to reverify perft 14 once Steven is done.

[mvk]

For the needs of the program, the 128 bit support is complete except for the encoder which generates a string of base 10 digits giving a 128 bit value.
[...]
Here is the table of the pre-calculated values of 10^n, n= 0..38:

Code: Select all

 0 00000000000000000000000000000001
 1 0000000000000000000000000000000a
 2 00000000000000000000000000000064
...
37 0785ee10d5da46d900f436a000000000
38 4b3b4ca85a86c47a098a224000000000

You can save yourself a lot of effort by looking at what is out there. In this case GMP. It has all of that. Or use Python for the non-critical parts:

Code: Select all

marcelk@bk:~> python -c 'print [hex(10**n) for n in range(39)]'
['0x1', '0xa', '0x64', '0x3e8', '0x2710', '0x186a0', '0xf4240', '0x989680', '0x5f5e100', '0x3b9aca00', '0x2540be400', '0x174876e800', '0xe8d4a51000', '0x9184e72a000', '0x5af3107a4000', '0x38d7ea4c68000', '0x2386f26fc10000', '0x16345785d8a0000', '0xde0b6b3a7640000', '0x8ac7230489e80000L', '0x56bc75e2d63100000L', '0x3635c9adc5dea00000L', '0x21e19e0c9bab2400000L', '0x152d02c7e14af6800000L', '0xd3c21bcecceda1000000L', '0x84595161401484a000000L', '0x52b7d2dcc80cd2e4000000L', '0x33b2e3c9fd0803ce8000000L', '0x204fce5e3e25026110000000L', '0x1431e0fae6d7217caa0000000L', '0xc9f2c9cd04674edea40000000L', '0x7e37be2022c0914b2680000000L', '0x4ee2d6d415b85acef8100000000L', '0x314dc6448d9338c15b0a00000000L', '0x1ed09bead87c0378d8e6400000000L', '0x13426172c74d822b878fe800000000L', '0xc097ce7bc90715b34b9f1000000000L', '0x785ee10d5da46d900f436a000000000L', '0x4b3b4ca85a86c47a098a224000000000L']

Just a thought.

[sje]

You can save yourself a lot of effort by looking at what is out there. In this case GMP. It has all of that. Or use Python for the non-critical parts

Actually, the purpose of generating the powers-of-ten table inside of Symbolic was to help verify its new 128 bit arithmetic. The table is also used in Symbolic's decimal string encoding based on an idea I stole form the 1976 Zurich ETH Pascal run time support for a Control Data mainframe. That routine encoded a single signed 60 bit integer while mine encodes an unsigned 128 bit integer made from two unsigned 64 bit integers.

For hexadecimal arithmetic, the Unix bc utility is simpler, smaller, and faster than Python, and Lisp is more general.

[sje]

I've made a new link with 100 positions which are the 100 positions with the highest perft(7) subtotals of the merge of all the Perft(14) work units processed so far. The records are sorted in descending order based on perft(7) subtotal.

The Tough Guy 100 set: https://dl.dropboxusercontent.com/u/316 ... /ToughGuys

The content of the above link will be updated as the project progresses.

On a fast machine, Symbolic can run the above in about 50 minutes using a 2^31 element transposition table combined with 128 bit signature goodness.

[mvk]

You can save yourself a lot of effort by looking at what is out there. In this case GMP. It has all of that. Or use Python for the non-critical parts

Actually, the purpose of generating the powers-of-ten table inside of Symbolic was to help verify its new 128 bit arithmetic. The table is also used in Symbolic's decimal string encoding based on an idea I stole form the 1976 Zurich ETH Pascal run time support for a Control Data mainframe. That routine encoded a single signed 60 bit integer while mine encodes an unsigned 128 bit integer made from two unsigned 64 bit integers.

For hexadecimal arithmetic, the Unix bc utility is simpler, smaller, and faster than Python, and Lisp is more general.

I believe you missed my point. Let me rephrase: What makes Symbolic such that it can't benefit from GMP's high precision arithmetic, and requires you to reinvent your own?

About my second part, and not really important, is that I don't understand the place of a speed argument in relation to non-critical parts.

[sje]

Symbolic needs to do 128 bit arithmetic at a rate faster than an external interpreter can provide. Also, that external interpreter may not even be present on small platforms like a BeagleBone Black or a Raspberry Pi. Or the interpreter might not even be available, as with an older PowerPC Mac.