Perft(13)

[sje]

I'm working on a new parallel enumeration algorithm which is analogous to PVS/YBW. It should do no worse than the current root split method and may be much better by enhancing inter-thread transposition entry reuse.

I got this running. Although it produced the correct results, for unknown reasons the threads are spending over 95% of the time waiting. So more work is needed.

[Sven]

Did you already find an explanation for the "ominously" growing estimated total time?

Code: Select all

after  81 hours:  808 days
after 141 hours:  896 days
after 250 hours: 1034 days
after 314 hours:  983 days
after 430 hours: 1048 days

Since I would expect an almost constant NPS I could only imagine that there are some differences between the expected and the real amount of nodes to visit. What is your formula to calculate the estimated total time?

There are 822,518 distinct perft(8) calculations required. The time estimate is:

(822,518 / completed(8)) * elapedtime

At present, completed(8) = 14,771 and elapsedtime = 455 hours

So, (822,518 / 14,777) * 455 hours -> 25,337 hours -> 1,056 days

Different perft(8) calculations take different times. Transposition usage also plays a part.

O.k., so you could also switch to the simpler method which might even be more accurate:

estimated_total_time = elapsed_time * estimated_total_nodes / visited_nodes

This would not suffer from the problem of different perft(8) calculations taking different times but would assume a fairly constant NPS over the whole time.

If you have doubts you could also publish both ways of estimating the total time, and watch how the values will develop.

Sven

[Edmund]

O.k., so you could also switch to the simpler method which might even be more accurate:

estimated_total_time = elapsed_time * estimated_total_nodes / visited_nodes

This would not suffer from the problem of different perft(8) calculations taking different times but would assume a fairly constant NPS over the whole time.

If you have doubts you could also publish both ways of estimating the total time, and watch how the values will develop.

Sven

This still fails to account for the speedgain of increased number of TT-Entries as the search progresses.

[Sven]

O.k., so you could also switch to the simpler method which might even be more accurate:

estimated_total_time = elapsed_time * estimated_total_nodes / visited_nodes

This would not suffer from the problem of different perft(8) calculations taking different times but would assume a fairly constant NPS over the whole time.

If you have doubts you could also publish both ways of estimating the total time, and watch how the values will develop.

Sven

This still fails to account for the speedgain of increased number of TT-Entries as the search progresses.

Correct, that's why I wrote "might even be more accurate" (not "perfectly accurate"). What you mentioned will be difficult to predict, but the potentially huge variance caused by different size of the perft(8) calculations can be avoided IMO with the purely node count based approach.

Sven

[sje]

In this context, an estimate is just that: an estimate. If it were possible to accurately predict the time it makes to calculate the sum, we'd already know what the sum was.

Subtotal results after 467 hours wall time:

0 of 20 perft(12)
2 of 400 perft(11)
52 of 5,362 perft(10)
1,020 of 72,078 perft(9)
15,073 of 822,518 perft(8) (ca. 1.83% of total)

Current total time estimate: 1,062 days (ca. 35 months)

[sje]

The ten most recent perft(8) subtotals:

Code: Select all

rnbqkbnr/2pppppp/1p6/p7/8/N2P1P2/PPP1P1PP/R1BQKBNR b KQkq - 0 3 8 199332232882
rnbqkbnr/2pppppp/1p6/p7/5P2/N2P4/PPP1P1PP/R1BQKBNR b KQkq - 0 3 8 169271250678
rnbqkbnr/1ppp1ppp/8/p3p3/4P3/1PN5/P1PP1PPP/R1BQKBNR b KQkq - 0 3 8 1070629411147
rnbqkbnr/2pppppp/1p6/p7/8/N2P2P1/PPP1PP1P/R1BQKBNR b KQkq - 0 3 8 276416763770
rnbqkbnr/2pppppp/1p6/p7/6P1/N2P4/PPP1PP1P/R1BQKBNR b KQkq - 0 3 8 262034237743
rnbqkbnr/1ppp1ppp/8/p3p3/8/1PN2P2/P1PPP1PP/R1BQKBNR b KQkq - 0 3 8 347453824108
rnbqkbnr/2pppppp/1p6/p7/8/N2P3P/PPP1PPP1/R1BQKBNR b KQkq - 0 3 8 213108594742
rnbqkbnr/2pppppp/1p6/p7/7P/N2P4/PPP1PPP1/R1BQKBNR b KQkq - 0 3 8 274943906865
rnbqkbnr/2pppppp/1p6/p7/8/3P4/PPP1PPPP/RNBQKBNR b KQkq - 1 3 8 237003061929
rnbqkbnr/1ppp1ppp/8/p3p3/5P2/1PN5/P1PPP1PP/R1BQKBNR b KQkq - 0 3 8 491330850307

The ten most recent perft(9) subtotals:

Code: Select all

rnbqkbnr/1pp1pppp/8/p2p4/8/1PN5/P1PPPPPP/R1BQKBNR w KQkq - 0 3 9 12295846574104
rnbqkbnr/1pppppp1/8/p6p/2P5/N7/PP1PPPPP/R1BQKBNR w KQkq - 0 3 9 4930646523606
1nbqkbnr/1ppppppp/r7/p7/2P5/N7/PP1PPPPP/R1BQKBNR w KQk - 1 3 9 6747745874436
1nbqkbnr/rppppppp/8/p7/2P5/N7/PP1PPPPP/R1BQKBNR w KQk - 1 3 9 4103551085137
r1bqkbnr/1ppppppp/n7/p7/2P5/N7/PP1PPPPP/R1BQKBNR w KQkq - 1 3 9 4324363979421
r1bqkbnr/1ppppppp/2n5/p7/2P5/N7/PP1PPPPP/R1BQKBNR w KQkq - 1 3 9 5036213881820
rnbqkb1r/1ppppppp/5n2/p7/2P5/N7/PP1PPPPP/R1BQKBNR w KQkq - 1 3 9 5176022169563
rnbqkb1r/1ppppppp/7n/p7/2P5/N7/PP1PPPPP/R1BQKBNR w KQkq - 1 3 9 4151881877841
rnbqkbnr/1ppp1ppp/4p3/p7/8/1PN5/P1PPPPPP/R1BQKBNR w KQkq - 0 3 9 13434812081312
rnbqkbnr/1ppppppp/8/8/p7/N2P4/PPP1PPPP/R1BQKBNR w KQkq - 0 3 9 7062576928176

The ten most recent perft(10) subtotals:

Code: Select all

rnbqkbnr/1ppppppp/8/p7/8/2N5/PPPPPPPP/1RBQKBNR b Kkq - 1 2 10 101933552154417
rnbqkbnr/1ppppppp/8/p7/8/N6N/PPPPPPPP/R1BQKB1R b KQkq - 1 2 10 89649475842393
rnbqkbnr/1ppppppp/8/p7/8/2N2N2/PPPPPPPP/R1BQKB1R b KQkq - 1 2 10 143695259623052
rnbqkbnr/1ppppppp/8/p7/8/NP6/P1PPPPPP/R1BQKBNR b KQkq - 0 2 10 96751671902306
rnbqkbnr/1ppppppp/8/p7/8/2N4N/PPPPPPPP/R1BQKB1R b KQkq - 1 2 10 113351075989581
rnbqkbnr/1ppppppp/8/p7/1P6/N7/P1PPPPPP/R1BQKBNR b KQkq - 0 2 10 123742798321122
rnbqkbnr/1ppppppp/8/p7/8/P1N5/1PPPPPPP/R1BQKBNR b KQkq - 0 2 10 114530965353808
rnbqkbnr/1ppppppp/8/p7/8/N1P5/PP1PPPPP/R1BQKBNR b KQkq - 0 2 10 144225591912302
rnbqkbnr/1ppppppp/8/p7/P7/2N5/1PPPPPPP/R1BQKBNR b KQkq - 0 2 10 94212916256726
rnbqkbnr/1ppppppp/8/p7/2P5/N7/PP1PPPPP/R1BQKBNR b KQkq - 0 2 10 121729545728858

The perft(11) subtotals:

Code: Select all

rnbqkbnr/1ppppppp/p7/8/8/N7/PPPPPPPP/R1BQKBNR w KQkq - 0 2 11 1865423942798492
rnbqkbnr/1ppppppp/p7/8/8/2N5/PPPPPPPP/R1BQKBNR w KQkq - 0 2 11 2458021022756805

[Sven]

In this context, an estimate is just that: an estimate. If it were possible to accurately predict the time it makes to calculate the sum, we'd already know what the sum was.

Subtotal results after 467 hours wall time:

0 of 20 perft(12)
2 of 400 perft(11)
52 of 5,362 perft(10)
1,020 of 72,078 perft(9)
15,073 of 822,518 perft(8) (ca. 1.83% of total)

Current total time estimate: 1,062 days (ca. 35 months)

If you were interested in avoiding that your estimates behave like a typical Windows Progress Bar (at "10%" displaying "15 seconds left" and at "99%" displaying "30 minutes left") then you would give my proposal a try

Is it difficult for you to publish one more number, the number of all nodes visited so far, in addition to what you already have?

Sven

[Sven]

If you were interested in avoiding that your estimates behave like a typical Windows Progress Bar (at "10%" displaying "15 seconds left" and at "99%" displaying "30 minutes left") then you would give my proposal a try

Just kidding of course, no offense intended
Sven

[sje]

Is it difficult for you to publish one more number, the number of all nodes visited so far, in addition to what you already have?

Just one number? I'll publish ALL the numbers!

https://public.me.com/chessnotation -> Perft -> Perft13 -> fcr1

Have fun.

[sje]

First benchmark results from the new machine (3.4 GHz Core i7-2600):

Perft(8): 26.2138 seconds
Perft(9): 233.047 seconds
Perft(10): 2939.82 seconds

All the totals so far are correct, and perft(11) is now in progress. I may re-run perft(12) as a final test before switching the perft(13) calculation to the new machine.