{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "library(ggplot2)\n",
    "# The game parameters are defined here\n",
    "\n",
    "# Size of the board (number of squares)\n",
    "board_size <- 50\n",
    "# The dice to choose from\n",
    "dice <- c(4, 6)\n",
    "# Cost of using a die\n",
    "costs <- rep(1, length(dice)) # By default, expected turn count is minimized\n",
    "\n",
    "# The pairs of squares connected with ladders\n",
    "# First column correspond to start squares, second to end squares\n",
    "ladders <- matrix(c(2, 10,\n",
    "                    8, 38,\n",
    "                    23, 41), ncol = 2, byrow = TRUE)\n",
    "# The pairs of squares connected with snakes\n",
    "snakes <- matrix(c(20, 14,\n",
    "                    49, 12,\n",
    "                    31, 7), ncol = 2, byrow = TRUE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Some optional validity checks\n",
    "if (any(ladders > board_size)) {\n",
    "  print(\"Some ladders are outside the game board.\")\n",
    "}\n",
    "if (any(snakes > board_size - 1)) {\n",
    "  print(\"Some snakes are outside the game board.\")\n",
    "}\n",
    "if (any(ladders[, 2] %in% snakes[, 1])) {\n",
    "  print(\"Some ladders lead to snake squares.\")\n",
    "}\n",
    "if (any(snakes[, 2] %in% ladders[, 1])) {\n",
    "  print(\"Some snakes lead to ladder squares.\")\n",
    "}\n",
    "if (length(costs) != length(dice)) {\n",
    "  print(\"The costs are not defined correctly.\")\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create transition matrices related to throwing a die\n",
    "create_transition_matrix <- function(die) {\n",
    "  m <- matrix(0, nrow = board_size, ncol = board_size)\n",
    "  for (i in seq_len(board_size - 1)) {\n",
    "    possible_squares <- seq(i+1, min(board_size, i + die))\n",
    "    m[i, possible_squares] <- 1 / die\n",
    "    m[i, board_size] <- 1 + m[i, board_size] - length(possible_squares) / die\n",
    "  }\n",
    "  for (i in seq_len(nrow(ladders))) {\n",
    "    m[, ladders[i, 2]] <- m[, ladders[i, 2]] + m[, ladders[i, 1]]\n",
    "    m[, ladders[i, 1]] <- 0\n",
    "  }\n",
    "  for (i in seq_len(nrow(snakes))) {\n",
    "    m[, snakes[i, 2]] <- m[, snakes[i, 2]] + m[, snakes[i, 1]]\n",
    "    m[, snakes[i, 1]] <- 0\n",
    "  }\n",
    "  m[board_size, board_size] <- 1\n",
    "  m\n",
    "}\n",
    "\n",
    "transition_matrices <- lapply(dice, create_transition_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solve the problem using value iteration\n",
    "\n",
    "# Initialization\n",
    "J <- (board_size - seq_len(board_size)) / (max(dice + 1) / 2)\n",
    "policy <- rep(\"-\", board_size)\n",
    "\n",
    "# Value iteration\n",
    "n_iters <- board_size * 2\n",
    "for (iter in seq_len(n_iters)) {\n",
    "  for (i in seq_len(board_size - 1)) {\n",
    "    penalty <- sapply(seq_along(dice), function(x) {costs[x] +\n",
    "        sum(J * transition_matrices[[x]][i, ])})\n",
    "    J[i] <- min(penalty)\n",
    "    policy[i] <- as.character(dice[which.min(penalty)])\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Visualize the results\n",
    "\n",
    "square_type <- rep(\"Normal\", board_size)\n",
    "square_type[ladders[, 1]] <- \"Ladder start\"\n",
    "square_type[ladders[, 2]] <- \"Ladder end\"\n",
    "square_type[snakes[, 1]] <- \"Snake start\"\n",
    "square_type[snakes[, 2]] <- \"Snake end\"\n",
    "\n",
    "# Note: A player should not end to a \"Ladder start\" or \"Snake start\" square\n",
    "# The costs correspond to a situation where the game is started from these squares ignoring the snake/ladder\n",
    "solution <- data.frame(\n",
    "  square = seq_len(board_size),\n",
    "  square_type = square_type,\n",
    "  expected_cost = J,\n",
    "  Die = as.factor(policy)\n",
    ")\n",
    "\n",
    "# Plot the expected amount of turns that are needed to win the game\n",
    "\n",
    "ggplot(solution, aes(x = square, y = expected_cost,\n",
    "                     col = Die, shape = square_type)) + \n",
    "  geom_point() +\n",
    "  xlab(\"Square\") +\n",
    "  ylab(\"Turns needed (expectation)\") + \n",
    "  labs(shape = \"Square type\") + \n",
    "  theme_bw()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "R",
   "language": "R",
   "name": "ir"
  },
  "language_info": {
   "codemirror_mode": "r",
   "file_extension": ".r",
   "mimetype": "text/x-r-source",
   "name": "R",
   "pygments_lexer": "r",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}