Perft(13) betting pool

[hgm]

I have got the final verdict on the accuracy of the 6-ply full width:

Code: Select all

perft(5) tot =  1499 mean = 19851211.416278 std =  59.598497% / sqrt(99.9M) = 0.00596% (cumulative 0.0107%)
perft(4) tot =  1282 mean =   736316.900936 std =  47.666721% / sqrt(83.0M) = 0.00524% (cumulative 0.00900%)
perft(3) tot =  1150 mean =    25486.833043 std =  41.495897% / sqrt(74.4M) = 0.00581% (cumulative 0.00732%)
perft(2) tot =  1025 mean =      906.915122 std =  28.374558% / sqrt(66.1M) = 0.00349% (cumulative 0.00456%)
perft(1) tot =   975 mean =       29.978462 std =  21.894053% / sqrt(62.5M) = 0.00277%

I calculated the mean and std deviation of terminal sub-trees of different depth of the perft(12) tree. For this I used the same sampling method as I use in the perft estimation, i.e. attenuate by a factor 32 each ply after the 6th. But I only take about 1000 of the thus selected sub-trees for complete expansion. (Which should be more than enough for an accurate std deviation estimate.)

I then divide this std deviation of sub-tree size by the number of sub-trees I sample in the perft(12) estimation (which is the nr of nodes at that level, divided by the applicable power of 32). This gives the std deviation introduced by the sampling of that level.

Finally I quadratically add the standard deviations of all levels together, which leads to a total of 0.00107%.

Note that there is also an odd-even effect in the variances: the difference between a 2- and 3-ply tree-size variance is much larger than between 1- and 2-ply. This is of course because positions with high mobility (= perft(1)) tend to have daughters with high mobility as well, but not necessarily above-average opponent mobility.

Due to this depth-correlation of mobilities, it would make sense to select moves from nodes with high mobility with a larger probability. By how much would be dependent on the remaining depth. This could be implemented, but the accounting would become more complex: in stead of single accepted/rejected counters per level, you would have to keep such a counter for every mobility (ignoring checks). And you would have to weight the branches relative to each other, as Peter does, by their inverse acceptance probability).

Another remark is that the attenuation 1/32 seems pretty optimal: it more or less flattens out the increase in variance towards lower plies, because it puts more samples there. Perhaps a little bit could be gained by reducing the number of samples at the 10-th ply, and devoting them to the 7th or 9th. (Although samples at the 10th ply are cheaper than at the 7th, because the remaining path is shorter.)

[Michel]

which leads to a total of 0.00107%.

which is

6.726159e+11

which seems quite spectacular.

However the actual error in your result is

6.284515e+16-62854969236701747=-9.819237e+12

which is 15 times bigger.

[Daniel Shawul]

I believe it is 0.0107% not 0.00107% as shown in the table.

[Michel]

I believe it is 0.0107% not 0.00107% as shown in the table.

Yes that makes sense. In that case UCT is still a bit ahead

4e12 * sqrt(12 * 100e6)=1.4e17

against

6.726159e+12 * sqrt(510055595 )=1.52e+17

but not by much.

As Sven was pointing out, perhaps the important factor 12 can be reduced by organizing the computations more cleverly.

[Daniel Shawul]

Besides that, we are comparing apples and oranges. The UCT part has been compared with uniform selection and shown to give a significant improvement. Now if HG's selective method catches up with UCT it only means Peter's MC is hurting it since I use that. Also my test with UCT never managed to expand all leaf nodes at depth=6 so the comparison should be done at depth=5 ...
Why don't we do a direct comparison of HG's selective method with Peter's MC for a depth=0 and depth=5 expansion. We can then clearly see which one is better. We can do comparison based on nodes count only inside the selective (MC) part i.e excluding all nodes in the full width section since both do it the same way there...

[Sven]

I believe it is 0.0107% not 0.00107% as shown in the table.

Yes that makes sense.

I don't think so, the 0.0107% is from the table HG posted and refers to perft(5) subtree results but the 0.00107% is from this part of his text:

Finally I quadratically add the standard deviations of all levels together, which leads to a total of 0.00107%.

where the matching of the digits 107 seems to be coincidental.

As Sven was pointing out, perhaps the important factor 12 can be reduced by organizing the computations more cleverly.

My stronger proposal was to simply add a node counter instead of estimating its value with a "hocus pocus" formula

Sven

[Michel]

Finally I quadratically add the standard deviations of all levels together, which leads to a total of 0.00107%.

The table lists the cumulative totals. I think the extra zero is simply a typo.

[Sven]

Finally I quadratically add the standard deviations of all levels together, which leads to a total of 0.00107%.

The table lists the cumulative totals. I think the extra zero is simply a typo.

O.k., might be true.
Sven

[hgm]

I believe it is 0.0107% not 0.00107% as shown in the table.

Indeed, that was a typo in the text.

This is my proposal for an improved method, which now becomes a cross-over between my old method and Peter's:

Code: Select all

double accepted[MAXPLY], total[MAXPLY];

double perft(int depth, double w)
{
  int res=0;
  double weight;
  n = MoveGen(); // returns number of legal moves (ignoring existing checks)
  weight = f(n,depth);
  for(ALL_MOVES) {
    if(depth == 1) res += w; else
    if(AcceptWithProbability(1./weight)) {
      accepted[depth += weight;
      MakeMove();
      res += perft(depth-1, w*weight);
      UnMake();
    }
    total[depth]++;
  }
  return res;
}

The final result is multiplied by (total[d]/accepted[d]) for every level d. Initial call is perft(12, 1.);.

The finesse is in the function f(n, depth), which determines the weights. In my original method f(n, depth) would always be 32. To make it more like Peter's original method it would be n, so that on average one move per node will be accepted. (Of course it still differs, because he uses exactly one move per node.) But this is a correction in the wrong direction. What I would do in stead is take f(n, d) = 32*n^((d-1)/2), where (d-1)/2 (integer division) is the number of ply the current stm has to move in future nodes within the depth.

[Daniel Shawul]

This game ain't over yet. I did a 4-ply width experiment with Peter's method and it has passed HG's result 500 mil nodes. Peter please get your hands dirty ! I counted the total nodes and the result after about 500 mil total nodes is:

Code: Select all

499M 6.286464e+016 +- 6.445827e+012 499945850 5.92sec
501M 6.286453e+016 +- 6.426359e+012 501532957 5.94sec
nodes 6.28645e+016
time 1895.34 sec

That is about (6.42e12/ 6.28549e16) * 100% = 0.0102%. That is better than all of HG's resuls unless I made a mistake.

The total noes count increases by about 1587000 every time perft is called. I calculated for all the perft(4) nodes as follows: Remaining depth is 12 - 4 = 8 so 197281 * 8 = 1578248 which is about as expected.

Here is the Log file