The mysterious crossover perft ply

[sje]

For perft estimators:

When the 50 move rule is observed, the longest chess game in slightly more than 12,000 ply. The very last perft(1) is at most 16.

The big question is: At what ply does the average branching factor first decrease?

[Sven]

When the 50 move rule is observed, the longest chess game in slightly more than 12,000 ply.

What is your source for the number of "slightly more than 12,000 ply"? The number that can be read frequently is 5,949 full moves = 11,898 plies. Guy Macon gives a smaller number: 11,799 plies. I think that number is quite accurate. After thinking about it I found only a minor correction into 11,796 plies (see my table below), although I am not sure whether all intermediate "99 ply" steps are forced to keep the game as long as possible:

Code: Select all

steps plies totalPlies cumulative action
   16   100       1600       1600 black BCFG pawns to rank 3
    1    99         99       1699 white A pawn to A3
    3   100        300       1999 white pieces capture black QBB
   15   100       1500       3499 white ADEH pawns to rank 6
    4   100        400       3899 white ADEH pawns capture black RRNN
    4   100        400       4299 white B7,C7,F7,G7 pawns promote
    1    99         99       4398 black A pawn to A6
   23   100       2300       6698 black ADEH pawns promote
    4   100        400       7098 white pieces to A2,D2,E2,H2,
                                  then black BCFG pawns capture these
    4   100        400       7498 black ADEH pawns promote
    1    99         99       7597 white B pawn to B3
   23   100       2300       9897 white BCFG pawns promote
    8   100        800      10697 white captures 8 black pieces
    1    99         99      10796 black captures 1 white piece
   10   100       1000      11796 black captures 10 white pieces

The procedure is based on the one by Guy Macon but slightly modified regarding the order of steps. I also changed the pawn files since I encountered the problem that with the original method of Macon the wBc1 and bBf8 could not move so that no enemy pawn could promote on their file. There could have been another fix for that but I found this one to be simple enough.

The very last perft(1) is at most 16.

What do you mean by "the very last perft(1)"?

The big question is: At what ply does the average branching factor first decrease?

I have run a small test using the "Peter1" method but with fw=0 (to save time) with the following results:

Code: Select all

depth fw cycles nodes    time       mcperft1 stddev   stddev% bf1   bf2
   12  0 832823 10000002 0:00:40.98 6.29E+22 1.01E+20 0.16%
   13  0 834013 10850011 0:00:45.08 1.98E+24 3.66E+21 0.18%   31.54
   14  0 835040 11700005 0:00:49.21 6.19E+25 1.30E+23 0.21%   31.17 31.36
   15  0 835935 12550002 0:00:53.47 2.02E+27 4.84E+24 0.24%   32.63 31.89
   16  0 836658 13400004 0:00:57.92 6.52E+28 1.72E+26 0.26%   32.27 32.45
   17  0 837292 14250015 0:01:02.25 2.17E+30 6.42E+27 0.30%   33.31 32.79
   18  0 837919 15100008 0:01:06.63 7.25E+31 2.40E+29 0.33%   33.41 33.36
   19  0 838405 15950008 0:01:11.19 2.46E+33 9.24E+30 0.38%   33.91 33.66
   20  0 838825 16800014 0:01:15.58 8.39E+34 3.59E+32 0.43%   34.13 34.02
   21  0 839202 17650002 0:01:20.22 2.89E+36 1.33E+34 0.46%   34.50 34.31
   22  0 839585 18500020 0:01:24.72 9.94E+37 5.34E+35 0.54%   34.32 34.41
   23  0 839854 19350015 0:01:29.42 3.54E+39 1.95E+37 0.55%   35.60 34.95
   24  0 840209 20200011 0:01:34.54 1.24E+41 8.02E+38 0.64%   35.17 35.39
   25  0 840387 21050019 0:01:38.46 4.41E+42 3.08E+40 0.70%   35.48 35.33
   26  0 840600 21900005 0:01:43.15 1.58E+44 1.27E+42 0.81%   35.78 35.63
   27  0 840796 22750008 0:01:48.41 5.76E+45 5.18E+43 0.90%   36.48 36.13
   28  0 840975 23600018 0:01:52.89 2.08E+47 2.08E+45 1.00%   36.17 36.32
   29  0 841093 24450023 0:01:57.34 7.56E+48 8.14E+46 1.08%   36.26 36.21
   30  0 841284 25300007 0:02:02.13 2.70E+50 3.18E+48 1.18%   35.74 36.00
   31  0 841285 26150027 0:02:06.95 9.78E+51 1.02E+50 1.05%   36.23 35.98
   32  0 841385 27000016 0:02:11.44 3.69E+53 5.54E+51 1.50%   37.72 36.97
   33  0 841541 27850033 0:02:16.00 1.35E+55 2.04E+53 1.51%   36.66 37.18
   34  0 841658 28700027 0:02:20.80 5.04E+56 8.85E+54 1.75%   37.30 36.98
   35  0 841568 29550034 0:02:25.36 1.93E+58 3.97E+56 2.06%   38.28 37.78
   36  0 841545 30400017 0:02:30.31 7.40E+59 1.54E+58 2.08%   38.33 38.30
   37  0 841577 31250024 0:02:35.51 2.68E+61 5.38E+59 2.01%   36.16 37.23
   38  0 841675 32100007 0:02:40.51 1.02E+63 2.62E+61 2.56%   38.23 37.18
   39  0 841623 32950011 0:02:45.07 3.80E+64 1.14E+63 3.00%   37.11 37.67
   40  0 841588 33800033 0:02:49.63 1.45E+66 4.08E+64 2.81%   38.18 37.64
   41  0 841573 34650013 0:02:55.13 5.28E+67 1.50E+66 2.83%   36.40 37.28
   42  0 841471 35500021 0:02:59.15 2.16E+69 9.74E+67 4.52%   40.87 38.57
   43  0 841430 36350001 0:03:04.36 9.13E+70 7.08E+69 7.76%   42.32 41.59
   44  0 841464 37200040 0:03:11.55 3.47E+72 3.04E+71 8.76%   38.05 40.13

Explanation of the rightmost columns:
mcperft1 = estimated perft (mean)
stddev = standard deviation of the mean
stddev% = stddev in percent of the mean
bf1 = mean(depth) / mean(depth-1)
bf2 = sqrt(mean(depth) / mean(depth-2))

It is obvious that the stddev% increases drastically towards the higher depths but nevertheless the estimated perft values should be accurate enough to get rough BF estimates. At least up to ply 28 where stddev% is not higher than 1% I think I can trust these BFs. According to that, and accounting for odd-even effects, it seems that there is some very small "intermediate crossover" at ply 25 (for odd plies) and at ply 30 (for even plies) before the bf1 values rise again later on. One surely needs to define, though, what exactly "crossover" should mean.

Sven

[sje]

I concede that the longest game may be slightly under 12 K ply instead of being slightly over that number.

Instead of saying "last perft", I should have said "maximum last branching factor", which is eight.

As for crossover, think of something like a discrete version of Rolle's Theorem. For perft(), this is the point (or the first point) where the average branching factor hits a (possibly local) maximum.