Perft(13) betting pool

[Daniel Shawul]

Well then shift a little to the left and sample there more often !?

Why not just 'sample' the move that has the exact right size sub-tree, and disregard all others?

Why not get the exact proportion for each move from the magician and do just one simulation ?

[Daniel Shawul]

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.

[Michel]

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

[Daniel Shawul]

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?

[Daniel Shawul]

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.

[Michel]

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.

This was your example remember. You claimed that your method was especially suited for this example.

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.

[Daniel Shawul]

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.

This was your example remember.

So no matter your best efforts , my sampling range will not be the largest i.e the first move as you are doing now.

Oops your best example even didn't get it to the first probably around the 3rd or 4th move. Your point being ?

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.

[petero2]

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).

I tried to construct a heuristic weight function to improve the perft(13) estimate. I used this code:

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 &#40;fullDepth <= 0&#41; &#123;
            int N = moves.size;
            double weights&#91;&#93; = new double&#91;N&#93;;
            double wAccum&#91;&#93; = new double&#91;N&#93;;
            double wTotal = 0;
            for &#40;int i = 0; i < N; i++) &#123;
                double w = getWeight&#40;moves.m&#91;i&#93;, depth&#41;;
                weights&#91;i&#93; = w;
                wTotal += w;
                wAccum&#91;i&#93; = wTotal;
            &#125;
            double r = rnd.nextDouble&#40;) * wTotal;
            int idx = Arrays.binarySearch&#40;wAccum, r&#41;;
            if &#40;idx < 0&#41; idx = -&#40;idx+1&#41;;

            pos.makeMove&#40;moves.m&#91;idx&#93;, ui&#41;;
            double tmp = perfTWeightSampled&#40;depth - 1, fullDepth - 1&#41;;
            pos.unMakeMove&#40;moves.m&#91;idx&#93;, ui&#41;;
            nodes += tmp * wTotal / weights&#91;idx&#93;;
        &#125; else &#123;
            for &#40;int mi = 0; mi < moves.size; mi++) &#123;
                Move m = moves.m&#91;mi&#93;;
                pos.makeMove&#40;m, ui&#41;;
                nodes += perfTWeightSampled&#40;depth - 1, fullDepth - 1&#41;;
                pos.unMakeMove&#40;m, ui&#41;;
            &#125;
        &#125;
        moveGen.returnMoveList&#40;moves&#41;;
        return nodes;
    &#125;

Note that a getWeight function that always returns 1 corresponds to my original method, which gives an estimated standard deviation of 2.55e16 for one call to perfTWeightSampled(13, 3). The "best" weight function I found looks like this:

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;
        }
    }

With this function the estimated standard deviation is 2.15e16 for one call to perfTWeightSampled(13, 3), which means I get the same accuracy as my original method with only (2.15/2.55)^2=0.71 times as many samples. However, my getWeight function is quite expensive, because it tests if the move gives check to the opponent king, so I suspect that this method would not really give much improvement in terms of standard deviation for a given amount of CPU time.

Are there any other ideas how to construct the getWeight function?

[Daniel Shawul]

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 ?

[Sven]

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.

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.

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