Page 1 of 1

question about non determinism of chess programs

Posted: Mon Feb 19, 2018 10:38 am
by Uri Blass
stockfish played in TCEC in the first move 3 different moves:
1.e4 1.d4 1.Nf3

Now the question is the following:

If you play engine A against engine B for n plies with no book(A is white) and repeat it for N games
how many different games you can expect to have of course it is a function of A B and n and N so there is a function f(A,B,n,N) and I think that it may be interesting to have an estimate for different pairs.

Of course
f(A,B,1,1)=1
f(A,B,1,N)=f(A,C,1,N)
It is possible to get an estimate for f(A,B,1,2) by asking A to calculate the first move many times.

for example if you get for engine A
70% of the cases 1.d4
20% of the cases 1.e4 and
10% of the cases 1.Nf3 then the estimate is
f(A,B,1,2)=(0.7*0.7+0.2*0.2+0.1*0.1)*1+(1-0.7*0.7-0.2*0.2+0.1*0.1)*2=0.54+0.46*2=1.46

Note that practically f is dependent also on hardware and time control and it may be interesting to know if f is smaller or bigger with longer time control or more cores.

Re: question about non determinism of chess programs

Posted: Mon Feb 19, 2018 7:32 pm
by Isaac
Interesting question. Maybe this thread has some relevant information: http://www.talkchess.com/forum/viewtopi ... w=&start=0.

Re: question about non determinism of chess programs

Posted: Tue Feb 20, 2018 5:51 am
by bob
Uri Blass wrote:stockfish played in TCEC in the first move 3 different moves:
1.e4 1.d4 1.Nf3

Now the question is the following:

If you play engine A against engine B for n plies with no book(A is white) and repeat it for N games
how many different games you can expect to have of course it is a function of A B and n and N so there is a function f(A,B,n,N) and I think that it may be interesting to have an estimate for different pairs.

Of course
f(A,B,1,1)=1
f(A,B,1,N)=f(A,C,1,N)
It is possible to get an estimate for f(A,B,1,2) by asking A to calculate the first move many times.

for example if you get for engine A
70% of the cases 1.d4
20% of the cases 1.e4 and
10% of the cases 1.Nf3 then the estimate is
f(A,B,1,2)=(0.7*0.7+0.2*0.2+0.1*0.1)*1+(1-0.7*0.7-0.2*0.2+0.1*0.1)*2=0.54+0.46*2=1.46

Note that practically f is dependent also on hardware and time control and it may be interesting to know if f is smaller or bigger with longer time control or more cores.
It is more complicated than that. MOST non-determinism (except that caused by parallel search) is caused by timing inconsistencies. You can't use exactly the same number of cpu cycles per search. Years ago when I started cluster testing, I was completely surprised as to how non-deterministic chess engines were unless you resort to fixed depth searches. I played 100 games from the same starting position and no two games were duplicated. In the grossest examples, the results varied, white would win some, lose some and draw some, all from the same starting position with no book whatsoever. But more noticeable was the fact that I never got two games with the same sequence of moves from beginning to end. Throw in SMP non-determinism and the genie is way out of the bottle.

Re: question about non determinism of chess programs

Posted: Tue Feb 20, 2018 7:38 am
by Laskos
Uri Blass wrote:stockfish played in TCEC in the first move 3 different moves:
1.e4 1.d4 1.Nf3

Now the question is the following:

If you play engine A against engine B for n plies with no book(A is white) and repeat it for N games
how many different games you can expect to have of course it is a function of A B and n and N so there is a function f(A,B,n,N) and I think that it may be interesting to have an estimate for different pairs.

Of course
f(A,B,1,1)=1
f(A,B,1,N)=f(A,C,1,N)
It is possible to get an estimate for f(A,B,1,2) by asking A to calculate the first move many times.

for example if you get for engine A
70% of the cases 1.d4
20% of the cases 1.e4 and
10% of the cases 1.Nf3 then the estimate is
f(A,B,1,2)=(0.7*0.7+0.2*0.2+0.1*0.1)*1+(1-0.7*0.7-0.2*0.2+0.1*0.1)*2=0.54+0.46*2=1.46

Note that practically f is dependent also on hardware and time control and it may be interesting to know if f is smaller or bigger with longer time control or more cores.
This is related:
http://www.talkchess.com/forum/viewtopi ... _view=flat

Re: question about non determinism of chess programs

Posted: Tue Feb 20, 2018 7:39 am
by Jouni
In NCM Stockfish testing they played previously 10 000 games without book. Result: only 2-3 same games at most! It was 2 cores test.

Re: question about non determinism of chess programs

Posted: Tue Feb 20, 2018 7:44 am
by Laskos
Jouni wrote:In NCM Stockfish testing they played previously 10 000 games without book. Result: only 2-3 same games at most! It was 2 cores test.
Games to the end are one thing, for how many plies (n) it plays identically is important. We usually seek unrelated games in testing, so even if the full games are not identical, a large bunch might be very related, and the result skewed.