Perft(13), the result

[sje]

This thread is the continuation of http://www.talkchess.com/forum/viewtopic.php?t=43827

The perft(13) run has almost completed some 426 days after it started. The run has been performed with ONE program running on ONE machine, continuously except for a dozen or so power outages which consumed a hundred hours or so of wall time.

At the time of this post, the run has completed 399 of the required 400 draft 11 calculations and the last one should finish in a few hours.

However, that last draft 11 count had already been calculated on a different machine, and I have put together that number with the other 399 results to get a result for perft(13). So I have an answer! But it is not yet the single machine/single program calculation answer which will soon arrive.

[Ajedrecista]

Hello Steven:

This thread is the continuation of http://www.talkchess.com/forum/viewtopic.php?t=43827

The perft(13) run has almost completed some 426 days after it started. The run has been performed with ONE program running on ONE machine, continuously except for a dozen or so power outages which consumed a hundred hours or so of wall time.

At the time of this post, the run has completed 399 of the required 400 draft 11 calculations and the last one should finish in a few hours.

However, that last draft 11 count had already been calculated on a different machine, and I have put together that number with the other 399 results to get a result for perft(13). So I have an answer! But it is not yet the single machine/single program calculation answer which will soon arrive.

I took 399 draft 11 results from here, I removed FEN strings by hand and wrote a very short programme in Fortran 95 for sum all these 399 integers. The sum is 1,972,627,708,215,314,878 if I did things correctly; if I sum the draft 11 of 1.- e4, Nh6 that you calculated the last week (8,439,066,785,081,361), I obtain Perft(13) = 1,972,627,708,215,314,878 + 8,439,066,785,081,361 = 1,981,066,775,000,396,239... the same as the result by Paul Byrne! Congratulations to both of you.

http://www.talkchess.com/forum/viewtopi ... ht=#432579

...

1,981,066,775,000,396,239

...

-paul

Regards from Spain.

Ajedrecista.

[sje]

To extract the last field of the records in the draft11 file, use the Unix cut program:

Code: Select all

cut -f 8 -d ' ' <draft11 >c11

To add a bunch of big integers, use the Unix bc program or Common Lisp (like sbcl).

As mentioned above, the 399+1 result does confirm Paul's result from last November. The single program/single machine result should appear in a few hours. I am sure that it will be identical.

[sje]

Let's see what Lisp says with its "r" format directive:

Code: Select all

* (format nil "~r" 1981066775000396239)

"one quintillion nine hundred eighty-one quadrillion sixty-six trillion seven hundred seventy-five billion three hundred ninety-six thousand two hundred thirty-nine"

[Daniel Shawul]

Let's see what Lisp says with its "r" format directive:

Code: Select all

* (format nil "~r" 1981066775000396239)

"one quintillion nine hundred eighty-one quadrillion sixty-six trillion seven hundred seventy-five billion three hundred ninety-six thousand two hundred thirty-nine"

Congratulations,your perseverance finally paid off. I will check later by how many miles I missed the exact value
Daniel

[sje]

The main run has just completed, taking fourteen months to the day.

The earlier 399+1 confirmation is confirmed with the single program/single machine result. Here in the ply one expansion, the first level of proof:

Code: Select all

Na3 63,558,937,554,457,795
Nc3 84,663,535,534,493,517
Nf3 82,432,607,453,980,338
Nh3 64,658,238,653,217,709
a3 54,239,338,583,061,004
a4 79,097,912,720,718,078
b3 72,470,867,205,869,240
b4 73,447,518,515,970,566
c3 85,630,662,795,901,357
c4 97,580,419,694,352,415
d3 141,516,447,571,471,634
d4 213,234,089,428,603,755
e3 241,123,823,129,738,679
e4 246,890,754,665,609,637
f3 43,376,546,076,090,990
f4 61,027,789,644,649,681
g3 75,907,561,722,826,536
g4 65,566,769,916,823,116
h3 53,765,991,918,774,270
h4 80,876,962,213,785,922 

Depth: 13   Count: 1,981,066,775,000,396,239

The 20 ply one positions can be seen at http://dl.dropbox.com/u/31633927/Perft/Perft13/draft12 and these form the first level of proof.

The 400 ply two positions can be seen at http://dl.dropbox.com/u/31633927/Perft/Perft13/draft11 and these form the second level of proof.

For each of the above two links, the entries are presented in the order in which they were generated.

All of the perft(n) calculations to date are here: https://dl.dropbox.com/u/31633927/Perft/InitialPosition

[Jan Brouwer]

Congratulations!, nice extension to integer sequence A048987.

Hmmmm, I wonder, does anyone happen to know perft 14?

Jan

[stegemma]

It is interesting that the most played openings seems to be the ones that start with the moves that have the biggest perft(13):

• e4 246,890,754,665,609,637
  e3 241,123,823,129,738,679
  d4 213,234,089,428,603,755
  d3 141,516,447,571,471,634
  c4 97,580,419,694,352,415
  c3 85,630,662,795,901,357
  Nc3 84,663,535,534,493,517
  Nf3 82,432,607,453,980,338
  h4 80,876,962,213,785,922
  a4 79,097,912,720,718,078
  g3 75,907,561,722,826,536
  b4 73,447,518,515,970,566
  b3 72,470,867,205,869,240
  g4 65,566,769,916,823,116
  Nh3 64,658,238,653,217,709
  Na3 63,558,937,554,457,795
  f4 61,027,789,644,649,681
  a3 54,239,338,583,061,004
  h3 53,765,991,918,774,270
  f3 43,376,546,076,090,990

Maybe chess players already knows that numbers just by intuition?

[Adam Hair]

Congratulations for reaching the completion of the computation. Very few have the perseverance to take on and finish this challenge, especially given the power problems you have had.

[JuLieN]

Congratulation Stevens for this enormous computing!

(The bad news is: getting one ply deeper at this speed would necessitate 23 years and four months ).

I believe Peter Österlund got the most precise bet by far :

My bet is:

1981075670675789312 (estimated value)
0000059997681255613 (estimated standard deviation)

My method uses N plies of full-width search, then 13-N plies of pruned
search. In the pruned part of the tree I search exactly one child node
for each node. (This seemed to give a lower standard deviation per
time unit than H.G.Muller's method that has a fixed move acceptance
probability if I understood correctly.)

I set N=3, called the search method repeatedly in an infinite loop,
then let it run in the background until I had around 180000 samples.
I finally computed the average and standard deviation of all samples.

The code looks basically like this:

Code: Select all

private final void doPerfTSampled() {
    while (true)
        System.out.printf("%d\n", perfTSampled(13, 3));
}

private final long perfTSampled(int depth, int fullDepth) {
    MoveGen.MoveList moves = moveGen.pseudoLegalMoves(pos);
    MoveGen.removeIllegal(pos, moves);
    if ((depth == 1) || (moves.size == 0))
        return moves.size;
    UndoInfo ui = new UndoInfo();
    if (fullDepth <= 0) {
        int r = rnd.nextInt(moves.size);
        pos.makeMove(moves.m[r], ui);
        long nodes = perfTSampled(depth - 1, fullDepth - 1);
        pos.unMakeMove(moves.m[r], ui);
        return nodes * moves.size;
    } else {
        long nodes = 0;
        for (int mi = 0; mi < moves.size; mi++) {
            pos.makeMove(moves.m[mi], ui);
            nodes += perfTSampled(depth - 1, fullDepth - 1);
            pos.unMakeMove(moves.m[mi], ui);
        }
        return nodes;
    }
}

His prediction was remarkably close to the final result!