question about non determinism of chess programs

Discussion of anything and everything relating to chess playing software and machines.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Uri Blass
Posts: 8556
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

question about non determinism of chess programs

Post by Uri Blass » Mon Feb 19, 2018 10:38 am

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.

Isaac
Posts: 265
Joined: Sat Feb 22, 2014 7:37 pm

Re: question about non determinism of chess programs

Post by Isaac » Mon Feb 19, 2018 7:32 pm

Interesting question. Maybe this thread has some relevant information: http://www.talkchess.com/forum/viewtopi ... w=&start=0.

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: question about non determinism of chess programs

Post by bob » Tue Feb 20, 2018 5:51 am

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.

User avatar
Laskos
Posts: 9410
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: question about non determinism of chess programs

Post by Laskos » Tue Feb 20, 2018 7:38 am

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

Jouni
Posts: 1979
Joined: Wed Mar 08, 2006 7:15 pm

Re: question about non determinism of chess programs

Post by Jouni » Tue Feb 20, 2018 7:39 am

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

User avatar
Laskos
Posts: 9410
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: question about non determinism of chess programs

Post by Laskos » Tue Feb 20, 2018 7:44 am

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.

Post Reply