BruteForceCartepole.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Brute Forcing the Cartpole problem\n",
    "\n",
    "Gym's Cartpole problem is a common benchmark, but how hard is it? To investigate this problem I decided to see how hard it is to brute force a solution.\n",
    "\n",
    "Read more here: https://medium.com/@twocolossi/brute-forcing-the-cartpole-problem-4d04c9c34b12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Imports\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gym\n",
    "from gym import envs\n",
    "import numpy as np\n",
    "import time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Policy Generator\n",
    "\n",
    "To brute force the problem, we discretise the state space. The 'Pole Angle' and 'Pole Velocity At Tip' are both split into 3 buckets creating 9 possible states of the environment (we ignore the cart position and velocity observations). Cartpole only has 2 actions, so with 9 states, we have 512 (2^9) deterministic greedy policies (A Policy that will always pick the same one action given the same state). \n",
    "\n",
    "To create the policies, we convert the numbers 0 to 511 to binary and reshape them to a 3 by 3 matrix. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def createPolicy(id):\n",
    "    binary = unpackbits(np.array([id]), 9)\n",
    "    return np.reshape(binary, (3,3))\n",
    "\n",
    "#Credit for this function https://stackoverflow.com/a/51509307\n",
    "def unpackbits(x, num_bits):\n",
    "          xshape = list(x.shape)\n",
    "          x = x.reshape([-1,1])\n",
    "          to_and = 2**np.arange(num_bits).reshape([1,num_bits])\n",
    "          return (x & to_and).astype(bool).astype(int).reshape(xshape + [num_bits])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create a class to discretise the observation space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DiscreteBox(object):\n",
    "    def __init__(self, low, high, shape):\n",
    "        self.low, self.high, self.shape = low, high, shape\n",
    "\n",
    "    def Discretise(self, state):   \n",
    "        discreteState = [int(np.floor((state[i] - self.low[i])/(self.high[i]-self.low[i])*(self.shape[i]-1))) for i in range(len(state))]\n",
    "        return tuple([np.min([self.shape[i]-1, np.max([discreteState[i], 0])]) for i in range(len(state))])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create environment and discretiser\n",
    "\n",
    "We have set the bounds for discrete space tighter than that seen in the observation space. We have a very limited amount of buckets so we need one of the buckets to be in a stable area of the state space. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = gym.make('CartPole-v1')\n",
    "\n",
    "thetaHigh = 10 * 2 * np.pi / 360\n",
    "high = np.array([thetaHigh, np.radians(15)])\n",
    "observationSpace = DiscreteBox(-high, high, (3,3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Identify possible solutions\n",
    "\n",
    "It would be computationally expensive to fully evaluate every policy, so, to start, we filter out policies by running them on cartpole once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "34 potential solutions found in 1.7 seconds.\n"
    }
   ],
   "source": [
    "startTime = time.time()\n",
    "resample = []\n",
    "for i in range(512):\n",
    "    state = env.reset()\n",
    "    policy = createPolicy(i)\n",
    "    step = 0\n",
    "    while True:\n",
    "        step += 1\n",
    "        state = observationSpace.Discretise(state[2:])\n",
    "        action = policy[state]\n",
    "        state, r, terminal, info = env.step(action)\n",
    "        if terminal or step >= 200:\n",
    "            if step > 195:\n",
    "                resample.append(i)\n",
    "            break\n",
    "\n",
    "print(str(len(resample)) + ' potential solutions found in ' + \"{:.1f}\".format(time.time()-startTime) + ' seconds.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find solutions\n",
    "\n",
    "We can now run each possilbe solution for 100 episodes. If they average over 195 reward they are solutions to the cartpole problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "Solution at Index: 60 , score: 200.0\nSolution at Index: 124 , score: 200.0\nSolution at Index: 188 , score: 200.0\nSolution at Index: 252 , score: 200.0\nSolution at Index: 316 , score: 200.0\nSolution at Index: 380 , score: 200.0\nSolution at Index: 444 , score: 200.0\nSolution at Index: 508 , score: 200.0\n8 solutions found in 39.1 seconds.\n"
    }
   ],
   "source": [
    "startTime, solutionCount = time.time(), 0\n",
    "for i in resample:\n",
    "    avg = 0\n",
    "    for k in range(100):\n",
    "        state = env.reset()\n",
    "        policy = createPolicy(i)\n",
    "        step = 0\n",
    "        while True:\n",
    "            step += 1\n",
    "            state = observationSpace.Discretise(state[2:])\n",
    "            action = policy[state]\n",
    "            state, r, terminal, info = env.step(action)\n",
    "            if terminal or step >= 200:\n",
    "                avg += step\n",
    "                break\n",
    "    if avg/100 >= 195:\n",
    "        print(\"Solution at Index: \" + str(i) + \" , score: \" + str(avg/100))\n",
    "        solutionCount += 1\n",
    "\n",
    "print(str(solutionCount) + ' solutions found in ' + \"{:.1f}\".format(time.time()-startTime) + ' seconds.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "8 solutions found at about 5 seconds per solution. That is pretty competitive for solve times. \n",
    "\n",
    "Now, clearly, this is not a good method to solve the cartpole problem. The solutions are very unstable, none of them could balance the pole for more than 300 timesteps.  Yet, they are valid solutions. I don't think that this discredits cartpole as a benchmark problem, but perhaps the reward pass average should be increased."
   ]
  }
 ],
 "metadata": {
  "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.7.5-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python37564bit47d146cc5c834d3aadd19303fc80d1ee",
   "display_name": "Python 3.7.5 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}