Perft(13) betting pool

[petero2]

My algorithm is quite similar to UCT but it is not exactly like UCT. Here is what I do:

1. Start with an in-memory tree with only one node representing the root position.

2. Do a random walk starting from the root, until a leaf node is reached. The probability controlling which child to visit are calculated from data in the child nodes. This probably causes some cache misses, but as a compensation I store moves in the tree nodes too, so I don't have to call the move generator until I reach a leaf node.

3. When a leaf node is reached, I decide if it should be split. A node is split if there are fewer than 4M nodes in the tree, the node has been visited at least 20 times, the remaining depth is > 1, and the "cost" for this node is at least 90% of the largest cost for a leaf node seen during the last 1000 random walks. "cost" is defined as sqrt(mean^2 + variance).

4. If a leaf node is split, child nodes are created for all legal moves.

5. If a leaf node is not split, I continue with a uniform probability random walk until the "perft" depth is reached. No hashing or tree node lookup is performed in this step. Just move generation and make/unmake moves.

6. As the recursion unwinds, the mean and variance estimates are updated for all visited in-memory tree nodes.

7. A single perft estimate computed from the just completed random walk is logged. If 1000 such values have been accumulated, print the average to standard output.

8. Go back to step 2.


I optimized my implementation a bit, and now it takes around 57 minutes on a 2.4 GHz Core2 CPU (using only one core) to generate 100e6 tree walks for perft(12). The code currently spends over 60% of the CPU time in a function that removes illegal moves from a pseudo-legal move list. I think this function can be optimized quite a lot though. Currently it just plays all moves and tests which moves leave the king in check.

The source code is here: http://web.comhem.se/petero2home/PerfTE ... 4.java.txt. If you actually want to run it, you also need BitBoard.java from CuckooChess.

[Daniel Shawul]

Well what you describe below is exactly UCT with Michel's formula AFAIAC. I had difficulty testing his formula because it lacked
the "visits" count for a node. Your step (3) decides if to split a node without comparing it to other sibling
nodes. To achieve that you needed more heuristic since you do not compare with other siblings to pick the best.
You just decide if a node is worth splitting by itself.
The basic idea of UCT tree search over plain MC (without tree) is to investigate (split) nodes worth splitting i.e bigger nodes for perft.
So when you do that you gain much of what UCT is meant for. The tree will dynamically grow towards the bigger nodes f.i in an LMR tree.
It will grow towards the best looking move for tree search. There are many methods to control how aggressively you want to control the growth of the tree..
I will go through your steps one by one:

My algorithm is quite similar to UCT but it is not exactly like UCT. Here is what I do:

1. Start with an in-memory tree with only one node representing the root position.

I start with the root node expanded (20 moves) but that is no difference. For a UCT search, you
have to return a move to play eventually so it is usual to start with a splitted root node.

2. Do a random walk starting from the root, until a leaf node is reached. The probability controlling which child to visit are calculated from data in the child nodes. This probably causes some cache misses, but as a compensation I store moves in the tree nodes too, so I don't have to call the move generator until I reach a leaf node.

This is the monte carlo part. A light MC visits all children uniformly while a heavy MC use different heuristics that usually make it slower but could be better overall.
BTW "heavy" and "light" is not my terminology. It is an accepted terminology in the GO programming field.

3. When a leaf node is reached, I decide if it should be split. A node is split if there are fewer than 4M nodes in the tree, the node has been visited at least 20 times, the remaining depth is > 1, and the "cost" for this node is at least 90% of the largest cost for a leaf node seen during the last 1000 random walks. "cost" is defined as sqrt(mean^2 + variance).

This is the formula part that you do differently. You do not compare to other siblings.
-> Your first criterion 4M nodes is to not run out of memory. There are two solution for this when used for tree search (a) Store less visited part of the tree on disk
(b) Prune parts of the tree. The latter is not applicable for perft because we need exact estimates.
-> Your second criterion UCT has it too. Mine is I think at 1000 right now. Lowering that should expand the tree more.
-> Your third criterion is Michel's formula a heuristic to have an idea of the cost of the node sqrt(mean^2 + variance)

4. If a leaf node is split, child nodes are created for all legal moves.

Same as UCT and a major component because you decide here to visit the bigger nodes. The tree
will be guided to the bigger nodes.

5. If a leaf node is not split, I continue with a uniform probability random walk until the "perft" depth is reached. No hashing or tree node lookup is performed in this step. Just move generation and make/unmake moves.

Same. A light MC search. If you start using your previous static heuristic for captures or the HT method, it will become a heavy MC.

6. As the recursion unwinds, the mean and variance estimates are updated for all visited in-memory tree nodes.

Same. I do exactly that and is easy for perft. But this back propagation step is more difficult
for tree search. Remi coulom had a complex Backup operator before UCT was invented.

7. A single perft estimate computed from the just completed random walk is logged. If 1000 such values have been accumulated, print the average to standard output.

8. Go back to step 2.

I optimized my implementation a bit, and now it takes around 57 minutes on a 2.4 GHz Core2 CPU (using only one core) to generate 100e6 tree walks for perft(12). The code currently spends over 60% of the CPU time in a function that removes illegal moves from a pseudo-legal move list. I think this function can be optimized quite a lot though. Currently it just plays all moves and tests which moves leave the king in check.

The source code is here: http://web.comhem.se/petero2home/PerfTE ... 4.java.txt. If you actually want to run it, you also need BitBoard.java from CuckooChess.

I think comparison by number of simulations should be fine. I was under the impression that it was the HT version you tested, in which case time tests would be more appropriate.

[Michel]

"cost" is defined as sqrt(mean^2 + variance)

My conjecture is that the correct measure to decide splitting is what
I call the "defect".

sqrt(mean^2 + variance)-mean

See here for the motivation

http://talkchess.com/forum/viewtopic.ph ... 24&t=39678

and here for some mathematical properties of the defect

http://www.talkchess.com/forum/viewtopi ... 99&t=39678

It might be wrong since I have not been able to test this theory (no time).

[Daniel Shawul]

My method doesn't actually use all of the 100 mil simulations. If you looked at the detailed data it only used 72mil simulations with about 30% wasted. I may be able to avoid that wastage because only reason I did it was to avoid bias of the mean in the previous method.

I tested this and I was worried for nothing. The old bias is gone now that I started using a second sequence of random numbers for calculating the mean. And I got an improved estimate with all of the 100 mil simulation. BTW you should consider doing that too unless you think you solved the problem in some other way...

Mean 6.285769e+016
Stddev 4.059742e+012

The StdDev is now very close to your best result. I still use a large N value before splitting compared to yours so I will start decreasing now.
Another problem I see now is that, I was reporting the variance for the first sequence of random numbers that I use for guiding the search. I guess it would be appropriate to report the second variance that the mean is calculated from. It maybe slightly larger.

[Daniel Shawul]

"cost" is defined as sqrt(mean^2 + variance)

My conjecture is that the correct measure to decide splitting is what
I call the "defect".

sqrt(mean^2 + variance)-mean

See here for the motivation

http://talkchess.com/forum/viewtopic.ph ... 24&t=39678

and here for some mathematical properties of the defect

http://www.talkchess.com/forum/viewtopi ... 99&t=39678

It might be wrong since I have not been able to test this theory (no time).

Ok. I will test it by picking the maximum among the sibling with

Code: Select all

X = sqrt(mean^2 + variance)-mean

My doubt about it is that the mean and variance when used alone as UCT formula more or less give the same result. So it seems redundant to have them if you keep moving statistic for both variance and mean. The sub-tree size ratio usually gives slightly higher results. See for instance the overlapping curves in my second plot.
You considered that the sub-tree size is not exactly known when deriving your formula.The best I have so far uses the formula below. The idea is that it is is a multi-armed bandit problem with its major goal of reducing variance so I estimated the _reduction_ of variance afte one more game by sigma^2/N - sigma^2/ N + 1

Code: Select all

X = variance / (visits + 1)

Who knows I may get better results with your formula.

[Ajedrecista]

Hi everybody:

In other thread, Mr. Edwards has posted the result of four Perft(11) subtotals of the Perft(13) count:

Na3, a6 ---> 1,865,423,942,798,492
Nc3, a6 ---> 2,458,021,022,756,805
b3, a6 ---> 2,110,456,650,953,864
a3, a6 ---> 1,562,327,606,120,748

I hope I do not post typos... I think these subtotals are a good test for probing your Monte Carlo methods (or the methods you want) for seeing the accuracy of them. So far, I have seen some estimates (in other positions) which errors are below |0.01%| if I remember correctly. Since I do not know about these methods (I only 'play with the numbers' to get estimates of whole Perft(13) and my best is ~ (1.9804681 ± 0.0002024)e+18), I ask if you can estimate these four subtotals, please. Thanks in advance.

Regards from Spain.

Ajedrecista.

[Daniel Shawul]

I tested Michel's formula and result is

Mean 6.28488e+16
Stddev 4.067365e+012

It comes in second along with the "calculated variance" formula I have. Earlier using the reduction of variance formula instead of the variance itself gave me a slight improvement. And it also seem to be the case here. Using variance alone should give same as Michel's formula too but I didn't test it. I have also included variance calculation for the second sequence and using the full 100mil simulation as well. It seems the stddev of the second sequence is slightly larger

Code: Select all

Time : 6466516ms Tree : nodes 1614127 depth 4/0 pps 15464 visits 100000000
0 h2h3   1.808455e+015 +- 6.906907e+011 1.815399e+015 +- 7.113876e+011   3174174     35268
0 h2h4   2.611763e+015 +- 8.300280e+011 2.620096e+015 +- 8.585781e+011   4303654     58513
0 g2g3   2.492309e+015 +- 8.108317e+011 2.497709e+015 +- 8.345404e+011   4044450     52102
0 g2g4   2.211145e+015 +- 7.637275e+011 2.218017e+015 +- 7.833472e+011   3395131     37105
0 f2f3   1.548109e+015 +- 6.390439e+011 1.552341e+015 +- 6.567933e+011   2462996     21350
0 f2f4   2.046800e+015 +- 7.347973e+011 2.050850e+015 +- 7.566386e+011   3593849     42568
0 e2e3   7.146504e+015 +- 1.373019e+012 7.162305e+015 +- 1.437084e+012  11242434    239616
0 e2e4   7.253183e+015 +- 1.383219e+012 7.262269e+015 +- 1.442706e+012  11247294    242570
0 d2d3   4.585442e+015 +- 1.099817e+012 4.589407e+015 +- 1.123575e+012   5905012     91432
0 d2d4   6.312233e+015 +- 1.290369e+012 6.326721e+015 +- 1.343273e+012   9445682    189179
0 c2c3   2.747365e+015 +- 8.513104e+011 2.751565e+015 +- 8.727413e+011   4610649     66595
0 c2c4   3.114154e+015 +- 9.063460e+011 3.119165e+015 +- 9.290840e+011   4938563     72533
0 b2b3   2.398929e+015 +- 7.954971e+011 2.407453e+015 +- 8.236375e+011   3994945     51757
0 b2b4   2.406209e+015 +- 7.966972e+011 2.412220e+015 +- 8.191831e+011   3969892     51515
0 a2a3   1.820376e+015 +- 6.929546e+011 1.824569e+015 +- 7.143713e+011   3219768     37075
0 a2a4   2.564674e+015 +- 8.225188e+011 2.573188e+015 +- 8.507408e+011   4210777     56829
0 g1h3   2.127477e+015 +- 7.491387e+011 2.133039e+015 +- 7.690881e+011   3522637     40919
0 g1f3   2.698640e+015 +- 8.437277e+011 2.703992e+015 +- 8.647789e+011   3963533     46915
0 b1c3   2.724611e+015 +- 8.477778e+011 2.729051e+015 +- 8.739067e+011   4980935     74174
0 b1a3   2.096467e+015 +- 7.436589e+011 2.099463e+015 +- 7.640610e+011   3773625     47335
Perft 6.271485e+016 +- 4.067365e+012  6.284882e+016 +- 4.203077e+012
move e2e4

[Michel]

It comes in second along with the "calculated variance" formula I have.

Thanks for testing.

Meanwhile I discovered a more or less fatal conceptual flaw in the back propagation part of my own tree splitting implementation. I had forgotten that it is not really a tree but a directed graph:-( so the parent of a node may not be unique).

I will start over from scratch.

[Michel]

I did some test runs with my tree growing perft implementation (ignoring the tree vs graph problem). The results are comparable to what has been posted here.

However when inspecting the generated tree it seems to be basically uniform (with the leafnodes distributed over the two largest depths).

This suggest that tree growing might be overkill for this problem. Just expanding
the tree to a certain depth and then using dynamically adapting weights
at the leaf nodes of the expanded subtree might be enough.

[Sven]

Hi everybody:

In other thread, Mr. Edwards has posted the result of four Perft(11) subtotals of the Perft(13) count:

Na3, a6 ---> 1,865,423,942,798,492
Nc3, a6 ---> 2,458,021,022,756,805
b3, a6 ---> 2,110,456,650,953,864
a3, a6 ---> 1,562,327,606,120,748

I hope I do not post typos... I think these subtotals are a good test for probing your Monte Carlo methods (or the methods you want) for seeing the accuracy of them. So far, I have seen some estimates (in other positions) which errors are below |0.01%| if I remember correctly. Since I do not know about these methods (I only 'play with the numbers' to get estimates of whole Perft(13) and my best is ~ (1.9804681 ± 0.0002024)e+18), I ask if you can estimate these four subtotals, please. Thanks in advance.

Regards from Spain.

Ajedrecista.

I have implemented the original method of Peter Österlund with uniform move selection probabilities (i.e. no weights, tree splitting, UCT, or other sophisticated methods ) in my C++ engine KnockOut. In my tests I always used fullDepth=0. For the four positions above I get the following perft(11) estimates, in each case after 5,000,000 random walks (where one random walk is one MC game for fullDepth=0):

Code: Select all

           1.Na3 a6      1.Nc3 a6      1.b3 a6       1.a3 a6
mean       1.866258E+15  2.456335E+15  2.113448E+15  1.562362E+15
true value 1.865424E+15  2.458021E+15  2.110457E+15  1.562328E+15
Error      8.340470E+11  1.686219E+12  2.990849E+12  3.415721E+1
Error%     0.0447%       0.0686%       0.1417%       0.0022%

[EDIT: the table above initially had wrong contents, fixed it.]

The last few digits may be rounded by Excel. I can't provide any standard deviation since I have not implemented the required functionality for that purpose, and do not store the sample values. Currently I only calculate the mean value of all samples.

Each of the four runs above took about 4 minutes on a Core2Duo 2.4GHz Laptop. I would guess this is quite slow.

For the initial position I get the following perft(12) result after 100,000,000 random walks (about 90 minutes):

Code: Select all

           perft(12) from initial pos
mean       62,836,664,667,437,300
true value 62,854,969,236,701,700
Error      1.830457E+13
Error%     0.0291%

I also ran a quick test of perft(13) with only 10,000,000 random walks (about 9 minutes) and got the following result:

Code: Select all

           perft(13) from initial pos
mean       1,981,794,079,918,660,000

Sven