Perft(13) betting pool

[petero2]

The idea with the "moveGen" metric was that if you assume that most of the CPU time is spent generating legal move lists, it would be a fair comparison to use (standard deviation) * sqrt(number of generated move lists) as a performance metric. If a program does a significant amount of computation that is not move list generation, this metric will of course be "too good" compared to other programs that spend almost all their time generating move lists. My "Peter1" method spends about 80% of the CPU time generating legal move lists, according to the java profiler.

Regarding the need for a second sequence of random numbers, I also had problems which I think was caused by the same effect. See http://talkchess.com/forum/viewtopic.ph ... 77&t=39678. I didn't find a solution to that problem, so instead I switched to the "Peter2" method.

[Daniel Shawul]

@HG, I know why so I didn't need an explanation. Just wanted to do some numerical comparison if you have them. Never mind.

[Daniel Shawul]

Regarding the need for a second sequence of random numbers, I also had problems which I think was caused by the same effect. See http://talkchess.com/forum/viewtopic.ph ... 77&t=39678. I didn't find a solution to that problem, so instead I switched to the "Peter2" method.

Well I thought I solved it with second sequence of random numbers which at least worked for the depth limited version. Maybe I didn't. But again since you do grow a tree in Peter2, the problem should still be there , no ?

[Michel]

My "Peter1" method spends about 80% of the CPU time generating legal move lists,

I just profiled my implementation (in GNU Chess) and for me it is even 95%
(if I interprete the gprof output correctly). 86% of the total time is used to
filter out illegal pseudo legal moves.

It's curious that your implementation of Peter1 seems to be twice as fast as mine even though mine is written in C. What hardware are you using?

[petero2]

Regarding the need for a second sequence of random numbers, I also had problems which I think was caused by the same effect. See http://talkchess.com/forum/viewtopic.ph ... 77&t=39678. I didn't find a solution to that problem, so instead I switched to the "Peter2" method.

Well I thought I solved it with second sequence of random numbers which at least worked for the depth limited version. Maybe I didn't. But again since you do grow a tree in Peter2, the problem should still be there , no ?

No, because the Peter2 method does a series of random walks from the root. The first part (up to the leaf node) is weighted, the second part is unweighted. But both parts have weight * probability = 1, so a single random walk will generate an unbiased estimate. The final result is just the average value of all random walk values, which is of course unbiased when all individual values are unbiased.

The fact that the weights change dynamically is not a problem, because as long as weight * probability = 1, the result is still unbiased.

[Daniel Shawul]

So what I do the same thing? The fact that you do non-uniform sampling doesn't mean it makes it biased.
I never use weights inside my tree or in the montecarlo part. I just do splitting which Peter does too. I think the problem maybe the fact that I introduced wasted nodes that I didn't have in the other tests I did before. I knew that had an effect so I only recently introduced it..

[petero2]

My "Peter1" method spends about 80% of the CPU time generating legal move lists,

I just profiled my implementation (in GNU Chess) and for me it is even 95%
(if I interprete the gprof output correctly). 86% of the total time is used to
filter out illegal pseudo legal moves.

It's curious that your implementation of Peter1 seems to be twice as fast as mine even though mine is written in C. What hardware are you using?

My hardware is, according to /proc/cpuinfo: Intel(R) Core(TM)2 Duo CPU T9500 @2.60GHz

My move generator is a standard variable shift magic bitboard generator. I agree with HGM that for generating pseudo-legal move lists, bitboard is probably no advantage. But I think it could still be an advantage for generating legal move lists, because of opportunities to optimize in-check detection.

I got a significant speed up after removing all unused evaluation stuff from my code. I also optimized the "removeIllegal" function to first decide if the side to move is in check, then quickly sort out the easy cases. My code spends a little over 40% of the time in the removeIllegal function. The function looks like this:

Code: Select all

public static final void removeIllegal(Position pos, MoveList moveList) {
    int length = 0;
    UndoInfo ui = new UndoInfo();

    boolean isInCheck = inCheck(pos);
    final long occupied = pos.whiteBB | pos.blackBB;
    int kSq = pos.getKingSq(pos.whiteMove);
    long kingAtks = BitBoard.rookAttacks(kSq, occupied) | BitBoard.bishopAttacks(kSq, occupied);
    if (isInCheck) {
        kingAtks |= pos.pieceTypeBB[pos.whiteMove ? Piece.BKNIGHT : Piece.WKNIGHT];
        for &#40;int mi = 0; mi < moveList.size; mi++) &#123;
            Move m = moveList.m&#91;mi&#93;;
            boolean legal;
            if (&#40;m.from != kSq&#41; && (&#40;kingAtks & &#40;1L<<m.to&#41;) == 0&#41;) &#123;
                legal = false;
            &#125; else &#123;
                pos.makeMove&#40;m, ui&#41;;
                pos.setWhiteMove&#40;!pos.whiteMove&#41;;
                legal = !inCheck&#40;pos&#41;;
                pos.setWhiteMove&#40;!pos.whiteMove&#41;;
                pos.unMakeMove&#40;m, ui&#41;;
            &#125;
            if &#40;legal&#41;
                moveList.m&#91;length++&#93;.copyFrom&#40;m&#41;;
        &#125;
    &#125; else &#123;
        for &#40;int mi = 0; mi < moveList.size; mi++) &#123;
            Move m = moveList.m&#91;mi&#93;;
            boolean legal;
            if (&#40;m.from != kSq&#41; && (&#40;kingAtks & &#40;1L<<m.from&#41;) == 0&#41;) &#123;
                legal = true;
            &#125; else &#123;
                pos.makeMove&#40;m, ui&#41;;
                pos.setWhiteMove&#40;!pos.whiteMove&#41;;
                legal = !inCheck&#40;pos&#41;;
                pos.setWhiteMove&#40;!pos.whiteMove&#41;;
                pos.unMakeMove&#40;m, ui&#41;;
            &#125;
            if &#40;legal&#41;
                moveList.m&#91;length++&#93;.copyFrom&#40;m&#41;;
        &#125;
    &#125;
    moveList.size = length;
&#125;

[Daniel Shawul]

Well I checked both versions one with wasted nodes and the other without wasted nodes, and it seems both get it down to 1.1e12. But the error bar is of high. The curve is the usual smooth 1/sqrt(N) looking curve I have been showing before. The only explanation is that sampling 10x less often (sticking to weight estimates for long) adds more bias for whatever reason.Earlier I update the relative proportions every time I compute perft. Weight-multiplier is not the issue as I have none of that. I use uniform MC and a non-uniform sampling in the tree with splitting.

Edit: After 62 iterations for the wasted nodes version I have this
6.285725e+016 +- 1.310330e+012 Is that acceptable ?

[Michel]

6.285725e+016 +- 1.310330e+012 Is that acceptable ?

This corresponds to a z value of 1.74 which is very reasonable (I would
still be worried though about the value of 3.33 that appeared earlier).

How many nodes did you use to get this result?

[Daniel Shawul]

A better estimate at the 80th iteration

Perft 6.156842e+016 +- 3.598160e+012 6.285619e+016 +- 1.237483e+012

I now see that Peter uses a depth limit for tree expansion of ply < 5. That was one of my two solutions I provided to solve the problem. I tested with ply < 3 and got unbiased estimates so may be I should recalculate with depth limit of 5. But also it is not clear if that was a solution because I used a formula which forces the SD for each move to be equal, and it became biased! So there might still be bias in there even if you use depth limits.
But I really really want to understand what is going on because I can adjust just a couple of parameters and lower the variance down but there is no obvious explanation.

The 3.33 was for the one which uses the wasted nodes.
Edit: Well it ended up much worse. So I am going back to depth limited depth = 5. It is not clear if it will solve the problem completely even though you get an acceptable result. I can come up with a formula that will make it biased.