{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "industrial-employer",
   "metadata": {},
   "source": [
    "# Dice trading"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unique-smooth",
   "metadata": {},
   "source": [
    "1. We consider a game of dices.\n",
    "At the beginning of a turn the player have a certain amount of points (starting with $0$). He can decide\n",
    "to buy one new dice (one per turn maximum, to be kept until the end) for $p = 5$ points, only if he have\n",
    "at least $p + 1$ points. The player then throw his dices ($6$ faces, independent, equilibrated), and add the\n",
    "maximum of all dices to his points. The game play for $T = 10$ turns. The player want to maximize the\n",
    "expected number of points at the end. For simplicity we assume that we can have at most $3$ dices.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "educational-catholic",
   "metadata": {},
   "source": [
    "Example ($9$ points, $5$ turn game)\n",
    "$$\n",
    "\\begin{aligned}\n",
    "&\\\\\n",
    "&\\begin{array}{|l|l|l|l|}\n",
    "\\hline\n",
    "\\text{turn} & \\text{dice roll} & \\text{action} &\\text{total points} \\\\\n",
    "\\hline\n",
    "1 &3 &\\text{ cannot buy} &3  \\\\ \\hline\n",
    "2 &4 &\\text{ do not buy} & 7 \\\\ \\hline\n",
    "3 &5 &\\text{buy} & 7  \\\\ \\hline\n",
    "4 & \\max(3,2) & \\text{buy} & 5\\\\ \\hline\n",
    "5 & \\max(1,2,6) & \\text{do not buy} & 11 \\\\ \\hline\n",
    "\\end{array}\n",
    "\\\\\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unlimited-telescope",
   "metadata": {},
   "source": [
    "(a) Determine the dynamical system considered in this problem. (specify state, control, dynamics)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "electronic-former",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "trying-twins",
   "metadata": {},
   "source": [
    "(b) A strategy is a function taking as argument the time-step t and the current state x and returning\n",
    "a control. Implement a very simple strategy (a heuristic)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "native-annotation",
   "metadata": {},
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "\u001b[91msyntax: extra token \"Write\" after end of expression\u001b[39m",
     "output_type": "error",
     "traceback": [
      "\u001b[91msyntax: extra token \"Write\" after end of expression\u001b[39m",
      "",
      "Stacktrace:",
      " [1] top-level scope at In[1]:1",
      " [2] include_string(::Function, ::Module, ::String, ::String) at ./loading.jl:1091"
     ]
    }
   ],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "danish-earth",
   "metadata": {},
   "source": [
    "(c) Write a simulator taking as argument a strategy and an integer returning the estimated expected cost associated to the strategy with $95\\%$ confidence interval."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "three-status",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "funded-sequence",
   "metadata": {},
   "source": [
    "(d) Compute the law of the maximum of 1,2 or 3 dices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "stylish-skiing",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "express-negative",
   "metadata": {},
   "source": [
    "(e) Find the optimal value $V_0$ and strategy $\\pi^\\star$ by Dynamic Programming. Describe the optimal strategy in simple term."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "judicial-director",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "sound-ancient",
   "metadata": {},
   "source": [
    "(f) Check by simulation that the optimal value $V_0$ is indeed obtained when using the strategy $\\pi^\\star$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "athletic-reward",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "superior-stanford",
   "metadata": {},
   "source": [
    "(g) For which horizon will it never be interesting to buy (at price 5 ?)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "recovered-injury",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "documented-halloween",
   "metadata": {},
   "source": [
    "(h) What happens if we do not restrict the maximum number of dices that one can have ? (still buying only one per turn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "entertaining-crown",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "amber-hampton",
   "metadata": {},
   "source": [
    "2. We now consider an extension of the previous game. At any turn, once the dices are thrown, the player, if he has at least 2 dice, can loose a dice to double the gain of the throw. As before he can buy a dice at the beginning of next round."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "controversial-communications",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "funded-phenomenon",
   "metadata": {},
   "source": [
    "(a) Assuming that we can have at most 5 dices, compute the optimal value and describe the optimal strategy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "plastic-pottery",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "incident-anthropology",
   "metadata": {},
   "source": [
    "(b) What happen if we do not restrict the maximum number of dices that can be owned by a player ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "sacred-click",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "registered-ghana",
   "metadata": {},
   "source": [
    "(c) Returning with a maximum of 5 dices, we now assume that, at the end of the game, the remaining\n",
    "dices are sold to the ”next player” for K where K is given in the following table:\n",
    "$$\n",
    "\\begin{aligned}\n",
    "&\\\\\n",
    "&\\begin{array}{|c|c|c|c|c|c|}\n",
    "\\hline\n",
    "D &1 &2 &3 &4 &5 \\\\ \\hline\n",
    "K &0 &2 &4 &5 &8 \\\\ \\hline\n",
    "\\end{array}\n",
    "\\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "What is the optimal value for this problem ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "sophisticated-origin",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "dynamic-monte",
   "metadata": {},
   "source": [
    "(d) What value K should you use at the end of the $10$ turn game to represent a $20$ turn game ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ecological-vermont",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "dirty-plain",
   "metadata": {},
   "source": [
    "e) Suggest an efficient way of finding a quasi-optimal strategy and value for a $10^{10}$ turn game."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "interior-fundamentals",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.6.2",
   "language": "julia",
   "name": "julia-1.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}