An ordered categorical regression approach to rating chess players.

Hi all

I was watching the Tata Steel chess tournament; the big question of the event was if Anand was going to qualify for the final in London.

As I was ponder the question I thought not for the first time that elo is more or less useless for making such predictions.  The main problems are that elo does not take into account the value of white vs black pieces and does not account for a player preponderance to draw.

This post considers an ordered categorical regression model as an alternative to elo. The model has four parameters per player; I know only having one would be nice as it lets there be a clear A is better than B sort of comparison but real life is not always nice. The four parameters are a players strength with white (S_{W} ), strength with black S_{B} ), preponderance to draw with white D_{w} ), and preponderance to draw with black D_{B} ). To explain what these parameters mean consider a match between two players (lets call them Vladimir and Nikitia). Vlad “the lad” has the white pieces; he has a S^{\text{Vlad}}_{w} = 1 and a D^{\text{Vlad}}_{W} = 0.25.  Nikitia “the shoe” has black with S^{\text{Nik}}_{B} = 0 and a D^{\text{Nik}}_{B} = 0.5.

The first value that must be computed is the “mid point” (x_{\text{mid}}= S_{B}^{\text{Nik}} - S^{\text{Vlad}}_{w} = -1). This can be thought of as the border between white’s territory in the outcome space and black’s. New the “draw zone” must be calculated. It has two boarders; these are black wins to draw boarder and the draw to white wins boarder. The black wins to draw board is x_{\text{BD}} = x_{\text{mid}} -  D^{\text{Nik}}_{B}= -1.5 and the draw to white wins boarder is x_{\text{DW}} = x_{\text{mid}} +  D^{\text{Vlad}}_{W}= -0.75. Figure 1 shows the three lines for this example.

Screen Shot 2019-12-01 at 1.21.23 PM

Figure 1: The out come regions of a match between Vlad and Nikita. Red red area is the probability that Nikita wins, the blue area is the probability that the game is a draw, and the green area is the probability that Vlad wins.

Next if we imagine a standard Gaussian distribution (mean is zero and standard deviation is one) behind the x_{\text{mid}}, x_{\text{BD}}, and x_{\text{DW}} points on the number line then a probability of the each result (Black wins, draw, or white wins) can be calculated by integrating over the appropriate region. That is, on Fig. 1 the red area that goes from -Inf to the black wins draw boarder is the probability that black wins and is P[\text{black win}] =  \Phi[x_{\text{BD}}] . The blue area that goes from the black wins draw boarder  to the draw white wins board is  the probability that the game is a draw and is P[\text{draw}] =  \Phi[x_{\text{DW}}] -\Phi[x_{\text{BD}}] .  And P[\text{white wins}] =  1- \Phi[x_{\text{DW}}] . In the Vlad vs Nik example these probabilities are 6.68% black wins, 15.98% draw, and 77.33% white wins.

Applying this method to the Tata Tournament and using MCMC to estimate the parameters I get the  distributions of player strengths shown in Fig. 2. Note that Anand is defined as having strength 0 for both black and white as this method is only ordering (ok not really ordering but giving relative strengths with black and white…) the users not creating an absolute measure.

Screen Shot 2019-12-02 at 7.29.38 PM.png

Figure 2: the marginal posterior densities of player strengths with black and white.

A surprising result of Fig. 2 is that Carlsen is not the strongest player; he is ~ second strongest with white and third with black. What gives? Figure 3 shows the marginal posterior histograms of  the draw parameters for each user; there I can be seen that Giri and Nakamura are much higher in their preponderance to draw!

Screen Shot 2019-12-02 at 7.32.48 PM

Figure 3: the marginal posterior densities of player preponderances to draw with black and white.

That is it for this week. I hope this was interesting.

#full result data from tata steal
data.tata= read.csv("tata_results.csv", header=T)

# reducing it down to just which player has white, black and result.
# not player "names" are indices 
d.tata = data.tata[,c(5,6,4)]

g.LL <-function(data, m)
{
n = nrow(data)
np = 10 

log.P = 0


for ( i in 1:n)
  {
  # get the indeces of the users
  W_i = data[i,1]
  B_i = data[i,2]
  R   = data[i,3]
  
  # calc the boundries
  mid =  m[(np)+B_i] -  m[W_i]  
  DW  = mid + m[(2*np)+W_i]
  BD  = mid - m[(3*np)+B_i]
  
  # calc prob of the result
  if( R == "W") {P =  log(1-pnorm(DW))            }
  if( R == "D") {P =  log(pnorm(DW) - pnorm(BD))  }
  if( R == "B") {P =  log(pnorm(BD))              }
  log.P = log.P + P
  }

return(log.P)

}
#g.LL(data= d.tata, m= c(rep(0, 10), rep(0, 10), rep(0.1, 10), rep(0.1,10) ) )


g.MCMC <- function(N = 100, m.start= c(rep(0, 10), rep(0, 10), rep(0.1, 10), rep(0.1,10) )) { np = 10 # number of players in the event  # the upper and lower prior bounds of the ratings  # strengths can between -3  (very weak)and 3 (very strong) # draw peronderance must be > 0; is is nvers draws 3 is draws almost always  
LB = c(rep(-3, np), # player strength white 
       rep(-3, np),  # player strength black
       rep(0, np), # player propnderance to draw white 
       rep(0,np)) # player propnderance to draw black 
UB = c(rep( 3, np), rep( 3, np), rep(6, np), rep(6,np))

# proposal standard error 
Q.sigma = 0.25

m.old = m.start
LL.old = -Inf


# the record of the sampled paramter values 
REC = data.frame(matrix(0, ncol=4*np+1, nrow=N))
colnames(REC) = c("LL", 
                  "SW1", "SW2", "SW3", "SW4", "SW5", "SW6", "SW7",  "SW8", "SW9", "SW10", 
                  "SB1", "SB2", "SB3", "SB4", "SB5", "SB6", "SB7",  "SB8", "SB9", "SB10", 
                  "DW1", "DW2", "DW3", "DW4", "DW5", "DW6", "DW7",  "DW8", "DW9", "FW10", 
                  "DB1", "DB2", "DB3", "DB4", "DB5", "DB6", "DB7",  "DB8", "DB9", "FB10") 

# standard MCMC steps 
for ( i in 1:N)
  {
  ORDER =sample(c(2:10, 12:(np*4)) )#1:(np*4)
  for (j in ORDER)
    {

      m.prime = m.old
      m.prime[j] = m.prime[j] + rnorm(1, sd = Q.sigma)
      LL.prime = -Inf
      if ( min(m.prime >= LB) & min(m.prime <= UB) )
          {
          LL.prime = g.LL(data= d.tata, m=m.prime  )
          }
    
      A = exp(LL.prime - LL.old)
      r = runif(1)
      if(r <= A )
        {
        m.old = m.prime
        LL.old = LL.prime
        }
      
    }

  REC[i,1] = LL.old
  REC[i,2:41] = m.old
  
  
  print(i)
  print(LL.old)
  print(round(m.old[1:10],3))
  }
  

return(REC)
}

plotting code

Mat = matrix(c(21,22,23,
21, 1, 2,
21, 3, 4,
21, 5, 6,
21, 7, 8,
21, 9,10,
21,11,12,
21,13,14,
21,15,16,
21,17,18,
21,19,20), nrow=11, ncol=3, byrow=T)
layout(Mat, widths = c(0.2, 1,1), heights=c(0.5, 1,1,1,1,1 , 1,1,1,1,1))
par(mar=c(0.5,0,0,1))

g.hist <-function(x, bounds=c(-12, 12), nb, ylab. = "Anand", xlab. = "Strength White")
{
b = seq(bounds[1], bounds[2], length.out = nb+1 )
h= hist(x, breaks=b, plot=F)
plot(h$mids, h$den, type="n", xlab="", ylab =ylab., xaxt="n", yaxt="n")
axis(3, at = mean(b), tick=F, labels = xlab.)
axis(2, at = max(h$den)/2, tick=F, labels = ylab.)
polygon(c(min(b),h$mids, max(b) ), c(0, h$den, 0), col="grey", border=F)
abline(v = 0, lwd=3, col="blue")
}
g.hist(x=Samp[,2], bounds=c(-3, 3), nb= 50, ylab. = "Anand", xlab. = "Strength White")
g.hist(x=Samp[,12],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "Strength Black")
g.hist(x=Samp[,3], bounds=c(-3, 3), nb= 50, ylab. = "Aronian", xlab. = "")
g.hist(x=Samp[,13],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,4], bounds=c(-3, 3), nb= 50, ylab. = "Carlsen", xlab. = "")
g.hist(x=Samp[,14],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,5], bounds=c(-3, 3), nb= 50, ylab. = "Giri", xlab. = "")
g.hist(x=Samp[,15],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,6], bounds=c(-3, 3), nb= 50, ylab. = "Gujrathi", xlab. = "")
g.hist(x=Samp[,16],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,7], bounds=c(-3, 3), nb= 50, ylab. = "Harikrishna ", xlab. = "")
g.hist(x=Samp[,17],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,8], bounds=c(-3, 3), nb= 50, ylab. = "Liren", xlab. = "")
g.hist(x=Samp[,18],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,9], bounds=c(-3, 3), nb= 50, ylab. = "Nakamura", xlab. = "")
g.hist(x=Samp[,19],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,10], bounds=c(-3, 3), nb= 50, ylab. = "Nepomniachtchi", xlab. = "")
g.hist(x=Samp[,20],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,11], bounds=c(-3, 3), nb= 50, ylab. = "So", xlab. = "")
g.hist(x=Samp[,21],bounds=c(-3, 3), nb= 50, ylab. = "", xlab. = "")

Mat = matrix(c(21,22,23,
21, 1, 2,
21, 3, 4,
21, 5, 6,
21, 7, 8,
21, 9,10,
21,11,12,
21,13,14,
21,15,16,
21,17,18,
21,19,20), nrow=11, ncol=3, byrow=T)
layout(Mat, widths = c(0.2, 1,1), heights=c(0.5, 1,1,1,1,1 , 1,1,1,1,1))
par(mar=c(0.5,0,0,1))
g.hist(x=Samp[,2+20], bounds=c(0, 3), nb= 50, ylab. = "Anand", xlab. = "Draw White")
g.hist(x=Samp[,12+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "Draw Black")
g.hist(x=Samp[,3+20], bounds=c(0, 3), nb= 50, ylab. = "Aronian", xlab. = "")
g.hist(x=Samp[,13+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,4+20], bounds=c(0, 3), nb= 50, ylab. = "Carlsen", xlab. = "")
g.hist(x=Samp[,14+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,5+20], bounds=c(0, 3), nb= 50, ylab. = "Giri", xlab. = "")
g.hist(x=Samp[,15+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,6+20], bounds=c(0, 3), nb= 50, ylab. = "Gujrathi", xlab. = "")
g.hist(x=Samp[,16+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,7+20], bounds=c(0, 3), nb= 50, ylab. = "Harikrishna ", xlab. = "")
g.hist(x=Samp[,17+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,8+20], bounds=c(0, 3), nb= 50, ylab. = "Liren", xlab. = "")
g.hist(x=Samp[,18+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,9+20], bounds=c(0, 3), nb= 50, ylab. = "Nakamura", xlab. = "")
g.hist(x=Samp[,19+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,10+20],bounds=c(0, 3), nb= 50, ylab. = "Nepomniachtchi", xlab. = "")
g.hist(x=Samp[,20+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "")
g.hist(x=Samp[,11+20],bounds=c(0, 3), nb= 50, ylab. = "So", xlab. = "")
g.hist(x=Samp[,21+20],bounds=c(0, 3), nb= 50, ylab. = "", xlab. = "")

<\pre>