# Game instructions
Consider the following board game: A game board has 12 spaces. The swine senses the Christmas spirit and manages to run away from home couple of weeks beforehand. Fortunately for it, the butcher is a bit of a drunkard and easily distracted. The swine starts on space 7, and a butcher on space 1. On each game turn a 6-sided die is rolled. On a result of 1 to 3, the swine moves that many spaces forward. On a result of 5 or 6, the butcher moves that many spaces forward. On result 4, both advance one space forward. The swine wins if it reaches the river at space 12 (the final roll does not have to be exact, moving past space 12 is OK). The butcher wins if he catches up with the swine (or moves past it).

What are the probabilities of winning for the swine and the butcher?

Your assignment is to create a mathematical or statistical model to find these probabilities, and implement the solution as a computer program in whatever language you like. You will present it during the interview and we will discuss it with you. 

Consider the following questions as well: 
- Can you make your model easily extendable for different initial conditions (board size and initial positions)?
- Pros and cons of the approach?
- Can you say something about how long the game takes (also under different initial conditions)?


```python
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import itertools
```

# Model: dynamic programming

#### Initialize game parameters


```python
board_size = 12
swine_start = 7
butcher_start = 1

if butcher_start >= swine_start:
    raise ValueError('Error in starting positions: The swine has to start ahead of the butcher.')
elif swine_start >= board_size:
    raise ValueError('Error in starting positions: The river has to lie ahead of the swine.')
```

#### DP formulation
Assume a fixed board size. Let $s$ be the position of the swine on the board, $b$ the position of the butcher on the board, and $F(s, b)$ the probability that the swine wins the game if the swine is at space $s$ and the butcher at space $b$.

The recurrence relation can be formulated as follows:

\begin{align}
    F(s, b \mid s \geq \text{board size}) = & 1 & \text{Swine has won with 100% probability if end of board is reached} \\
    F(s, b \mid s \leq b) = & 0 & \text{Swine wins with 0% probability if the butcher is ahead or at the same square} \\
    F(s, b) =  & 1/6 \cdot F(s+1, b) + & \text{DP recurrence relation} \\
               & 1/6 \cdot F(s+2, b) + \\
               & 1/6 \cdot F(s+3, b) + \\
               & 1/6 \cdot F(s+1, b+1) + \\
               & 1/6 \cdot F(s, b+5) + \\
               & 1/6 \cdot F(s, b+6)
\end{align}

The equations express that the swine's probability of winning is a weighted combination of its winning chances in all possible subsequent states.

#### Prefill winning probabilities known at start


```python
swine_positions = np.arange(swine_start, board_size+1)
butcher_positions = np.arange(butcher_start, board_size+1)
probs = pd.DataFrame(np.nan*np.ones(shape=(len(swine_positions), len(butcher_positions))), index=swine_positions, columns=butcher_positions)

# Swine has won with 100% probability if end of board is reached. 
probs.loc[board_size, :] = 1.0 

# Swine wins with 0% probability if the butcher is ahead or at the same square.
# I.e. upper right triangle should be zeros.
mask = np.ones(probs.shape, dtype='bool')
triu = np.triu_indices(n=probs.shape[0], m=probs.shape[0])
mask[tuple([triu[0], triu[1] + probs.shape[1] - probs.shape[0]])] = False
probs.where(mask, other=0.0, inplace=True)
```


```python
probs
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>10</th>
      <th>11</th>
      <th>12</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>7</th>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
    </tr>
    <tr>
      <th>8</th>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
    </tr>
    <tr>
      <th>9</th>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
    </tr>
    <tr>
      <th>10</th>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>0.0</td>
      <td>0.0</td>
      <td>0.0</td>
    </tr>
    <tr>
      <th>11</th>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>NaN</td>
      <td>0.0</td>
      <td>0.0</td>
    </tr>
    <tr>
      <th>12</th>
      <td>1.0</td>
      <td>1.0</td>
      <td>1.0</td>
      <td>1.0</td>
      <td>1.0</td>
      <td>1.0</td>
      <td>1.0</td>
      <td>1.0</td>
      <td>1.0</td>
      <td>1.0</td>
      <td>1.0</td>
      <td>0.0</td>
    </tr>
  </tbody>
</table>
</div>



#### Solve DP


```python
def F(probs, sp, bp):
    """Calculate the swine's probability of winning based on the current swine and butcher position.
    
    Arguments
        - probs: dataframe of swine's winning chances (known and unknown)
        - sp:    swine's current position
        - bp:    butcher's current position
    """
    
    # Check that the current positions are not lower than the starting positions.
    if sp < probs.index.min():
        sp = probs.index.min()
        print('Swine position lower than starting position: using swine starting position ({}) instead.'.format(swine_start))
    if bp < probs.columns.min():
        bp = probs.columns.min()
        print('Butcher position lower than starting position: using butcher starting position ({}) instead.'.format(butcher_start))
    
    # Check that neither the swine nor the butcher has already reached the end of the board.
    # If so, reset position to the last space on the board.
    if sp > probs.index.max():
#         print('Swine position exceeds board length: using highest possible position instead.')
        sp = probs.index.max()
    if bp > probs.columns.max():
#         print('Butcher position exceeds board length: using highest possible position instead.')
        bp = probs.columns.max()
    
    # If the requested probability is already known: return from storage.
    if not np.isnan(probs.loc[sp, bp]):
        return probs.loc[sp, bp]
    
    # Else: calculate the requested probability according to the DP recurrence, store and return.
    else:
        prob = 1/6 * F(probs, sp+1, bp) \
               + 1/6 * F(probs, sp+2, bp) \
               + 1/6 * F(probs, sp+3, bp) \
               + 1/6 * F(probs, sp+1, bp+1) \
               + 1/6 * F(probs, sp, bp+5) \
               + 1/6 * F(probs, sp, bp+6)
        
        probs.loc[sp, bp] = prob
        
        return prob
```


```python
swine_winning_prob = F(probs, swine_start, butcher_start)
print('The swine and the butcher start at space {} and {} respectively. The board is {} spaces long.'.format(swine_start, butcher_start, board_size))
print('The probability that the swine wins is {:.1f}%.'.format(swine_winning_prob*100))
```

    The swine and the butcher start at space 7 and 1 respectively. The board is 12 spaces long.
    The probability that the swine wins is 51.2%.


b0b1f31011d80ff94471c0a6d78e4ab2d8afb62a
ipynb
Jupyter Notebook
dp.ipynb
MeekeRoet/swine-escape
4201354dbc6cef7f84b6c6b7ad395292b29cccf8
MIT
dp.ipynb
MeekeRoet/swine-escape
4201354dbc6cef7f84b6c6b7ad395292b29cccf8
MIT
dp.ipynb
MeekeRoet/swine-escape
4201354dbc6cef7f84b6c6b7ad395292b29cccf8
MIT
Qwen/Qwen-72B
1. YES
2. YES