Perft(13) betting pool

[Michel]

But comparison is a waste of time IMHO if the conditions are not similar.

The conditions are similar. The conditions are to construct an unbiased estimator for Perft(12) with the lowest possible value for sd*sqrt(moveGen).

[Daniel Shawul]

Maybe I made a mistake I don't know. But the code is the one I used to generate the other data I have been posting. There are lots of issues to discuss but you guys insist on comparing methods... I will make the plot when it is done and see if there are obvious problems.

[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 ?