Why not get the exact proportion for each move from the magician and do just one simulation ?hgm wrote:Why not just 'sample' the move that has the exact right size sub-tree, and disregard all others?Daniel Shawul wrote:Well then shift a little to the left and sample there more often !?
Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
And you made a mistake again. That is what you pay for trying to be the magician.
My estimate, _if I believe your calculation_, is (2^d/2) * d not just 2^(d/2)...
I can even sample many moves in the middle equally so I don't see your point when you just multiply the middle move by d. What If I average the inter-quartile range or use a skewed pdf.
My estimate, _if I believe your calculation_, is (2^d/2) * d not just 2^(d/2)...
I can even sample many moves in the middle equally so I don't see your point when you just multiply the middle move by d. What If I average the inter-quartile range or use a skewed pdf.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Perft(13) betting pool
Sorry for being unclear. I said the _median_ is 2^(d/2). To know the value around which you sample.
Your estimate is (d+1)*(2^(d/2)) which is much smaller than 2^(d+1)
for large d. Take d=20 in a typical middle game position.
(d+1)*2^(d/2)=21504
2^(d+1)=2097152
Your estimate is (d+1)*(2^(d/2)) which is much smaller than 2^(d+1)
for large d. Take d=20 in a typical middle game position.
(d+1)*2^(d/2)=21504
2^(d+1)=2097152
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Two things: One I said I am going to take more samples towards the mean.
Not just the middle. The average obviously will be shifted towards the left.
Second, how did you come up with an EBF of 2?
Not just the middle. The average obviously will be shifted towards the left.
Second, how did you come up with an EBF of 2?
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
With your assumed EBF, I would sample those move with 2^(d+1) / d more often. 2^(d+1) / d = 2^x. So that would be x = d + 1 - ln(d) / ln(2)
This is the second time you would contrive the examples to pull the mean closer to the larger values. Small EBF and large depth! be fair.
For d = 20, x = 20 + 1 - ln(20)/ln(2) = 21 - 4.32 = 16.68. So no matter your best efforts , my sampling range will not be the largest i.e the first move as you are doing now.
This is the second time you would contrive the examples to pull the mean closer to the larger values. Small EBF and large depth! be fair.
For d = 20, x = 20 + 1 - ln(20)/ln(2) = 21 - 4.32 = 16.68. So no matter your best efforts , my sampling range will not be the largest i.e the first move as you are doing now.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Perft(13) betting pool
This was your example remember. You claimed that your method was especially suited for this example.This is the second time you would contrive the examples to pull the mean closer to the larger values. Small EBF and large depth! be fair.
If you are going to sample around the mean then you have to know what the mean is and we are back to square one.
Last edited by Michel on Tue Jul 26, 2011 6:01 pm, edited 1 time in total.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Oops your best example even didn't get it to the first probably around the 3rd or 4th move. Your point being ?Michel wrote:This was your example remember.This is the second time you would contrive the examples to pull the mean closer to the larger values. Small EBF and large depth! be fair.
So no matter your best efforts , my sampling range will not be the largest i.e the first move as you are doing now.
I said sample more towards the mean which probably lies around the middle. You misunderstood that as if I told you to take the median...
Well to make it clear estimate the mean and sample around that more often, and that will give you a head start on estimating the mean. Anyway my point was to demonstrate a simple heuristic even with a fixed multiplier..
You guys try again and again to shift the mean towards the larger sub-tree size in order to get the mean and variance correct at the same time.
-
- Posts: 688
- Joined: Mon Apr 19, 2010 7:07 pm
- Location: Sweden
- Full name: Peter Osterlund
Re: Perft(13) betting pool
I tried to construct a heuristic weight function to improve the perft(13) estimate. I used this code:Michel wrote: I did a quick variance computation for the non uniform Peter method.
It seems that to get the smallest variance, moves that reduce the tree should be selected less frequently (and of course to get an unbiased estimator the pay off should be the inverse of the selection probabilty as in HGM's post).
I think this applies to captures since these reduce the tree permanently (and not all captures are equal in this respect).
There is an exact formula for the optimal weights but since the terms are unknown it is not clear if this is useful (although one could use heuristics to estimate the terms).
Code: Select all
private final double perfTWeightSampled(int depth, int fullDepth) {
double nodes = 0;
MoveGen.MoveList moves = moveGen.pseudoLegalMoves(pos);
MoveGen.removeIllegal(pos, moves);
if ((depth == 1) || (moves.size == 0)) {
int ret = moves.size;
moveGen.returnMoveList(moves);
return ret;
}
UndoInfo ui = new UndoInfo();
if (fullDepth <= 0) {
int N = moves.size;
double weights[] = new double[N];
double wAccum[] = new double[N];
double wTotal = 0;
for (int i = 0; i < N; i++) {
double w = getWeight(moves.m[i], depth);
weights[i] = w;
wTotal += w;
wAccum[i] = wTotal;
}
double r = rnd.nextDouble() * wTotal;
int idx = Arrays.binarySearch(wAccum, r);
if (idx < 0) idx = -(idx+1);
pos.makeMove(moves.m[idx], ui);
double tmp = perfTWeightSampled(depth - 1, fullDepth - 1);
pos.unMakeMove(moves.m[idx], ui);
nodes += tmp * wTotal / weights[idx];
} else {
for (int mi = 0; mi < moves.size; mi++) {
Move m = moves.m[mi];
pos.makeMove(m, ui);
nodes += perfTWeightSampled(depth - 1, fullDepth - 1);
pos.unMakeMove(m, ui);
}
}
moveGen.returnMoveList(moves);
return nodes;
}
Code: Select all
private final double getWeight(Move m, int depth) {
double w = MoveGen.givesCheck(pos, m) ? 0.20 : 1;
int cap = pos.squares[m.to];
switch (cap) {
case Piece.WPAWN: case Piece.BPAWN:
return w * 0.95;
case Piece.WKNIGHT: case Piece.BKNIGHT:
return w * 0.95;
case Piece.WBISHOP: case Piece.BBISHOP:
return w * 0.90;
case Piece.WROOK: case Piece.BROOK:
return w * 0.85;
case Piece.WQUEEN: case Piece.BQUEEN:
return w * 0.80;
default:
return w;
}
}
Are there any other ideas how to construct the getWeight function?
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Can you also print out the means ? For example after 1 million games, starting Monte carlo from the root, I get around 1.9806e18 with uniform PRNG. Can you do an unbiased estimate using weighing _all_ captures by 80%,90% 95% 100% 105% 110% , so that we can see how the mean is affected ?
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Perft(13) betting pool
My implementation counts shorter games as "illegal" games (i.e. "does not count them as legal"), and therefore also increments the total games counter for these. This is how I understood the initial description given by Uri, and this is also what I think is most natural. But it may be wrong, or not optimal, I don't know yet.Daniel Shawul wrote:Sven,
Uri is saying that he did not mean to count shorter games when he said count legal games. I see no where where he tells that shorter games should not be included but now he is claiming that is what he had in mind.
Did you increment the legal games count when shorter games are encountered or even the total games count. With the bit higher estimate i.e 1.997e18, I thought that could be the case.
I think there is some confusion about the term "counting" in this context. The proposal you made a couple of posts above seems to imply that shorter games should not affect both the count of legal games and the total count of games. Could you please explain again why you expect this to be better than not doing so? You asked me to implement it but I did not do it so far, and would like to understand it first.
How does Peter's method deal with shorter games?
Should we even consider to exclude game-terminating moves from the list of generated moves (which might become expensive) so that our random games are always full-length games?
One more note regarding the estimate of 1.997...e+18 I published a while ago after quickly implementing the method of Uri in my engine. There are at least two factors influencing the accuracy of that number:
1) the low number of sample games I was able to play so far,
2) the fact that the perft(1) upper bound values U(i) are only approximated values u(i) <= U(i) for all i > 7 (or i > 8, I don't remember).
That might explain why this estimate is different from some other estimates given here. The value is simply not accurate enough yet. My CPU time available for such tasks is limited, so please be patient ...
Sven