dynamic-programming.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import tensorflow as tf\n",
    "import matplotlib.pyplot as plt\n",
    "from IPython.display import clear_output\n",
    "from random import randint, random\n",
    "from time import sleep"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Utilities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_board(agent_position):\n",
    "    fields = list(range(16))\n",
    "    board = \"-----------------\\n\"\n",
    "    for i in range(0, 16, 4):\n",
    "        line = fields[i:i+4]\n",
    "        for field in line:\n",
    "            if field == agent_position:\n",
    "                board += \"| A \"\n",
    "            elif field == fields[0] or field == fields[-1]:\n",
    "                board += \"| X \"\n",
    "            else:\n",
    "                board += \"|   \"\n",
    "        board += \"|\\n\"\n",
    "        board += \"-----------------\\n\"     \n",
    "    print(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------------\n",
      "| X |   |   |   |\n",
      "-----------------\n",
      "|   |   |   |   |\n",
      "-----------------\n",
      "| A |   |   |   |\n",
      "-----------------\n",
      "|   |   |   | X |\n",
      "-----------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print_board(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_state_to_state_prime_verbose_map():\n",
    "    l = list(range(16))\n",
    "    state_to_state_prime = {}\n",
    "    for i in l:\n",
    "        if i == 0 or i == 15:\n",
    "            state_to_state_prime[i] = {'N': 0, 'E': 0, 'S': 0, 'W': 0}\n",
    "        elif i % 4 == 0:\n",
    "            state_to_state_prime[i] = {'N': i - 4 if i - 4 in l else i, 'E': i + 1 if i + 1 in l else i, 'S': i + 4 if i + 4 in l else i, 'W': i}\n",
    "        elif i % 4 == 3:\n",
    "            state_to_state_prime[i] = {'N': i - 4 if i - 4 in l else i, 'E': i, 'S': i + 4 if i + 4 in l else i, 'W': i - 1 if i - 1 in l else i}\n",
    "        else:\n",
    "            state_to_state_prime[i] = {'N': i - 4 if i - 4 in l else i, 'E': i + 1 if i + 1 in l else i, 'S': i + 4 if i + 4 in l else i, 'W': i - 1 if i - 1 in l else i}\n",
    "\n",
    "    return state_to_state_prime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_random_policy():\n",
    "    return {i: {'N': 0.0, 'E': 0.0, 'S': 0.0, 'W': 0.0} if i == 0 or i == 15 else {'N': 0.25, 'E': 0.25, 'S': 0.25, 'W': 0.25} for i in range(16)} # [N, E, S, W]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_probability_map():\n",
    "    states = list(range(16))\n",
    "    state_to_state_prime = create_state_to_state_prime_verbose_map()\n",
    "    \n",
    "    probability_map = {}\n",
    "    \n",
    "    for state in states:\n",
    "        for move in [\"N\", \"E\", \"S\", \"W\"]:\n",
    "            for prime in states:\n",
    "                probability_map[(prime, -1, state, move)] = 0 if prime != state_to_state_prime[state][move] else 1\n",
    "            \n",
    "    return probability_map"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Agent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def agent(policy, starting_position=None, verbose=False):\n",
    "    l = list(range(16))\n",
    "    state_to_state_prime = create_state_to_state_prime_verbose_map()\n",
    "    agent_position = randint(1, 14) if starting_position is None else starting_position\n",
    "        \n",
    "    step_number = 1\n",
    "    action_taken = None\n",
    "    \n",
    "    if verbose:\n",
    "        print(\"Move: {} Position: {} Action: {}\".format(step_number, agent_position, action_taken))\n",
    "        print_board(agent_position)\n",
    "        print(\"\\n\")\n",
    "        sleep(2)\n",
    "    \n",
    "    while not (agent_position == 0 or agent_position == 15):\n",
    "        if verbose:\n",
    "            clear_output(wait=True)\n",
    "            print(\"Move: {} Position: {} Action: {}\".format(step_number, agent_position, action_taken))\n",
    "            print_board(agent_position)\n",
    "            print(\"\\n\")\n",
    "            sleep(1)\n",
    "        \n",
    "        current_policy = policy[agent_position]\n",
    "        next_move = random()\n",
    "        lower_bound = 0\n",
    "        for action, chance in current_policy.items():\n",
    "            if chance == 0:\n",
    "                continue\n",
    "            if lower_bound <= next_move < lower_bound + chance:\n",
    "                agent_position = state_to_state_prime[agent_position][action]\n",
    "                action_taken = action\n",
    "                break \n",
    "            lower_bound = lower_bound + chance\n",
    "                \n",
    "        step_number += 1   \n",
    "                \n",
    "    if verbose:\n",
    "        clear_output(wait=True)\n",
    "        print(\"Move: {} Position: {} Action: {}\".format(step_number, agent_position, action_taken))\n",
    "        print_board(agent_position)\n",
    "        print(\"Win!\")\n",
    "    \n",
    "    return step_number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Random policy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100.0%\n",
      "\n",
      "Average steps to finish: 19.843\n"
     ]
    }
   ],
   "source": [
    "data = []\n",
    "\n",
    "for i in range(1000):\n",
    "    clear_output(wait=True)\n",
    "    print(\"{}%\\n\".format((i + 1) / 10))\n",
    "    data.append(agent(create_random_policy()))\n",
    "    \n",
    "print(\"Average steps to finish: {}\".format(sum(data)/len(data)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Move: 9 Position: 15 Action: E\n",
      "-----------------\n",
      "| X |   |   |   |\n",
      "-----------------\n",
      "|   |   |   |   |\n",
      "-----------------\n",
      "|   |   |   |   |\n",
      "-----------------\n",
      "|   |   |   | A |\n",
      "-----------------\n",
      "\n",
      "Win!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "agent(create_random_policy(), verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Create greedy policy based on V(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_greedy_policy(V_s):\n",
    "    s_to_sprime = create_state_to_state_prime_verbose_map()\n",
    "    policy = {}\n",
    "        \n",
    "    for state in range(16):\n",
    "        \n",
    "        state_values = {a: V_s[s_to_sprime[state][a]] for a in ['N', 'S', 'E', 'W']}\n",
    "        \n",
    "        if state == 0 or state == 15:\n",
    "            policy[state] = {'N': 0.0, 'E': 0.0, 'S': 0.0, 'W': 0.0}\n",
    "        else:\n",
    "            max_actions = [k for k, v in state_values.items() if v == max(state_values.values())]\n",
    "            policy[state] = {a: 1 / len(max_actions) if a in max_actions else 0.0 for a in ['N', 'S', 'E', 'W']}\n",
    "    return policy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Iterative policy evaluation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def iterative_policy_evaluation(policy, theta=0.01, discount_rate=0.5):\n",
    "    V_s = {i: 0 for i in range(16)} # 1.\n",
    "    probablitiy_map = create_probability_map() # 2.\n",
    "\n",
    "    delta = 100 # 3.\n",
    "    while not delta < theta: # 4.\n",
    "        delta = 0 # 5.\n",
    "        for state in range(16): # 6.\n",
    "            v = V_s[state] # 7.\n",
    "            \n",
    "            total = 0 # 8.\n",
    "            for action in [\"N\", \"E\", \"S\", \"W\"]:\n",
    "                action_total = 0\n",
    "                for state_prime in range(16):\n",
    "                    action_total += probablitiy_map[(state_prime, -1, state, action)] * (-1 + discount_rate * V_s[state_prime])\n",
    "                total += policy[state][action] * action_total   \n",
    "                \n",
    "            V_s[state] = round(total, 1) # 9.\n",
    "            delta = max(delta, abs(v - V_s[state])) # 10.\n",
    "    return V_s # 11."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: 0.0, 1: -1.7, 2: -1.9, 3: -1.9, 4: -1.7, 5: -1.9, 6: -1.9, 7: -1.9, 8: -1.9, 9: -1.9, 10: -1.9, 11: -1.7, 12: -1.9, 13: -1.9, 14: -1.7, 15: 0.0}\n",
      "{0: 0.0, 1: -1.0, 2: -1.5, 3: -1.8, 4: -1.0, 5: -1.5, 6: -1.8, 7: -1.5, 8: -1.5, 9: -1.8, 10: -1.5, 11: -1.0, 12: -1.8, 13: -1.5, 14: -1.0, 15: 0.0}\n"
     ]
    }
   ],
   "source": [
    "policy = create_random_policy()\n",
    "V_s = iterative_policy_evaluation(policy)\n",
    "policy = create_greedy_policy(V_s)\n",
    "print(V_s)\n",
    "\n",
    "V_s = iterative_policy_evaluation(policy)\n",
    "policy = create_greedy_policy(V_s)\n",
    "print(V_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100.0%\n",
      "\n",
      "Average steps to finish: 2.98\n"
     ]
    }
   ],
   "source": [
    "data = []\n",
    "\n",
    "for i in range(1000):\n",
    "    clear_output(wait=True)\n",
    "    print(\"{}%\\n\".format((i + 1) / 10))\n",
    "    data.append(agent(policy))\n",
    "    \n",
    "print(\"Average steps to finish: {}\".format(sum(data)/len(data)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Move: 3 Position: 15 Action: S\n",
      "-----------------\n",
      "| X |   |   |   |\n",
      "-----------------\n",
      "|   |   |   |   |\n",
      "-----------------\n",
      "|   |   |   |   |\n",
      "-----------------\n",
      "|   |   |   | A |\n",
      "-----------------\n",
      "\n",
      "Win!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "agent(policy, verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Value iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def value_iteration(V_s, theta=0.01, discount_rate=0.5):\n",
    "    probablitiy_map = create_probability_map()\n",
    "\n",
    "    delta = 100\n",
    "    while not delta < theta:\n",
    "        delta = 0\n",
    "        for state in range(1, 15):\n",
    "            v = V_s[state]\n",
    "            \n",
    "            totals = {}\n",
    "            for action in [\"N\", \"S\", \"E\", \"W\"]:\n",
    "                total = 0\n",
    "                for state_prime in range(16):\n",
    "                    total += probablitiy_map[(state_prime, -1, state, action)] * (-1 + discount_rate * V_s[state_prime])\n",
    "                totals[action] = total\n",
    "            \n",
    "            V_s[state] = round(max(totals.values()), 4)\n",
    "            delta = max(delta, abs(v - V_s[state]))\n",
    "    return V_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: 0, 1: -1.0, 2: -1.5, 3: -1.75, 4: -1.0, 5: -1.5, 6: -1.75, 7: -1.5, 8: -1.5, 9: -1.75, 10: -1.5, 11: -1.0, 12: -1.75, 13: -1.5, 14: -1.0, 15: 0}\n"
     ]
    }
   ],
   "source": [
    "V_s = {i: 0 for i in range(16)}\n",
    "V_s = value_iteration(V_s)\n",
    "policy = create_greedy_policy(V_s)\n",
    "\n",
    "print(V_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100.0%\n",
      "\n",
      "Average steps to finish: 3.035\n"
     ]
    }
   ],
   "source": [
    "data = []\n",
    "\n",
    "for i in range(1000):\n",
    "    clear_output(wait=True)\n",
    "    print(\"{}%\\n\".format((i + 1) / 10))\n",
    "    data.append(agent(policy))\n",
    "    \n",
    "print(\"Average steps to finish: {}\".format(sum(data)/len(data)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Move: 4 Position: 15 Action: S\n",
      "-----------------\n",
      "| X |   |   |   |\n",
      "-----------------\n",
      "|   |   |   |   |\n",
      "-----------------\n",
      "|   |   |   |   |\n",
      "-----------------\n",
      "|   |   |   | A |\n",
      "-----------------\n",
      "\n",
      "Win!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "agent(policy, verbose=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: {'E': 0, 'N': 0, 'S': 0, 'W': 0},\n",
       " 1: {'E': 2, 'N': 1, 'S': 5, 'W': 0},\n",
       " 2: {'E': 3, 'N': 2, 'S': 6, 'W': 1},\n",
       " 3: {'E': 3, 'N': 3, 'S': 7, 'W': 2},\n",
       " 4: {'E': 5, 'N': 0, 'S': 8, 'W': 4},\n",
       " 5: {'E': 6, 'N': 1, 'S': 9, 'W': 4},\n",
       " 6: {'E': 7, 'N': 2, 'S': 10, 'W': 5},\n",
       " 7: {'E': 7, 'N': 3, 'S': 11, 'W': 6},\n",
       " 8: {'E': 9, 'N': 4, 'S': 12, 'W': 8},\n",
       " 9: {'E': 10, 'N': 5, 'S': 13, 'W': 8},\n",
       " 10: {'E': 11, 'N': 6, 'S': 14, 'W': 9},\n",
       " 11: {'E': 11, 'N': 7, 'S': 15, 'W': 10},\n",
       " 12: {'E': 13, 'N': 8, 'S': 12, 'W': 12},\n",
       " 13: {'E': 14, 'N': 9, 'S': 13, 'W': 12},\n",
       " 14: {'E': 15, 'N': 10, 'S': 14, 'W': 13},\n",
       " 15: {'E': 0, 'N': 0, 'S': 0, 'W': 0}}"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "create_state_to_state_prime_verbose_map()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: {'E': 0.0, 'N': 0.0, 'S': 0.0, 'W': 0.0},\n",
       " 1: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 2: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 3: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 4: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 5: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 6: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 7: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 8: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 9: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 10: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 11: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 12: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 13: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 14: {'E': 0.25, 'N': 0.25, 'S': 0.25, 'W': 0.25},\n",
       " 15: {'E': 0.0, 'N': 0.0, 'S': 0.0, 'W': 0.0}}"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "create_random_policy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1024"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(create_probability_map())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}