---
title: 'Statistical Thinking using Randomisation and Simulation'
subtitle: "Game simulation and decision theory"
author: Di Cook (dicook@monash.edu, @visnut)
date: "W1.C2"
output:
  xaringan::moon_reader:
    css: ["default", "myremark.css"]
    self_contained: false
    nature:
      highlightStyle: github
      highlightLines: true
      countIncrementalSlides: false
---

```{r setup, include = FALSE}
library(knitr)
opts_chunk$set(
  message = FALSE,
  cache = FALSE,
  echo = FALSE,
  fig.height = 5,
  fig.width = 8,
  fig.align = "center",
  collapse = TRUE,
  comment = "#>"
)
options(digits=2)
library(tidyverse)
library(gridExtra)
```


# Overview 

- Decision Theory is concerned with the mathematical analysis of decision making when the __state of the world is uncertain__ but information can be obtained about it by means of observation or experimentation.
- Some __action must be chosen__ from a well defined set of alternatives, but the exact circumstances in which the action must be taken are unknown.
- Different actions implies different consequences and therefore have different merit according to the decision maker's preference.

---
# Overview

- Assuming that __some numerical value__ can be assigned to the different combinations of circumstances and actions provides a basis for assessing __how reasonable a particular action is in different situations__.
- It may be possible to obtain __data__ that will yield information about the prevailing circumstances, or prior information concerning the __frequency with which different circumstances arise__.
- The aim of __decision theory__ is to provide a means of exploiting such information to determine a __reasonable__ (optimal?) __course of action__.

---
# Rock, paper, scissors

Strategy      | Decision   | Rock | Paper | Scissors
-----|-----|-----|-----|-----
$a_1$ | Rock | 0 |  -1 | 1
$a_2$ | Paper | 1 | 0 | -1
$a_3$ | Scissors | -1 | 1 | 0

Your choices are $a_1, a_2, a_3$. Depending on what the opponent chooses you win (1), lose (-1) or tie (0). __What should you choose?__

---
# Decision under ignorance/risk

- Decision under __ignorance__: probability of the possible outcomes __unknown or does not exist__
- Decision under __risk__: __probability__ of the possible outcomes __known__
- Decision under uncertainty: synonym for ignorance, or as a broader term referring to both risk and ignorance

---
class: inverse middle 
# Your turn

What is rock, paper, scissors?

- Decision under risk?
- Decision under ignorance?

---
# Zero-sum two person games

- The payoff is the amount of money each player receives after choosing their respective strategies 
- Whatever one player loses, the other player wins.
- Each player must choose his own strategy without knowing what his opponent is going to do.
- An objective is to determine optimal winning strategies.

---
# Rock, paper, scissors

Strategy      | Decision  | Rock (1/3) | Paper  (1/3) | Scissors (1/3) 
----- | ----- | ----- | ----- | -----
$a_1$ | Rock | 0 |  -1 | 1
$a_2$ | Paper | 1 | 0 | -1
$a_3$ | Scissors | -1 | 1 | 0

Whatever you choose you have a 1/3 of winning, losing or tieing.

---
# Let's simulate the game

- Fix your decision to be $a_1$, without loss of generality
- Randomly generate the opponents response
- Count the number of times you win, lose, tie

Run 1:

```{r}
set.seed(106)
d <- sample(c("Rock", "Paper", "Scissors"), 10000, replace=TRUE)
table(d)
```

Run 2:

```{r}
d <- sample(c("Rock", "Paper", "Scissors"), 10000, replace=TRUE)
table(d)
```

Run 3:

```{r}
d <- sample(c("Rock", "Paper", "Scissors"), 10000, replace=TRUE)
table(d)
```

There is no optimal strategy.

---
# Different probabilities

Strategy      | Decision  | Rock (0.354) | Paper  (0.350) | Scissors (0.296) 
----- | ----- | ----- | ----- | -----
$a_1$ | Rock | 0 |  -1 | 1
$a_2$ | Paper | 1 | 0 | -1
$a_3$ | Scissors | -1 | 1 | 0

But people have some patterns when they play, generally. It is reported that people tend to play rock and paper more than scissors.
(Probabilities reported in article in [http://www.telegraph.co.uk](http://www.telegraph.co.uk/men/thinking-man/11051704/How-to-always-win-at-rock-paper-scissors.html))

Check that the probabilities sum to 1. (Why?) Now what should be your strategy?

Also, look at this [twitter poll](https://twitter.com/nj_tierney/status/888345405871636480).

---
class: inverse middle 
# Your turn

If your strategy is 

- $a_1$, 
- $a_2$, or
- $a_3$,

your chance of winning should be?

```{r eval=FALSE}
0.296, 0.354, 0.350
```

---
# Let's simulate it

- Generate $n$ samples from a `uniform(0,1)` distribution
- Bin the number into `0-0.354, 0.354-0.654, 0.654-1` to match the probabilities of opponent choices
- Count the proportion of $n$ times you would win under each strategy $a_1, a_2, a_3$.

For each of the following runs, my $n=10000$.

Your strategy is $a_1$, `Rock`:

```{r}
d <- runif(100000)
dd <- cut(d, c(0, 0.354, 0.654, 1), labels=c("Tie", "Lose", "Win"))
length(dd[dd=="Win"])/100000
```

Your strategy is $a_2$, `Paper`:

```{r}
d <- runif(100000)
dd <- cut(d, c(0, 0.354, 0.654, 1), labels=c("Win", "Tie", "Lose"))
length(dd[dd=="Win"])/100000
```

Your strategy is $a_3$, `Scissors`:

```{r}
d <- runif(100000)
dd <- cut(d, c(0, 0.354, 0.654, 1), labels=c("Lose", "Win", "Tie"))
length(dd[dd=="Win"])/100000
```

---
# Pay off matrix, includes opp payoff

Strategy      | Decision  | Rock (0.354) | Paper  (0.350) | Scissors (0.296) 
----- | ----- | ----- | ----- | -----
$a_1$ | Rock | 0, 0 |  -1, 1 | 1, -1
$a_2$ | Paper | 1, -1 | 0, 0 | -1, 1
$a_3$ | Scissors | -1, 1 | 1, -1 | 0, 0

$$\mbox{payoff}|a_1 = 0\times 0.354 - 1\times0.350 + 1\times 0.296 = -0.054 $$
$$\mbox{payoff}|a_2 =  1\times 0.354 + 0\times0.350 - 1\times 0.296 = 0.058 $$

$$\mbox{payoff}|a_3 =  -1\times 0.354 + 1\times0.350 + 0\times 0.296 = -0.004$$

There's a clear winner!

---
class: inverse middle 
# Your turn

Under a different payoff?

Strategy      | Decision  | Rock (0.354) | Paper  (0.350) | Scissors (0.296) 
----- | ----- | ----- | ----- | -----
$a_1$ | Rock | 0, 0 |  -1, 1 | 1, -1
$a_2$ | Paper | 2, -1 | -1, 0 | -1, 1
$a_3$ | Scissors | -1, 1 | 1, -1 | 0, 0

- Is it still a zero sum game?
- What is the expected payoff under each strategy?

```{r eval=FALSE}
$$\mbox{payoff}|a_1 = 0\times 0.354 - 1\times0.350 + 1\times 0.296 = -0.054 $$

$$\mbox{payoff}|a_2 =  2\times 0.354 - 1\times0.350 - 1\times 0.296 = 0.062 $$

$$\mbox{payoff}|a_3 =  -1\times 0.354 + 1\times0.350 + 0\times 0.296 = -0.004$$
```

---
# Playing until someone loses all their money

Suppose you choose strategy $a_2$, for all your turns. 

```{r}
set.seed(1)
play <- function() {
  my_money <- 1
  i <- 0
  while(my_money<2&&my_money>-1) {
    i <- i+1
    #cat(i, " ", my_money, "\n")
    d <- runif(1)
    #cat(i, ",", my_money, ",", d, "\n")
    if (d<0.354)
      my_money <- my_money+1
    else if (d>=0.654)
      my_money <-  my_money-1
  }
  return(list(nturns=i, winnings=my_money))
}
play()
```

---
# Simulate 100 times

```{r fig.height=4}
results <- NULL
for (i in 1:100) {
  results <- bind_rows(results, unlist(play()))
}
p1 <- ggplot(results, aes(x=factor(winnings))) + geom_bar()
p2 <- ggplot(results, aes(x=nturns)) + 
  geom_histogram() + xlab("Number of turns")
grid.arrange(p1, p2, ncol=2)
```

The expected earnings with strategy $a_2$ is `r mean(results$winnings)` (estimated using mean of simulated winnings).

---
# Dependency between consecutive games

People have a tendency to stay with their previous choice of moves, if they won, otherwise to switch to the what would have been the winning move assuming that the opponent won't change. Using this knowledge, could give you an advantage. We can simulate this too. Let's compare two new strategies for consecutive moves:

- $a_1$: Counter those moves of opponent as above
- $a_2$: Purely random choice of move each time

```{r}
set.seed(23)
play <- function(opp, you) {
  result <- 0
  if (opp == "Rock") {
    if (you == "Paper") {
      result <- 1
    }
    else if (you == "Scissors") {
      result <- -1
    }
  }
  else if (opp == "Paper") {
    if (you == "Rock") {
      result <- -1
    }
    else if (you == "Scissors") {
      result <- 1
    }
  }
  else if (opp == "Scissors") {
    if (you == "Rock") {
      result <- 1
    }
    else if (you == "Paper") {
      result <- -1
    }
  }
  return(result)
}
strategy1 <- function(opp, you) {
  result <- play(opp, you)
  if (result == 1 | result == -1) {
    if (you == "Rock") {
      opp_new <- "Paper"
      you_new <- "Scissors"
    }
    else if (you == "Paper") {
      opp_new <- "Scissors"
      you_new <- "Rock"
    }
    else if (you == "Scissors") {
      opp_new <- "Rock"
      you_new <- "Paper"
    }
  }
  else if (result == 0) {
    opp_new <- sample(c("Rock", "Paper", "Scissors"), 1)
    you_new <- sample(c("Rock", "Paper", "Scissors"), 1)
  }
  return(list(opp_new, you_new))
}
strategy2 <- function(opp, you) {
  result <- play(opp, you)
  if (result == 1 | result == -1) {
    if (you == "Rock") {
      opp_new <- "Paper"
      you_new <- sample(c("Rock", "Paper", "Scissors"), 1)
    }
    else if (you == "Paper") {
      opp_new <- "Scissors"
      you_new <- sample(c("Rock", "Paper", "Scissors"), 1)
    }
    else if (you == "Scissors") {
      opp_new <- "Rock"
      you_new <- sample(c("Rock", "Paper", "Scissors"), 1)
    }
  }
  else if (result == 0) {
    opp_new <- sample(c("Rock", "Paper", "Scissors"), 1)
    you_new <- sample(c("Rock", "Paper", "Scissors"), 1)
  }
  return(list(opp_new, you_new))
}
opp <- "Rock"
you <- "Rock"
s1 <- NULL
for (i in 1:100) {
  new <- strategy1(opp, you)
  opp <- new[[1]]
  you <- new[[2]]
  #cat(opp, you, "\n")
  s1 <- c(s1, play(opp, you))
}
opp <- "Rock"
you <- "Rock"
s2 <- NULL
for (i in 1:100) {
  new <- strategy2(opp, you)
  opp <- new[[1]]
  you <- new[[2]]
  #cat(opp, you, "\n")
  s2 <- c(s2, play(opp, you))
}
```

---

Results with strategy 1:

```{r}
s1
```

Results with strategy 2:

```{r}
s2
```

Expected winnings, strategy 1 are `r mean(s1)`, and for stratgey 2 are `r mean(s2)`.

---
# Non-zero sum games

Examples:

- The prisoner's dilemma
- Chicken
- Deadlock and stag hunt

[Source](https://cs.stanford.edu/people/eroberts/courses/soco/projects/1998-99/game-theory/nonzero.html)


---
class: inverse middle 
# Share and share alike

<a rel="license" href="http://creativecommons.org/licenses/by/4.0/"><img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by/4.0/88x31.png" /></a><br />This work is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>.
