Perft(13) betting pool
Moderators: hgm, Harvey Williamson, bob
Re: Summary of Monte Carlo results for perft(12) so far
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.
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.

 Posts: 3428
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
@HG, I know why so I didn't need an explanation. Just wanted to do some numerical comparison if you have them. Never mind.

 Posts: 3428
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
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 ?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.
Re: Summary of Monte Carlo results for perft(12) so far
I just profiled my implementation (in GNU Chess) and for me it is even 95%My "Peter1" method spends about 80% of the CPU time generating legal move lists,
(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?
Re: Summary of Monte Carlo results for perft(12) so far
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.Daniel Shawul wrote: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 ?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.
The fact that the weights change dynamically is not a problem, because as long as weight * probability = 1, the result is still unbiased.

 Posts: 3428
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
So what I do the same thing? The fact that you do nonuniform 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..
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..
Re: Summary of Monte Carlo results for perft(12) so far
My hardware is, according to /proc/cpuinfo: Intel(R) Core(TM)2 Duo CPU T9500 @2.60GHzMichel wrote:I just profiled my implementation (in GNU Chess) and for me it is even 95%My "Peter1" method spends about 80% of the CPU time generating legal move lists,
(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 move generator is a standard variable shift magic bitboard generator. I agree with HGM that for generating pseudolegal 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 incheck 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 (int mi = 0; mi < moveList.size; mi++) {
Move m = moveList.m[mi];
boolean legal;
if ((m.from != kSq) && ((kingAtks & (1L<<m.to)) == 0)) {
legal = false;
} else {
pos.makeMove(m, ui);
pos.setWhiteMove(!pos.whiteMove);
legal = !inCheck(pos);
pos.setWhiteMove(!pos.whiteMove);
pos.unMakeMove(m, ui);
}
if (legal)
moveList.m[length++].copyFrom(m);
}
} else {
for (int mi = 0; mi < moveList.size; mi++) {
Move m = moveList.m[mi];
boolean legal;
if ((m.from != kSq) && ((kingAtks & (1L<<m.from)) == 0)) {
legal = true;
} else {
pos.makeMove(m, ui);
pos.setWhiteMove(!pos.whiteMove);
legal = !inCheck(pos);
pos.setWhiteMove(!pos.whiteMove);
pos.unMakeMove(m, ui);
}
if (legal)
moveList.m[length++].copyFrom(m);
}
}
moveList.size = length;
}

 Posts: 3428
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
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. Weightmultiplier is not the issue as I have none of that. I use uniform MC and a nonuniform 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 ?
Edit: After 62 iterations for the wasted nodes version I have this
6.285725e+016 + 1.310330e+012 Is that acceptable ?
Re: Summary of Monte Carlo results for perft(12) so far
This corresponds to a z value of 1.74 which is very reasonable (I would6.285725e+016 + 1.310330e+012 Is that acceptable ?
still be worried though about the value of 3.33 that appeared earlier).
How many nodes did you use to get this result?

 Posts: 3428
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
A better estimate at the 80th iteration
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.
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.Perft 6.156842e+016 + 3.598160e+012 6.285619e+016 + 1.237483e+012
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.