Discussion of chess software programming and technical issues.
Moderators: hgm, Harvey Williamson, bob
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

Michel
 Posts: 2038
 Joined: Sun Sep 28, 2008 11:50 pm
Post
by Michel » Sun Apr 05, 2015 7:47 am
The question of computing passing probabilities for SPRT tests often comes up and people then resort to simulation. Alternatively one could use my script
http://hardy.uhasselt.be/Toga/wald.py
However this script does much more and is therefore rather complicated. Moreover it depends on scipy which is a very large and heavy python package.
Therefore I extracted from wald.py a simple plain python script
http://hardy.uhasselt.be/Toga/sprta.py
that computes passing probabilities and average running times. It has no external dependencies. For instructions on how to use sprta.py I include a copy of the post I made on the SF forum.
Here is a simple plain python script for computing passing probabilities and average running times for SPRT tests
http://hardy.uhasselt.be/Toga/sprta.py
This is of course much faster than simulation and moreover no compilation is necessary.
The script is based on well known easy analytical formulas which can for example be found in this book
http://www.amazon.com/SequentialAnalys ... l+analysis
Example:
$ python sprta.py
Usage: sprta.py elo0 elo1 draw_elo elo
elo0,elo1 are expressed in BayesElo
elo is expressed in LogisticElo
$ python sprta.py 0 4 250 2
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 2.0
pass probability: 0.05%
avg running time: 16951
$ python sprta.py 0 4 250 0
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 0.0
pass probability: 5.00%
avg running time: 39909
$ python sprta.py 0 4 250 2
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 2.0
pass probability: 85.89%
avg running time: 51884
$ python sprta.py 0 4 250 4
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 4.0
pass probability: 99.86%
avg running time: 19854
$ python sprta.py 0 4 250 6
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 6.0
pass probability: 100.00%
avg running time: 11545
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Michel
 Posts: 2038
 Joined: Sun Sep 28, 2008 11:50 pm
Post
by Michel » Sun Apr 05, 2015 7:20 pm
For those that do not use python I did a quick line by line Ctranslation. The zip file
http://hardy.uhasselt.be/Toga/sprta.zip
contains the python script, the C translation, a (static) Linux binary and a Windows binary.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Laskos
 Posts: 9323
 Joined: Wed Jul 26, 2006 8:21 pm
 Full name: Kai Laskos
Post
by Laskos » Mon Apr 06, 2015 5:57 am
Michel wrote:The question of computing passing probabilities for SPRT tests often comes up and people then resort to simulation. Alternatively one could use my script
http://hardy.uhasselt.be/Toga/wald.py
However this script does much more and is therefore rather complicated. Moreover it depends on scipy which is a very large and heavy python package.
Therefore I extracted from wald.py a simple plain python script
http://hardy.uhasselt.be/Toga/sprta.py
that computes passing probabilities and average running times. It has no external dependencies. For instructions on how to use sprta.py I include a copy of the post I made on the SF forum.
Here is a simple plain python script for computing passing probabilities and average running times for SPRT tests
http://hardy.uhasselt.be/Toga/sprta.py
This is of course much faster than simulation and moreover no compilation is necessary.
The script is based on well known easy analytical formulas which can for example be found in this book
http://www.amazon.com/SequentialAnalys ... l+analysis
Example:
$ python sprta.py
Usage: sprta.py elo0 elo1 draw_elo elo
elo0,elo1 are expressed in BayesElo
elo is expressed in LogisticElo
$ python sprta.py 0 4 250 2
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 2.0
pass probability: 0.05%
avg running time: 16951
$ python sprta.py 0 4 250 0
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 0.0
pass probability: 5.00%
avg running time: 39909
$ python sprta.py 0 4 250 2
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 2.0
pass probability: 85.89%
avg running time: 51884
$ python sprta.py 0 4 250 4
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 4.0
pass probability: 99.86%
avg running time: 19854
$ python sprta.py 0 4 250 6
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 6.0
pass probability: 100.00%
avg running time: 11545
Can you make the script also output the LOS value for results of the matches at SPRT stop? The asymptotic value of LOS is (1 + erf[{wins  losses}/sqrt{2*(wins+losses)}] ) / 2, and is O(1) computation. The exact LOS is a sum over binomials, a O(N^2) computation, but asymptotically (N>infinity) they are the same. The reason I would like to see LOS is that I observed the typical LOS values for alpha, beta = 0.05, usually the SPRT stop occurs at LOS of 0.9900.995. Although Type I error is theoretically unbounded for LOS or pvalue as stopping rule, practically, say in the range N=100 games to 100,000 games, Type I error can be kept to 25% for LOS=0.999 or such.

lucasart
 Posts: 3036
 Joined: Mon May 31, 2010 11:29 am
 Full name: lucasart

Contact:
Post
by lucasart » Mon Apr 06, 2015 11:06 am
Laskos wrote:
Can you make the script also output the LOS value for results of the matches at SPRT stop? The asymptotic value of LOS is (1 + erf[{wins  losses}/sqrt{2*(wins+losses)}] ) / 2, and is O(1) computation. The exact LOS is a sum over binomials, a O(N^2) computation, but asymptotically (N>infinity) they are the same. The reason I would like to see LOS is that I observed the typical LOS values for alpha, beta = 0.05, usually the SPRT stop occurs at LOS of 0.9900.995. Although Type I error is theoretically unbounded for LOS or pvalue as stopping rule, practically, say in the range N=100 games to 100,000 games, Type I error can be kept to 25% for LOS=0.999 or such.
You need to understand the hypothesis that lie behind the formula you're using. The "LOS" (actually pvalue) is biaised at the SPRT stopping point. The only way your formula is correct, is when you run a fixed number of games decided in advance: (X1...Xn) need to be n random variable, independant and identically distributed, where n is not random (and especially not a function of the X(t) process).
Of course, the biais converges to zero as the stopping time goes to infinity. But still, it's biaised, especially when stopping happens early. That's why we don't print the pvalue of an SPRT test.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Laskos
 Posts: 9323
 Joined: Wed Jul 26, 2006 8:21 pm
 Full name: Kai Laskos
Post
by Laskos » Mon Apr 06, 2015 1:31 pm
lucasart wrote:Laskos wrote:
Can you make the script also output the LOS value for results of the matches at SPRT stop? The asymptotic value of LOS is (1 + erf[{wins  losses}/sqrt{2*(wins+losses)}] ) / 2, and is O(1) computation. The exact LOS is a sum over binomials, a O(N^2) computation, but asymptotically (N>infinity) they are the same. The reason I would like to see LOS is that I observed the typical LOS values for alpha, beta = 0.05, usually the SPRT stop occurs at LOS of 0.9900.995. Although Type I error is theoretically unbounded for LOS or pvalue as stopping rule, practically, say in the range N=100 games to 100,000 games, Type I error can be kept to 25% for LOS=0.999 or such.
You need to understand the hypothesis that lie behind the formula you're using. The "LOS" (actually pvalue) is biaised at the SPRT stopping point. The only way your formula is correct, is when you run a fixed number of games decided in advance: (X1...Xn) need to be n random variable, independant and identically distributed, where n is not random (and especially not a function of the X(t) process).
Of course, the biais converges to zero as the stopping time goes to infinity. But still, it's biaised, especially when stopping happens early. That's why we don't print the pvalue of an SPRT test.
If LOS stop rule is "I stop as soon as I get LOS 0.999 for the first time", then the bias is included in the Type I error derived by simulations. As for pvalue given by above formula, it converges to LOS for large number of games for fixed number of games.

Laskos
 Posts: 9323
 Joined: Wed Jul 26, 2006 8:21 pm
 Full name: Kai Laskos
Post
by Laskos » Tue Apr 07, 2015 6:12 am
Laskos wrote:lucasart wrote:Laskos wrote:
Can you make the script also output the LOS value for results of the matches at SPRT stop? The asymptotic value of LOS is (1 + erf[{wins  losses}/sqrt{2*(wins+losses)}] ) / 2, and is O(1) computation. The exact LOS is a sum over binomials, a O(N^2) computation, but asymptotically (N>infinity) they are the same. The reason I would like to see LOS is that I observed the typical LOS values for alpha, beta = 0.05, usually the SPRT stop occurs at LOS of 0.9900.995. Although Type I error is theoretically unbounded for LOS or pvalue as stopping rule, practically, say in the range N=100 games to 100,000 games, Type I error can be kept to 25% for LOS=0.999 or such.
You need to understand the hypothesis that lie behind the formula you're using. The "LOS" (actually pvalue) is biaised at the SPRT stopping point. The only way your formula is correct, is when you run a fixed number of games decided in advance: (X1...Xn) need to be n random variable, independant and identically distributed, where n is not random (and especially not a function of the X(t) process).
Of course, the biais converges to zero as the stopping time goes to infinity. But still, it's biaised, especially when stopping happens early. That's why we don't print the pvalue of an SPRT test.
If LOS stop rule is "I stop as soon as I get LOS 0.999 for the first time", then the bias is included in the Type I error derived by simulations. As for pvalue given by above formula, it converges to LOS for large number of games for fixed number of games.
By the way, your statement that frequentist inference LOS is actually pvalue is not correct. Just computed the pvalue for our problem, and it's only related to frequentist inference LOS.
If
Code: Select all
D = (wins  losses) / sqrt(2 * (wins + losses))
Then the asymptotic LOS is
Code: Select all
LOS(frequentist) = (1 + erf(D)) / 2
pvalue is
Code: Select all
pvalue = 1  erf(abs(D))
And the exact Bayesian LOS is
Code: Select all
LOS(Bayesian) = (1/2 * binomial(wins+losses, wins) + sum[i, 0, wins1] binomial(wins+losses, i)) / 2^(wins+losses)