Report.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conway's Game of Life controlled with Reinforcement Learning\n",
    "*Lucas Wilson, Dec 1, 2018*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "\n",
    "This project was to see how easily Conway's Game of Life (CGOL) could be controlled. This experimentation could have value in a couple of different areas. CGOL is a type of cellular automation and has emergent properties.\n",
    "* By \"controlling\" the system, it demonstrates an understanding of how underlying systems (individual cell manipulation) has an effect on large, emergent behaviors (cell population and structures). Emergent behavior is largely uncorrelated with underlying states, so such a control is not expected.\n",
    "* If CGOl is representative of processes found naturally in nature, then controlling the behavior of CGOl implies a potential to control processes in nature. With deep learning, this may be possible.\n",
    "\n",
    "To analyze this, I created the following:\n",
    "* A headless model of CGOL (used by the GUI) which can quickly simulate CGOL independent of the GUI\n",
    "* A Conway's Game of Life GUI for generating, viewing, and simulating Conway's Game of Life simulations.\n",
    "* A restricted feed forward neural network package made with PyTorch.\n",
    "* A Problem class definition which describes a problem for AI agents to interact with.\n",
    "* A general reinforcement agent to control these Problem objects\n",
    "\n",
    "I represented the CGOL problem with my Problem class. My reinforcement agent interacts with problems that follow the specified API, so it was then able to interact with my CGOL model. I defined several aspects of what available actions could be taken from specific states, how the initial state was created, what constituted as a reward (usually maximizing cell population), and how the size of the problem affected how the RL agent performed. I used making random actions as a control.\n",
    "\n",
    "### Findings\n",
    "* My final experiment shows that with enough training, the rl agent is capable of keeping a CGOL system moving (not filled with still life).\n",
    "* The RL agent favored not exploring the system to more passive moves: The RL agent's strategy was to create still life structures and then stop interacting with the system. If forced to be more interactive (reward incentives or limiting passive actions), it performed better.\n",
    "* If the initial state was always the same, it was very good at memorizing paths to maximize reward. However, if it was random, it performed worse. With random states, it would try to converge to a still life, and then stop interacting with the system. If it failed to converge, it performed as well as the control. This implies a lack of understanding of the system but instead a memorization of paths to still life.\n",
    "* For smaller cell grids, RL is extremely effective in maximizing the population of cells. That is because it is capable of memorizing the state space as opposed to learning it. For large state spaces, random action (control) outperformed the RL agent in population, but the RL agent was able to keep cells alive for longer (generations vs boom and bust populations).\n",
    "* The RL agent is capable of outperforming a random agent, but it lacks a true understanding of the system.\n",
    "\n",
    "# Methods\n",
    "\n",
    "I created a python package called `cgolai` to assist with this experimentation. The full source code for this is on [my github](https://github.com/larkwt96/c440), but all files needed are included in the submitted tar file.\n",
    "\n",
    "###  A headless model of CGOL (used by the GUI) which can quickly simulate CGOL independent of the GUI\n",
    "\n",
    "I built a headless model of CGOL so that I could run CGOl simulations quickly without the requirement of a GUI. I wrote the code myself. It's very efficient and designed specifically to work well with other components (the GUI and CgolProblem class). It records past cell states as well as what cells were modified before stepping to the next state. It's also capable of saving these records to file so that I can load them back up later.\n",
    "\n",
    "###  A Conway's Game of Life GUI for generating, viewing, and simulating Conway's Game of Life simulations.\n",
    "\n",
    "This component has little to do with AI, so you can skip it unless you're interested. I had fun with this since I haven't built many GUIs that weren't web pages. I struggled a lot to learn how pygame graphics work and how to design the view/controller and model dynamic. The only reason I built this was to be able to easily view and interact with CGOL simulations (which the model above generates).\n",
    "\n",
    "The GUI was built with pygame and generally follows the MVC pattern. Design and implementation were done completely by me with guidance from the pygame website docs and things I learned from CS 414 (OO software design). MVC was a logical decision since I already had the requirement of the CGOL model being independent, but the view and controller are very closely integrated (but still separate) since it's a small program.\n",
    "\n",
    "The software has lots of functionalities that let you save, load and draw your own CGOL initial conditions. You can let them play or you can move step by step (with rewinding also as a possibility). It's also easy to run:\n",
    "`python3 -m cgolai.cgol -f saved_simulation.dat`\n",
    "\n",
    "(I'm most proud of the game loop structure. Most guides have a loop which checks for events, but this uses CPU time to constantly check. I designed it to be completely event driven so that it will wait until an event occurs and act on it. However, when events occur very quickly, the thread swapping degraded performance. To solve this, I had it process all events when a single event was identified. Then, if lots of events were generated at once (a mouse drag or high simulation rate for example), it would process all of them while only blocking on one. While my simulation is paused, the CPU is completely idol.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the initial state. You can see dots in the middle. This symbolize flipped cells.\n",
    "\n",
    "<img src=\"proj/img/demo1.png\" style=\"display: inline-block;\" width=\"400px\" height=\"600px\"/>\n",
    "\n",
    "Here is the state a few iterations later\n",
    "\n",
    "<img src=\"proj/img/demo2.png\" style=\"display: inline-block;\" width=\"200px\" height=\"300px\"/>\n",
    "<img src=\"proj/img/demo3.png\" style=\"display: inline-block;\" width=\"200px\" height=\"300px\"/>\n",
    "<img src=\"proj/img/demo4.png\" style=\"display: inline-block;\" width=\"200px\" height=\"300px\"/>\n",
    "\n",
    "And about 100 iterations later:\n",
    "\n",
    "<img src=\"proj/img/demo5.png\" style=\"display: inline-block;\" width=\"200px\" height=\"300px\"/>\n",
    "\n",
    "This is a state filled with still life and oscillators. The cells will stay alive forever. My RL agent would converge to these and then avoid changing cells near any of the structures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  (Failed) Personal implementation of Neural Network\n",
    "\n",
    "Originally, I planned to implement a Neural Network manually, but it didn't work. I did the math to derive the gradient of the weights for batch stochastic gradient descent, but implementation doesn't work as well. \n",
    "\n",
    "**Problems**\n",
    "* NN doesn't fit well compared to given NN code from class and compared to the pytorch NN I built.\n",
    "* Weights and gradients explode\n",
    "\n",
    "**Why?**\n",
    "\n",
    "Probably incorrect math.\n",
    "\n",
    "###  A restricted feed forward neural network package made with PyTorch.\n",
    "\n",
    "I modeled the design using the documentation from [their website](https://pytorch.org/tutorials/beginner/blitz/neural_networks_tutorial.html). Instead of building my own `torch.nn.Module`, I used `torch.nn.Sequential` since it was exactly what I needed (a restricted feed forward neural network). I created a wrapper class called `cgolai.ai.NNTorch` for this module which builds the network as well as trains it.\n",
    "\n",
    "###  A Problem class definition which describes a problem for AI agents to interact with.\n",
    "\n",
    "I created a problem API:\n",
    "* A goal: maximize or minimize reward.\n",
    "* An initial state. `reset()` will initialize the state.\n",
    "* A set of available actions. `actions()` will return a list of actions\n",
    "* A means of performing actions. `do(action)` will perform the chosen action and return the state-action pair and reward\n",
    "* A definition of the state-action pair for SARSA. `key(action)` will return a state-action pair.\n",
    "* A means of checking for terminal states. `is_terminal()` will check for terminal states.\n",
    "\n",
    "The RL agent interacts with these objects. I separated this functionality so that I could insert whatever problem definition I want. This allows me to define other problems (such as Hanoi for testing) as well as variable problem definitions where I can limit the type of actions the RL agent can make.\n",
    "\n",
    "###  A general reinforcement agent to control these Problem objects\n",
    "\n",
    "The neural network Q-function uses my `pytorch` network, so back propagation and parameter optimization is handled automatically. I use ReLU as the activation functions and Adam as optimization technique.\n",
    "\n",
    "The Reinforcement Learning Agent was designed to model the code given in lecture 21 (RL with Neural Network as Q-function). The SARSA tuple comes from the problem object used by the reinforcement agent. The RL agent runs through the problem several times (ether reaching a maximum allowed steps or reaching a goal state). It collects Q-values and rewards. Once several runs have been made, the Q function is updated in batches.\n",
    "\n",
    "$Q(s_i, a_i) \\leftarrow r + Q(s_{i+1}, a_{i+1})$\n",
    "\n",
    "I update Q with TD but with a discount factor of 1 and a learning rate of 1 (so it's not really TD).\n",
    "\n",
    "Here is the general process of a single batch (some lines have been removed for readability).\n",
    "```python\n",
    "# reset the problem\n",
    "steps = 0\n",
    "self._problem.reset()\n",
    "\n",
    "# get first state-action key and reward\n",
    "action, q_val = self.choose_best_action(explore=True)\n",
    "key, reward = self._problem.do(action)\n",
    "\n",
    "# while there are still more state-action keys, explore them\n",
    "while not self._problem.is_terminal():\n",
    "\n",
    "    # step\n",
    "    steps += 1\n",
    "\n",
    "    # get expected Q-value for next action\n",
    "    action, q_val = self.choose_best_action(explore=True)\n",
    "\n",
    "    # collect sample: Q(s_i, a_i) = r + Q(s_i+1, a_i+1)\n",
    "    samples.append([*key, reward, q_val])\n",
    "\n",
    "    # get next key and reward\n",
    "    key, reward = self._problem.do(action)\n",
    "    replay_samples.append(key)\n",
    "```\n",
    "\n",
    "One difference with my code and the code provided is that my code never evaluates good actions to be taken from a goal state.\n",
    "\n",
    "### Experiment Results\n",
    "\n",
    "More details for experiments are in the [Experimentation](#Experimentation) section. The most notable experiment is Experiment 6 where I fix all the problems identified by experiments 1-5. **You don't have to read details for experiments 1-5, but do read experiment 6 if any.**\n",
    "\n",
    "#### Experiment 1\n",
    "* The optimal solution is to find a means of generating still life and then make no actions on the system.\n",
    "\n",
    "#### Experiment 2\n",
    "* However, it performed very similarly since it often found a way to choose cells which don't affect the generated still life structures.\n",
    "\n",
    "#### Experiment 3\n",
    "* Removing the ability to idle actually increases the performance of the RL agent (possibly due to better forced exploration).\n",
    "* Randomness hurts the performance as expected, but the RL agent is still capable of guiding the cells into still life structures when it recognizes the state.\n",
    "\n",
    "#### Experiment 4\n",
    "* I suspect that this factor doesn't have much of an affect on RL since the state deviates from the initial state so quickly.\n",
    "\n",
    "#### Experiment 5\n",
    "* RL is memorizing the small state space and doesn't perform well in large state spaces.\n",
    "\n",
    "**At this point, I decided to redesign how I was experimenting and how the problem space was designed altogether. Experiment 6 is much more telling and accurate.**\n",
    "\n",
    "#### Experiment 6\n",
    "* RL is potentially capable of learning how to keep a CGOL system stimulated."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pictures\n",
    "\n",
    "Here are sequences from a 10x10 trial.\n",
    "\n",
    "Here is the beginning of the trial:\n",
    "\n",
    "<img src=\"proj/img/test_start6.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/test_start7.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/test_start8.png\" style=\"display: inline;\"/>\n",
    "\n",
    "These domonstrate how the agent chooses open space. It behaved like this for about 7 iterations.\n",
    "\n",
    "<img src=\"proj/img/open_space1.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/open_space2.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/open_space3.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/open_space4.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/open_space5.png\" style=\"display: inline;\"/>\n",
    "\n",
    "Here is a solution it converges to after the system becomes an oscillator or still life. In this case, it was an oscillator.\n",
    "\n",
    "<img src=\"proj/img/osc_soln1.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/osc_soln2.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/osc_soln3.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/osc_soln4.png\" style=\"display: inline;\"/>\n",
    "\n",
    "Here is a few more example solutions. These are only still-life and no convergent behavior.\n",
    "\n",
    "<img src=\"proj/img/soln1.png\" style=\"display: inline;\"/>\n",
    "<img src=\"proj/img/soln2.png\" style=\"display: inline;\"/>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Results\n",
    "\n",
    "# Problem Definition\n",
    "First, I define what a problem is so that the RL agent can use it:\n",
    "    \n",
    "```python\n",
    "class Problem(ABC):\n",
    "    def __init__(self, maximize=True):\n",
    "        \"\"\" problem should be initialized to the point of where actions will return actions \"\"\"\n",
    "        self.maximize = maximize\n",
    "\n",
    "    @abstractmethod\n",
    "    def is_terminal(self):\n",
    "        \"\"\" Returns True iff the state is a terminal state \"\"\"\n",
    "        pass\n",
    "\n",
    "    @abstractmethod\n",
    "    def actions(self):\n",
    "        \"\"\" Returns list of possible actions \"\"\"\n",
    "        pass\n",
    "\n",
    "    @abstractmethod\n",
    "    def key(self, action):\n",
    "        \"\"\" Return the state-action key from the current state given the action \"\"\"\n",
    "        pass\n",
    "\n",
    "    @abstractmethod\n",
    "    def do(self, action):\n",
    "        \"\"\" Perform the specified action on current state, and returns (state-action key, reward) \"\"\"\n",
    "        pass\n",
    "\n",
    "    @abstractmethod\n",
    "    def reset(self):\n",
    "        \"\"\" Initialize the state to the initial position \"\"\"\n",
    "        pass\n",
    "```\n",
    "\n",
    "Problems have:\n",
    "* An initial state. `reset()` will initialize the state.\n",
    "* A set of available actions. `actions()` will return a list of actions\n",
    "* A means of performing actions. `do(action)` will perform the chosen action and return the state-action pair and reward\n",
    "* A definition of the state-action pair for SARSA. `key(action)` will return a state-action pair.\n",
    "* A means of checking for terminal states. `is_terminal()` will check for terminal states.\n",
    "\n",
    "## Problem Definition: CGOL\n",
    "\n",
    "I experiment with a couple different problem definitions in terms of CGOL.\n",
    "\n",
    "CGOL is a grid of \"cells\" defined by a set of rules:\n",
    "* Cells die when over or under populated (0, 1, 4+ neighbors)\n",
    "* Cells stay alive otherwise (2, 3 neighbors)\n",
    "* Cells can be born when there is a specific number of cells (3 neighbors)\n",
    "\n",
    "Terminology:\n",
    "* still-life - a shape which doesn't change through iterations\n",
    "* oscillator - a shape which changes shape but periodically returns to a previous iteration\n",
    "\n",
    "Project Specific Terminology:\n",
    "* maxout - This is my term: the terminal state is never reached since there is a still life and the actions being chosen are perpetuating the still life\n",
    "\n",
    "This is a type of cellular automation used to potentially simulate some forms of cellular automation found in nature (Caballero). The original problem definition is that the grid is infinite, but that kind of problem space is too large and complex, so I chose a fixed size for the grid. The edges are connected to the opposite edge making it a toroid shape.\n",
    "\n",
    "### State-Action Definition\n",
    "* State: More specifically, the RL is controlling CGOL on a toroid with the state as a grid of cells are alive or dead (1 or 0, respectively).\n",
    "* Actions: In the original problem, the only \"action\" is setting the initial state. The action varies from experiment but is generally a selection of cells which to revive or eliminate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reinforcement Learning Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to measure the effectiveness of the experiment, I have an agent that makes random actions to provide as a control.\n",
    "\n",
    "The problem with this kind of measurement, however, is that random actions are very likely to destroy still life's that exist in the grid. RL agents taking greedy actions will make the same move repeatedly if the state doesn't change. Therefore, (and my experimentation shows this) random agents can't avoid disrupting a still life while RL agents can. If reward is defined by how many iterations the agent can keep cells alive (while maximizing population).\n",
    "\n",
    "Experiments are a series of trials where the agent controls the problem, reward is collected, and if a maximum number of steps is reached, the problem is stopped (under the assumption that it can go on forever).\n",
    "\n",
    "The neural net for the RL agent has 3 layers. The number of nodes in each layer is the number of cells on the grid but capped at 300. Example, 4x4 is 16x16x16, but 20x20 is 300x300x300 not 400x400x400."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Experimentation\n",
    "\n",
    "## Experiment 1\n",
    "\n",
    "I define the available actions to be reviving or eliminating a single cell or doing nothing. The initial state was the same every time, and grid was 4x4 (very small). Reward was how many cells were still alive in the next generation.\n",
    "\n",
    "### Results:\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: same random flip of size 4x4 and density 0.3\n",
    "    cutoff: 500 steps\n",
    "    \n",
    "    base\n",
    "    base trial: 0; steps: 11; reward: 57; maxout: False\n",
    "    base trial: 1; steps: 14; reward: 63; maxout: False\n",
    "    base trial: 2; steps: 4; reward: 14; maxout: False\n",
    "    base trial: 3; steps: 4; reward: 16; maxout: False\n",
    "    base trial: 4; steps: 38; reward: 222; maxout: False\n",
    "    total steps: 71\n",
    "    total rewards: 372\n",
    "    total maxouts: 0\n",
    "\n",
    "    test\n",
    "    test trial: 0; steps: 500; reward: 4000; maxout: True\n",
    "    test trial: 1; steps: 500; reward: 4000; maxout: True\n",
    "    test trial: 2; steps: 500; reward: 4000; maxout: True\n",
    "    test trial: 3; steps: 500; reward: 4000; maxout: True\n",
    "    test trial: 4; steps: 500; reward: 4000; maxout: True\n",
    "    total steps: 2500\n",
    "    total rewards: 20000\n",
    "    total maxouts: 5\n",
    "   \n",
    "Because the initial state was the same every time, the RL agent did a simple search for optimal reinforcement. Without fail, the trails would all be maxed out during the testing phase. Through trial and error, it learned how to manipulate the initial state into a still life. Once a still life was generated, it would make actions that don't affect the still life (either not moving or selecting isolated cells far from the structure). \n",
    "\n",
    "**Conclusion: The optimal solution is to find a means of generating still life and then make no actions on the system.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experiment 2\n",
    "\n",
    "Variable change: Remove idle action.\n",
    "\n",
    "After removing the idle action, it forced the RL to interact with the system instead of idling to avoid destroying still life structures. \n",
    "\n",
    "### Results:\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: same random flip of size 4x4 and density 0.3 no idle\n",
    "    cutoff: 500 steps\n",
    "    \n",
    "    base\n",
    "    base trial: 0; steps: 3; reward: 15; maxout: False\n",
    "    base trial: 1; steps: 1; reward: 0; maxout: False\n",
    "    base trial: 2; steps: 19; reward: 108; maxout: False\n",
    "    base trial: 3; steps: 8; reward: 37; maxout: False\n",
    "    base trial: 4; steps: 1; reward: 0; maxout: False\n",
    "    total steps: 32\n",
    "    total rewards: 160\n",
    "    total maxouts: 0\n",
    "\n",
    "    test\n",
    "    test trial: 0; steps: 500; reward: 4000; maxout: True\n",
    "    test trial: 1; steps: 500; reward: 4000; maxout: True\n",
    "    test trial: 2; steps: 500; reward: 4000; maxout: True\n",
    "    test trial: 3; steps: 500; reward: 4000; maxout: True\n",
    "    test trial: 4; steps: 500; reward: 4000; maxout: True\n",
    "    total steps: 2500\n",
    "    total rewards: 20000\n",
    "    total maxouts: 5\n",
    "    \n",
    "Random seemed to have performed worse, but the chances of choosing the idle were 1/17. I don't think the changed affected the control very much, so this difference is likely due to chance.\n",
    "\n",
    "**Conclusion: However, it performed very similarly since it often found a way to choose cells which don't affect the generated still life structures.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experiment 3\n",
    "\n",
    "Variable change: Initial state is random\n",
    "\n",
    "Now, the initial state is randomly generated instead of the same state over and over. This forces the agent to have to learn to understand the board instead of finding a path to a still life. I also vary no idle again.\n",
    "\n",
    "### Results\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: static idle\n",
    "    base\n",
    "    total steps: 100\n",
    "    total rewards: 490\n",
    "    total maxouts: 0\n",
    "    test\n",
    "    total steps: 75\n",
    "    total rewards: 390\n",
    "    total maxouts: 0\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: static no idle\n",
    "    base\n",
    "    total steps: 145\n",
    "    total rewards: 710\n",
    "    total maxouts: 0\n",
    "    test\n",
    "    total steps: 7500\n",
    "    total rewards: 40110\n",
    "    total maxouts: 15\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: random idle\n",
    "    base\n",
    "    total steps: 85\n",
    "    total rewards: 404\n",
    "    total maxouts: 0\n",
    "    test\n",
    "    total steps: 1051\n",
    "    total rewards: 7692\n",
    "    total maxouts: 2\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: random no idle\n",
    "    base\n",
    "    total steps: 155\n",
    "    total rewards: 810\n",
    "    total maxouts: 0\n",
    "    test\n",
    "    total steps: 2060\n",
    "    total rewards: 13216\n",
    "    total maxouts: 4\n",
    "\n",
    "There are several things to notice here.\n",
    "\n",
    "### Idle vs No Idle\n",
    "\n",
    "* Disallowing no action moves seems to improve the agent's performance. With random states, it performed twice as well. \n",
    "* With non random initial states, the RL agent failed to find a means to maxout. This can be credited to a bad initial state that's very difficult (or impossible) to foster into emergent structures.\n",
    "* I wonder if this is due to better exploration since the agent is forced to interact with the system and break still life structures.\n",
    "\n",
    "**Conclusion: Removing the ability to idle actually increases the performance of the RL agent (possibly due to better forced exploration).**\n",
    "\n",
    "### Random initial states vs Same initial states\n",
    "\n",
    "* There is variability in the testing phase since the initial conditions are no longer static. This demonstrates that the RL agent is being forced to evaluate a path instead of using the one it memorized as good.\n",
    "* Randomness had no affect on the performance. This makes sense since the initial state has no effect on how the random agent behaves. A new random state vs the same random state is effectively the same.\n",
    "* The RL agent performed much worse with randomness. This makes sense since it's being forced to understand the system, but it's interesting that it still performs better than the control and is capable achieving maxout. I think that it randomly encounters a state that it recognizes from its training and it is able to control this state into a still life where it then chooses effectively idle actions.\n",
    "\n",
    "**Conclusion: Randomness hurts the performance as expected, but the RL agent is still capable of guiding the cells into still life structures when it recognizes the state.**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experiment 4\n",
    "\n",
    "Variable change: Variable density (the chance of a cell initially being alive)\n",
    "\n",
    "The density is how many cells are chosen to be alive.\n",
    "\n",
    "##### Results\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: new random flip of size 5x5 and density 0.3 no idle\n",
    "    base\n",
    "    total steps: 216\n",
    "    total rewards: 1457\n",
    "    total maxouts: 0\n",
    "    test\n",
    "    total steps: 3219\n",
    "    total rewards: 21141\n",
    "    total maxouts: 6\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: new random flip of size 5x5 and density 0.5 no idle\n",
    "    base\n",
    "    total steps: 323\n",
    "    total rewards: 2490\n",
    "    total maxouts: 0\n",
    "    test\n",
    "    total steps: 1878\n",
    "    total rewards: 9012\n",
    "    total maxouts: 3\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: new random flip of size 5x5 and density 0.7 no idle\n",
    "    base\n",
    "    total steps: 441\n",
    "    total rewards: 3476\n",
    "    total maxouts: 0\n",
    "    test\n",
    "    total steps: 2267\n",
    "    total rewards: 13397\n",
    "    total maxouts: 4\n",
    "\n",
    "The performance of control increased with density, and the RL agent has too much variability to tell. It seems to have performed well for lower and higher density but not very well for half alive / half dead.\n",
    "\n",
    "**Conclusion: I suspect that this factor doesn't have much of an affect on RL since the state deviates from the initial state so quickly.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experiment 5\n",
    "\n",
    "Variable: Problem/grid size\n",
    "\n",
    "##### Results\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: new random flip of size 4x4 and density 0.3\n",
    "    base\n",
    "    total steps: 35\n",
    "    total rewards: 176\n",
    "    total maxouts: 0\n",
    "\n",
    "    test\n",
    "    total steps: 1015\n",
    "    total rewards: 6902\n",
    "    total maxouts: 2\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: new random flip of size 10x10 and density 0.3\n",
    "    base\n",
    "    total steps: 450\n",
    "    total rewards: 8937\n",
    "    total maxouts: 0\n",
    "\n",
    "    test\n",
    "    total steps: 1688\n",
    "    total rewards: 15531\n",
    "    total maxouts: 3\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    Title: new random flip of size 20x20 and density 0.3\n",
    "    base\n",
    "    total steps: 2116\n",
    "    total rewards: 87956\n",
    "    total maxouts: 3\n",
    "\n",
    "    test\n",
    "    total steps: 2500\n",
    "    total rewards: 62130\n",
    "    total maxouts: 5\n",
    "\n",
    "For smaller cell grids, RL is extremely effective in maximizing the population of cells. That is because it is capable of memorizing the state space as opposed to learning it. For large state spaces, random action (control) outperformed the RL agent in population, but the RL agent was able to keep cells alive for longer (generations vs boom and bust populations).\n",
    "\n",
    "**Conclusion: RL is memorizing the small state space and doesn't perform well in large state spaces.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experiment 6\n",
    "\n",
    "Variable: Redefined the problem's reward and measurement methods.\n",
    "\n",
    "Changes to Problem:\n",
    "* To prevent the AI from learning repeating states (with oscillators and moves which don't alter the cell structures), I keep track of populations. If the cells have the same population multiple times close together, then I consider it to have found an oscillator. In these cases, I consider them terminal states and reward -5.\n",
    "* To further discourage static states, if the population doesn't change from one generation to the next, then I give reward of -1.\n",
    "* If the population changes, I reward 1. If the population is above a 50% density, then I reward 5.\n",
    "\n",
    "Changes to Experiment Practice\n",
    "* The trials use the same initial state. Before they didn't, so variation was due to chance. Now, if the control did better, then it is because the rl agent can't perform well.\n",
    "\n",
    "##### Results\n",
    "\n",
    "    Title: random initial states, 10x10 grid, 500 batches of 20\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    control\n",
    "    control trial: 0; steps: 99; reward: 73; maxout: False\n",
    "    control trial: 1; steps: 7; reward: 3; maxout: False\n",
    "    control trial: 2; steps: 54; reward: 26; maxout: False\n",
    "    control trial: 3; steps: 31; reward: 17; maxout: False\n",
    "    control trial: 4; steps: 145; reward: 113; maxout: False\n",
    "    control trial: 5; steps: 61; reward: 51; maxout: False\n",
    "    control trial: 6; steps: 83; reward: 63; maxout: False\n",
    "    control trial: 7; steps: 355; reward: 283; maxout: False\n",
    "    control trial: 8; steps: 218; reward: 184; maxout: False\n",
    "    control trial: 9; steps: 52; reward: 42; maxout: False\n",
    "    total steps: 1105\n",
    "    total rewards: 855\n",
    "    total maxouts: 0\n",
    "\n",
    "    -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-\n",
    "    rl agent\n",
    "    test trial: 0; steps: 25; reward: -1; maxout: False\n",
    "    test trial: 1; steps: 22; reward: 22; maxout: False\n",
    "    test trial: 2; steps: 72; reward: 54; maxout: False\n",
    "    test trial: 3; steps: 266; reward: 220; maxout: False\n",
    "    test trial: 4; steps: 240; reward: 196; maxout: False\n",
    "    test trial: 5; steps: 112; reward: 88; maxout: False\n",
    "    test trial: 6; steps: 196; reward: 146; maxout: False\n",
    "    test trial: 7; steps: 53; reward: 47; maxout: False\n",
    "    test trial: 8; steps: 112; reward: 68; maxout: False\n",
    "    test trial: 9; steps: 145; reward: 123; maxout: False\n",
    "    total steps: 1243\n",
    "    total rewards: 963\n",
    "    total maxouts: 0\n",
    "\n",
    "The total rewards and steps are higher, so the RL agent did perform slightly better. However, I don't know enough statistics to tell whether this is statistically significant.\n",
    "\n",
    "This fact in a 10x10 grid is really promising because it shows that the RL agent can perform at least as good as random. \n",
    "\n",
    "**Conclusion: RL is potentially capable of learning how to keep a CGOL system stimulated.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusions\n",
    "\n",
    "### What I Learned\n",
    "#### About Conway's Game of Life and applied Reinforcement Learning\n",
    "* The RL agent favored not exploring the system to more passive moves: The RL agent's strategy was to create still life structures and then stop interacting with the system. If forced to be more interactive (reward incentives or limiting passive actions), it performed better.\n",
    "* If the initial state was always the same, it was very good at memorizing paths to maximize reward. However, if it was random, it performed worse. With random states, it would try to converge to a still life, and then stop interacting with the system. If it failed to converge, it performed as well as the control. This implies a lack of understanding of the system but instead a memorization of paths to still life.\n",
    "* Experiments 1-5 show that for smaller cell grids, RL is extremely effective in maximizing the population of cells. That is because it is capable of memorizing the state space as opposed to learning it. For large state spaces, random action (control) outperformed the RL agent in population, but the RL agent was able to keep cells alive for longer (generations vs boom and bust populations).\n",
    "* However, experiment 6 shows more accurately that with enough training, the RL agent is capable of outperforming a random agent in even large grids with random initial states.\n",
    "\n",
    "#### About Programming and AI\n",
    "\n",
    "Here are some more general topics that I understand much more now:\n",
    "* Back propagation and minimization problems\n",
    "* The general SARSA Neural Network Q-function Reinforcement Learning Algorithm with TD.\n",
    "* Applying MVC to create GUI application where Model is independent from Controller/View\n",
    "* How to create installable python modules (my `cgolai` package can be installed like other packages, with `setup.py`).\n",
    "* Unit testing with python's `unittest` to test my module\n",
    "* Git for version control and distributed work (easy switching between GPU machine vs local)\n",
    "* Compressed pickling for storing model states\n",
    "* PEP 8 code style standards\n",
    "\n",
    "### Difficulties\n",
    "\n",
    "Difficulties:\n",
    "* I'm pretty sure that my conversions from numpy.ndarray/list/torch.Tensor result in my neural network training very inefficiently (either not using GPU or making unnecessary copies). It was functional, so I didn't look further into it.\n",
    "* Training larger networks took a while, so I usually didn't let the network train for long except for experiment 6. This means the RL agent wasn't performing as well as it could have, but I think letting it train longer has the same performance as the RL in a smaller state, i.e., it will memorize the larger state as well. However, since it can't really memorize the larger state, it would be interesting to know if it could draw accurate extrapolations from such an intense training.\n",
    "* I struggled with implementing a neural network by deriving my own gradient until I gave up and used PyTorch.\n",
    "* It was difficult learning how to use PyGame since I had never used it before.\n",
    "* These difficulties led to the time line being altered. The experimentation phase was compressed into a week, and the development of the model and RL agent were extended.\n",
    "\n",
    "Problems with my experimentation methodologies:\n",
    "* I didn't do much hyper-parameter tuning, so it's possible there are better parameters which train the model much better than my experiments found.\n",
    "* I put tables in my report instead of graphing them, which I apologize for.\n",
    "* Experiment 6 fixes some of my measurement issues (testing control vs rl agent with different initial state creates variability between testing, and this hinders results in experiment 1-5, but not 6).\n",
    "\n",
    "### Resources\n",
    "\n",
    "**See `cs440_notes.docx` for the reading component for the Honors Requirement.**\n",
    "* Sutton, Richard S., and Andrew G. Barto. Reinforcement Learning: An Introduction. Chapter 6: Temporal-Difference Learning. Second edition, complete draft. 5 Nov 2017.\n",
    "* Caballero, Lorena, Bob Hodge, and Sergio Hernandez. Conway’s “Game of Life” and the Epigenetic Principle.\n",
    "* Gadaleta, Sabino, and Gerhard Dangelmayr. Reinforcement Learning Chaos Control Using Value Sensitive Vector-Quantization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Sorry for going over the word count, but I think a majority of it is from my text results, and you don't need to read details for experiment 1-5*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Word count for file Report.ipynb is 5463\n"
     ]
    }
   ],
   "source": [
    "import io\n",
    "from IPython.nbformat import current\n",
    "import glob\n",
    "nbfile = glob.glob('Report.ipynb')\n",
    "if len(nbfile) > 1:\n",
    "    print('More than one ipynb file. Using the first one.  nbfile=', nbfile)\n",
    "with io.open(nbfile[0], 'r', encoding='utf-8') as f:\n",
    "    nb = current.read(f, 'json')\n",
    "word_count = 0\n",
    "for cell in nb.worksheets[0].cells:\n",
    "    if cell.cell_type == \"markdown\":\n",
    "        word_count += len(cell['source'].replace('#', '').lstrip().split(' '))\n",
    "print('Word count for file', nbfile[0], 'is', word_count)"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}