SPRT question

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Michel
Posts: 2046
Joined: Sun Sep 28, 2008 11:50 pm

Re: SPRT question

Post by Michel » Fri Aug 21, 2015 12:55 pm

Michel wrote: It is not clear to me if and when the SPRT will terminate with probabilty one if the number of games of A is kept fixed (it seems like an easy problem, but I have not taken the time to consider it properly). Obviously if eloA is only vaguely known, and the difference between eloA and eloB is small, one will never be able to prove there is a difference no matter how many games B plays (recall that A and B are not playing each other).
A quick back of the envelope calculation shows that under the following conditions

(0) The number of games of A is kept constant.
(1) eloA=eloA' (i.e. the measured elo of A, which stays constant, is equal to the true elo).
(2) eloB=eloA+epsilon/2 (i.e. halfway between H0 and H1)

there is a non-zero probability that the SPRT will not terminate.

Even if H0 or H1 is true _and epsilon is below some easily calculated bound_, depending on the number of games played by A, there will be a non-zero probability that the SPRT does not terminate.

So the conclusion is that when using the SPRT in this fashion one should add games for both A and B (although probably not in the same ratio).
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Michel
Posts: 2046
Joined: Sun Sep 28, 2008 11:50 pm

Re: SPRT question

Post by Michel » Mon Aug 24, 2015 10:42 pm

The results in the paper I quoted are only of asymptotic nature so I did some simulations to make sure that they also apply in the non-asymptotic cases we are considering and the good news is that they do! At least as far as the Type I/II error probabilities are concerned.

Of course the number of games required to get a sensible elo resolution when playing against foreign opponents is horrible compared with self play.

For those that are interested: below is the code to extract the (bayes)elo values from matrices with W/D/L values. The code is inefficient since L is just the transpose of W but I am too lazy to fix this now.

Code: Select all

 from __future__ import division
import math,scipy,scipy.optimize
import random
import numpy as np

bb=math.log(10)/400

def L_(x):
    return 1/(1+np.exp(-bb*x))

def WDL(de,elo):
    size=elo.shape[0]
    elo_columns=elo[np.newaxis]  
    elo_rows=elo[:,np.newaxis] 
    elo_diff=np.repeat(elo_rows,size,1)-np.repeat(elo_columns,size,0)
    W=L_(elo_diff-de)
    L=L_(-elo_diff-de)
    D=1-W-L
    return (W,D,L)

def LL(de,elo,w,d,l):
    (W,D,L)=WDL(de,elo)
    return(np.sum(w*np.log(W)+d*np.log(D)+l*np.log(L)))/2

def elo(de,elo_diff,w,d,l):
    return BayesElo(de,np.array([-elo_diff/2,elo_diff/2]),w,d,l)

def LLR(de,elo_diff1,elo_diff2,w,d,l):
    elo1=elo(de,elo_diff1,w,d,l)
    elo2=elo(de,elo_diff2,w,d,l)
    return LL(de,elo2,w,d,l)-LL(de,elo1,w,d,l)

def BayesElo(de,elo,w,d,l):
    """ de is draw elo """
    """ elo is a numpy array of presets """
    """ w,d,l are square numpy arrays with win,draw,loss counts """
    if elo.shape[0]==0:
        elo=np.array([0])
    vars=w.shape[0]-elo.shape[0]
    ret=scipy.optimize.minimize(lambda x:-LL(de,np.concatenate((elo,x)),w,d,l),np.zeros(vars),options={'disp':False})
    return np.concatenate((elo,ret.x))
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Michel
Posts: 2046
Joined: Sun Sep 28, 2008 11:50 pm

Re: SPRT question

Post by Michel » Tue Aug 25, 2015 10:14 am

Ok for possible further reference here is an implementation of the GSPRT

http://hardy.uhasselt.be/Toga/GSPRT.py

Here is the documentation of the main class

Code: Select all

class GSPRT:
    """ 
This class performs a GSPRT for H0:elo(player1)-elo(player0)=elo_diff1 versus H1:elo(player1)-elo(player0)=elo_diff2. 
See here for a description of the GSPRT as well as theoretical (asymptotic) results.

http://stat.columbia.edu/~jcliu/paper/GSPRT_SQA3.pdf

To record a result use the method self.record(player1,player2,result) where "result" is one of 'w','d','l'. 

To check the status of the test at any time use self.status(). This method return a tuple whose first entry 
is the number of games so far, whose second entry is a string which is either 'H0','H1' or '' 
and whose third parameter is a list of estimated elo values. Note that when the test terminates these estimates are
heavily biased. So their main purpose is entertainment.

The granularity parameter to the constructor controls how often the log likelihood ratio is recomputed. 
Making this parameter larger than one will speed up simulations. Note that making the granularity high will reduce 
the Type I/II parameters below their  design values because of overshooting. It is known how to correct for this (by estimating
the overshoot) but this has not been implemented.

When using this class with actual games one should use the default granularity (=1).
"""
    def __init__(self,alpha=0.05,beta=0.05,elo_diff1=0,elo_diff2=5,draw_elo=100,players=3,granularity=1):
To illustrate the use of this class the script performs a simulation.

Code: Select all

def simulate(granularity,de,epsilon,alpha,elo1,elo2,elo3):
    """
We simulate testing a new version of an engine with the help of one foreign engine.
"""
    g=GSPRT(alpha=alpha,beta=alpha,draw_elo=de,granularity=granularity,elo_diff1=0,elo_diff2=epsilon,players=3)
    elo=np.array([elo1,elo2,elo3])
    W,D,L=WDL(de,elo)
    for i in xrange(0,10000000):
        r=i%2
        c=2
        p=pick(W[r,c],D[r,c],L[r,c])
        g.record(r,c,p)
        if g.status()[1]!='':
            return g.status()
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Post Reply