t81_558_class_12_05_alpha_zero.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# T81-558: Applications of Deep Neural Networks\n",
    "**Module 12: Deep Learning and Security**\n",
    "* Instructor: [Jeff Heaton](https://sites.wustl.edu/jeffheaton/), McKelvey School of Engineering, [Washington University in St. Louis](https://engineering.wustl.edu/Programs/Pages/default.aspx)\n",
    "* For more information visit the [class website](https://sites.wustl.edu/jeffheaton/t81-558/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Module 12 Video Material\n",
    "\n",
    "* Part 12.1: Introduction to the OpenAI Gym [[Video]](https://www.youtube.com/watch?v=_KbUxgyisjM&list=PLjy4p-07OYzulelvJ5KVaT2pDlxivl_BN) [[Notebook]](t81_558_class_12_01_ai_gym.ipynb)\n",
    "* Part 12.2: Introduction to Q-Learning [[Video]](https://www.youtube.com/watch?v=uwcXWe_Fra0&list=PLjy4p-07OYzulelvJ5KVaT2pDlxivl_BN) [[Notebook]](t81_558_class_12_02_qlearningreinforcement.ipynb)\n",
    "* Part 12.3: Keras Q-Learning in the OpenAI Gym [[Video]](https://www.youtube.com/watch?v=Ya1gYt63o3M&list=PLjy4p-07OYzulelvJ5KVaT2pDlxivl_BN) [[Notebook]](t81_558_class_12_03_keras_reinforce.ipynb)\n",
    "* Part 12.4: Atari Games with Keras Neural Networks [[Video]](https://www.youtube.com/watch?v=t2yIu6cRa38&list=PLjy4p-07OYzulelvJ5KVaT2pDlxivl_BN) [[Notebook]](t81_558_class_12_04_atari.ipynb)\n",
    "* **Part 12.5: How Alpha Zero used Reinforcement Learning to Master Chess** [[Video]](https://www.youtube.com/watch?v=ikDgyD7nVI8&list=PLjy4p-07OYzulelvJ5KVaT2pDlxivl_BN) [[Notebook]](t81_558_class_12_05_alpha_zero.ipynb)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 12.5: How Alpha Zero used Reinforcement Learning to Master Chess\n",
    "\n",
    "### AlphaGo\n",
    "\n",
    "[Game of Go](https://en.wikipedia.org/wiki/Go_(game)) is:\n",
    "* 3,000 years old\n",
    "* 40M Players\n",
    "* $10^{170}$ board positions ($10^{78}$ to $10^{82}$ atoms in the known, observable universe)\n",
    "\n",
    "\n",
    "The original Google AlphaGo made use of two convolutional neural networks:\n",
    "\n",
    "* **Policy Network** - CNN that accepts a Go Board (19x19) and decides on a next move. \n",
    "* **Value Network** - CNN that accepts a Go Board (19x19) and evaluates who the likely winner will be.  Predicts winner or game -1 and +1 (win/loss).\n",
    "\n",
    "![AlphaGo Two Networks](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-1.png \"AlphaGo Two Networks\")\n",
    "\n",
    "Supervised learning based on human games.  Reproduce (policy network) \n",
    "Policy network plays itself\n",
    "\n",
    "Train value network by reinforcement learning\n",
    "\n",
    "![AlphaGo Training Pipeline](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-2.png \"AlphaGo Training Pipeline\")\n",
    "\n",
    "Narrow search space to reduce width of search\n",
    "Value network needs less depth\n",
    "\n",
    "Monte-Carlo tree search\n",
    "1. Traverse \n",
    "\n",
    "Lost one game.  Delusions\n",
    "\n",
    "Random rollouts\n",
    "\n",
    "### Exhaustive Search\n",
    "\n",
    "![Exhaustive Search](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-4.png \"Exhaustive Search\")\n",
    "\n",
    "### Reducing Breadth with Policy Network\n",
    "\n",
    "![Reducing Breadth with Policy Network](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-5.png \"Reducing Breadth with Policy Network\")\n",
    "\n",
    "### Monte Carlo Tree Search (MCTS): Selection\n",
    "\n",
    "[Monte Carlo tree search (MCTS)](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) is a heuristic search algorithm for some kinds of decision processes, most notably those employed in game play. MCTS was introduced in 2006 for computer Go. It has been used in other board games like chess and shogi, games with incomplete information such as bridge and poker, as well as in real-time video games.\n",
    "\n",
    "MCTS consists of four steps:\n",
    "\n",
    "* **Selection**: start from root R and select successive child nodes until a leaf node L is reached. The root is the current game state and a leaf is any node from which no simulation (playout) has yet been initiated. The section below says more about a way of biasing choice of child nodes that lets the game tree expand towards the most promising moves, which is the essence of Monte Carlo tree search.\n",
    "* **Expansion**: unless L ends the game decisively (e.g. win/loss/draw) for either player, create one (or more) child nodes and choose node C from one of them. Child nodes are any valid moves from the game position defined by L.\n",
    "* **Simulation**: complete one random playout from node C. This step is sometimes also called playout or rollout. A playout may be as simple as choosing uniform random moves until the game is decided (for example in chess, the game is won, lost, or drawn).\n",
    "* **Backpropagation**: use the result of the playout to update information in the nodes on the path from C to R.\n",
    "\n",
    "\n",
    "* Q-Value is the accumulated rewards from previous move selection\n",
    "* U-Value ii policy network reward\n",
    "\n",
    "The selection step of MCTS for AlphaGo is summarized as follows:\n",
    "\n",
    "![Monte Carlo Tree Search (MCTS): Selection](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-6.png \"Monte Carlo Tree Search (MCTS): Selection\")\n",
    "\n",
    "### Monte Carlo Tree Search (MCTS): Expansion\n",
    "\n",
    "The expansion step of MCTS for AlphaGo is summarized as follows:\n",
    "\n",
    "![Monte Carlo Tree Search (MCTS): Expansion](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-7.png \"Monte Carlo Tree Search (MCTS): Expansion\")\n",
    "\n",
    "### Monte Carlo Tree Search (MCTS): Evaluation\n",
    "\n",
    "The evaluation step of MCTS for AlphaGo is summarized as follows:\n",
    "\n",
    "![Monte Carlo Tree Search (MCTS): Evaluation](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-8.png \"Monte Carlo Tree Search (MCTS): Evaluation\")\n",
    "\n",
    "### Monte Carlo Tree Search (MCTS): Backup\n",
    "\n",
    "The backup step of MCTS for AlphaGo is summarized as follows:\n",
    "\n",
    "![Monte Carlo Tree Search (MCTS): Backup](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-9.png \"Monte Carlo Tree Search (MCTS): Backup\")\n",
    "\n",
    "### AlphaGo Hardware\n",
    "\n",
    "AlphaGo requires considerable hardware to traverse while performing MCTS.  Later versions will improve this.\n",
    "\n",
    "![AlphaGo Hardware](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-10.png \"AlphaGo Hardware\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AlphaGo Master\n",
    "\n",
    "AlphaGo master is similar to AlphaGo, except it does away with the breakout step.  AlphaGo Master played Ke Jia, AlphaGo Master Won 3-0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### AlphaGo Zero\n",
    "\n",
    "* No human data\n",
    "* No human feature engineering\n",
    "* Single neural network (combine policy and value networks)\n",
    "* Simpler search\n",
    "\n",
    "Combined single network is made up of: many residual blocks 4 of convolutional layers 16, 17 with batch normalization 18 and rectifier non-linearities 19.\n",
    "\n",
    "### Reinforcement Learning\n",
    "\n",
    "AlphaGo Zero is trained entirely by self-play from initially from policies that are quite random.  The combined neural network is trained at each iteration to predict the same move as the \n",
    "\n",
    "![AlphaGo Zero Zero Plays Itself](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-11.png \"AlphaGo Zero Plays Itself\")\n",
    "\n",
    "![Policy Zero is Trained Against AlphaGo Zero's Moves](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-12.png \"Reinforcement Learning in AlphaGo Master\")\n",
    "\n",
    "![Value Network is Trained to Predict Winner](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-13.png \"Value Network is Trained to Predict Winner\")\n",
    "\n",
    "![New Value and Policy Network used in Next Iteration](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-14.png \"New Value and Policy Network used in Next Iteration\")\n",
    "\n",
    "Two-step process:\n",
    "\n",
    "* **Search-Based Policy Improvement**\n",
    "    * Run MCTS search using current network\n",
    "    * Actions selected by MCTS > actions selected by raw network\n",
    "* **Seach-Based Policy Evaluation**\n",
    "    * Play self-play games with AlphaGo search\n",
    "    * Evaluate improved policy by the average outcome\n",
    "\n",
    "State of the art residual network\n",
    "\n",
    "Random rollouts removed, only used neural network to evaluate.  More general, maybe apply to other games.\n",
    "\n",
    "MCTS - Lookahead, train neural network (policy) to come up with same result.\n",
    "Train value net to better predict winner\n",
    "\n",
    "Iterate over:\n",
    "* Search-Based Policy Improvement\n",
    "* Search-Based Policy Evaluation (key feature)\n",
    "\n",
    "\n",
    "AlphaGo Zero uses a single neural network to suggest moves, so it requires much less computation power than previous version.  \n",
    "\n",
    "![Alpha Go Master](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-15.png \"AlphaGo Master Hardware\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### AlphaZero\n",
    "\n",
    "* chess\n",
    "* shogi\n",
    "* Go\n",
    "\n",
    "![New Value and Policy Network used in Next Iteration](https://raw.githubusercontent.com/jeffheaton/t81_558_deep_learning/master/images/alpha-zero-16.png \"New Value and Policy Network used in Next Iteration\")\n",
    "\n",
    "Chess is:\n",
    "\n",
    "* Most studied domain in the history of AI\n",
    "* Highly specialized systems have been successful in chess\n",
    "* Shogi (Japanese Chess) is computationally harder than chess\n",
    "* State of the art engines are based on alpha-beta search (form of minimax)\n",
    "\n",
    "2016 TCEC - Stockfish has very specialized algorithms for each of the following:\n",
    "\n",
    "* Board Representation\n",
    "* Search\n",
    "* Transposition Table\n",
    "* Move Ordering\n",
    "* Selectivity\n",
    "* Evaluation\n",
    "* End Game Tablebases\n",
    "\n",
    "Elo rating\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3.6 (tensorflow)",
   "language": "python",
   "name": "rga"
  },
  "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}