{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 73,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "248cb143-5a6b-4e38-af09-109dec4fd953"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 74,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "a6207118-5cb8-421a-88af-152dc4fa940b"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 75,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"Hai Chen\"\n",
        "permission = True\n",
        "anonymous = False"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 76,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 77,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 729
        },
        "id": "gYYeNcdM_maE",
        "outputId": "dd3eaf23-5f98-407c-9a08-c2ecc5e9c6b6"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - your definitions here\n",
              "* **Other concept** - your definitions here\n",
              "* **Etc.** - your definitions here\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 78,
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "outputs": [],
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" No function overloading as in Java.  Python functions can have default values.\n",
        "\n",
        "Keyword arguments:  functions can be called with arguments out of order.  Keyword arguments are used after positional arguments.\n",
        "\n",
        "Dynamic scope: functions use most recent value assigned to a variable.\n",
        "\n",
        "Default arguements and memorization: default parameter values are evalued only at the first time when the function is called.\n",
        "\n",
        "Functions are \"first order\" objects\", which are entities that can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables.\n",
        "\n",
        "Creating a calls.\n",
        "\n",
        "Class class_name:\n",
        "\n",
        "    attribute = ..\n",
        "\n",
        "    def __init__(self, arg1, ...):\n",
        "      ...\n",
        "\n",
        "\"__init__\" constructor is called when an object is instantiated.\n",
        "\n",
        "Other special build-in methods:\n",
        "\"__str__, __len__, __cmp__, __copy__, __add__, __neg__\"\n",
        "\n",
        "Generators are iterators.\n",
        "\"yield\" to create generators.\n",
        "Benefits of generators:\n",
        "    less code than a standard iterator\n",
        "    maintain local state automatically\n",
        "    values are computed one at a time, as they are needed\n",
        "    avoids storing the entire sequence in memory\n",
        "    good for aggregating(summing, counting) items, only one pass.\n",
        "    crucial for infinite sequences\n",
        "bad if inspection of individual values are needed.\n",
        "\n",
        "enumerate(iterable, start =0)\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 79,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 571
        },
        "id": "ydOK__lwWgdp",
        "outputId": "c7eb3136-943f-41a7-c650-bca594de09cb"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " No function overloading as in Java.  Python functions can have default values.\n",
              "\n",
              "Keyword arguments:  functions can be called with arguments out of order.  Keyword arguments are used after positional arguments.\n",
              "\n",
              "Dynamic scope: functions use most recent value assigned to a variable.\n",
              "\n",
              "Default arguements and memorization: default parameter values are evalued only at the first time when the function is called.\n",
              "\n",
              "Functions are \"first order\" objects\", which are entities that can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables.\n",
              "\n",
              "Creating a calls.\n",
              "\n",
              "Class class_name:\n",
              "\n",
              "    attribute = ..\n",
              "\n",
              "    def __init__(self, arg1, ...):\n",
              "      ...\n",
              "\n",
              "\"__init__\" constructor is called when an object is instantiated.\n",
              "\n",
              "Other special build-in methods:\n",
              "\"__str__, __len__, __cmp__, __copy__, __add__, __neg__\"\n",
              "\n",
              "Generators are iterators.\n",
              "\"yield\" to create generators.\n",
              "Benefits of generators:\n",
              "    less code than a standard iterator\n",
              "    maintain local state automatically\n",
              "    values are computed one at a time, as they are needed\n",
              "    avoids storing the entire sequence in memory\n",
              "    good for aggregating(summing, counting) items, only one pass.\n",
              "    crucial for infinite sequences\n",
              "bad if inspection of individual values are needed.\n",
              "\n",
              "enumerate(iterable, start =0)\n",
              "\n",
              " \n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 80,
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Search\n",
        "A search problem can be defined formally as:\n",
        "A set of possible states – state space.\n",
        "The initial state\n",
        "A set of one or more goal states\n",
        "The actions available.  Given a state Actions(s) returns a finite set of actions\n",
        "A transition model describes what each action does.  Result(s, a) returns the resulting state.\n",
        "An action cost function: Action-Cost(s,a,s’)\n",
        "\n",
        "A sequence of actions forma a path, and a solution is a path from the initial state to a goal state.\n",
        "Assuming the action costs are additive.  An optimal solution has the lowest path cost among all solutions.\n",
        "The state space can be represented by a graph, in which vertices are states and directed edges are actions\n",
        "\n",
        "The formulation of the problem is a model, an abstract mathematical description.\n",
        "Abstraction, the process of removing detail from a representation.\n",
        "\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" Standardized problem is intended to illustrate or exercise various problem -solving methods.  Real-world problem is one whose solutions people actually use and whose formulation is idiosyncratic.\n",
        "Standardized: \n",
        "a grid world problem is a two-dimensional rectangular array of square cells.\n",
        "\n",
        "Sokoban puzzle, the agent is to push a number of boxes, scattered about the grid, to designated storage locations. (at most one box per cell)\n",
        "\n",
        "Sliding tile puzzle including 8-puzzle\n",
        "\n",
        "Donald Knuth problem has infinite states \n",
        "States: positive real numbers\n",
        "Initial state: 4\n",
        "Actions: apply square root, floor, or factorial operation (factorial for integers only)\n",
        "Transition model: as given by the mathematical definition of the operations\n",
        "Goal state: the desired positive integer\n",
        "Action cost: each action costs 1\n",
        "\n",
        "Infinite state space arise frequently in tasks involving the generation of mathematical expressions, circuits, proofs, programs and other recurrsively defined objects.\n",
        "Real-world problems\n",
        "\n",
        "Route-finding problem, Touring problem, the traveling salesperson problem(TSP)\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" A Search Algorithm takes a search problem as input and returns a solution or an indication of failure.\n",
        "\n",
        "Search Tree. \n",
        "Each node corresponds to a state in the state space and the edges correspond to actions.The root corresponds to the initial state.\n",
        "Frontier is a set of unexpanded nodes.  Any state that has had a node generated for it has been REACHED (whether or not that node has been expanded).\n",
        "Frontier separates the interior region where every state has been  expanded, and the exterior region of states that have not yet been reached.\n",
        "\n",
        "Best-first search\n",
        "Choose a node, n, from the frontier, with minimum value of some evaluation function, f(n), to expand next.\n",
        "Search algorithms require Search Data Structures to keep track of the search tree.  A node is represented by a data structure with four components:\n",
        "The state that the node corresponds; \n",
        "the parent node; \n",
        "the action that was applied to the parent’s state to generate this node; \n",
        "Path-cost as the total cost of the path from the initial sate to this node.\n",
        "\n",
        "Data structure to store the frontier is a queue of some kind. \n",
        "Priority queue first pops the node with the minimum cost according to some evaluation function, f.  used in best-first search.\n",
        "FIFO queue that pops the node added to the queue first is used in BFS.\n",
        "LIFO queue (or a stack) that pops the most recently added node is used in DFS.\n",
        "\n",
        "The reached states can be stored as a lookup table(hash table) where each key is a state and each value is the node for that state.\n",
        "A repeated state in the search tree is generated by a cycle, which is a special case of a redundant path. \n",
        "Three approaches to eliminate redundant paths.  \n",
        "First, remember all previously reached states, appropriate for state spaces with many redundant paths, preferred choice when the table of reached states will fit in memory.\n",
        "Second, it is impossible or rare for two paths to reach the same state for some problems such as an assembly problem. Don’t track reached states to save memory and don’t check for redundant paths.  \n",
        "A search algorithm is a graph search if it checks for redundant paths, and a tree-like search if it does not.\n",
        "Third, compromise and check for cycles but not for redundant paths.  \n",
        "\n",
        "Measure search algorithms’ performance in four ways: completeness, cost optimality, time complexity and space complexity.  \n",
        "\n",
        "To be complete, a search algorithm must be systematic in the way it explores an infinite state space. \"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\"\n",
        "BFS is a systematic search strategy that is complete (even on infinite state spaces).  Early goal test, checking if a node is a solution when it is generated, \n",
        "rather than the late goal test used by best-first search, waiting until a node is popped off the queue.\n",
        "\n",
        "BFS is cost-optimal for problems with same cost for all actions, but not for problems without that property.  It is complete in either case.\n",
        "It is exponential-complexity for both time and space.  \n",
        "Uninformed search can solve only the samllest instances of exponential-complexity search problems,\n",
        "\n",
        "Dijkastra’s algorithm or uniform-cost search (misleading name).  \n",
        "Implemented as a call to best-first search with Path-Cost as the evaluation function.  \n",
        "$O(b^{1+\\lfloor C^*/e \\rfloor})$, $C^*$: the optimal solution’s cost, e: lower bound on the cost of each action.  \n",
        "When all action costs are equal, $b^{1+\\lfloor C*/e \\rfloor}$ is just $b^{(d+1)}$, and uniform-cost search is similar to BFS.\n",
        "\n",
        "DFS is not cost optimal, returning the first solution it finds. For finite state spaces that are trees DFS is efficient and complete.  \n",
        "For acyclic state spaces it will systematically explore the entire space.\n",
        "In cyclic state spaces it can get stuck in an infinite loop.  In infinite state spaces, it is not systematic and incomplete.\n",
        "\n",
        "DFS is used for problems where a tree-like search is feasible, has much smaller needs for memory.  \n",
        "The frontier in BFS is like the surface of an ever-expanding sphere, while the frontier in DFS is just a radius of the sphere.  \n",
        "\n",
        "Depth-first tree-like search has been adopted as the basic workhorse of many areas of AI including constraint satisfaction, propositional satisfiability and logic programming.\n",
        "\n",
        "Backtracking search is a variant of DFS, using even less memory.  It generates one successor at a time; each partially expanded node remembers which successor to generate next.  \n",
        "In addition, successors are generated by modifying the current state rather than allocating memory to new state.  \n",
        "This reduces the memory requirements to just one state description and a path of O(m) actions.\n",
        "\n",
        "Depth limited search, with a depth limit, l, and treat all nodes at depth l as if they had no successors. \n",
        "\n",
        "Iterative deepening search tries different depth values until either a solution is found or returning a failure. It combines many benefits of DFS and BFS.  \n",
        "Memory requirements are modest, O(bd) (solution) or O(bm) (no solution in finite state spaces).  \n",
        "Like BFS, it is optimal for problems with same cost for all actions, and is complete on finite acyclic state spaces, or on any finite state space when we check nodes for cycles all the way up the path.\n",
        "In general, it is preferred when the search state space is too large to fit in memory and the depth of the solution is unknown.\n",
        "\n",
        "Bidirectional search, simultaneously searches forward from the initial state and backwards from the goal state.  $b^(d/2) +b^(d/2)$ is much less than $b^d$.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" A problem-solving agent needs to plan ahead.  The computational process it undertakes is called search.\n",
        "The agent will consider a sequence of actions that form a path to a goal state, and such a sequence is called a solution.\n",
        "\n",
        "In an environment that is fully obersable, deterministic and known, the solution is a fixed sequence of actions.\n",
        "\n",
        "In a partially observable or nonderterministic environment, the solution must recommend different future actions depending on the percepts it receives.  Branching strategy.\n",
        "\n",
        "Tree search is a generalizaed algorithm to solve search problems.  It enumerates in some order all possible path from the initial state.\n",
        "It searches through explicit tree generation: root is the initial state, nodes in search tree generated through transition model. Different paths to the same node are distinct. \n",
        "\n",
        "BFS idea: expand the shallowest unexpanded nodes. Frontier is a FIFO queue.\n",
        "\n",
        "BFS is complete if b is finie, time complexity is $O(b^d)$. Its space complexity is $O(b^d)$ too and is a big problem.  It is optimal if cost =1 per step.  Ohterwise not optimal.\n",
        "Exponential space and time complexity.\n",
        "\n",
        "DFS idea: expand the deepest unexpanded node.  Frontier is a LIFO queue.\n",
        "DFS is incomplete in infinite-depth spaces, space with loops.  It is complete in finite spaces.  Its time complexity is $O(b^m)$, m is maximum depth of state space.\n",
        "If m > d, DFS is worse than BFS.  But if solustions are dense, DFS is faster than BFS.\n",
        "\n",
        "DFS' space complexity is $O(b*m) - linear space!\n",
        "It is not optimal.\n",
        "\n",
        "Use DFS if space is restricted, or many possible solutions with long paths and wrong paths are terminated quickly, or search can be fine-tuned quickly\n",
        "Use BFS if there are possible infinite paths, or some solutions have short paths, or can quickly discard unlikely paths.\n",
        "\n",
        "Depth limit DFS time complexity $O(b^l)$ and space complexity $O(bl)$\n",
        "Iterative deepening search uses depth-limit search as subroutine with increasing l.  It is complete and optimal as goal is always found at d the depth of the shallowest goal-node.\n",
        "Time complexity is $O(b^d)$. Space complexity is $O(bd)$.\n",
        "\n",
        "Both BFS and Iterative deepening search are complete and optimal.  Others are not.\n",
        "\n",
        "Inoformed Search uses domain-specifi information about hte location of the goals in order to find a solution more efficiently.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"state space\": \"the set of states reachable from initial state by taking some sequence of actions\",\n",
        "\"frontier\": \"states that are avaible for expaning\",\n",
        "\"path\": \"sequence of actions leading from one state to another state\", \n",
        "\"b\": \"maximum branching factor of search tree\",\n",
        "\"d\": \"depth of the shallowest goal node\"  \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 81,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "4e56c442-e8f0-4eb9-c86e-0523af337f3e"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Search\n",
              "A search problem can be defined formally as:\n",
              "A set of possible states – state space.\n",
              "The initial state\n",
              "A set of one or more goal states\n",
              "The actions available.  Given a state Actions(s) returns a finite set of actions\n",
              "A transition model describes what each action does.  Result(s, a) returns the resulting state.\n",
              "An action cost function: Action-Cost(s,a,s’)\n",
              "\n",
              "A sequence of actions forma a path, and a solution is a path from the initial state to a goal state.\n",
              "Assuming the action costs are additive.  An optimal solution has the lowest path cost among all solutions.\n",
              "The state space can be represented by a graph, in which vertices are states and directed edges are actions\n",
              "\n",
              "The formulation of the problem is a model, an abstract mathematical description.\n",
              "Abstraction, the process of removing detail from a representation.\n",
              "\n",
              " \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Standardized problem is intended to illustrate or exercise various problem -solving methods.  Real-world problem is one whose solutions people actually use and whose formulation is idiosyncratic.\n",
              "Standardized: \n",
              "a grid world problem is a two-dimensional rectangular array of square cells.\n",
              "\n",
              "Sokoban puzzle, the agent is to push a number of boxes, scattered about the grid, to designated storage locations. (at most one box per cell)\n",
              "\n",
              "Sliding tile puzzle including 8-puzzle\n",
              "\n",
              "Donald Knuth problem has infinite states \n",
              "States: positive real numbers\n",
              "Initial state: 4\n",
              "Actions: apply square root, floor, or factorial operation (factorial for integers only)\n",
              "Transition model: as given by the mathematical definition of the operations\n",
              "Goal state: the desired positive integer\n",
              "Action cost: each action costs 1\n",
              "\n",
              "Infinite state space arise frequently in tasks involving the generation of mathematical expressions, circuits, proofs, programs and other recurrsively defined objects.\n",
              "Real-world problems\n",
              "\n",
              "Route-finding problem, Touring problem, the traveling salesperson problem(TSP)\n",
              " \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " A Search Algorithm takes a search problem as input and returns a solution or an indication of failure.\n",
              "\n",
              "Search Tree. \n",
              "Each node corresponds to a state in the state space and the edges correspond to actions.The root corresponds to the initial state.\n",
              "Frontier is a set of unexpanded nodes.  Any state that has had a node generated for it has been REACHED (whether or not that node has been expanded).\n",
              "Frontier separates the interior region where every state has been  expanded, and the exterior region of states that have not yet been reached.\n",
              "\n",
              "Best-first search\n",
              "Choose a node, n, from the frontier, with minimum value of some evaluation function, f(n), to expand next.\n",
              "Search algorithms require Search Data Structures to keep track of the search tree.  A node is represented by a data structure with four components:\n",
              "The state that the node corresponds; \n",
              "the parent node; \n",
              "the action that was applied to the parent’s state to generate this node; \n",
              "Path-cost as the total cost of the path from the initial sate to this node.\n",
              "\n",
              "Data structure to store the frontier is a queue of some kind. \n",
              "Priority queue first pops the node with the minimum cost according to some evaluation function, f.  used in best-first search.\n",
              "FIFO queue that pops the node added to the queue first is used in BFS.\n",
              "LIFO queue (or a stack) that pops the most recently added node is used in DFS.\n",
              "\n",
              "The reached states can be stored as a lookup table(hash table) where each key is a state and each value is the node for that state.\n",
              "A repeated state in the search tree is generated by a cycle, which is a special case of a redundant path. \n",
              "Three approaches to eliminate redundant paths.  \n",
              "First, remember all previously reached states, appropriate for state spaces with many redundant paths, preferred choice when the table of reached states will fit in memory.\n",
              "Second, it is impossible or rare for two paths to reach the same state for some problems such as an assembly problem. Don’t track reached states to save memory and don’t check for redundant paths.  \n",
              "A search algorithm is a graph search if it checks for redundant paths, and a tree-like search if it does not.\n",
              "Third, compromise and check for cycles but not for redundant paths.  \n",
              "\n",
              "Measure search algorithms’ performance in four ways: completeness, cost optimality, time complexity and space complexity.  \n",
              "\n",
              "To be complete, a search algorithm must be systematic in the way it explores an infinite state space. \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "BFS is a systematic search strategy that is complete (even on infinite state spaces).  Early goal test, checking if a node is a solution when it is generated, \n",
              "rather than the late goal test used by best-first search, waiting until a node is popped off the queue.\n",
              "\n",
              "BFS is cost-optimal for problems with same cost for all actions, but not for problems without that property.  It is complete in either case.\n",
              "It is exponential-complexity for both time and space.  \n",
              "Uninformed search can solve only the samllest instances of exponential-complexity search problems,\n",
              "\n",
              "Dijkastra’s algorithm or uniform-cost search (misleading name).  \n",
              "Implemented as a call to best-first search with Path-Cost as the evaluation function.  \n",
              "$O(b^{1+\\lfloor C^*/e \rfloor})$, $C^*$: the optimal solution’s cost, e: lower bound on the cost of each action.  \n",
              "When all action costs are equal, $b^{1+\\lfloor C*/e \rfloor}$ is just $b^{(d+1)}$, and uniform-cost search is similar to BFS.\n",
              "\n",
              "DFS is not cost optimal, returning the first solution it finds. For finite state spaces that are trees DFS is efficient and complete.  \n",
              "For acyclic state spaces it will systematically explore the entire space.\n",
              "In cyclic state spaces it can get stuck in an infinite loop.  In infinite state spaces, it is not systematic and incomplete.\n",
              "\n",
              "DFS is used for problems where a tree-like search is feasible, has much smaller needs for memory.  \n",
              "The frontier in BFS is like the surface of an ever-expanding sphere, while the frontier in DFS is just a radius of the sphere.  \n",
              "\n",
              "Depth-first tree-like search has been adopted as the basic workhorse of many areas of AI including constraint satisfaction, propositional satisfiability and logic programming.\n",
              "\n",
              "Backtracking search is a variant of DFS, using even less memory.  It generates one successor at a time; each partially expanded node remembers which successor to generate next.  \n",
              "In addition, successors are generated by modifying the current state rather than allocating memory to new state.  \n",
              "This reduces the memory requirements to just one state description and a path of O(m) actions.\n",
              "\n",
              "Depth limited search, with a depth limit, l, and treat all nodes at depth l as if they had no successors. \n",
              "\n",
              "Iterative deepening search tries different depth values until either a solution is found or returning a failure. It combines many benefits of DFS and BFS.  \n",
              "Memory requirements are modest, O(bd) (solution) or O(bm) (no solution in finite state spaces).  \n",
              "Like BFS, it is optimal for problems with same cost for all actions, and is complete on finite acyclic state spaces, or on any finite state space when we check nodes for cycles all the way up the path.\n",
              "In general, it is preferred when the search state space is too large to fit in memory and the depth of the solution is unknown.\n",
              "\n",
              "Bidirectional search, simultaneously searches forward from the initial state and backwards from the goal state.  $b^(d/2) +b^(d/2)$ is much less than $b^d$.\n",
              " \n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " A problem-solving agent needs to plan ahead.  The computational process it undertakes is called search.\n",
              "The agent will consider a sequence of actions that form a path to a goal state, and such a sequence is called a solution.\n",
              "\n",
              "In an environment that is fully obersable, deterministic and known, the solution is a fixed sequence of actions.\n",
              "\n",
              "In a partially observable or nonderterministic environment, the solution must recommend different future actions depending on the percepts it receives.  Branching strategy.\n",
              "\n",
              "Tree search is a generalizaed algorithm to solve search problems.  It enumerates in some order all possible path from the initial state.\n",
              "It searches through explicit tree generation: root is the initial state, nodes in search tree generated through transition model. Different paths to the same node are distinct. \n",
              "\n",
              "BFS idea: expand the shallowest unexpanded nodes. Frontier is a FIFO queue.\n",
              "\n",
              "BFS is complete if b is finie, time complexity is $O(b^d)$. Its space complexity is $O(b^d)$ too and is a big problem.  It is optimal if cost =1 per step.  Ohterwise not optimal.\n",
              "Exponential space and time complexity.\n",
              "\n",
              "DFS idea: expand the deepest unexpanded node.  Frontier is a LIFO queue.\n",
              "DFS is incomplete in infinite-depth spaces, space with loops.  It is complete in finite spaces.  Its time complexity is $O(b^m)$, m is maximum depth of state space.\n",
              "If m > d, DFS is worse than BFS.  But if solustions are dense, DFS is faster than BFS.\n",
              "\n",
              "DFS' space complexity is $O(b*m) - linear space!\n",
              "It is not optimal.\n",
              "\n",
              "Use DFS if space is restricted, or many possible solutions with long paths and wrong paths are terminated quickly, or search can be fine-tuned quickly\n",
              "Use BFS if there are possible infinite paths, or some solutions have short paths, or can quickly discard unlikely paths.\n",
              "\n",
              "Depth limit DFS time complexity $O(b^l)$ and space complexity $O(bl)$\n",
              "Iterative deepening search uses depth-limit search as subroutine with increasing l.  It is complete and optimal as goal is always found at d the depth of the shallowest goal-node.\n",
              "Time complexity is $O(b^d)$. Space complexity is $O(bd)$.\n",
              "\n",
              "Both BFS and Iterative deepening search are complete and optimal.  Others are not.\n",
              "\n",
              "Inoformed Search uses domain-specifi information about hte location of the goals in order to find a solution more efficiently.\n",
              " \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **State space** - the set of states reachable from initial state by taking some sequence of actions\n",
              "* **Frontier** - states that are avaible for expaning\n",
              "* **Path** - sequence of actions leading from one state to another state\n",
              "* **B** - maximum branching factor of search tree\n",
              "* **D** - depth of the shallowest goal node\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 82,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Informed search uses domain specific hints about the location of the goals to find solution more efficiently.\n",
        "The hints come in the form of a heuristic function $h(n)$ = estimated cost of the cheapest path from the state at node n to a goal state.\n",
        "\n",
        "\n",
        "Greedy best-first search expands first the node with the lowest $h(n)$ value, which appears to be closet to the goal.  Evaluation function $f(n) = h(n)$.\n",
        "It is complete in finite state spaces, but not in infinite spaces.  The worst case time and space complexity is $O(|V|)$.  \n",
        "With good heuristic functions, the complexity can be reduced substantially, with some approaching $O(bm)$.\n",
        "\n",
        "\n",
        "A* search is a best-frist search that uses the evaluation function $f(n) = g(n) + h(n)$. $g(n)$ is the path cost from initial state to node n.\n",
        "An admissible heuristic is one that never overestimates the cost to reach a goal.\n",
        "A* is cost optimal with admissible heuristic.\n",
        "\n",
        "A heuristic $h(n)$ is consistent if for every node n and every successor n' of n generated by an action a, $h(n) \\leq c(n,a,n')+h(n')$.\n",
        "Triangle inequality, $h(n)$ is the side from n to G(goal).\n",
        "Every consistent (stronger property) heuristic is admissible (but not vice versa).  With a consistent heuristic, a state is on the optimal path when it is reached for the first time.\n",
        "\n",
        "\n",
        "Search contour of A* with a good heuristic fans out from the start node, streching toward a goal state and become more narrowly focused around an optimal path.\n",
        "The contours of uniform-cost search will be \"circular\" around the start state, spreading out equally in all directions.\n",
        "\n",
        "\n",
        "A* is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.\n",
        "A* expands many nodes, if we are willing to accept suboptimal solutions, or satisficing solutions that are \"good enough\", a search can be more efficient by expanding fewer nodes.\n",
        "Using inadmissible heuristic that may overestimate risk missing the optimal.\n",
        "Weighted A* search weights the heuristic value more heavily by $f(n) = g(n) + W*h(n)$ for $w >1$.\n",
        "Weighted A* is a little \"greedy\" since it weights more on the search towards a goal.  It wont ignore the path cost completely.\n",
        "\n",
        "\n",
        "Beam search is one of the memory-bound strategies.  It keeps only the $k$ nodes with the best $f$ scores.  It is incomplete and suboptimal.\n",
        "It limits the size of the frontier.  Choosing $k$ to make good use of available memory.  \n",
        "  \"\"\"\n",
        "chapter3_6 = \"\"\" effective branching factor b* is used to characterize the quality of a heuristic. \n",
        "\n",
        "If the A* search expands N nodes and the solution depth is d, b* is the branching factor that a uniform tree of depth d would have to have to contain N+1 nodes.\n",
        "$N+1 = 1+b^*+ (b^*)^2+...+(b^*)^d$.  A good heuristic would have b* close to 1.\n",
        "\n",
        "\n",
        "If $h_2(n) \\geq h_1(n)$, $h_2$ dominates $h_1$. Generally it is better to use a heuristic function with higher values.\n",
        "\n",
        "\n",
        "A problem with fewer restrictions is called a relaxed problem.  The state-space graph of a relaxed problem is a supergraph of the original state space because the removal of restrictions creates added edges in the graph.\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.  Hence, generating heuristics from relaxed problems.\n",
        "\n",
        "\n",
        "Generating heuristics from subproblems: pattern databases.  Deriving admissible heuristics from the solution cost of a subproblem of the original problem.\n",
        "Disjoint pattern databases.\n",
        "Generating heuristics with landmarks works well in route-finding problems.  Differential heuristic takes the difference between the cost from start node to the landmark and the cost from the landmark to the goal. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Uniform cost search is a search algorithm tranversing or searching a weighted tree, tree structure or graph.\n",
        "\n",
        "Uniform-cost search extends best-first search, alway expanding node with the lowest path cost.  The frontier is a priority queue.\n",
        "Unlike BFS, which checks if a node is a goal state before adding it to the frontier/queue, UCS enqueues the node and checks if the node is goal when selecting it for expansion.\n",
        "If a better path to the same state is found, it updates the node on the frontier.\n",
        "\n",
        "\n",
        "BFS explores equally in all directions while Uniform-cost search uses priority queue for its froniter and prefers to explore lowest-cost paths,\n",
        "resulting in \"cost contours\". \n",
        "\n",
        "Better idea: best-first search that expands node based an evaluation function $f(n)$, which includes estimated distance to goal.\n",
        "Heuristic function $h(n)$ takes a state n and return an estimate of the distance from n to goal.\n",
        "\n",
        "\n",
        "Greedy search replaces $g(n)$ in best-first search with $f(n) = h(n)$. Greedy search can stuck in loops and is incomplete.\n",
        "\n",
        "A* seach is the best known form of best-first search.  $f(n) = g(n) + h(n)$.  Heuristic is admissible if $h(n) \\leq h^*(n), h^*(n)$ is the actual cost.  $h(n) \\geq 0$.  If $h(n)$ is admissible, A* search is optimal.\n",
        "If two admissible heuristic $h_2(n) \\geq h_1(n)$ for all n, then $h_2$ dominates $h_1$.  $h_2$ is more accurate and thus better for the search.\n",
        "\n",
        "Consistent heuristics are always admissible.\n",
        "\n",
        "  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Manhattan distance\" : \"sum of the horizontal and vetical distance \",\n",
        "\"city-block distance\" : \"Manhattan distance\",   \n",
        "\"consistent heuristic\" : \"a heuristic function whose estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour.\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 83,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "4869b29f-c126-430d-ed04-f7e5888fbd94"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your definition of 'consistent heuristic' is too long!\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " Informed search uses domain specific hints about the location of the goals to find solution more efficiently.\n",
              "The hints come in the form of a heuristic function $h(n)$ = estimated cost of the cheapest path from the state at node n to a goal state.\n",
              "\n",
              "\n",
              "Greedy best-first search expands first the node with the lowest $h(n)$ value, which appears to be closet to the goal.  Evaluation function $f(n) = h(n)$.\n",
              "It is complete in finite state spaces, but not in infinite spaces.  The worst case time and space complexity is $O(|V|)$.  \n",
              "With good heuristic functions, the complexity can be reduced substantially, with some approaching $O(bm)$.\n",
              "\n",
              "\n",
              "A* search is a best-frist search that uses the evaluation function $f(n) = g(n) + h(n)$. $g(n)$ is the path cost from initial state to node n.\n",
              "An admissible heuristic is one that never overestimates the cost to reach a goal.\n",
              "A* is cost optimal with admissible heuristic.\n",
              "\n",
              "A heuristic $h(n)$ is consistent if for every node n and every successor n' of n generated by an action a, $h(n) \\leq c(n,a,n')+h(n')$.\n",
              "Triangle inequality, $h(n)$ is the side from n to G(goal).\n",
              "Every consistent (stronger property) heuristic is admissible (but not vice versa).  With a consistent heuristic, a state is on the optimal path when it is reached for the first time.\n",
              "\n",
              "\n",
              "Search contour of A* with a good heuristic fans out from the start node, streching toward a goal state and become more narrowly focused around an optimal path.\n",
              "The contours of uniform-cost search will be \"circular\" around the start state, spreading out equally in all directions.\n",
              "\n",
              "\n",
              "A* is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.\n",
              "A* expands many nodes, if we are willing to accept suboptimal solutions, or satisficing solutions that are \"good enough\", a search can be more efficient by expanding fewer nodes.\n",
              "Using inadmissible heuristic that may overestimate risk missing the optimal.\n",
              "Weighted A* search weights the heuristic value more heavily by $f(n) = g(n) + W*h(n)$ for $w >1$.\n",
              "Weighted A* is a little \"greedy\" since it weights more on the search towards a goal.  It wont ignore the path cost completely.\n",
              "\n",
              "\n",
              "Beam search is one of the memory-bound strategies.  It keeps only the $k$ nodes with the best $f$ scores.  It is incomplete and suboptimal.\n",
              "It limits the size of the frontier.  Choosing $k$ to make good use of available memory.  \n",
              "  \n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " effective branching factor b* is used to characterize the quality of a heuristic. \n",
              "\n",
              "If the A* search expands N nodes and the solution depth is d, b* is the branching factor that a uniform tree of depth d would have to have to contain N+1 nodes.\n",
              "$N+1 = 1+b^*+ (b^*)^2+...+(b^*)^d$.  A good heuristic would have b* close to 1.\n",
              "\n",
              "\n",
              "If $h_2(n) \\geq h_1(n)$, $h_2$ dominates $h_1$. Generally it is better to use a heuristic function with higher values.\n",
              "\n",
              "\n",
              "A problem with fewer restrictions is called a relaxed problem.  The state-space graph of a relaxed problem is a supergraph of the original state space because the removal of restrictions creates added edges in the graph.\n",
              "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.  Hence, generating heuristics from relaxed problems.\n",
              "\n",
              "\n",
              "Generating heuristics from subproblems: pattern databases.  Deriving admissible heuristics from the solution cost of a subproblem of the original problem.\n",
              "Disjoint pattern databases.\n",
              "Generating heuristics with landmarks works well in route-finding problems.  Differential heuristic takes the difference between the cost from start node to the landmark and the cost from the landmark to the goal. \n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Uniform cost search is a search algorithm tranversing or searching a weighted tree, tree structure or graph.\n",
              "\n",
              "Uniform-cost search extends best-first search, alway expanding node with the lowest path cost.  The frontier is a priority queue.\n",
              "Unlike BFS, which checks if a node is a goal state before adding it to the frontier/queue, UCS enqueues the node and checks if the node is goal when selecting it for expansion.\n",
              "If a better path to the same state is found, it updates the node on the frontier.\n",
              "\n",
              "\n",
              "BFS explores equally in all directions while Uniform-cost search uses priority queue for its froniter and prefers to explore lowest-cost paths,\n",
              "resulting in \"cost contours\". \n",
              "\n",
              "Better idea: best-first search that expands node based an evaluation function $f(n)$, which includes estimated distance to goal.\n",
              "Heuristic function $h(n)$ takes a state n and return an estimate of the distance from n to goal.\n",
              "\n",
              "\n",
              "Greedy search replaces $g(n)$ in best-first search with $f(n) = h(n)$. Greedy search can stuck in loops and is incomplete.\n",
              "\n",
              "A* seach is the best known form of best-first search.  $f(n) = g(n) + h(n)$.  Heuristic is admissible if $h(n) \\leq h^*(n), h^*(n)$ is the actual cost.  $h(n) \\geq 0$.  If $h(n)$ is admissible, A* search is optimal.\n",
              "If two admissible heuristic $h_2(n) \\geq h_1(n)$ for all n, then $h_2$ dominates $h_1$.  $h_2$ is more accurate and thus better for the search.\n",
              "\n",
              "Consistent heuristics are always admissible.\n",
              "\n",
              "  \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Manhattan distance** - sum of the horizontal and vetical distance \n",
              "* **City-block distance** - Manhattan distance\n",
              "* **Consistent heuristic** - a heuristic function whose estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour.\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 84,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Competitive  environments, in which two or more agents have conflicting goals, giving rise to adversarial search problems.\n",
        "\n",
        "Deterministic, two-player, tern-taking, perfect information, zero-sum games.  \n",
        "\n",
        "\n",
        "A game can be formally defined with following elements:\n",
        "\n",
        "The initial state $S_0$.  \n",
        "Whose turn to move in a state S.  \n",
        "A set of legal moves/actions in sate S.  \n",
        "Transition model which defines the state resulting from taking action a in state S.  \n",
        "A terminal test (terminal states are where the game ends.)\n",
        "Utility function which defines the final numeric value to player p when the game ends in terminal state s.\n",
        "\n",
        "\n",
        "Game tree is a search tree that follows every sequence of moves all the way to a terminal state.  Maybe infinite if the state space is unbounded or the rules of the game allow for infinitely repeating positions.\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" Ply, one move for one player bringing one level deeper in the game tree.\n",
        "\n",
        "Given a game tree, the optimal strategy can be determined by working out the minimax value of each state in the tree.   Assuming both players play optimally from there to the end of the game, the minimax value is the utility (for Max) of being in that state,.  In a non-terminal state, MAX prefers to move to a state of maximum value when it is MAX’s turn, and MIN prefers a state of minimum value.\n",
        "\n",
        "\n",
        "The minimax algorithm performs a complete depth-first exploration of the game tree.  The time complexity is O(b^m), and the space complexity is O(bm) for an algorithm that generates all actions at once, or O(m) for an algorithm that generates actions one at a time.  The exponential complexity makes MINIMAX impractical for complex games.\n",
        "\n",
        "\n",
        "Optimal decisions in multiplayer games\n",
        "First, replacing the single value for each node with a vector of values.  Utility function returns a vector of utilities.  This vector gives the utility of the state from each player’s viewpoint.  For nonterminal states, in general, the backed-up value of a node n is the utility vector of the successor state with the highest value for the player choosing at n.\n",
        "\n",
        "\n",
        "Alpha-Beta pruning\n",
        "\n",
        "α = the value of the best (highest- value) choice found so far at any choice point along the path for MAX “at least”\n",
        "β = the value of the best (lowest-value) choice found so far at any choice point along the path for MIN “at most”\n",
        "\n",
        "\n",
        "Alpha-beta search updates the values of α and β as it goes along and prunes the remaining branches at a node as soon as the value of the current node is know to be worse than the current α  or β value for MAX or MIN, respectively.\n",
        "\n",
        "\n",
        "Move ordering\n",
        "\n",
        "The effectiveness of alpha-beta pruning is highly dependent on the order in which the states are examined.  \n",
        "If ordering the successors perfectly, alpha-beta would need to examine only $O(b^{m/2})$ nodes to pick the best move.  With random move ordering, it would be $O(b^{3m/4})$ for moderate b. \n",
        "\n",
        "\n",
        "Adding dynamic move-ordering schemes, trying the moves that were found to be best in the past. The past could be the previous move or from previous exploration of the current move through iterative deepening.  The killer move heuristic tries killer moves first.\n",
        "\n",
        "\n",
        "Transpositions: different permutations of the move sequence that end up in the same position, and this problem can be addressed with a transposition table that catches the heuristic value of states. \n",
        "\n",
        "\n",
        "Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth.  It explores a wide but shallow portion of the tree.  \n",
        "Type B strategy ignores moves that look bad, and follows promising lines “as far as possible”. It explores a deep but narrow portion of the tree.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" Apply a heuristic evaluation function to states and cut off the search early. Replacing the utility function with EVAL, which estimates a state's utility.\n",
        "Also replacing terminal test with cutoff test, which returns true at terminal states but otherwise determines weather to cut off the search based on depth and any other property it chooses to consider.\n",
        "\n",
        "\n",
        "Weighted linear function\n",
        "In chess, weights are based on human experience.  If such kind of experience is not available, machine learning techniques can estimate the weights of the evaluation function.\n",
        "\n",
        "\n",
        "Cutoff test replaces terminal test: \n",
        "if game.IS_CUTOFF(state, depth) then return game.EVAL(state, player), null\n",
        "IS_CUTOFF returns true for all depth greater than some fixed depth d and for all terminal states.  EVAL returns terminal val for terminal states.\n",
        "\n",
        "\n",
        "Quiescent: positions in which there is no pending  move (such as a capturing the queen) that would wildly swing the evaluation.  For nonquiescent positions the IS_CUTOFF returns false, and the search continues until quiescent positions are reached.\n",
        "\n",
        "\n",
        "Horizon effect, push obvious “loss” beyond cutoff horizon such that the search consider the moves are good even though leading to “loss” that beyond the horizon the search can see.\n",
        "One strategy to mitigate the horizon effect is to allow singular extensions, moves that are clearly better than all other moves in a given position, even when the search would normally be cut off at that point.\n",
        "\n",
        "\n",
        "Forward pruning prunes moves that appear to be poor, and it saves computation time at the risk of making an error. (this is a Type B stretey)\n",
        "Beam search is a type of forward pruning.\n",
        "\n",
        "\n",
        "The ProbCut or probabilistic cut algorithm is another type of forward pruning that uses statics gained from prior experience to reduce the chance of the best move being pruned.  Alph-beta prunes any node that is proved outside the current alpha-beta window.\n",
        "ProbCut prunes nodes that are probably outside the window.\n",
        "Another type of forward pruning is Late Move Reduction.  It assumes the move ordering is done well.  The moves apprearing later in possible moves is probably not good.  Instead of pruning them completely, do a limited depth search on the late moves.\n",
        "If the returned value is greater than current alpha, then redo the search to the full depth.\n",
        "\n",
        "\n",
        "Search versus lookup\n",
        "Many game playing programs use table lookup rather than search for the openning and ending of games.\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" Go has a branching factor that starts at 361, which mean alpha-beta search would be limited to only 4 to 5 ply.  \n",
        "Second, it is difficult to define a good evaluation function for Go because material value is not a strong indicator, and most positions are in flux until the endgame.  \n",
        "Modern Go programs have abandoned alpha-beta search and instead use MCTS.\n",
        "\n",
        "\n",
        "Instead of using heuristic evaluation function for a state, MCTS estimates the value of a state with the average of utility over a number of simulations of complete games from that state.\n",
        "A simulation, a rollout, or a playout chooses moves until a terminal position is reached.  \n",
        "Playout policy biased the moves towards good ones is needed instead of choosing random moves.\n",
        "\n",
        "\n",
        "Conventional wisdom is that MCTS has advantage over alpha-beta in games such as Go where the branching factor is very high or in games that is difficult to define a good evaluation function.\n",
        "\n",
        "\n",
        "MC search can be applied to new games that has no prior experience to draw upon to define evaluation function.  MC search does not need more information as long as the rules are known.\n",
        "The selection and playout policy can be learned using neural networks trained by self-play alone.\n",
        "\n",
        "\n",
        "Stochastic games that include a random element are a little closer to the unpredictability of real life.\n",
        "Include chance nodes in addition to  Max an Min nodes. We can calculate expected value of a position, which is the average over all possible outcomes of the chance nodes, instead of having definite minimax values.\n",
        "That is expectiminimax value.\n",
        "\n",
        "\n",
        "Evaluation function must return values that are a positive linear transformation of the probability of winning (or of the expected utility).\n",
        "\n",
        "\n",
        "Expectiminimax's time complexity is $O(b^m n^m)$ vs minimax's $O(b^m)$, where n is the number of distinct rolls.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Decision theory deals with choosing among actions based on how desirable is their immediate outcomes.\n",
        "\n",
        "Expected utility of an action is the average utility vlaue of the outcomes, weighted by the the probability of the respective outcome.\n",
        "\n",
        "Maximum expected utility (MEU) principle is that a rational agent chooses the action that maximizes the expected utility.\n",
        "\n",
        "There are other possible reasonable way to make decision such as minimizing the worst possible loss.\n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Uncertain outcomes controlled by chance not adversary.\n",
        "Expectimax search: max nodes play just like in minimax; chance nodes replaces min nodes, with expected utilities as the weighted average of all possible children.\n",
        "\n",
        "Expectiminimax.  Environment is an extra \"random agent\".  Hence, max nodes followed by chance nodes, then followed by min nodes and chance nodes...\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 85,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "b8c87235-7d5d-4a16-8d4a-eb86420ef5c0"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " Competitive  environments, in which two or more agents have conflicting goals, giving rise to adversarial search problems.\n",
              "\n",
              "Deterministic, two-player, tern-taking, perfect information, zero-sum games.  \n",
              "\n",
              "\n",
              "A game can be formally defined with following elements:\n",
              "\n",
              "The initial state $S_0$.  \n",
              "Whose turn to move in a state S.  \n",
              "A set of legal moves/actions in sate S.  \n",
              "Transition model which defines the state resulting from taking action a in state S.  \n",
              "A terminal test (terminal states are where the game ends.)\n",
              "Utility function which defines the final numeric value to player p when the game ends in terminal state s.\n",
              "\n",
              "\n",
              "Game tree is a search tree that follows every sequence of moves all the way to a terminal state.  Maybe infinite if the state space is unbounded or the rules of the game allow for infinitely repeating positions.\n",
              " \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Ply, one move for one player bringing one level deeper in the game tree.\n",
              "\n",
              "Given a game tree, the optimal strategy can be determined by working out the minimax value of each state in the tree.   Assuming both players play optimally from there to the end of the game, the minimax value is the utility (for Max) of being in that state,.  In a non-terminal state, MAX prefers to move to a state of maximum value when it is MAX’s turn, and MIN prefers a state of minimum value.\n",
              "\n",
              "\n",
              "The minimax algorithm performs a complete depth-first exploration of the game tree.  The time complexity is O(b^m), and the space complexity is O(bm) for an algorithm that generates all actions at once, or O(m) for an algorithm that generates actions one at a time.  The exponential complexity makes MINIMAX impractical for complex games.\n",
              "\n",
              "\n",
              "Optimal decisions in multiplayer games\n",
              "First, replacing the single value for each node with a vector of values.  Utility function returns a vector of utilities.  This vector gives the utility of the state from each player’s viewpoint.  For nonterminal states, in general, the backed-up value of a node n is the utility vector of the successor state with the highest value for the player choosing at n.\n",
              "\n",
              "\n",
              "Alpha-Beta pruning\n",
              "\n",
              "α = the value of the best (highest- value) choice found so far at any choice point along the path for MAX “at least”\n",
              "β = the value of the best (lowest-value) choice found so far at any choice point along the path for MIN “at most”\n",
              "\n",
              "\n",
              "Alpha-beta search updates the values of α and β as it goes along and prunes the remaining branches at a node as soon as the value of the current node is know to be worse than the current α  or β value for MAX or MIN, respectively.\n",
              "\n",
              "\n",
              "Move ordering\n",
              "\n",
              "The effectiveness of alpha-beta pruning is highly dependent on the order in which the states are examined.  \n",
              "If ordering the successors perfectly, alpha-beta would need to examine only $O(b^{m/2})$ nodes to pick the best move.  With random move ordering, it would be $O(b^{3m/4})$ for moderate b. \n",
              "\n",
              "\n",
              "Adding dynamic move-ordering schemes, trying the moves that were found to be best in the past. The past could be the previous move or from previous exploration of the current move through iterative deepening.  The killer move heuristic tries killer moves first.\n",
              "\n",
              "\n",
              "Transpositions: different permutations of the move sequence that end up in the same position, and this problem can be addressed with a transposition table that catches the heuristic value of states. \n",
              "\n",
              "\n",
              "Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth.  It explores a wide but shallow portion of the tree.  \n",
              "Type B strategy ignores moves that look bad, and follows promising lines “as far as possible”. It explores a deep but narrow portion of the tree.\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Apply a heuristic evaluation function to states and cut off the search early. Replacing the utility function with EVAL, which estimates a state's utility.\n",
              "Also replacing terminal test with cutoff test, which returns true at terminal states but otherwise determines weather to cut off the search based on depth and any other property it chooses to consider.\n",
              "\n",
              "\n",
              "Weighted linear function\n",
              "In chess, weights are based on human experience.  If such kind of experience is not available, machine learning techniques can estimate the weights of the evaluation function.\n",
              "\n",
              "\n",
              "Cutoff test replaces terminal test: \n",
              "if game.IS_CUTOFF(state, depth) then return game.EVAL(state, player), null\n",
              "IS_CUTOFF returns true for all depth greater than some fixed depth d and for all terminal states.  EVAL returns terminal val for terminal states.\n",
              "\n",
              "\n",
              "Quiescent: positions in which there is no pending  move (such as a capturing the queen) that would wildly swing the evaluation.  For nonquiescent positions the IS_CUTOFF returns false, and the search continues until quiescent positions are reached.\n",
              "\n",
              "\n",
              "Horizon effect, push obvious “loss” beyond cutoff horizon such that the search consider the moves are good even though leading to “loss” that beyond the horizon the search can see.\n",
              "One strategy to mitigate the horizon effect is to allow singular extensions, moves that are clearly better than all other moves in a given position, even when the search would normally be cut off at that point.\n",
              "\n",
              "\n",
              "Forward pruning prunes moves that appear to be poor, and it saves computation time at the risk of making an error. (this is a Type B stretey)\n",
              "Beam search is a type of forward pruning.\n",
              "\n",
              "\n",
              "The ProbCut or probabilistic cut algorithm is another type of forward pruning that uses statics gained from prior experience to reduce the chance of the best move being pruned.  Alph-beta prunes any node that is proved outside the current alpha-beta window.\n",
              "ProbCut prunes nodes that are probably outside the window.\n",
              "Another type of forward pruning is Late Move Reduction.  It assumes the move ordering is done well.  The moves apprearing later in possible moves is probably not good.  Instead of pruning them completely, do a limited depth search on the late moves.\n",
              "If the returned value is greater than current alpha, then redo the search to the full depth.\n",
              "\n",
              "\n",
              "Search versus lookup\n",
              "Many game playing programs use table lookup rather than search for the openning and ending of games.\n",
              " \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Go has a branching factor that starts at 361, which mean alpha-beta search would be limited to only 4 to 5 ply.  \n",
              "Second, it is difficult to define a good evaluation function for Go because material value is not a strong indicator, and most positions are in flux until the endgame.  \n",
              "Modern Go programs have abandoned alpha-beta search and instead use MCTS.\n",
              "\n",
              "\n",
              "Instead of using heuristic evaluation function for a state, MCTS estimates the value of a state with the average of utility over a number of simulations of complete games from that state.\n",
              "A simulation, a rollout, or a playout chooses moves until a terminal position is reached.  \n",
              "Playout policy biased the moves towards good ones is needed instead of choosing random moves.\n",
              "\n",
              "\n",
              "Conventional wisdom is that MCTS has advantage over alpha-beta in games such as Go where the branching factor is very high or in games that is difficult to define a good evaluation function.\n",
              "\n",
              "\n",
              "MC search can be applied to new games that has no prior experience to draw upon to define evaluation function.  MC search does not need more information as long as the rules are known.\n",
              "The selection and playout policy can be learned using neural networks trained by self-play alone.\n",
              "\n",
              "\n",
              "Stochastic games that include a random element are a little closer to the unpredictability of real life.\n",
              "Include chance nodes in addition to  Max an Min nodes. We can calculate expected value of a position, which is the average over all possible outcomes of the chance nodes, instead of having definite minimax values.\n",
              "That is expectiminimax value.\n",
              "\n",
              "\n",
              "Evaluation function must return values that are a positive linear transformation of the probability of winning (or of the expected utility).\n",
              "\n",
              "\n",
              "Expectiminimax's time complexity is $O(b^m n^m)$ vs minimax's $O(b^m)$, where n is the number of distinct rolls.\n",
              "\n",
              "\n",
              " \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Decision theory deals with choosing among actions based on how desirable is their immediate outcomes.\n",
              "\n",
              "Expected utility of an action is the average utility vlaue of the outcomes, weighted by the the probability of the respective outcome.\n",
              "\n",
              "Maximum expected utility (MEU) principle is that a rational agent chooses the action that maximizes the expected utility.\n",
              "\n",
              "There are other possible reasonable way to make decision such as minimizing the worst possible loss.\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Uncertain outcomes controlled by chance not adversary.\n",
              "Expectimax search: max nodes play just like in minimax; chance nodes replaces min nodes, with expected utilities as the weighted average of all possible children.\n",
              "\n",
              "Expectiminimax.  Environment is an extra \"random agent\".  Hence, max nodes followed by chance nodes, then followed by min nodes and chance nodes...\n",
              " \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 86,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" CSP uses a factored representation for each state: a set of variables, each of which has a value.  A problem is solved when each variable has a value that satisfies all the constraints on the variable.\n",
        "\n",
        "CSP search algorithms take advantage of the structure of states and use general rather than domain-specific heuristics to enable the solution of complex problems.  \n",
        "The main idea is to eliminate large portions of the search space by identifying variable/value combinations that violate the constraints.\n",
        "\n",
        "A CSP consists of:\n",
        "  X, a set of variables; \n",
        "  D, a set of domains, one for each variable; \n",
        "  and C, a set of constraints.  \n",
        "\n",
        "A domain $D_i$ consists of a set of allowable values {$v_1,…, v_k$} for variable $X_i$.  \n",
        "\n",
        "\n",
        "An assignment (of value to variable) that does not violate any constraints is called a consistent or legal assignment.  A complete assignment is one in which every variable is assigned a value.  \n",
        "A solution to a CSP is a consistent, complete assignment.\n",
        "\n",
        "\n",
        "To visualize a CSP as a constraint graph, where the nodes correspond to variables of the problem, and an edge connects any two variables that participate in a constraint.\n",
        "\n",
        "\n",
        "Reasons to formulate a problem as a CSP: \n",
        "a) a natural representation for a wide variety of problems.  \n",
        "B)CSP solvers are fast and efficient thanks to years of development.  \n",
        "C) a CSP solver can quickly prune large swathes of the search space that an atomic state-space searcher cannot.\n",
        "\n",
        "\n",
        "The simplest kind of CSP involves variables that have discrete, finite domains.  \n",
        "Types of constraints.  Unary, binary, higher order, global constraint (need not involve all the variables, but an arbitrary number of variables.), and cryptarithmetic puzzles.\n",
        "\n",
        "\n",
        "Every finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced.  (transform any CSP into one with only binary constraints)\n",
        "\n",
        "\n",
        "Preference constraints can often be encoded as costs on individual variable assignments.\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" CSP algorithm can either generate successors by choosing a new variable assignment or do constraint propagation, which is a specific type of inference: using the constraints to reduce the number of legal values for a variable.  Constraint propagation may be intertwined with search or be done as a preprocessing.\n",
        "\n",
        "\n",
        "Local consistency: \n",
        "1. Node consistency.  \n",
        "2. Arc consistency.  A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints.  \n",
        "$X_i$ is arc-consistent with respect to another variable $X_j$ if for every value in the domain $D_i$ there is some value in the domain $D_j$ that satisfies the binary constraint on the arc (Xi, Xj).  \n",
        "A graph is arc-consistent if every variable is arc-consistent with every other variable.\n",
        "\n",
        "\n",
        "AC-3 maintains a queue of arcs, which initially contains all the arcs in the CSP (each binary constraint becomes two arcs). Pops off an arbitrary arc $(X_i, X_j)$ from the queue, and make Xi arc-consistent with Xj.  \n",
        "If $D_i$ is unchanged, moves on to the next arc.  If $D_i$ is revised (smaller), then add to the queue all arcs $(X_k, X_i)$ where $X_k$ is a neighbor of $X_i$.  \n",
        "If $D_i$ is revised down to nothing,  there is no solution.  Otherwise, keep checking until no more arc in the queue.\n",
        "\n",
        "AC-3 time complexity: $O(cd^3)$, for a CSP with n variables, each with domain size at most d, and with c  binary constraints (arcs).\n",
        "\n",
        "\n",
        "3. Path consistency.  It tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
        "4. K-consistency.  A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.  \n",
        "1-consistency is node consistency.  2-consistency is arc consistency.  For binary constraint graphs, 3-consistency is path consistency.\n",
        "\n",
        "\n",
        "Strongly k-consistent, if a CSP is k-consistent and also (k-1)-consistent, …, all the way to 1-consistent.  Then the problem is solved.  First, choose a consistent value for X1, then (guaranteed to be able) to choose a value for X2 … \n",
        "For each variable Xi, only need to search through the d values in the domain to find a value consistent with X1,…,Xi-1.  Run time is $O(n^2d)$.\n",
        "Any algorithm for establishing n-consistency must take time and space exponential in n in the worst case. \n",
        "\n",
        "\n",
        "A simple consistency procedure for a higher-order constraint is sometimes more effective than applying arc consistency to an equivalent set of binary constraints.\n",
        "For large resource-limited (Atmost) problems with integer values, domains are represented by upper and lower bounds and are managed by bounds propagation.  \n",
        "A CSP is bounds-consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y.\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" Commutativity. The order of application of any given set of actions does not matter.  \n",
        "A CSP with n variables of domain size d would end up with a search tree where all the complete assignments (thus solutions) are leaf nodes at depth n.  \n",
        "The tree has $n!d^n$ leaves (branching factor is nd at top level, (n-1)d at next level...) but only $d^n$ possible complete assignments.\n",
        "\n",
        "\n",
        "Variable and value ordering.  \n",
        "Minimum-remaining-values (MRV) heuristic, also called the “most constrained variable” or “fail-first” heuristic.  \n",
        "The Degree Heuristic selects the variable that is involved in the largest number of constraints on other unassigned variables (most “constraining”).  \n",
        "Least constraining value heuristic prefers the value that rules out the fewest choices for the neighboring variables.  \n",
        "\n",
        "\n",
        "Variable selection shall be fail-first, but value selection be fail-last because every variable has to be assigned eventually.  So by choosing the ones that are likely to fail first, we will on average have fewer successful assignments to backtrack over.  For value ordering, the trick is that we only need one solution, hence, it makes sense to look for the mostly values first.\n",
        "Interleaving search and inference.\n",
        "\n",
        "\n",
        "Forward checking: when a variable X is assigned, establish arc consistency for it:  for every unassigned variable Y that is connected to X by a constraint, delete any value that is inconsistent with X from Y’s domain.\n",
        "Combining MRV heuristic with forward checking is more effective for many problems.\n",
        "\n",
        "\n",
        "Maintaining Arc Consistency (MAC) algorithm detects inconsistencies created by forward checking deleting inconsistent values (such as between Yi and Yj). After assigning a value to Xi, MAC calls AC-3, but start with only the arc (Xj, Xi), rather than all arcs, for all Xj that are unassigned neighbors of Xi. If any variable has its domain reduced to empty, backtrack immediately.\n",
        "\n",
        "\n",
        "Chronological backtracking backs up to the proceeding variable and try a different value, revisiting the most recent decision point.  \n",
        "\n",
        "\n",
        "A more intelligent approach keeps a conflict set that tracks a set of assignments that are in conflict with the variable causing search failure.  The backjumping  method backtracks to the most recent assignment in the conflict set.  Forward checking can supply the conflict set without extra work.\n",
        "\n",
        "\n",
        "Simple backjumping is redundant in forward checking search.\n",
        "Conflict-directed backjumping identifies (a different and deeper-notion conflict set) the set of proceeding variables, together with any subsequent variables, that causes a variable has no consistent solution.\n",
        "\n",
        "\n",
        "Constraint learning finds a minimum set of variables from the conflict set that causes the problem.  This set of variables along with their corresponding values are no-good.  Record the no-good.\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" Local search algorithms turn out to be very effective in solving many CSPs.\n",
        "USing complete stat formulation where each state assigns a value to every varialbe, and then changes the value of one variable at a time.\n",
        "The min-conflicts heuristic, which selects the value that results in the minimum number of conflicts with other variables.\n",
        "\n",
        "\n",
        "Constraint weighting concentrates the search on the important constraints.\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" Independent subproblems.  Finding connected components of the constraint graph can help identify independence.\n",
        "Each subproblem has c(a constant) variables from the total n varialbes. There are n/c subproblems, and each takes $O(d^c)$ to solve.  Total work is $O(d^c n/c)$ which is linear in n.\n",
        "Without decomposition, it is $O(d^n)$.\n",
        "\n",
        "\n",
        "Directional arc onsistency (DAC): A CSP is DAC under an ordering of variables $X_1, X_2, ..., X_n$ if and only if every $X_i$ is arc-consistent with each $X_j$ for j>i.\n",
        "\n",
        "\n",
        "Topological sort.  Make it directional arc consistent in n steps (n-1 edges for the tree), comparing up to d possible domain values for two variables, for a total time of $O(nd^2)$.\n",
        "Once having a directed arc-consistent graph, march down the list of variables and choosse any remaining vlue.\n",
        "Efficent algorithm for trees, try to reduce more general constraint graph to trees.\n",
        "\n",
        "\n",
        "Cuset conditioning reduce a constraint graph to a tree by removing nodes.  Choose a subset S such that the constraint graph becomes a tree after removing S.  S is a cycle cutset.\n",
        "For each possible assignment to the variables in S that satisfies all constraints on S, remove any value that are inconsistent with the assignment(for S) from the domains of the remaining variables(on the tree).  \n",
        "If there is a solution to the remaining part of the CSP, return it with the assignment for S.  If the cycle cutset has size c, the total run time is $O(d^c(n-c)d^2)$.\n",
        "\n",
        "\n",
        "Tree decomposition: transformation of a constraint graph into a tree.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Solutions to CSPs can be found by a general purpose algorithm.\n",
        "\n",
        "CSPs may have discrete variables with finite domains or infinite domains.  They may have continuous variables.\n",
        "\n",
        "\n",
        "Search for CSPs only need to consider assignments to a single variable at each node, hence b=d and there are $d^n$ leaves.\n",
        "Backtracking search is DFS for CSPs with single-variable assignments.\n",
        "\n",
        "\n",
        "With following heuristics, backtracking search can gain big efficiency.\n",
        "choosing the most constrainted variable for assignment,\n",
        "choosing the most constraining variable for tie breaker of most constrainted variable,\n",
        "choosing the least constraining value,\n",
        "forward checking.\n",
        "\n",
        "CSP solvers combine search and constraint propagation (inference).\n",
        "\n",
        "Constraint graph with nodes as variables and edges as constraints.\n",
        "\n",
        "\n",
        "AC-3 complexity: total numbers of arcs is 2*n*(n-1) = $O(n^2)$\n",
        "checking an arc takes $O(d^2)$ time, for maximum d values in any domain.\n",
        "each arc can only be inserted into the queue d times.\n",
        "Total time complexity $O(n^2d^3)$.\n",
        "A pair of variable $X_i,X_j$ is path-consistent with $X_m$ if for every assignment $X_i =a, X_j=b$ that is consistent with constraint of $x_i, X_j$, \n",
        "there is a value for $X_m$ in its domain such that both $X_i, X_m$ and $X_j, X_m$ are consistent with their repective constraints.\n",
        "\n",
        "Constraint graph that is a tree can be solved efficiently (linear time to n the number of variables).  Do a topological sort adn march down the list.\n",
        "Cycle cutset algorithm $O(d^{c+2}(n-c))$\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 87,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "994d1b64-fa6a-4f30-f881-04743aba9298"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " CSP uses a factored representation for each state: a set of variables, each of which has a value.  A problem is solved when each variable has a value that satisfies all the constraints on the variable.\n",
              "\n",
              "CSP search algorithms take advantage of the structure of states and use general rather than domain-specific heuristics to enable the solution of complex problems.  \n",
              "The main idea is to eliminate large portions of the search space by identifying variable/value combinations that violate the constraints.\n",
              "\n",
              "A CSP consists of:\n",
              "  X, a set of variables; \n",
              "  D, a set of domains, one for each variable; \n",
              "  and C, a set of constraints.  \n",
              "\n",
              "A domain $D_i$ consists of a set of allowable values {$v_1,…, v_k$} for variable $X_i$.  \n",
              "\n",
              "\n",
              "An assignment (of value to variable) that does not violate any constraints is called a consistent or legal assignment.  A complete assignment is one in which every variable is assigned a value.  \n",
              "A solution to a CSP is a consistent, complete assignment.\n",
              "\n",
              "\n",
              "To visualize a CSP as a constraint graph, where the nodes correspond to variables of the problem, and an edge connects any two variables that participate in a constraint.\n",
              "\n",
              "\n",
              "Reasons to formulate a problem as a CSP: \n",
              "a) a natural representation for a wide variety of problems.  \n",
              "B)CSP solvers are fast and efficient thanks to years of development.  \n",
              "C) a CSP solver can quickly prune large swathes of the search space that an atomic state-space searcher cannot.\n",
              "\n",
              "\n",
              "The simplest kind of CSP involves variables that have discrete, finite domains.  \n",
              "Types of constraints.  Unary, binary, higher order, global constraint (need not involve all the variables, but an arbitrary number of variables.), and cryptarithmetic puzzles.\n",
              "\n",
              "\n",
              "Every finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced.  (transform any CSP into one with only binary constraints)\n",
              "\n",
              "\n",
              "Preference constraints can often be encoded as costs on individual variable assignments.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " CSP algorithm can either generate successors by choosing a new variable assignment or do constraint propagation, which is a specific type of inference: using the constraints to reduce the number of legal values for a variable.  Constraint propagation may be intertwined with search or be done as a preprocessing.\n",
              "\n",
              "\n",
              "Local consistency: \n",
              "1. Node consistency.  \n",
              "2. Arc consistency.  A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints.  \n",
              "$X_i$ is arc-consistent with respect to another variable $X_j$ if for every value in the domain $D_i$ there is some value in the domain $D_j$ that satisfies the binary constraint on the arc (Xi, Xj).  \n",
              "A graph is arc-consistent if every variable is arc-consistent with every other variable.\n",
              "\n",
              "\n",
              "AC-3 maintains a queue of arcs, which initially contains all the arcs in the CSP (each binary constraint becomes two arcs). Pops off an arbitrary arc $(X_i, X_j)$ from the queue, and make Xi arc-consistent with Xj.  \n",
              "If $D_i$ is unchanged, moves on to the next arc.  If $D_i$ is revised (smaller), then add to the queue all arcs $(X_k, X_i)$ where $X_k$ is a neighbor of $X_i$.  \n",
              "If $D_i$ is revised down to nothing,  there is no solution.  Otherwise, keep checking until no more arc in the queue.\n",
              "\n",
              "AC-3 time complexity: $O(cd^3)$, for a CSP with n variables, each with domain size at most d, and with c  binary constraints (arcs).\n",
              "\n",
              "\n",
              "3. Path consistency.  It tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
              "4. K-consistency.  A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.  \n",
              "1-consistency is node consistency.  2-consistency is arc consistency.  For binary constraint graphs, 3-consistency is path consistency.\n",
              "\n",
              "\n",
              "Strongly k-consistent, if a CSP is k-consistent and also (k-1)-consistent, …, all the way to 1-consistent.  Then the problem is solved.  First, choose a consistent value for X1, then (guaranteed to be able) to choose a value for X2 … \n",
              "For each variable Xi, only need to search through the d values in the domain to find a value consistent with X1,…,Xi-1.  Run time is $O(n^2d)$.\n",
              "Any algorithm for establishing n-consistency must take time and space exponential in n in the worst case. \n",
              "\n",
              "\n",
              "A simple consistency procedure for a higher-order constraint is sometimes more effective than applying arc consistency to an equivalent set of binary constraints.\n",
              "For large resource-limited (Atmost) problems with integer values, domains are represented by upper and lower bounds and are managed by bounds propagation.  \n",
              "A CSP is bounds-consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Commutativity. The order of application of any given set of actions does not matter.  \n",
              "A CSP with n variables of domain size d would end up with a search tree where all the complete assignments (thus solutions) are leaf nodes at depth n.  \n",
              "The tree has $n!d^n$ leaves (branching factor is nd at top level, (n-1)d at next level...) but only $d^n$ possible complete assignments.\n",
              "\n",
              "\n",
              "Variable and value ordering.  \n",
              "Minimum-remaining-values (MRV) heuristic, also called the “most constrained variable” or “fail-first” heuristic.  \n",
              "The Degree Heuristic selects the variable that is involved in the largest number of constraints on other unassigned variables (most “constraining”).  \n",
              "Least constraining value heuristic prefers the value that rules out the fewest choices for the neighboring variables.  \n",
              "\n",
              "\n",
              "Variable selection shall be fail-first, but value selection be fail-last because every variable has to be assigned eventually.  So by choosing the ones that are likely to fail first, we will on average have fewer successful assignments to backtrack over.  For value ordering, the trick is that we only need one solution, hence, it makes sense to look for the mostly values first.\n",
              "Interleaving search and inference.\n",
              "\n",
              "\n",
              "Forward checking: when a variable X is assigned, establish arc consistency for it:  for every unassigned variable Y that is connected to X by a constraint, delete any value that is inconsistent with X from Y’s domain.\n",
              "Combining MRV heuristic with forward checking is more effective for many problems.\n",
              "\n",
              "\n",
              "Maintaining Arc Consistency (MAC) algorithm detects inconsistencies created by forward checking deleting inconsistent values (such as between Yi and Yj). After assigning a value to Xi, MAC calls AC-3, but start with only the arc (Xj, Xi), rather than all arcs, for all Xj that are unassigned neighbors of Xi. If any variable has its domain reduced to empty, backtrack immediately.\n",
              "\n",
              "\n",
              "Chronological backtracking backs up to the proceeding variable and try a different value, revisiting the most recent decision point.  \n",
              "\n",
              "\n",
              "A more intelligent approach keeps a conflict set that tracks a set of assignments that are in conflict with the variable causing search failure.  The backjumping  method backtracks to the most recent assignment in the conflict set.  Forward checking can supply the conflict set without extra work.\n",
              "\n",
              "\n",
              "Simple backjumping is redundant in forward checking search.\n",
              "Conflict-directed backjumping identifies (a different and deeper-notion conflict set) the set of proceeding variables, together with any subsequent variables, that causes a variable has no consistent solution.\n",
              "\n",
              "\n",
              "Constraint learning finds a minimum set of variables from the conflict set that causes the problem.  This set of variables along with their corresponding values are no-good.  Record the no-good.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Local search algorithms turn out to be very effective in solving many CSPs.\n",
              "USing complete stat formulation where each state assigns a value to every varialbe, and then changes the value of one variable at a time.\n",
              "The min-conflicts heuristic, which selects the value that results in the minimum number of conflicts with other variables.\n",
              "\n",
              "\n",
              "Constraint weighting concentrates the search on the important constraints.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Independent subproblems.  Finding connected components of the constraint graph can help identify independence.\n",
              "Each subproblem has c(a constant) variables from the total n varialbes. There are n/c subproblems, and each takes $O(d^c)$ to solve.  Total work is $O(d^c n/c)$ which is linear in n.\n",
              "Without decomposition, it is $O(d^n)$.\n",
              "\n",
              "\n",
              "Directional arc onsistency (DAC): A CSP is DAC under an ordering of variables $X_1, X_2, ..., X_n$ if and only if every $X_i$ is arc-consistent with each $X_j$ for j>i.\n",
              "\n",
              "\n",
              "Topological sort.  Make it directional arc consistent in n steps (n-1 edges for the tree), comparing up to d possible domain values for two variables, for a total time of $O(nd^2)$.\n",
              "Once having a directed arc-consistent graph, march down the list of variables and choosse any remaining vlue.\n",
              "Efficent algorithm for trees, try to reduce more general constraint graph to trees.\n",
              "\n",
              "\n",
              "Cuset conditioning reduce a constraint graph to a tree by removing nodes.  Choose a subset S such that the constraint graph becomes a tree after removing S.  S is a cycle cutset.\n",
              "For each possible assignment to the variables in S that satisfies all constraints on S, remove any value that are inconsistent with the assignment(for S) from the domains of the remaining variables(on the tree).  \n",
              "If there is a solution to the remaining part of the CSP, return it with the assignment for S.  If the cycle cutset has size c, the total run time is $O(d^c(n-c)d^2)$.\n",
              "\n",
              "\n",
              "Tree decomposition: transformation of a constraint graph into a tree.\n",
              "\n",
              " \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " Solutions to CSPs can be found by a general purpose algorithm.\n",
              "\n",
              "CSPs may have discrete variables with finite domains or infinite domains.  They may have continuous variables.\n",
              "\n",
              "\n",
              "Search for CSPs only need to consider assignments to a single variable at each node, hence b=d and there are $d^n$ leaves.\n",
              "Backtracking search is DFS for CSPs with single-variable assignments.\n",
              "\n",
              "\n",
              "With following heuristics, backtracking search can gain big efficiency.\n",
              "choosing the most constrainted variable for assignment,\n",
              "choosing the most constraining variable for tie breaker of most constrainted variable,\n",
              "choosing the least constraining value,\n",
              "forward checking.\n",
              "\n",
              "CSP solvers combine search and constraint propagation (inference).\n",
              "\n",
              "Constraint graph with nodes as variables and edges as constraints.\n",
              "\n",
              "\n",
              "AC-3 complexity: total numbers of arcs is 2*n*(n-1) = $O(n^2)$\n",
              "checking an arc takes $O(d^2)$ time, for maximum d values in any domain.\n",
              "each arc can only be inserted into the queue d times.\n",
              "Total time complexity $O(n^2d^3)$.\n",
              "A pair of variable $X_i,X_j$ is path-consistent with $X_m$ if for every assignment $X_i =a, X_j=b$ that is consistent with constraint of $x_i, X_j$, \n",
              "there is a value for $X_m$ in its domain such that both $X_i, X_m$ and $X_j, X_m$ are consistent with their repective constraints.\n",
              "\n",
              "Constraint graph that is a tree can be solved efficiently (linear time to n the number of variables).  Do a topological sort adn march down the list.\n",
              "Cycle cutset algorithm $O(d^{c+2}(n-c))$\n",
              "\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 88,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" The central component of a knowledge-based agent is its knowledge base (KB), which is a set of sentences (not identical to the sentences of English and other natural languages).  \n",
        "\n",
        "Each sentence represents some assertion about the world and is expressed in a knowledge representation language.\n",
        "\n",
        "\n",
        "When the sentence is taken as being given without being derived from other sentences, it is an axiom.\n",
        "\n",
        "\n",
        "Both operations to add new sentences to the KB and to query what is known may involve inference, which is deriving new sentences from existing ones.  \n",
        "\n",
        "A KB may initially contain some background knowledge.\n",
        "\n",
        "\n",
        "Declarative approach vs procedural approach.  Declarative approach starts with an empty KB, and TELL sentences one by one until the agent knows how to operate in its environment.  \n",
        "\n",
        "\n",
        "Procedural approach encodes desired behaviors directly as program code.  Successful agent often combines both.\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" Performance measure, Environment, Actuators, Sensors. \"\"\"\n",
        "chapter7_3 = \"\"\" A logic must define the semantics, or meaning, of sentences.  The semantics defines the truth of each sentence with respect to each possible world.  \n",
        "\n",
        "\n",
        "To be precise, use the term model in stead of “possible world”.  Models are mathematical abstractions, each of which has a fixed truth value for every relevant sentence.  \n",
        "\n",
        "\n",
        "If a sentence α is true in model m, m satisfies α or m is a model of α.  M(α) means the set of all models of α.\n",
        "\n",
        "\n",
        "A sentence follows logically from another sentence. α entails β.  α |= β iif M(α) is subset of M(β). \n",
        "\n",
        " Note that if α|= β, then α is a stronger assertion than β, and it rules more possible worlds.\n",
        "\n",
        "\n",
        "Model checking:  an inference algorithm that enumerates all possible models to check if α is true in all models in which KB is true.\n",
        "\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\"  Atomic sentences consist of a single proposition symbol.  \n",
        "\n",
        "Complex sentences ae constructed from simper sentences, using parentheses and operators (logic connectives): \n",
        "\n",
        "negation, \n",
        "\n",
        "and (conjunction), \n",
        "\n",
        "or (disjunction), \n",
        "\n",
        "implies (an implication from premise or antecedent to conclusion or consequence.  They are also known as rules or if-then statements.)  \n",
        "\n",
        "If and only if (biconditional).\n",
        "\n",
        "\n",
        "Propositional entailment algorithm (model checking)’s time complexity is $O(2^n)$ since there are $2^n$ models, and space complexity is only O(n) as the enumeration is depth-first.\n",
        "\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" Entailment can be done by theorem proving, applying rules of inference directly to the sentences in KB to construct a proof of the desired sentence without consulting models.  \n",
        "If the number of models is large but the length of the proof is short, then theorem proving can be more efficient than model checking.\n",
        "\n",
        "Deduction, α|= β iif α => β.\n",
        "\n",
        "α|= β  iif (α ^ ¬β) is unsatisfiable (contradiction by showing that assumes a sentence β to be false and leads to a contradiction with known axioms α)\n",
        "\n",
        "\n",
        "Inference rules:\n",
        "Modus Ponens $(α=> β, α)/ β$, whenever sentences of the form α=> β and α are given, the sentence β can be inferred.\n",
        "And_Elimination:   α ^ β / α,  from a conjunction, any of the conjuncts can be inferred.\n",
        "\n",
        "Searching for proofs is an alternative to enumerating models.  In many practical cases finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how man of them there are.\n",
        "\n",
        "\n",
        "Monotonicity, the set of entailed sentences can only increases information is added to the KB. For any sentences α and β, if KB|= α then KB^β |= α.\n",
        "\n",
        "\n",
        "Unit resolution rule takes a clause (a disjunction of literals) and a literal (which is a complementary literal to some literal in the clause) and produces a new clause.\n",
        "\n",
        "\n",
        "Full resolution rule, generalized from the unit resolution rule, takes two clauses and produces a new clause containing all the literals of the two original clauses except the two complementary literals.\n",
        "Resolve ONLY one pair of complementary literals at a time.\n",
        "\n",
        "\n",
        "A sentence expressed as a conjunction of clauses is in conjunctive normal form (CNF)\n",
        "\n",
        "\n",
        "Definite clause is a disjunction of literals of which exactly one is positive.\n",
        "Horn clause is a disjunction of literals of which at most one is positive.\n",
        "Horn clause is closed under resolution, meaning if you resolve two Horn clauses, you get back a Horn clause.  \n",
        "K-CNF sentence is a CNF sentence where each clause has at most k literals.\n",
        "\n",
        "\n",
        "KB containing only definite clauses are interesting for three reasons:\n",
        "1.\tEvery definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal.  \n",
        "In Horn form, the premise is called the body and the conclusion is called the head.  A sentence consisting of a single positive literal is called a fact.\n",
        "\n",
        "2.\tInference with Horn clause can be efficiently done by forward chaining and backward chaining algorithms.\n",
        "\n",
        "3.\tDeciding entailment with Horn clauses can be done in linear time. \n",
        "\n",
        "Forward chaining is data-directed reasoning.  Backward chaining is goal-directed reasoning.  The cost of backward-chaining is much less than linear in the size of the KB, since the process touches only relevant facts.\n",
        "\n",
        "\n",
        "Many combinational problems in computer science can be reduced to checking the satisfiability of a propositional sentence.\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" There are two kinds of sentences: axioms and derived sentences.  Axioms is a given sentence.  \n",
        "Inference is the process of deriving new sentences from old sentences. \n",
        "\n",
        "Wampa world is deterministic, discrete, static, single-agent, sequential and partically observable.\n",
        "\n",
        "Entailment can be used to derive conclusion, and that is the process of logical inference.\n",
        "\n",
        "An inference algorithm i allows us to conclude that α is true, α is derived from KB by i. KB $⊢_i$ 𝛂.\n",
        "\n",
        "Quality of inference algorithm we seek: sound and complete.\n",
        "\n",
        "Resolution yields a complete inference algorithm.\n",
        "\n",
        "Resolution algorithm shows that KB ⋀ ¬𝛂 is unsatifiable in order to prove KB |= 𝛂.  (proof by contradiction)\n",
        "Steps: convert KB ⋀ ¬𝛂 into CNF (conjuctive normal form); apply the resolution rule to the resulting clauses; resolve every pair that contains complementary literals to produce a new clause;\n",
        "if the new clause is not present, then add it to the set; continue the process until either of the two:\n",
        "   1. there are no new clauses that can be added. KB does not entail 𝛂.\n",
        "   2. Two clauses resolve to be the empty clause, KB does entail 𝛂.\n",
        "\n",
        "Every definite clause can be written as implication whose premise is a conjunction of positive literals and conclusion is a positive literal.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Implication elimination\" : \"(𝛂 ⟹ β) ≡ (¬𝛂 ⋁ β)\",  \n",
        "\"Distributivity of ⋀ over ⋁\" : \"((𝛂 ⋀ β) ⋁ ɣ) ≡ ((𝛂 ⋀ β) ⋁ (𝛂 ⋀ ɣ))) \",\n",
        "\"Distributivity of ⋁ over ⋀ \":\"((𝛂 ⋁ β) ⋀ ɣ) ≡ ((𝛂 ⋁ β) ⋀ (𝛂 ⋁ ɣ))) \",\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 89,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "ec401655-834a-496c-9208-cc6af6864150"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " The central component of a knowledge-based agent is its knowledge base (KB), which is a set of sentences (not identical to the sentences of English and other natural languages).  \n",
              "\n",
              "Each sentence represents some assertion about the world and is expressed in a knowledge representation language.\n",
              "\n",
              "\n",
              "When the sentence is taken as being given without being derived from other sentences, it is an axiom.\n",
              "\n",
              "\n",
              "Both operations to add new sentences to the KB and to query what is known may involve inference, which is deriving new sentences from existing ones.  \n",
              "\n",
              "A KB may initially contain some background knowledge.\n",
              "\n",
              "\n",
              "Declarative approach vs procedural approach.  Declarative approach starts with an empty KB, and TELL sentences one by one until the agent knows how to operate in its environment.  \n",
              "\n",
              "\n",
              "Procedural approach encodes desired behaviors directly as program code.  Successful agent often combines both.\n",
              " \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Performance measure, Environment, Actuators, Sensors. \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " A logic must define the semantics, or meaning, of sentences.  The semantics defines the truth of each sentence with respect to each possible world.  \n",
              "\n",
              "\n",
              "To be precise, use the term model in stead of “possible world”.  Models are mathematical abstractions, each of which has a fixed truth value for every relevant sentence.  \n",
              "\n",
              "\n",
              "If a sentence α is true in model m, m satisfies α or m is a model of α.  M(α) means the set of all models of α.\n",
              "\n",
              "\n",
              "A sentence follows logically from another sentence. α entails β.  α |= β iif M(α) is subset of M(β). \n",
              "\n",
              " Note that if α|= β, then α is a stronger assertion than β, and it rules more possible worlds.\n",
              "\n",
              "\n",
              "Model checking:  an inference algorithm that enumerates all possible models to check if α is true in all models in which KB is true.\n",
              "\n",
              " \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "  Atomic sentences consist of a single proposition symbol.  \n",
              "\n",
              "Complex sentences ae constructed from simper sentences, using parentheses and operators (logic connectives): \n",
              "\n",
              "negation, \n",
              "\n",
              "and (conjunction), \n",
              "\n",
              "or (disjunction), \n",
              "\n",
              "implies (an implication from premise or antecedent to conclusion or consequence.  They are also known as rules or if-then statements.)  \n",
              "\n",
              "If and only if (biconditional).\n",
              "\n",
              "\n",
              "Propositional entailment algorithm (model checking)’s time complexity is $O(2^n)$ since there are $2^n$ models, and space complexity is only O(n) as the enumeration is depth-first.\n",
              "\n",
              " \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " Entailment can be done by theorem proving, applying rules of inference directly to the sentences in KB to construct a proof of the desired sentence without consulting models.  \n",
              "If the number of models is large but the length of the proof is short, then theorem proving can be more efficient than model checking.\n",
              "\n",
              "Deduction, α|= β iif α => β.\n",
              "\n",
              "α|= β  iif (α ^ ¬β) is unsatisfiable (contradiction by showing that assumes a sentence β to be false and leads to a contradiction with known axioms α)\n",
              "\n",
              "\n",
              "Inference rules:\n",
              "Modus Ponens $(α=> β, α)/ β$, whenever sentences of the form α=> β and α are given, the sentence β can be inferred.\n",
              "And_Elimination:   α ^ β / α,  from a conjunction, any of the conjuncts can be inferred.\n",
              "\n",
              "Searching for proofs is an alternative to enumerating models.  In many practical cases finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how man of them there are.\n",
              "\n",
              "\n",
              "Monotonicity, the set of entailed sentences can only increases information is added to the KB. For any sentences α and β, if KB|= α then KB^β |= α.\n",
              "\n",
              "\n",
              "Unit resolution rule takes a clause (a disjunction of literals) and a literal (which is a complementary literal to some literal in the clause) and produces a new clause.\n",
              "\n",
              "\n",
              "Full resolution rule, generalized from the unit resolution rule, takes two clauses and produces a new clause containing all the literals of the two original clauses except the two complementary literals.\n",
              "Resolve ONLY one pair of complementary literals at a time.\n",
              "\n",
              "\n",
              "A sentence expressed as a conjunction of clauses is in conjunctive normal form (CNF)\n",
              "\n",
              "\n",
              "Definite clause is a disjunction of literals of which exactly one is positive.\n",
              "Horn clause is a disjunction of literals of which at most one is positive.\n",
              "Horn clause is closed under resolution, meaning if you resolve two Horn clauses, you get back a Horn clause.  \n",
              "K-CNF sentence is a CNF sentence where each clause has at most k literals.\n",
              "\n",
              "\n",
              "KB containing only definite clauses are interesting for three reasons:\n",
              "1.\tEvery definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal.  \n",
              "In Horn form, the premise is called the body and the conclusion is called the head.  A sentence consisting of a single positive literal is called a fact.\n",
              "\n",
              "2.\tInference with Horn clause can be efficiently done by forward chaining and backward chaining algorithms.\n",
              "\n",
              "3.\tDeciding entailment with Horn clauses can be done in linear time. \n",
              "\n",
              "Forward chaining is data-directed reasoning.  Backward chaining is goal-directed reasoning.  The cost of backward-chaining is much less than linear in the size of the KB, since the process touches only relevant facts.\n",
              "\n",
              "\n",
              "Many combinational problems in computer science can be reduced to checking the satisfiability of a propositional sentence.\n",
              " \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " There are two kinds of sentences: axioms and derived sentences.  Axioms is a given sentence.  \n",
              "Inference is the process of deriving new sentences from old sentences. \n",
              "\n",
              "Wampa world is deterministic, discrete, static, single-agent, sequential and partically observable.\n",
              "\n",
              "Entailment can be used to derive conclusion, and that is the process of logical inference.\n",
              "\n",
              "An inference algorithm i allows us to conclude that α is true, α is derived from KB by i. KB $⊢_i$ 𝛂.\n",
              "\n",
              "Quality of inference algorithm we seek: sound and complete.\n",
              "\n",
              "Resolution yields a complete inference algorithm.\n",
              "\n",
              "Resolution algorithm shows that KB ⋀ ¬𝛂 is unsatifiable in order to prove KB |= 𝛂.  (proof by contradiction)\n",
              "Steps: convert KB ⋀ ¬𝛂 into CNF (conjuctive normal form); apply the resolution rule to the resulting clauses; resolve every pair that contains complementary literals to produce a new clause;\n",
              "if the new clause is not present, then add it to the set; continue the process until either of the two:\n",
              "   1. there are no new clauses that can be added. KB does not entail 𝛂.\n",
              "   2. Two clauses resolve to be the empty clause, KB does entail 𝛂.\n",
              "\n",
              "Every definite clause can be written as implication whose premise is a conjunction of positive literals and conclusion is a positive literal.\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Implication elimination** - (𝛂 ⟹ β) ≡ (¬𝛂 ⋁ β)\n",
              "* **Distributivity of ⋀ over ⋁** - ((𝛂 ⋀ β) ⋁ ɣ) ≡ ((𝛂 ⋀ β) ⋁ (𝛂 ⋀ ɣ))) \n",
              "* **Distributivity of ⋁ over ⋀ ** - ((𝛂 ⋁ β) ⋀ ɣ) ≡ ((𝛂 ⋁ β) ⋀ (𝛂 ⋁ ɣ))) \n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 90,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "b3c4c5ad-e5d9-4477-8467-1e683b037f1a"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - your definitions here\n",
              "* **Other concept** - your definitions here\n",
              "* **Etc.** - your definitions here\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " No function overloading as in Java.  Python functions can have default values.\n",
              "\n",
              "Keyword arguments:  functions can be called with arguments out of order.  Keyword arguments are used after positional arguments.\n",
              "\n",
              "Dynamic scope: functions use most recent value assigned to a variable.\n",
              "\n",
              "Default arguements and memorization: default parameter values are evalued only at the first time when the function is called.\n",
              "\n",
              "Functions are \"first order\" objects\", which are entities that can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables.\n",
              "\n",
              "Creating a calls.\n",
              "\n",
              "Class class_name:\n",
              "\n",
              "    attribute = ..\n",
              "\n",
              "    def __init__(self, arg1, ...):\n",
              "      ...\n",
              "\n",
              "\"__init__\" constructor is called when an object is instantiated.\n",
              "\n",
              "Other special build-in methods:\n",
              "\"__str__, __len__, __cmp__, __copy__, __add__, __neg__\"\n",
              "\n",
              "Generators are iterators.\n",
              "\"yield\" to create generators.\n",
              "Benefits of generators:\n",
              "    less code than a standard iterator\n",
              "    maintain local state automatically\n",
              "    values are computed one at a time, as they are needed\n",
              "    avoids storing the entire sequence in memory\n",
              "    good for aggregating(summing, counting) items, only one pass.\n",
              "    crucial for infinite sequences\n",
              "bad if inspection of individual values are needed.\n",
              "\n",
              "enumerate(iterable, start =0)\n",
              "\n",
              " \n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Search\n",
              "A search problem can be defined formally as:\n",
              "A set of possible states – state space.\n",
              "The initial state\n",
              "A set of one or more goal states\n",
              "The actions available.  Given a state Actions(s) returns a finite set of actions\n",
              "A transition model describes what each action does.  Result(s, a) returns the resulting state.\n",
              "An action cost function: Action-Cost(s,a,s’)\n",
              "\n",
              "A sequence of actions forma a path, and a solution is a path from the initial state to a goal state.\n",
              "Assuming the action costs are additive.  An optimal solution has the lowest path cost among all solutions.\n",
              "The state space can be represented by a graph, in which vertices are states and directed edges are actions\n",
              "\n",
              "The formulation of the problem is a model, an abstract mathematical description.\n",
              "Abstraction, the process of removing detail from a representation.\n",
              "\n",
              " \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Standardized problem is intended to illustrate or exercise various problem -solving methods.  Real-world problem is one whose solutions people actually use and whose formulation is idiosyncratic.\n",
              "Standardized: \n",
              "a grid world problem is a two-dimensional rectangular array of square cells.\n",
              "\n",
              "Sokoban puzzle, the agent is to push a number of boxes, scattered about the grid, to designated storage locations. (at most one box per cell)\n",
              "\n",
              "Sliding tile puzzle including 8-puzzle\n",
              "\n",
              "Donald Knuth problem has infinite states \n",
              "States: positive real numbers\n",
              "Initial state: 4\n",
              "Actions: apply square root, floor, or factorial operation (factorial for integers only)\n",
              "Transition model: as given by the mathematical definition of the operations\n",
              "Goal state: the desired positive integer\n",
              "Action cost: each action costs 1\n",
              "\n",
              "Infinite state space arise frequently in tasks involving the generation of mathematical expressions, circuits, proofs, programs and other recurrsively defined objects.\n",
              "Real-world problems\n",
              "\n",
              "Route-finding problem, Touring problem, the traveling salesperson problem(TSP)\n",
              " \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " A Search Algorithm takes a search problem as input and returns a solution or an indication of failure.\n",
              "\n",
              "Search Tree. \n",
              "Each node corresponds to a state in the state space and the edges correspond to actions.The root corresponds to the initial state.\n",
              "Frontier is a set of unexpanded nodes.  Any state that has had a node generated for it has been REACHED (whether or not that node has been expanded).\n",
              "Frontier separates the interior region where every state has been  expanded, and the exterior region of states that have not yet been reached.\n",
              "\n",
              "Best-first search\n",
              "Choose a node, n, from the frontier, with minimum value of some evaluation function, f(n), to expand next.\n",
              "Search algorithms require Search Data Structures to keep track of the search tree.  A node is represented by a data structure with four components:\n",
              "The state that the node corresponds; \n",
              "the parent node; \n",
              "the action that was applied to the parent’s state to generate this node; \n",
              "Path-cost as the total cost of the path from the initial sate to this node.\n",
              "\n",
              "Data structure to store the frontier is a queue of some kind. \n",
              "Priority queue first pops the node with the minimum cost according to some evaluation function, f.  used in best-first search.\n",
              "FIFO queue that pops the node added to the queue first is used in BFS.\n",
              "LIFO queue (or a stack) that pops the most recently added node is used in DFS.\n",
              "\n",
              "The reached states can be stored as a lookup table(hash table) where each key is a state and each value is the node for that state.\n",
              "A repeated state in the search tree is generated by a cycle, which is a special case of a redundant path. \n",
              "Three approaches to eliminate redundant paths.  \n",
              "First, remember all previously reached states, appropriate for state spaces with many redundant paths, preferred choice when the table of reached states will fit in memory.\n",
              "Second, it is impossible or rare for two paths to reach the same state for some problems such as an assembly problem. Don’t track reached states to save memory and don’t check for redundant paths.  \n",
              "A search algorithm is a graph search if it checks for redundant paths, and a tree-like search if it does not.\n",
              "Third, compromise and check for cycles but not for redundant paths.  \n",
              "\n",
              "Measure search algorithms’ performance in four ways: completeness, cost optimality, time complexity and space complexity.  \n",
              "\n",
              "To be complete, a search algorithm must be systematic in the way it explores an infinite state space. \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "BFS is a systematic search strategy that is complete (even on infinite state spaces).  Early goal test, checking if a node is a solution when it is generated, \n",
              "rather than the late goal test used by best-first search, waiting until a node is popped off the queue.\n",
              "\n",
              "BFS is cost-optimal for problems with same cost for all actions, but not for problems without that property.  It is complete in either case.\n",
              "It is exponential-complexity for both time and space.  \n",
              "Uninformed search can solve only the samllest instances of exponential-complexity search problems,\n",
              "\n",
              "Dijkastra’s algorithm or uniform-cost search (misleading name).  \n",
              "Implemented as a call to best-first search with Path-Cost as the evaluation function.  \n",
              "$O(b^{1+\\lfloor C^*/e \rfloor})$, $C^*$: the optimal solution’s cost, e: lower bound on the cost of each action.  \n",
              "When all action costs are equal, $b^{1+\\lfloor C*/e \rfloor}$ is just $b^{(d+1)}$, and uniform-cost search is similar to BFS.\n",
              "\n",
              "DFS is not cost optimal, returning the first solution it finds. For finite state spaces that are trees DFS is efficient and complete.  \n",
              "For acyclic state spaces it will systematically explore the entire space.\n",
              "In cyclic state spaces it can get stuck in an infinite loop.  In infinite state spaces, it is not systematic and incomplete.\n",
              "\n",
              "DFS is used for problems where a tree-like search is feasible, has much smaller needs for memory.  \n",
              "The frontier in BFS is like the surface of an ever-expanding sphere, while the frontier in DFS is just a radius of the sphere.  \n",
              "\n",
              "Depth-first tree-like search has been adopted as the basic workhorse of many areas of AI including constraint satisfaction, propositional satisfiability and logic programming.\n",
              "\n",
              "Backtracking search is a variant of DFS, using even less memory.  It generates one successor at a time; each partially expanded node remembers which successor to generate next.  \n",
              "In addition, successors are generated by modifying the current state rather than allocating memory to new state.  \n",
              "This reduces the memory requirements to just one state description and a path of O(m) actions.\n",
              "\n",
              "Depth limited search, with a depth limit, l, and treat all nodes at depth l as if they had no successors. \n",
              "\n",
              "Iterative deepening search tries different depth values until either a solution is found or returning a failure. It combines many benefits of DFS and BFS.  \n",
              "Memory requirements are modest, O(bd) (solution) or O(bm) (no solution in finite state spaces).  \n",
              "Like BFS, it is optimal for problems with same cost for all actions, and is complete on finite acyclic state spaces, or on any finite state space when we check nodes for cycles all the way up the path.\n",
              "In general, it is preferred when the search state space is too large to fit in memory and the depth of the solution is unknown.\n",
              "\n",
              "Bidirectional search, simultaneously searches forward from the initial state and backwards from the goal state.  $b^(d/2) +b^(d/2)$ is much less than $b^d$.\n",
              " \n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " A problem-solving agent needs to plan ahead.  The computational process it undertakes is called search.\n",
              "The agent will consider a sequence of actions that form a path to a goal state, and such a sequence is called a solution.\n",
              "\n",
              "In an environment that is fully obersable, deterministic and known, the solution is a fixed sequence of actions.\n",
              "\n",
              "In a partially observable or nonderterministic environment, the solution must recommend different future actions depending on the percepts it receives.  Branching strategy.\n",
              "\n",
              "Tree search is a generalizaed algorithm to solve search problems.  It enumerates in some order all possible path from the initial state.\n",
              "It searches through explicit tree generation: root is the initial state, nodes in search tree generated through transition model. Different paths to the same node are distinct. \n",
              "\n",
              "BFS idea: expand the shallowest unexpanded nodes. Frontier is a FIFO queue.\n",
              "\n",
              "BFS is complete if b is finie, time complexity is $O(b^d)$. Its space complexity is $O(b^d)$ too and is a big problem.  It is optimal if cost =1 per step.  Ohterwise not optimal.\n",
              "Exponential space and time complexity.\n",
              "\n",
              "DFS idea: expand the deepest unexpanded node.  Frontier is a LIFO queue.\n",
              "DFS is incomplete in infinite-depth spaces, space with loops.  It is complete in finite spaces.  Its time complexity is $O(b^m)$, m is maximum depth of state space.\n",
              "If m > d, DFS is worse than BFS.  But if solustions are dense, DFS is faster than BFS.\n",
              "\n",
              "DFS' space complexity is $O(b*m) - linear space!\n",
              "It is not optimal.\n",
              "\n",
              "Use DFS if space is restricted, or many possible solutions with long paths and wrong paths are terminated quickly, or search can be fine-tuned quickly\n",
              "Use BFS if there are possible infinite paths, or some solutions have short paths, or can quickly discard unlikely paths.\n",
              "\n",
              "Depth limit DFS time complexity $O(b^l)$ and space complexity $O(bl)$\n",
              "Iterative deepening search uses depth-limit search as subroutine with increasing l.  It is complete and optimal as goal is always found at d the depth of the shallowest goal-node.\n",
              "Time complexity is $O(b^d)$. Space complexity is $O(bd)$.\n",
              "\n",
              "Both BFS and Iterative deepening search are complete and optimal.  Others are not.\n",
              "\n",
              "Inoformed Search uses domain-specifi information about hte location of the goals in order to find a solution more efficiently.\n",
              " \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **State space** - the set of states reachable from initial state by taking some sequence of actions\n",
              "* **Frontier** - states that are avaible for expaning\n",
              "* **Path** - sequence of actions leading from one state to another state\n",
              "* **B** - maximum branching factor of search tree\n",
              "* **D** - depth of the shallowest goal node\n",
              "\n",
              "\n",
              "## WARNING: Your definition of 'consistent heuristic' is too long!\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " Informed search uses domain specific hints about the location of the goals to find solution more efficiently.\n",
              "The hints come in the form of a heuristic function $h(n)$ = estimated cost of the cheapest path from the state at node n to a goal state.\n",
              "\n",
              "\n",
              "Greedy best-first search expands first the node with the lowest $h(n)$ value, which appears to be closet to the goal.  Evaluation function $f(n) = h(n)$.\n",
              "It is complete in finite state spaces, but not in infinite spaces.  The worst case time and space complexity is $O(|V|)$.  \n",
              "With good heuristic functions, the complexity can be reduced substantially, with some approaching $O(bm)$.\n",
              "\n",
              "\n",
              "A* search is a best-frist search that uses the evaluation function $f(n) = g(n) + h(n)$. $g(n)$ is the path cost from initial state to node n.\n",
              "An admissible heuristic is one that never overestimates the cost to reach a goal.\n",
              "A* is cost optimal with admissible heuristic.\n",
              "\n",
              "A heuristic $h(n)$ is consistent if for every node n and every successor n' of n generated by an action a, $h(n) \\leq c(n,a,n')+h(n')$.\n",
              "Triangle inequality, $h(n)$ is the side from n to G(goal).\n",
              "Every consistent (stronger property) heuristic is admissible (but not vice versa).  With a consistent heuristic, a state is on the optimal path when it is reached for the first time.\n",
              "\n",
              "\n",
              "Search contour of A* with a good heuristic fans out from the start node, streching toward a goal state and become more narrowly focused around an optimal path.\n",
              "The contours of uniform-cost search will be \"circular\" around the start state, spreading out equally in all directions.\n",
              "\n",
              "\n",
              "A* is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.\n",
              "A* expands many nodes, if we are willing to accept suboptimal solutions, or satisficing solutions that are \"good enough\", a search can be more efficient by expanding fewer nodes.\n",
              "Using inadmissible heuristic that may overestimate risk missing the optimal.\n",
              "Weighted A* search weights the heuristic value more heavily by $f(n) = g(n) + W*h(n)$ for $w >1$.\n",
              "Weighted A* is a little \"greedy\" since it weights more on the search towards a goal.  It wont ignore the path cost completely.\n",
              "\n",
              "\n",
              "Beam search is one of the memory-bound strategies.  It keeps only the $k$ nodes with the best $f$ scores.  It is incomplete and suboptimal.\n",
              "It limits the size of the frontier.  Choosing $k$ to make good use of available memory.  \n",
              "  \n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " effective branching factor b* is used to characterize the quality of a heuristic. \n",
              "\n",
              "If the A* search expands N nodes and the solution depth is d, b* is the branching factor that a uniform tree of depth d would have to have to contain N+1 nodes.\n",
              "$N+1 = 1+b^*+ (b^*)^2+...+(b^*)^d$.  A good heuristic would have b* close to 1.\n",
              "\n",
              "\n",
              "If $h_2(n) \\geq h_1(n)$, $h_2$ dominates $h_1$. Generally it is better to use a heuristic function with higher values.\n",
              "\n",
              "\n",
              "A problem with fewer restrictions is called a relaxed problem.  The state-space graph of a relaxed problem is a supergraph of the original state space because the removal of restrictions creates added edges in the graph.\n",
              "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.  Hence, generating heuristics from relaxed problems.\n",
              "\n",
              "\n",
              "Generating heuristics from subproblems: pattern databases.  Deriving admissible heuristics from the solution cost of a subproblem of the original problem.\n",
              "Disjoint pattern databases.\n",
              "Generating heuristics with landmarks works well in route-finding problems.  Differential heuristic takes the difference between the cost from start node to the landmark and the cost from the landmark to the goal. \n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Uniform cost search is a search algorithm tranversing or searching a weighted tree, tree structure or graph.\n",
              "\n",
              "Uniform-cost search extends best-first search, alway expanding node with the lowest path cost.  The frontier is a priority queue.\n",
              "Unlike BFS, which checks if a node is a goal state before adding it to the frontier/queue, UCS enqueues the node and checks if the node is goal when selecting it for expansion.\n",
              "If a better path to the same state is found, it updates the node on the frontier.\n",
              "\n",
              "\n",
              "BFS explores equally in all directions while Uniform-cost search uses priority queue for its froniter and prefers to explore lowest-cost paths,\n",
              "resulting in \"cost contours\". \n",
              "\n",
              "Better idea: best-first search that expands node based an evaluation function $f(n)$, which includes estimated distance to goal.\n",
              "Heuristic function $h(n)$ takes a state n and return an estimate of the distance from n to goal.\n",
              "\n",
              "\n",
              "Greedy search replaces $g(n)$ in best-first search with $f(n) = h(n)$. Greedy search can stuck in loops and is incomplete.\n",
              "\n",
              "A* seach is the best known form of best-first search.  $f(n) = g(n) + h(n)$.  Heuristic is admissible if $h(n) \\leq h^*(n), h^*(n)$ is the actual cost.  $h(n) \\geq 0$.  If $h(n)$ is admissible, A* search is optimal.\n",
              "If two admissible heuristic $h_2(n) \\geq h_1(n)$ for all n, then $h_2$ dominates $h_1$.  $h_2$ is more accurate and thus better for the search.\n",
              "\n",
              "Consistent heuristics are always admissible.\n",
              "\n",
              "  \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Manhattan distance** - sum of the horizontal and vetical distance \n",
              "* **City-block distance** - Manhattan distance\n",
              "* **Consistent heuristic** - a heuristic function whose estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour.\n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " Competitive  environments, in which two or more agents have conflicting goals, giving rise to adversarial search problems.\n",
              "\n",
              "Deterministic, two-player, tern-taking, perfect information, zero-sum games.  \n",
              "\n",
              "\n",
              "A game can be formally defined with following elements:\n",
              "\n",
              "The initial state $S_0$.  \n",
              "Whose turn to move in a state S.  \n",
              "A set of legal moves/actions in sate S.  \n",
              "Transition model which defines the state resulting from taking action a in state S.  \n",
              "A terminal test (terminal states are where the game ends.)\n",
              "Utility function which defines the final numeric value to player p when the game ends in terminal state s.\n",
              "\n",
              "\n",
              "Game tree is a search tree that follows every sequence of moves all the way to a terminal state.  Maybe infinite if the state space is unbounded or the rules of the game allow for infinitely repeating positions.\n",
              " \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Ply, one move for one player bringing one level deeper in the game tree.\n",
              "\n",
              "Given a game tree, the optimal strategy can be determined by working out the minimax value of each state in the tree.   Assuming both players play optimally from there to the end of the game, the minimax value is the utility (for Max) of being in that state,.  In a non-terminal state, MAX prefers to move to a state of maximum value when it is MAX’s turn, and MIN prefers a state of minimum value.\n",
              "\n",
              "\n",
              "The minimax algorithm performs a complete depth-first exploration of the game tree.  The time complexity is O(b^m), and the space complexity is O(bm) for an algorithm that generates all actions at once, or O(m) for an algorithm that generates actions one at a time.  The exponential complexity makes MINIMAX impractical for complex games.\n",
              "\n",
              "\n",
              "Optimal decisions in multiplayer games\n",
              "First, replacing the single value for each node with a vector of values.  Utility function returns a vector of utilities.  This vector gives the utility of the state from each player’s viewpoint.  For nonterminal states, in general, the backed-up value of a node n is the utility vector of the successor state with the highest value for the player choosing at n.\n",
              "\n",
              "\n",
              "Alpha-Beta pruning\n",
              "\n",
              "α = the value of the best (highest- value) choice found so far at any choice point along the path for MAX “at least”\n",
              "β = the value of the best (lowest-value) choice found so far at any choice point along the path for MIN “at most”\n",
              "\n",
              "\n",
              "Alpha-beta search updates the values of α and β as it goes along and prunes the remaining branches at a node as soon as the value of the current node is know to be worse than the current α  or β value for MAX or MIN, respectively.\n",
              "\n",
              "\n",
              "Move ordering\n",
              "\n",
              "The effectiveness of alpha-beta pruning is highly dependent on the order in which the states are examined.  \n",
              "If ordering the successors perfectly, alpha-beta would need to examine only $O(b^{m/2})$ nodes to pick the best move.  With random move ordering, it would be $O(b^{3m/4})$ for moderate b. \n",
              "\n",
              "\n",
              "Adding dynamic move-ordering schemes, trying the moves that were found to be best in the past. The past could be the previous move or from previous exploration of the current move through iterative deepening.  The killer move heuristic tries killer moves first.\n",
              "\n",
              "\n",
              "Transpositions: different permutations of the move sequence that end up in the same position, and this problem can be addressed with a transposition table that catches the heuristic value of states. \n",
              "\n",
              "\n",
              "Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth.  It explores a wide but shallow portion of the tree.  \n",
              "Type B strategy ignores moves that look bad, and follows promising lines “as far as possible”. It explores a deep but narrow portion of the tree.\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Apply a heuristic evaluation function to states and cut off the search early. Replacing the utility function with EVAL, which estimates a state's utility.\n",
              "Also replacing terminal test with cutoff test, which returns true at terminal states but otherwise determines weather to cut off the search based on depth and any other property it chooses to consider.\n",
              "\n",
              "\n",
              "Weighted linear function\n",
              "In chess, weights are based on human experience.  If such kind of experience is not available, machine learning techniques can estimate the weights of the evaluation function.\n",
              "\n",
              "\n",
              "Cutoff test replaces terminal test: \n",
              "if game.IS_CUTOFF(state, depth) then return game.EVAL(state, player), null\n",
              "IS_CUTOFF returns true for all depth greater than some fixed depth d and for all terminal states.  EVAL returns terminal val for terminal states.\n",
              "\n",
              "\n",
              "Quiescent: positions in which there is no pending  move (such as a capturing the queen) that would wildly swing the evaluation.  For nonquiescent positions the IS_CUTOFF returns false, and the search continues until quiescent positions are reached.\n",
              "\n",
              "\n",
              "Horizon effect, push obvious “loss” beyond cutoff horizon such that the search consider the moves are good even though leading to “loss” that beyond the horizon the search can see.\n",
              "One strategy to mitigate the horizon effect is to allow singular extensions, moves that are clearly better than all other moves in a given position, even when the search would normally be cut off at that point.\n",
              "\n",
              "\n",
              "Forward pruning prunes moves that appear to be poor, and it saves computation time at the risk of making an error. (this is a Type B stretey)\n",
              "Beam search is a type of forward pruning.\n",
              "\n",
              "\n",
              "The ProbCut or probabilistic cut algorithm is another type of forward pruning that uses statics gained from prior experience to reduce the chance of the best move being pruned.  Alph-beta prunes any node that is proved outside the current alpha-beta window.\n",
              "ProbCut prunes nodes that are probably outside the window.\n",
              "Another type of forward pruning is Late Move Reduction.  It assumes the move ordering is done well.  The moves apprearing later in possible moves is probably not good.  Instead of pruning them completely, do a limited depth search on the late moves.\n",
              "If the returned value is greater than current alpha, then redo the search to the full depth.\n",
              "\n",
              "\n",
              "Search versus lookup\n",
              "Many game playing programs use table lookup rather than search for the openning and ending of games.\n",
              " \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Go has a branching factor that starts at 361, which mean alpha-beta search would be limited to only 4 to 5 ply.  \n",
              "Second, it is difficult to define a good evaluation function for Go because material value is not a strong indicator, and most positions are in flux until the endgame.  \n",
              "Modern Go programs have abandoned alpha-beta search and instead use MCTS.\n",
              "\n",
              "\n",
              "Instead of using heuristic evaluation function for a state, MCTS estimates the value of a state with the average of utility over a number of simulations of complete games from that state.\n",
              "A simulation, a rollout, or a playout chooses moves until a terminal position is reached.  \n",
              "Playout policy biased the moves towards good ones is needed instead of choosing random moves.\n",
              "\n",
              "\n",
              "Conventional wisdom is that MCTS has advantage over alpha-beta in games such as Go where the branching factor is very high or in games that is difficult to define a good evaluation function.\n",
              "\n",
              "\n",
              "MC search can be applied to new games that has no prior experience to draw upon to define evaluation function.  MC search does not need more information as long as the rules are known.\n",
              "The selection and playout policy can be learned using neural networks trained by self-play alone.\n",
              "\n",
              "\n",
              "Stochastic games that include a random element are a little closer to the unpredictability of real life.\n",
              "Include chance nodes in addition to  Max an Min nodes. We can calculate expected value of a position, which is the average over all possible outcomes of the chance nodes, instead of having definite minimax values.\n",
              "That is expectiminimax value.\n",
              "\n",
              "\n",
              "Evaluation function must return values that are a positive linear transformation of the probability of winning (or of the expected utility).\n",
              "\n",
              "\n",
              "Expectiminimax's time complexity is $O(b^m n^m)$ vs minimax's $O(b^m)$, where n is the number of distinct rolls.\n",
              "\n",
              "\n",
              " \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Decision theory deals with choosing among actions based on how desirable is their immediate outcomes.\n",
              "\n",
              "Expected utility of an action is the average utility vlaue of the outcomes, weighted by the the probability of the respective outcome.\n",
              "\n",
              "Maximum expected utility (MEU) principle is that a rational agent chooses the action that maximizes the expected utility.\n",
              "\n",
              "There are other possible reasonable way to make decision such as minimizing the worst possible loss.\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Uncertain outcomes controlled by chance not adversary.\n",
              "Expectimax search: max nodes play just like in minimax; chance nodes replaces min nodes, with expected utilities as the weighted average of all possible children.\n",
              "\n",
              "Expectiminimax.  Environment is an extra \"random agent\".  Hence, max nodes followed by chance nodes, then followed by min nodes and chance nodes...\n",
              " \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " CSP uses a factored representation for each state: a set of variables, each of which has a value.  A problem is solved when each variable has a value that satisfies all the constraints on the variable.\n",
              "\n",
              "CSP search algorithms take advantage of the structure of states and use general rather than domain-specific heuristics to enable the solution of complex problems.  \n",
              "The main idea is to eliminate large portions of the search space by identifying variable/value combinations that violate the constraints.\n",
              "\n",
              "A CSP consists of:\n",
              "  X, a set of variables; \n",
              "  D, a set of domains, one for each variable; \n",
              "  and C, a set of constraints.  \n",
              "\n",
              "A domain $D_i$ consists of a set of allowable values {$v_1,…, v_k$} for variable $X_i$.  \n",
              "\n",
              "\n",
              "An assignment (of value to variable) that does not violate any constraints is called a consistent or legal assignment.  A complete assignment is one in which every variable is assigned a value.  \n",
              "A solution to a CSP is a consistent, complete assignment.\n",
              "\n",
              "\n",
              "To visualize a CSP as a constraint graph, where the nodes correspond to variables of the problem, and an edge connects any two variables that participate in a constraint.\n",
              "\n",
              "\n",
              "Reasons to formulate a problem as a CSP: \n",
              "a) a natural representation for a wide variety of problems.  \n",
              "B)CSP solvers are fast and efficient thanks to years of development.  \n",
              "C) a CSP solver can quickly prune large swathes of the search space that an atomic state-space searcher cannot.\n",
              "\n",
              "\n",
              "The simplest kind of CSP involves variables that have discrete, finite domains.  \n",
              "Types of constraints.  Unary, binary, higher order, global constraint (need not involve all the variables, but an arbitrary number of variables.), and cryptarithmetic puzzles.\n",
              "\n",
              "\n",
              "Every finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced.  (transform any CSP into one with only binary constraints)\n",
              "\n",
              "\n",
              "Preference constraints can often be encoded as costs on individual variable assignments.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " CSP algorithm can either generate successors by choosing a new variable assignment or do constraint propagation, which is a specific type of inference: using the constraints to reduce the number of legal values for a variable.  Constraint propagation may be intertwined with search or be done as a preprocessing.\n",
              "\n",
              "\n",
              "Local consistency: \n",
              "1. Node consistency.  \n",
              "2. Arc consistency.  A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints.  \n",
              "$X_i$ is arc-consistent with respect to another variable $X_j$ if for every value in the domain $D_i$ there is some value in the domain $D_j$ that satisfies the binary constraint on the arc (Xi, Xj).  \n",
              "A graph is arc-consistent if every variable is arc-consistent with every other variable.\n",
              "\n",
              "\n",
              "AC-3 maintains a queue of arcs, which initially contains all the arcs in the CSP (each binary constraint becomes two arcs). Pops off an arbitrary arc $(X_i, X_j)$ from the queue, and make Xi arc-consistent with Xj.  \n",
              "If $D_i$ is unchanged, moves on to the next arc.  If $D_i$ is revised (smaller), then add to the queue all arcs $(X_k, X_i)$ where $X_k$ is a neighbor of $X_i$.  \n",
              "If $D_i$ is revised down to nothing,  there is no solution.  Otherwise, keep checking until no more arc in the queue.\n",
              "\n",
              "AC-3 time complexity: $O(cd^3)$, for a CSP with n variables, each with domain size at most d, and with c  binary constraints (arcs).\n",
              "\n",
              "\n",
              "3. Path consistency.  It tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
              "4. K-consistency.  A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.  \n",
              "1-consistency is node consistency.  2-consistency is arc consistency.  For binary constraint graphs, 3-consistency is path consistency.\n",
              "\n",
              "\n",
              "Strongly k-consistent, if a CSP is k-consistent and also (k-1)-consistent, …, all the way to 1-consistent.  Then the problem is solved.  First, choose a consistent value for X1, then (guaranteed to be able) to choose a value for X2 … \n",
              "For each variable Xi, only need to search through the d values in the domain to find a value consistent with X1,…,Xi-1.  Run time is $O(n^2d)$.\n",
              "Any algorithm for establishing n-consistency must take time and space exponential in n in the worst case. \n",
              "\n",
              "\n",
              "A simple consistency procedure for a higher-order constraint is sometimes more effective than applying arc consistency to an equivalent set of binary constraints.\n",
              "For large resource-limited (Atmost) problems with integer values, domains are represented by upper and lower bounds and are managed by bounds propagation.  \n",
              "A CSP is bounds-consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Commutativity. The order of application of any given set of actions does not matter.  \n",
              "A CSP with n variables of domain size d would end up with a search tree where all the complete assignments (thus solutions) are leaf nodes at depth n.  \n",
              "The tree has $n!d^n$ leaves (branching factor is nd at top level, (n-1)d at next level...) but only $d^n$ possible complete assignments.\n",
              "\n",
              "\n",
              "Variable and value ordering.  \n",
              "Minimum-remaining-values (MRV) heuristic, also called the “most constrained variable” or “fail-first” heuristic.  \n",
              "The Degree Heuristic selects the variable that is involved in the largest number of constraints on other unassigned variables (most “constraining”).  \n",
              "Least constraining value heuristic prefers the value that rules out the fewest choices for the neighboring variables.  \n",
              "\n",
              "\n",
              "Variable selection shall be fail-first, but value selection be fail-last because every variable has to be assigned eventually.  So by choosing the ones that are likely to fail first, we will on average have fewer successful assignments to backtrack over.  For value ordering, the trick is that we only need one solution, hence, it makes sense to look for the mostly values first.\n",
              "Interleaving search and inference.\n",
              "\n",
              "\n",
              "Forward checking: when a variable X is assigned, establish arc consistency for it:  for every unassigned variable Y that is connected to X by a constraint, delete any value that is inconsistent with X from Y’s domain.\n",
              "Combining MRV heuristic with forward checking is more effective for many problems.\n",
              "\n",
              "\n",
              "Maintaining Arc Consistency (MAC) algorithm detects inconsistencies created by forward checking deleting inconsistent values (such as between Yi and Yj). After assigning a value to Xi, MAC calls AC-3, but start with only the arc (Xj, Xi), rather than all arcs, for all Xj that are unassigned neighbors of Xi. If any variable has its domain reduced to empty, backtrack immediately.\n",
              "\n",
              "\n",
              "Chronological backtracking backs up to the proceeding variable and try a different value, revisiting the most recent decision point.  \n",
              "\n",
              "\n",
              "A more intelligent approach keeps a conflict set that tracks a set of assignments that are in conflict with the variable causing search failure.  The backjumping  method backtracks to the most recent assignment in the conflict set.  Forward checking can supply the conflict set without extra work.\n",
              "\n",
              "\n",
              "Simple backjumping is redundant in forward checking search.\n",
              "Conflict-directed backjumping identifies (a different and deeper-notion conflict set) the set of proceeding variables, together with any subsequent variables, that causes a variable has no consistent solution.\n",
              "\n",
              "\n",
              "Constraint learning finds a minimum set of variables from the conflict set that causes the problem.  This set of variables along with their corresponding values are no-good.  Record the no-good.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Local search algorithms turn out to be very effective in solving many CSPs.\n",
              "USing complete stat formulation where each state assigns a value to every varialbe, and then changes the value of one variable at a time.\n",
              "The min-conflicts heuristic, which selects the value that results in the minimum number of conflicts with other variables.\n",
              "\n",
              "\n",
              "Constraint weighting concentrates the search on the important constraints.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Independent subproblems.  Finding connected components of the constraint graph can help identify independence.\n",
              "Each subproblem has c(a constant) variables from the total n varialbes. There are n/c subproblems, and each takes $O(d^c)$ to solve.  Total work is $O(d^c n/c)$ which is linear in n.\n",
              "Without decomposition, it is $O(d^n)$.\n",
              "\n",
              "\n",
              "Directional arc onsistency (DAC): A CSP is DAC under an ordering of variables $X_1, X_2, ..., X_n$ if and only if every $X_i$ is arc-consistent with each $X_j$ for j>i.\n",
              "\n",
              "\n",
              "Topological sort.  Make it directional arc consistent in n steps (n-1 edges for the tree), comparing up to d possible domain values for two variables, for a total time of $O(nd^2)$.\n",
              "Once having a directed arc-consistent graph, march down the list of variables and choosse any remaining vlue.\n",
              "Efficent algorithm for trees, try to reduce more general constraint graph to trees.\n",
              "\n",
              "\n",
              "Cuset conditioning reduce a constraint graph to a tree by removing nodes.  Choose a subset S such that the constraint graph becomes a tree after removing S.  S is a cycle cutset.\n",
              "For each possible assignment to the variables in S that satisfies all constraints on S, remove any value that are inconsistent with the assignment(for S) from the domains of the remaining variables(on the tree).  \n",
              "If there is a solution to the remaining part of the CSP, return it with the assignment for S.  If the cycle cutset has size c, the total run time is $O(d^c(n-c)d^2)$.\n",
              "\n",
              "\n",
              "Tree decomposition: transformation of a constraint graph into a tree.\n",
              "\n",
              " \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " Solutions to CSPs can be found by a general purpose algorithm.\n",
              "\n",
              "CSPs may have discrete variables with finite domains or infinite domains.  They may have continuous variables.\n",
              "\n",
              "\n",
              "Search for CSPs only need to consider assignments to a single variable at each node, hence b=d and there are $d^n$ leaves.\n",
              "Backtracking search is DFS for CSPs with single-variable assignments.\n",
              "\n",
              "\n",
              "With following heuristics, backtracking search can gain big efficiency.\n",
              "choosing the most constrainted variable for assignment,\n",
              "choosing the most constraining variable for tie breaker of most constrainted variable,\n",
              "choosing the least constraining value,\n",
              "forward checking.\n",
              "\n",
              "CSP solvers combine search and constraint propagation (inference).\n",
              "\n",
              "Constraint graph with nodes as variables and edges as constraints.\n",
              "\n",
              "\n",
              "AC-3 complexity: total numbers of arcs is 2*n*(n-1) = $O(n^2)$\n",
              "checking an arc takes $O(d^2)$ time, for maximum d values in any domain.\n",
              "each arc can only be inserted into the queue d times.\n",
              "Total time complexity $O(n^2d^3)$.\n",
              "A pair of variable $X_i,X_j$ is path-consistent with $X_m$ if for every assignment $X_i =a, X_j=b$ that is consistent with constraint of $x_i, X_j$, \n",
              "there is a value for $X_m$ in its domain such that both $X_i, X_m$ and $X_j, X_m$ are consistent with their repective constraints.\n",
              "\n",
              "Constraint graph that is a tree can be solved efficiently (linear time to n the number of variables).  Do a topological sort adn march down the list.\n",
              "Cycle cutset algorithm $O(d^{c+2}(n-c))$\n",
              "\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " The central component of a knowledge-based agent is its knowledge base (KB), which is a set of sentences (not identical to the sentences of English and other natural languages).  \n",
              "\n",
              "Each sentence represents some assertion about the world and is expressed in a knowledge representation language.\n",
              "\n",
              "\n",
              "When the sentence is taken as being given without being derived from other sentences, it is an axiom.\n",
              "\n",
              "\n",
              "Both operations to add new sentences to the KB and to query what is known may involve inference, which is deriving new sentences from existing ones.  \n",
              "\n",
              "A KB may initially contain some background knowledge.\n",
              "\n",
              "\n",
              "Declarative approach vs procedural approach.  Declarative approach starts with an empty KB, and TELL sentences one by one until the agent knows how to operate in its environment.  \n",
              "\n",
              "\n",
              "Procedural approach encodes desired behaviors directly as program code.  Successful agent often combines both.\n",
              " \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Performance measure, Environment, Actuators, Sensors. \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " A logic must define the semantics, or meaning, of sentences.  The semantics defines the truth of each sentence with respect to each possible world.  \n",
              "\n",
              "\n",
              "To be precise, use the term model in stead of “possible world”.  Models are mathematical abstractions, each of which has a fixed truth value for every relevant sentence.  \n",
              "\n",
              "\n",
              "If a sentence α is true in model m, m satisfies α or m is a model of α.  M(α) means the set of all models of α.\n",
              "\n",
              "\n",
              "A sentence follows logically from another sentence. α entails β.  α |= β iif M(α) is subset of M(β). \n",
              "\n",
              " Note that if α|= β, then α is a stronger assertion than β, and it rules more possible worlds.\n",
              "\n",
              "\n",
              "Model checking:  an inference algorithm that enumerates all possible models to check if α is true in all models in which KB is true.\n",
              "\n",
              " \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "  Atomic sentences consist of a single proposition symbol.  \n",
              "\n",
              "Complex sentences ae constructed from simper sentences, using parentheses and operators (logic connectives): \n",
              "\n",
              "negation, \n",
              "\n",
              "and (conjunction), \n",
              "\n",
              "or (disjunction), \n",
              "\n",
              "implies (an implication from premise or antecedent to conclusion or consequence.  They are also known as rules or if-then statements.)  \n",
              "\n",
              "If and only if (biconditional).\n",
              "\n",
              "\n",
              "Propositional entailment algorithm (model checking)’s time complexity is $O(2^n)$ since there are $2^n$ models, and space complexity is only O(n) as the enumeration is depth-first.\n",
              "\n",
              " \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " Entailment can be done by theorem proving, applying rules of inference directly to the sentences in KB to construct a proof of the desired sentence without consulting models.  \n",
              "If the number of models is large but the length of the proof is short, then theorem proving can be more efficient than model checking.\n",
              "\n",
              "Deduction, α|= β iif α => β.\n",
              "\n",
              "α|= β  iif (α ^ ¬β) is unsatisfiable (contradiction by showing that assumes a sentence β to be false and leads to a contradiction with known axioms α)\n",
              "\n",
              "\n",
              "Inference rules:\n",
              "Modus Ponens $(α=> β, α)/ β$, whenever sentences of the form α=> β and α are given, the sentence β can be inferred.\n",
              "And_Elimination:   α ^ β / α,  from a conjunction, any of the conjuncts can be inferred.\n",
              "\n",
              "Searching for proofs is an alternative to enumerating models.  In many practical cases finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how man of them there are.\n",
              "\n",
              "\n",
              "Monotonicity, the set of entailed sentences can only increases information is added to the KB. For any sentences α and β, if KB|= α then KB^β |= α.\n",
              "\n",
              "\n",
              "Unit resolution rule takes a clause (a disjunction of literals) and a literal (which is a complementary literal to some literal in the clause) and produces a new clause.\n",
              "\n",
              "\n",
              "Full resolution rule, generalized from the unit resolution rule, takes two clauses and produces a new clause containing all the literals of the two original clauses except the two complementary literals.\n",
              "Resolve ONLY one pair of complementary literals at a time.\n",
              "\n",
              "\n",
              "A sentence expressed as a conjunction of clauses is in conjunctive normal form (CNF)\n",
              "\n",
              "\n",
              "Definite clause is a disjunction of literals of which exactly one is positive.\n",
              "Horn clause is a disjunction of literals of which at most one is positive.\n",
              "Horn clause is closed under resolution, meaning if you resolve two Horn clauses, you get back a Horn clause.  \n",
              "K-CNF sentence is a CNF sentence where each clause has at most k literals.\n",
              "\n",
              "\n",
              "KB containing only definite clauses are interesting for three reasons:\n",
              "1.\tEvery definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal.  \n",
              "In Horn form, the premise is called the body and the conclusion is called the head.  A sentence consisting of a single positive literal is called a fact.\n",
              "\n",
              "2.\tInference with Horn clause can be efficiently done by forward chaining and backward chaining algorithms.\n",
              "\n",
              "3.\tDeciding entailment with Horn clauses can be done in linear time. \n",
              "\n",
              "Forward chaining is data-directed reasoning.  Backward chaining is goal-directed reasoning.  The cost of backward-chaining is much less than linear in the size of the KB, since the process touches only relevant facts.\n",
              "\n",
              "\n",
              "Many combinational problems in computer science can be reduced to checking the satisfiability of a propositional sentence.\n",
              " \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " There are two kinds of sentences: axioms and derived sentences.  Axioms is a given sentence.  \n",
              "Inference is the process of deriving new sentences from old sentences. \n",
              "\n",
              "Wampa world is deterministic, discrete, static, single-agent, sequential and partically observable.\n",
              "\n",
              "Entailment can be used to derive conclusion, and that is the process of logical inference.\n",
              "\n",
              "An inference algorithm i allows us to conclude that α is true, α is derived from KB by i. KB $⊢_i$ 𝛂.\n",
              "\n",
              "Quality of inference algorithm we seek: sound and complete.\n",
              "\n",
              "Resolution yields a complete inference algorithm.\n",
              "\n",
              "Resolution algorithm shows that KB ⋀ ¬𝛂 is unsatifiable in order to prove KB |= 𝛂.  (proof by contradiction)\n",
              "Steps: convert KB ⋀ ¬𝛂 into CNF (conjuctive normal form); apply the resolution rule to the resulting clauses; resolve every pair that contains complementary literals to produce a new clause;\n",
              "if the new clause is not present, then add it to the set; continue the process until either of the two:\n",
              "   1. there are no new clauses that can be added. KB does not entail 𝛂.\n",
              "   2. Two clauses resolve to be the empty clause, KB does entail 𝛂.\n",
              "\n",
              "Every definite clause can be written as implication whose premise is a conjunction of positive literals and conclusion is a positive literal.\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Implication elimination** - (𝛂 ⟹ β) ≡ (¬𝛂 ⋁ β)\n",
              "* **Distributivity of ⋀ over ⋁** - ((𝛂 ⋀ β) ⋁ ɣ) ≡ ((𝛂 ⋀ β) ⋁ (𝛂 ⋀ ɣ))) \n",
              "* **Distributivity of ⋁ over ⋀ ** - ((𝛂 ⋁ β) ⋀ ɣ) ≡ ((𝛂 ⋁ β) ⋀ (𝛂 ⋁ ɣ))) \n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [
        "cw5IpDLCZa4W",
        "s3Uk9gQTevcj",
        "46MQLR-Gx8dZ"
      ],
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
