---
title: "The Elo method in chess"
output: html_document
editor_options: 
  chunk_output_type: inline
---
```{r setup, include=FALSE}
# cache results
knitr::opts_chunk$set(cache=TRUE, echo = FALSE, eval = FALSE, message=FALSE, warning = FALSE, fig.align='center')
```

**Elo method** was coined by the physics professor and excellent chess player Arpad Elo. In 1970, FIDE, the World Chess Federation, agreed to adopt the Elo Rating System. 

The method works as follows.
Suppose that players $i$ and $j$ match. Let $s_{i,j}$ be the **actual score** of $i$ in the match against $j$. We have that:

+ $s_{i,j} = 1$ if $i$ wins;
+ $s_{i,j} = 0$ if $i$ loses; and 
+ $s_{i,j} = 0.5$ if there is a draw. 

Notice that the actual score $s_{j,i}$ of $j$ in the match against $i$ is $1 - s_{i,j}$. 
Let $\mu_{i,j}$ be the **expected score** of $i$ in the match against $j$. We have that:

$$
\begin{array}{lll}
\mu_{i,j} & = & \frac{1}{1 + 10^{-(r_i - r_j) / \zeta}} = 
\frac{10^{r_i / \zeta}}{10^{r_i / \zeta} + 10^{r_j / \zeta}} \\\\
\end{array}
$$  

with $r_i$ and $r_j$ the ratings of $i$ and $j$ before the match and $\zeta$ is a constant. Notice that the expected score $\mu_{j,i}$ of $j$ in the match against $i$ is $1 - \mu_{i,j}$.  


```{r logistic, echo = FALSE, eval = TRUE}
## Logistic function
logistic = function(x, z=400) {
  return(1 / (1 + 10^(-x / z)))
}
limit = 1000
plot(logistic, xlim=c(-limit, limit), lwd=3, xlab="rating difference", ylab = "logistic")
abline(h=0.5, lty=2)
```

We assume that initially all player ratings are equal to 0. When players $i$ and $j$ match, the new ratings $r_i$ of $i$ and $r_j$ of $j$ are modified using the following update rule: 

$$
\begin{array}{lll}
r_{i} & \leftarrow & r_i + \kappa (s_{i,j} - \mu_{i,j}) 
\\
r_j & \leftarrow & r_j + \kappa (s_{j,i} - \mu_{j,i})
\end{array}
$$

where $\kappa$ is a constant. 

The Elo thesis is: 

> *If a player performs as expected, it gains nothing. If it performs better than expected, it is rewarded, while if it performs poorer than expected, it is penalized.* 

According to the movie [The social network](https://www.youtube.com/watch?v=BzZRr4KV59I&feature=youtu.be) by David Fincher, it appears that the Elo’s method formed the basis for rating people on Zuckerberg’s Web site Facemash, which was the predecessor of Facebook. 

## Dataset
* A [CSV](training_data.csv) with outcomes of 65053 distinct chess games (White, Black and Score). The possible values for Score represent the three possible outcomes of a chess game (1=White wins, 0.5=draw, 0=Black wins). Read the [details](https://www.kaggle.com/c/chess/data).

## Challenges
1. An interesting property of Elo’s ratings is that the sum of all player ratings is always 0. Formally show this property. (Hint: use the fact that $s_{i,j} + s_{j,i}=1$ and $\mu_{i,j} + \mu_{j,i} =1$)
1. Write an optimized version of the Elo's rating function below (use also the above property)
2. Compare the execution time of the original and optimized version on this chess dataset

```{r echo = TRUE}
library(readr)
games = read_csv("training_data.csv")
```


```{r echo = TRUE}
##  Elo
# INPUT
# games: a *dataframe* with matches
# zeta: logistic parameter
# k: update factor
# OUTPUT
# r: rating vector
elo_slow = function(games, z = 400, k = 25) {
  
  # number of players
  players = unique(c(games$White, games$Black))
  n = max(players)

  # number of games
  m = nrow(games)
  
  # old rating vector
  rold = rep(0, n)
  
  # new rating vector
  rnew = rep(0, n)
  
  for (i in 1:m) {

    # White player
    # compute update
    score = games[[i, "Score"]]
    spread = rold[games[[i, "White"]]] - rold[games[[i, "Black"]]]
    mu = 1 / (1 + 10^(-spread / z))
    update = k * (score - mu)
    # update rating
    rnew[games[[i,"White"]]] = rold[games[[i,"White"]]] + update
    
    # Black player
    # compute update
    score = 1 - games[[i, "Score"]]
    spread = rold[games[[i, "Black"]]] - rold[games[[i, "White"]]]
    mu = 1 / (1 + 10^(-spread / z))
    update = k * (score - mu)
    # update rating
    rnew[games[[i,"Black"]]] = rold[games[[i,"Black"]]] + update
    
    # update old ratings
    rold[games[[i,"White"]]] = rnew[games[[i,"White"]]]
    rold[games[[i,"Black"]]] = rnew[games[[i,"Black"]]]
  }
  return(rnew)
}

```




```{r}
##  Elo rating system (optimized)
# INPUT
# games: a *matrix* with matches
# zeta: logistic parameter
# k: update factor
# OUTPUT
# r: rating vector
elo_fast = function(games, z = 400, k = 25) {
  
  # number of players
  players = unique(c(games[, "White"], games[, "Black"]))
  n = max(players)

  # number of games
  m = nrow(games)
  
  # old rating vector
  rold = rep(0, n)
  
  # new rating vector
  rnew = rep(0, n)
  
  for (i in 1:m) {

    # White player
    score = games[i, "Score"]
    spread = rold[games[i, "White"]] - rold[games[i, "Black"]]
    mu = 1 / (1 + 10^(-spread / z))
    update = k * (score - mu)
    rnew[games[i, "White"]] = rold[games[i, "White"]] + update
    
    # Black player (we know that: update white + update black = 0)
    rnew[games[i,"Black"]] = rold[games[i,"Black"]] - update
    
    # update old ratings
    rold[games[i,"White"]] = rnew[games[i,"White"]]
    rold[games[i,"Black"]] = rnew[games[i,"Black"]]
  }
  return(rnew)
}

```


```{r}
# compare
games_matrix = as.matrix(games)
t1 = system.time({e1 = elo_fast(games_matrix)})
t2 = system.time({e2 = elo_slow(games)})

# check correctness
sum(abs(e1 - e2))

# check times
t1
t2
t2/t1
```


