Perft(13) betting pool

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Defect of a node?

Post by hgm » Fri Aug 12, 2011 2:53 pm

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.)
Last edited by hgm on Fri Aug 12, 2011 3:10 pm, edited 1 time in total.

Michel
Posts: 1966
Joined: Sun Sep 28, 2008 11:50 pm

Re: Defect of a node?

Post by Michel » Fri Aug 12, 2011 3:07 pm

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
Posts: 3504
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Defect of a node?

Post by Daniel Shawul » Fri Aug 12, 2011 3:18 pm

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

Michel
Posts: 1966
Joined: Sun Sep 28, 2008 11:50 pm

Re: Defect of a node?

Post by Michel » Fri Aug 12, 2011 3:29 pm

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
Posts: 3504
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Defect of a node?

Post by Daniel Shawul » Fri Aug 12, 2011 3:38 pm

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
Posts: 3698
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Defect of a node?

Post by Sven » Fri Aug 12, 2011 4:22 pm

Michel wrote:
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.
Michel wrote: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
Posts: 1966
Joined: Sun Sep 28, 2008 11:50 pm

Re: Defect of a node?

Post by Michel » Fri Aug 12, 2011 4:26 pm

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
Posts: 3698
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Defect of a node?

Post by Sven » Fri Aug 12, 2011 4:37 pm

Michel wrote:
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

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Defect of a node?

Post by hgm » Fri Aug 12, 2011 4:49 pm

Daniel Shawul wrote:I believe it is 0.0107% not 0.00107% as shown in the table.
Indeed, that was a typo in the text. :oops:

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
Posts: 3504
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Defect of a node?

Post by Daniel Shawul » Fri Aug 12, 2011 5:27 pm

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

Post Reply