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.
Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 689
- Joined: Mon Apr 19, 2010 7:07 pm
- Location: Sweden
- Full name: Peter Osterlund
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Defect of a node?
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:
have to return a move to play eventually so it is usual to start with a splitted root node.
BTW "heavy" and "light" is not my terminology. It is an accepted terminology in the GO programming field.
-> 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)
will be guided to the bigger nodes.
for tree search. Remi coulom had a complex Backup operator before UCT was invented.
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:
I start with the root node expanded (20 moves) but that is no difference. For a UCT search, you
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.
have to return a move to play eventually so it is usual to start with a splitted root 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.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.
BTW "heavy" and "light" is not my terminology. It is an accepted terminology in the GO programming field.
This is the formula part that you do differently. You do not compare to other siblings.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).
-> 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)
Same as UCT and a major component because you decide here to visit the bigger nodes. The tree4. If a leaf node is split, child nodes are created for all legal moves.
will be guided to the bigger nodes.
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.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. I do exactly that and is easy for perft. But this back propagation step is more difficult6. As the recursion unwinds, the mean and variance estimates are updated for all visited in-memory tree nodes.
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 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.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.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Defect of a node?
My conjecture is that the correct measure to decide splitting is what"cost" is defined as sqrt(mean^2 + variance)
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).
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Defect of a node?
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...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.
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.Mean 6.285769e+016
Stddev 4.059742e+012
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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Defect of a node?
Ok. I will test it by picking the maximum among the sibling withMichel wrote:My conjecture is that the correct measure to decide splitting is what"cost" is defined as sqrt(mean^2 + variance)
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).
Code: Select all
X = sqrt(mean^2 + variance)-mean
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)
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Yet another piece of perft(13)
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.
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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Defect of a node?
I tested Michel's formula and result is
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 largerMean 6.28488e+16
Stddev 4.067365e+012
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
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Defect of a node?
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.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Defect of a node?
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.
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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Yet another piece of perft(13)
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):Ajedrecista wrote: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.
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%
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%
Code: Select all
perft(13) from initial pos
mean 1,981,794,079,918,660,000
Last edited by Sven on Tue Aug 09, 2011 6:12 pm, edited 1 time in total.