{
  "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": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "4d6e23f3-1fee-4a05-dcc7-002dab4154a9"
      },
      "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": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "e47b4e0f-ec8f-4ec2-f39b-8ccf8a16cd25"
      },
      "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": null,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "The problem of achieving agreement between our true preferences and the objective we put into the machine is called the value alignment problem: the values or objectives put into the machine must be aligned with those of the human.\\n\n",
        "Ultimately, we want agents that are provably beneficial to humans.\n",
        "\"\"\" \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 = \"\"\"\n",
        "Weak AI- machine acts as if it were intelligent\\n\n",
        "Strong AI - machine actually is intelligent\\n\n",
        "The embodied cognition approach claims that it makes no sense to consider the brain separately: cognition takes place within a body, which is embedded in an environment.\\n\n",
        "\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "Chinese Room:\\n\n",
        "Imagine a human, who understands only English, inside a room that contains a rule book, written in English, and various stacks of paper. Pieces of paper containing indecipherable symbols are slipped under the door to the room. The human follows the instructions in the rule book, finding symbols in the stacks, writing symbols on new pieces of paper, rearranging the stacks, and so on. Eventually, the instructions will cause one or more symbols to be transcribed onto a piece of paper that is passed back to the outside world. From the outside, we see a system that is taking input in the form of Chinese sentences and generating fluent, intelligent Chinese responses.\n",
        "Argues computer doesn't understand Chinese, just like the human.\\n\n",
        "\"\"\"\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 = \"\"\"Rational Agents:\\n\n",
        "Agent: anything that perceives its environment through sensors and acts on its environmnet through actuators\\n\n",
        "Percept: agent's perceptual inputs at any given instance\\n\n",
        "Agent function f:P->a maps a sequence of percept vectors P to action a from set A\\n\n",
        "Agent program runs on physical architecture to produce f. Agent = architecture + program\\n\n",
        "Rational Agent: Selects action a to maximize its expected performance measure\\n\n",
        "\n",
        "Fully Observable vs Partially Observable\\n\n",
        "Deterministic vs Non-Deterministic vs Stochastic\\n\n",
        "(Agent action+environment known, environment random, probabalistic outcome for each action)\\n\n",
        "Episodic vs Sequential\\n\n",
        "(Current dec. ind of past actions, current dec. effects future ones)\\n\n",
        "Static vs Dynamic\\n\n",
        "Discrete vs Continuous (#environment states, #actions)\\n\n",
        "\n",
        "Hardest Case:\\n\n",
        "- Continuous\n",
        "- Partially Observable\n",
        "- Stochastic\n",
        "- Multiagent\n",
        "\"\"\"\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",
        "\"qualia\": \"intrinsic nature of experiences\",\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": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1411
        },
        "id": "gYYeNcdM_maE",
        "outputId": "e9834421-55e6-4219-8185-e27668432736"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "\n",
              "The problem of achieving agreement between our true preferences and the objective we put into the machine is called the value alignment problem: the values or objectives put into the machine must be aligned with those of the human.\n",
              "\n",
              "Ultimately, we want agents that are provably beneficial to humans.\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "\n",
              "Weak AI- machine acts as if it were intelligent\n",
              "\n",
              "Strong AI - machine actually is intelligent\n",
              "\n",
              "The embodied cognition approach claims that it makes no sense to consider the brain separately: cognition takes place within a body, which is embedded in an environment.\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              "\n",
              "Chinese Room:\n",
              "\n",
              "Imagine a human, who understands only English, inside a room that contains a rule book, written in English, and various stacks of paper. Pieces of paper containing indecipherable symbols are slipped under the door to the room. The human follows the instructions in the rule book, finding symbols in the stacks, writing symbols on new pieces of paper, rearranging the stacks, and so on. Eventually, the instructions will cause one or more symbols to be transcribed onto a piece of paper that is passed back to the outside world. From the outside, we see a system that is taking input in the form of Chinese sentences and generating fluent, intelligent Chinese responses.\n",
              "Argues computer doesn't understand Chinese, just like the human.\n",
              "\n",
              "\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",
              "Rational Agents:\n",
              "\n",
              "Agent: anything that perceives its environment through sensors and acts on its environmnet through actuators\n",
              "\n",
              "Percept: agent's perceptual inputs at any given instance\n",
              "\n",
              "Agent function f:P->a maps a sequence of percept vectors P to action a from set A\n",
              "\n",
              "Agent program runs on physical architecture to produce f. Agent = architecture + program\n",
              "\n",
              "Rational Agent: Selects action a to maximize its expected performance measure\n",
              "\n",
              "\n",
              "Fully Observable vs Partially Observable\n",
              "\n",
              "Deterministic vs Non-Deterministic vs Stochastic\n",
              "\n",
              "(Agent action+environment known, environment random, probabalistic outcome for each action)\n",
              "\n",
              "Episodic vs Sequential\n",
              "\n",
              "(Current dec. ind of past actions, current dec. effects future ones)\n",
              "\n",
              "Static vs Dynamic\n",
              "\n",
              "Discrete vs Continuous (#environment states, #actions)\n",
              "\n",
              "\n",
              "Hardest Case:\n",
              "\n",
              "- Continuous\n",
              "- Partially Observable\n",
              "- Stochastic\n",
              "- Multiagent\n",
              "\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",
              "* **Qualia** - intrinsic nature of experiences\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": null,
      "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 = \"\"\"-Strings, tuples are immutable\\n\n",
        "-Lists are mutable, use y = x[:] to get a (shallow) copy\\n\n",
        "-Dictionaries are unordered & work by hashing, so keys must be immutable\\n\n",
        "-Variable number of non-keyword arguments:\\n\n",
        "  *def func(*args): //unknown # of args\\n\n",
        "  *def func(**kwargs): //dict of args\\n\n",
        "-Class must have __init__\\n\n",
        "-class child_class(parent_class):\\n\n",
        "-Subclass can overwrite parent class methods\\n\n",
        "-List comprehension:\\n\n",
        "li = [3, 6, 2, 7, 1, 9]\\n\n",
        "[elem * 2 for elem in li if elem > 4]\\n\n",
        "-Sets: discard = no error, remove = error\\n\n",
        "-Iterators use memory efficiently\\n\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"static typing\" : \"Vars can only refer to objects of a declared type, JAVA, type errors caught at compile-time\",\n",
        "\"dynamic typing\" : \"Vars come into existence when first assigned, PYTHON, type errors caught at runtime\"\n",
        "\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ydOK__lwWgdp",
        "outputId": "9b56f1be-31ee-4cf4-9a05-5ee32f026d66"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "-Strings, tuples are immutable\n",
              "\n",
              "-Lists are mutable, use y = x[:] to get a (shallow) copy\n",
              "\n",
              "-Dictionaries are unordered & work by hashing, so keys must be immutable\n",
              "\n",
              "-Variable number of non-keyword arguments:\n",
              "\n",
              "  *def func(*args): //unknown # of args\n",
              "\n",
              "  *def func(**kwargs): //dict of args\n",
              "\n",
              "-Class must have __init__\n",
              "\n",
              "-class child_class(parent_class):\n",
              "\n",
              "-Subclass can overwrite parent class methods\n",
              "\n",
              "-List comprehension:\n",
              "\n",
              "li = [3, 6, 2, 7, 1, 9]\n",
              "\n",
              "[elem * 2 for elem in li if elem > 4]\n",
              "\n",
              "-Sets: discard = no error, remove = error\n",
              "\n",
              "-Iterators use memory efficiently\n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Static typing** - Vars can only refer to objects of a declared type, JAVA, type errors caught at compile-time\n",
              "* **Dynamic typing** - Vars come into existence when first assigned, PYTHON, type errors caught at runtime\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": null,
      "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 = \"\"\"\n",
        "open-loop system: Once agent finds solution, it can ignore precepts (Fully-observable, deterministic)\\n\n",
        "close-loop system: use when change model is incorrect, or nondeterministic environment\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"standardized problem: benchmark for researchers\\n\n",
        "-sokoban puzzle, in which the agent’s goal is to push a number of boxes, scattered about the grid, to designated storage locations, $n*n!/(b!(n-b)!)$ states\\n\n",
        "-grid world\\n\n",
        "-sliding-tile\\n\n",
        "-Donald Knuth factorial/root\\n\n",
        "real-world problem:\\n\n",
        "-route-finding problem (one desitination)\\n\n",
        "-touring problem (must visit all nodes with path less than cost C ie. TSP)\\n\n",
        "-VLSI layout (place/route components on chip)\\n\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Best-first-search:\\n\n",
        "Expand nodes in frontier according to some rule/priority function.\\n\n",
        "Algorithm Measurements:\\n\n",
        "-Completeness: find a solution when there is one, report failure when there isn't\\n\n",
        "-Cost optimality: lowest-cost path?\\n\n",
        "-Time optimality\\n\n",
        "-Space complexity\\n\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "BFS:\\n\n",
        "- Expand to shallowest unexapnded node\n",
        "- Frontier is FIFO queue \n",
        "- Uses early goal test, checking whether a node is a solution as soon as it is generated, rather than the late goal test that best-first search use\n",
        "- $1+b + b^2 + ... + b^d = O(b^d)$ space and time (d = depth of shallowest goal)\n",
        "- Complete if b is finite, optimal if edge-cost = 1\\n\n",
        "Uniform cost search (Dijkstras):\\n\n",
        "- Process frontier from lowest-highest edge cost\\n\n",
        "- C* (cost of optimal sol), $\\epsilon$ (smallest edge cost), $O(b^{1+C^*/\\epsilon})$ space and time\n",
        "- Complete, cost-optimal\\n\n",
        "DFS:\\n\n",
        "- Expand to deepest unexpanded node\n",
        "- Frontier is LIFO queue\n",
        "- Not complete (fails in infinite depth, spaces with loops), complete in finite spaces\n",
        "- $O(b^m)$ time, bad if $m >> d$, good in dense graphs. m is max length of any path in state space\n",
        "- $O(bm)$ space, keep track of nodes on path\n",
        "- Not optimal\\n\n",
        "Bidirectional Search:\\n\n",
        "- simultaneously searches forward from the initial state and backwards from the goal states\n",
        "- Optimal if uniform edge cost and BFS, or uniform cost search from each end\n",
        "- Otherwise, keep track of best solution so far\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "1. States, 2. Initial state, 3. Actions, 4. Transitions $(s, a_i) \\implies s_r$, 5. Path cost: additive, 6. Goal states\n",
        "Solution: sequence of actions from initial state to a goal state\\n\n",
        "Optimal solution: Lowest Path cost\\n\n",
        "\n",
        "Tree search:\\n\n",
        "- Different paths to same node treated as distinct\n",
        "Graph search:\\n\n",
        "- Keep track of states we have visited\n",
        "- Memory intensive\\n\n",
        "\n",
        "Use BFS: possible inf. paths, some solutions have short path\\n\n",
        "Use DFS: space is restricted, many possible solutions with long paths\n",
        "\n",
        "Depth-limited search:\\n\n",
        "- DFS with depth limit (diameter) l\n",
        "- Optimal if l=d, incomplete if l < d, not optimal if l > d\n",
        "- $O(b^d)$ time and space\\n\n",
        "\n",
        "Iterative Deepening Search:\\n\n",
        "- Use depth-limited-search as subroutine, increasing l\n",
        "- Complete (if no inf paths)\n",
        "- Optimal if edge-cost = 1\n",
        "- $O(b^d)$ time, $O(bd)$ space\n",
        "\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",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "5a53b86f-c7eb-4143-f9b7-40a1bc20ae95"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "\n",
              "open-loop system: Once agent finds solution, it can ignore precepts (Fully-observable, deterministic)\n",
              "\n",
              "close-loop system: use when change model is incorrect, or nondeterministic environment\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "standardized problem: benchmark for researchers\n",
              "\n",
              "-sokoban puzzle, in which the agent’s goal is to push a number of boxes, scattered about the grid, to designated storage locations, $n*n!/(b!(n-b)!)$ states\n",
              "\n",
              "-grid world\n",
              "\n",
              "-sliding-tile\n",
              "\n",
              "-Donald Knuth factorial/root\n",
              "\n",
              "real-world problem:\n",
              "\n",
              "-route-finding problem (one desitination)\n",
              "\n",
              "-touring problem (must visit all nodes with path less than cost C ie. TSP)\n",
              "\n",
              "-VLSI layout (place/route components on chip)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "Best-first-search:\n",
              "\n",
              "Expand nodes in frontier according to some rule/priority function.\n",
              "\n",
              "Algorithm Measurements:\n",
              "\n",
              "-Completeness: find a solution when there is one, report failure when there isn't\n",
              "\n",
              "-Cost optimality: lowest-cost path?\n",
              "\n",
              "-Time optimality\n",
              "\n",
              "-Space complexity\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "BFS:\n",
              "\n",
              "- Expand to shallowest unexapnded node\n",
              "- Frontier is FIFO queue \n",
              "- Uses early goal test, checking whether a node is a solution as soon as it is generated, rather than the late goal test that best-first search use\n",
              "- $1+b + b^2 + ... + b^d = O(b^d)$ space and time (d = depth of shallowest goal)\n",
              "- Complete if b is finite, optimal if edge-cost = 1\n",
              "\n",
              "Uniform cost search (Dijkstras):\n",
              "\n",
              "- Process frontier from lowest-highest edge cost\n",
              "\n",
              "- C* (cost of optimal sol), $\\epsilon$ (smallest edge cost), $O(b^{1+C^*/\\epsilon})$ space and time\n",
              "- Complete, cost-optimal\n",
              "\n",
              "DFS:\n",
              "\n",
              "- Expand to deepest unexpanded node\n",
              "- Frontier is LIFO queue\n",
              "- Not complete (fails in infinite depth, spaces with loops), complete in finite spaces\n",
              "- $O(b^m)$ time, bad if $m >> d$, good in dense graphs. m is max length of any path in state space\n",
              "- $O(bm)$ space, keep track of nodes on path\n",
              "- Not optimal\n",
              "\n",
              "Bidirectional Search:\n",
              "\n",
              "- simultaneously searches forward from the initial state and backwards from the goal states\n",
              "- Optimal if uniform edge cost and BFS, or uniform cost search from each end\n",
              "- Otherwise, keep track of best solution so far\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "1. States, 2. Initial state, 3. Actions, 4. Transitions $(s, a_i) \\implies s_r$, 5. Path cost: additive, 6. Goal states\n",
              "Solution: sequence of actions from initial state to a goal state\n",
              "\n",
              "Optimal solution: Lowest Path cost\n",
              "\n",
              "\n",
              "Tree search:\n",
              "\n",
              "- Different paths to same node treated as distinct\n",
              "Graph search:\n",
              "\n",
              "- Keep track of states we have visited\n",
              "- Memory intensive\n",
              "\n",
              "\n",
              "Use BFS: possible inf. paths, some solutions have short path\n",
              "\n",
              "Use DFS: space is restricted, many possible solutions with long paths\n",
              "\n",
              "Depth-limited search:\n",
              "\n",
              "- DFS with depth limit (diameter) l\n",
              "- Optimal if l=d, incomplete if l < d, not optimal if l > d\n",
              "- $O(b^d)$ time and space\n",
              "\n",
              "\n",
              "Iterative Deepening Search:\n",
              "\n",
              "- Use depth-limited-search as subroutine, increasing l\n",
              "- Complete (if no inf paths)\n",
              "- Optimal if edge-cost = 1\n",
              "- $O(b^d)$ time, $O(bd)$ space\n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\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": null,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "Heuristic f(n)\\n\n",
        "Greedy BFS:\\n\n",
        "- Process frontier according to f(n)\n",
        "- UCS but with heuristic instead of cost function\n",
        "- Not optimal (tank a big cost in order to have small costs)\n",
        "- Not complete (can get stuck in loops)\n",
        "- O(|V|) space and time\\n\n",
        "A*:\\n\n",
        "- f(n) = g(n) + h(n) \n",
        "- Frontier as priority queue by increasing f(n)\\n\n",
        "Admissibility:\\n\n",
        "- h(n) never overestimates cost to reach goal\n",
        "- Admissibility => optimal\n",
        "- Inadmissible but one cost-optimal path on which h(n) is admissible for all nodes on the path => optimal\n",
        "- Inadmissible but optimal solution has cost C* and second-best has cost C2, if h(n) never overestimates by $>C_2-C^*$ => optimal\\n\n",
        "Consistency:\\n\n",
        "- For every node n and successor n' generated by action a, $h(n) \\leq c(n,a,n') + h(n')$\n",
        "- Triangle inequality\n",
        "- Consistent implies admissible\n",
        "- With a consistent heuristic, the first time we reach a state it will be on an optimal path, so we never have to re-add a state to the frontier\\n\n",
        "\n",
        "Weighted A* provides this guarantee. In bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost, as long as we can find it quickly.\\n\n",
        "\n",
        "Speedy Search\\n:\n",
        "- h(n) = estimated number of actions required to reach a goal, regardless of the cost of those actions\n",
        "- unbounded-cost \\n\n",
        "\n",
        "\n",
        "Memory Tricks:\\n\n",
        "- Reference counts: keep track of how many times we've reached state, remove from reached table if count goes to 0. (ie grid world, only can reach state in 4 ways)\n",
        "- Beam search:\n",
        "  - Limits the size of the frontier. The easiest approach is to keep only the nodes with the best k-scores, discarding any other expanded nodes. \\n\n",
        "- Iterative Deepening A* (IDA*):\n",
        "  - Cutoff is smallest f(n) of any node that exceeded cutoff on previous iteration\n",
        "- Recursive Best First Search (RBFS):\n",
        "  - DFS but keeps track of f-value of best alternate path available from any ancestor of the current node\n",
        "  - If the current node exceeds this limit, the recursion unwinds back to the alternative path\n",
        "  - As the recursion unwinds, RBFS replaces the f-value of each node along the path with a backed-up value (the best f-value of its children)\n",
        "  - RBFS remembers the f-value of the best leaf in the forgotten subtree and can therefore decide whether it’s worth reexpanding the subtree at some later time\n",
        "- Simplified Memory-bounded A* (SMA*):\n",
        "  - Proceeds just like A*, expanding the best leaf until memory is full\n",
        "  - If full, then drops worst leaf node (highest f-value)\n",
        "  - Backs up this f-value in parent, so we known quality of path in subtree should we need to expand it again later\n",
        "  - In bad executions, we can flip-flop between recovering deleted information\n",
        "  - Complete if depth is less than memory size (our solution can fit in memory)\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "Effective branching factor: if A* generates N nodes and solution is depth d, then b* is branching factor of uniform tree depth d+1 with N+1 nodes\\n\n",
        "Effective depth: A* reduces tree depth by this constant (compared to uninformed search tree)\\n\n",
        "Dominance:\\n\n",
        "- $h_2(n) \\geq h_1(n)$ for all n, and is better for search\n",
        "- Best heuristic: $h*(n)$ oracle heuristic, dominates all\n",
        "- Worst heuristic: h_{we're already here}(n) = 0, dominated by all\\n\n",
        "Relaxed Problems: \\n\n",
        "- Cost of optimal solution to a relaxed problem is an admissible heuristic for original problem\n",
        "- ie h_{out of place}(n), h_{manhattan dist} in 8-puzzle \n",
        "- Relaxed-problem is supergraph of original problem, since removing restrictions adds edges b/w states\n",
        "- These edges might be \"shortcuts\" in optimal solution in relaxed-problem that we cannot take in original problem\\n\n",
        "\n",
        "If we have collection of admissible heuristics, $h(n) = $ max of all them\\n\n",
        "Disjoint pattern databases:\\n\n",
        "- Store exact solution cost to various subproblems (ie. 8-puzzle with tiles 1-2-3-4)\n",
        "- Take max of all these heuristics\n",
        "- If patterns are disjoint, then can add the heuristics (ie. tiles 1-2-3-4, and tiles 5-6-7-8)\\n\n",
        "Landmarks:\\n\n",
        "- Precompute optimal path to certain states called landmark points\n",
        "- Can also add shortcut edges (precomputed shortest distances between two states)\n",
        "- Differential heuristic: $h_{DH}(n) = max_L |C^*(n,L) - C*(goal, L)|$ is admissible\n",
        "- Precompute shortest path from each vertex to each landmark, and each landmark to goal\\n\n",
        "Metalevel learning:\\n\n",
        "- Learn from algorithm execution (internal state of program) to avoid exploring unpromising subtrees\\n\n",
        "Learning:\\n\n",
        "- Can learn by looking at examples of problem with multiple heuristics, and learning weights to create linear combo from them\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "e578c109-362b-4fee-b762-6bacf1da6bd2"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "Heuristic f(n)\n",
              "\n",
              "Greedy BFS:\n",
              "\n",
              "- Process frontier according to f(n)\n",
              "- UCS but with heuristic instead of cost function\n",
              "- Not optimal (tank a big cost in order to have small costs)\n",
              "- Not complete (can get stuck in loops)\n",
              "- O(|V|) space and time\n",
              "\n",
              "A*:\n",
              "\n",
              "- f(n) = g(n) + h(n) \n",
              "- Frontier as priority queue by increasing f(n)\n",
              "\n",
              "Admissibility:\n",
              "\n",
              "- h(n) never overestimates cost to reach goal\n",
              "- Admissibility => optimal\n",
              "- Inadmissible but one cost-optimal path on which h(n) is admissible for all nodes on the path => optimal\n",
              "- Inadmissible but optimal solution has cost C* and second-best has cost C2, if h(n) never overestimates by $>C_2-C^*$ => optimal\n",
              "\n",
              "Consistency:\n",
              "\n",
              "- For every node n and successor n' generated by action a, $h(n) \\leq c(n,a,n') + h(n')$\n",
              "- Triangle inequality\n",
              "- Consistent implies admissible\n",
              "- With a consistent heuristic, the first time we reach a state it will be on an optimal path, so we never have to re-add a state to the frontier\n",
              "\n",
              "\n",
              "Weighted A* provides this guarantee. In bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost, as long as we can find it quickly.\n",
              "\n",
              "\n",
              "Speedy Search\n",
              ":\n",
              "- h(n) = estimated number of actions required to reach a goal, regardless of the cost of those actions\n",
              "- unbounded-cost \n",
              "\n",
              "\n",
              "\n",
              "Memory Tricks:\n",
              "\n",
              "- Reference counts: keep track of how many times we've reached state, remove from reached table if count goes to 0. (ie grid world, only can reach state in 4 ways)\n",
              "- Beam search:\n",
              "  - Limits the size of the frontier. The easiest approach is to keep only the nodes with the best k-scores, discarding any other expanded nodes. \n",
              "\n",
              "- Iterative Deepening A* (IDA*):\n",
              "  - Cutoff is smallest f(n) of any node that exceeded cutoff on previous iteration\n",
              "- Recursive Best First Search (RBFS):\n",
              "  - DFS but keeps track of f-value of best alternate path available from any ancestor of the current node\n",
              "  - If the current node exceeds this limit, the recursion unwinds back to the alternative path\n",
              "  - As the recursion unwinds, RBFS replaces the f-value of each node along the path with a backed-up value (the best f-value of its children)\n",
              "  - RBFS remembers the f-value of the best leaf in the forgotten subtree and can therefore decide whether it’s worth reexpanding the subtree at some later time\n",
              "- Simplified Memory-bounded A* (SMA*):\n",
              "  - Proceeds just like A*, expanding the best leaf until memory is full\n",
              "  - If full, then drops worst leaf node (highest f-value)\n",
              "  - Backs up this f-value in parent, so we known quality of path in subtree should we need to expand it again later\n",
              "  - In bad executions, we can flip-flop between recovering deleted information\n",
              "  - Complete if depth is less than memory size (our solution can fit in memory)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "Effective branching factor: if A* generates N nodes and solution is depth d, then b* is branching factor of uniform tree depth d+1 with N+1 nodes\n",
              "\n",
              "Effective depth: A* reduces tree depth by this constant (compared to uninformed search tree)\n",
              "\n",
              "Dominance:\n",
              "\n",
              "- $h_2(n) \\geq h_1(n)$ for all n, and is better for search\n",
              "- Best heuristic: $h*(n)$ oracle heuristic, dominates all\n",
              "- Worst heuristic: h_{we're already here}(n) = 0, dominated by all\n",
              "\n",
              "Relaxed Problems: \n",
              "\n",
              "- Cost of optimal solution to a relaxed problem is an admissible heuristic for original problem\n",
              "- ie h_{out of place}(n), h_{manhattan dist} in 8-puzzle \n",
              "- Relaxed-problem is supergraph of original problem, since removing restrictions adds edges b/w states\n",
              "- These edges might be \"shortcuts\" in optimal solution in relaxed-problem that we cannot take in original problem\n",
              "\n",
              "\n",
              "If we have collection of admissible heuristics, $h(n) = $ max of all them\n",
              "\n",
              "Disjoint pattern databases:\n",
              "\n",
              "- Store exact solution cost to various subproblems (ie. 8-puzzle with tiles 1-2-3-4)\n",
              "- Take max of all these heuristics\n",
              "- If patterns are disjoint, then can add the heuristics (ie. tiles 1-2-3-4, and tiles 5-6-7-8)\n",
              "\n",
              "Landmarks:\n",
              "\n",
              "- Precompute optimal path to certain states called landmark points\n",
              "- Can also add shortcut edges (precomputed shortest distances between two states)\n",
              "- Differential heuristic: $h_{DH}(n) = max_L |C^*(n,L) - C*(goal, L)|$ is admissible\n",
              "- Precompute shortest path from each vertex to each landmark, and each landmark to goal\n",
              "\n",
              "Metalevel learning:\n",
              "\n",
              "- Learn from algorithm execution (internal state of program) to avoid exploring unpromising subtrees\n",
              "\n",
              "Learning:\n",
              "\n",
              "- Can learn by looking at examples of problem with multiple heuristics, and learning weights to create linear combo from them\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 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",
        "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": null,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "Perfect information (ie no hidden cards), 2-player, Turn-taking Games\\n\n",
        "MAX moves first\\n\n",
        "Evaluation Function f(n):\\n\n",
        "- Based on static features of board alone\n",
        "- f(n) > 0 MAX is winning in position n\n",
        "- f(n) = 0 tied\n",
        "- f(n) < 0 MIN is winning in position n\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Minimax Algorithm:\\n\n",
        "- DFS of game tree (nodes are positions, edges are plies)\n",
        "- Leaf nodes have utility values\n",
        "- MAX/MIN alternate levels of tree\n",
        "- MAX chooses node with largest value, MIN chooses node with smallest value\n",
        "- max depth m, b legal moves, $O(b^m)$ time, $O(bm) space\n",
        "Alpha-Beta Pruning:\\n\n",
        "- Can calculate correct minimax algorithm without evaluating parts of tree (pruning)\n",
        "- alpha: MAX's current lower bound on outcome\n",
        "- beta: MIN's current upper bound on outcome\n",
        "- MAX never allows a move that could lead to a worse score than alpha\n",
        "- MIN never allows a move that could lead to a better score than beta\\n\n",
        "Move ordering:\\n\n",
        "- Runtime heavily depends on order you process moves in\n",
        "- Ideal alpha-beta pruning, only need to process $O(b^{m/2})$ nodes, so effective branching factor becomes $\\sqrt(b)$ \n",
        "- Using random move order will result in about $O(b^{3m/4})$ nodes\n",
        "- Can use iterative deepening search. Ply depth of 1, then order moves based on resulting utilities, then ply depth of 2, considering moves in that order, etc.\\n\n",
        "\n",
        "Transposition table: Keeps track of game states and heuristic value of states so we don't have to recompute\\n\n",
        "Type A Strategy: wide but shallow (fixed depth)\\n\n",
        "Type B Strategy: narrow but deep (follow promising moves to end)\\n\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"Evaluation Functions:\n",
        "- Estimate expected utility of player when game is in state s\n",
        "- Can use features (ie. # of white pawns, # of white rooks, ...)\n",
        "- Can calculate expected utility based on prior games in this position (P1 won 82% of games in this position)\n",
        "- Can use weighted linear function of features\\n\n",
        "Cutting off search:\\n\n",
        "- Can cut off search after fixed depth, but evaluation function might swing drastically if we had looked one more level\n",
        "- Quiescent positions are when no move that drastically swings evaluation function exists\n",
        "- Quiescence search sometimes restricted to consider certain types of moves (ie capture moves) that will quickly resolve the uncertainties position\n",
        "- Horizon effect: opponent has move that is damaging and unavoidable, but you can stall with filler (sometimes bad) moves, pushing this devestating move over the cutoff horizon\n",
        "- Allow singular extensions: moves that are clearly better than all other moves in a position, even if this pushes us beyond the cutoff\\n\n",
        "Forward Pruning (eliminate some moves):\\n\n",
        "- Beam search: only consider n best moves according to evaluation function of the next states (greedy)\n",
        "- ProbCut: use statistics gained from prior experience to lessen the chance that the best move will be pruned\n",
        "- Late move reduction: works under assumption that move ordering has been done well (moves that appear later in the list of possible moves are less likely to be good moves)\n",
        "  - Reduce the depth to which we search these late moves, thereby saving time\\n\n",
        "Lookup:\\n\n",
        "- Can run retrograde minimax search from every possible position (of endgame), and create policy describing best move\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Expectiminimax:\n",
        "- Add chance nodes. Value of chance node is expected value of all its children\n",
        "- Slow and expensive to run\n",
        "- Can still prune cleverly. If utilities are bounded between two values, then we can bound the value of a chance node without looking at all its children. \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "Expected utility = possible utility values weighted by probability\\n\n",
        "A rational agent should choose action that receives the maximum expected utility (MEU)\\n\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "Preference Constraints:\n",
        "- ORDERABILITY - agent must prefer A to B, prefer B to A, or be indifferent\n",
        "- TRANSITIVITY\n",
        "- CONTINUITY - If $A > B > C$ then there exists a probability such that the agent is indifferent between getting B and getting A with prob p and C with prob 1-p\n",
        "- SUBSTITUTABILITY - If A ~ B, then $[p, A; 1-p, C] \\tilde [p, B; 1-p, C]$\n",
        "- MONOTONICITY - If A > B are only two outcomes of lottery, then the agent prefers lottery that has higher prob for A\n",
        "- DECOMPOSABILITY - compresses 2 lotteries into single one (using MR)\\n\n",
        "Theorem: a utility function exists for any rational agent\\n\n",
        "Value-utility function: value of options matters\\n\n",
        "Ordinal-utility function: only ranking options matters\\n\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "Preference elicitation - presenting choices and gathering preferences\\n\n",
        "Normalized utilities - scale from $u_{\\bot} = 0$ to $u_{T} = 1$\\n\n",
        "Standard lottery - [p, u_{T}; 1-p, u_{\\bot}]$ \\n\n",
        "\n",
        "Value of a statistical life = $10 million\\n\n",
        "Micromort\\n\n",
        "QALY - quality-adjusted life year\\n\n",
        "EMV - expected monetary value \\n\n",
        "We say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\\n\n",
        "risk-averse - prefer guarenteed payoff that is < EMV\\n\n",
        "risk-seeking - prefer guarenteed payoff that is > EMV\\n\n",
        "Certainty equivalent - amount you accept in place of a lottery\\n\n",
        "Insurance premium - diff b/w certainty equivalent and EMV\\n\n",
        "optimizer’s curse - tendency for the estimated expected utility of the best choice to be too high\\n\n",
        "Certaintly effect - people want certainty\\n\n",
        "Ambiguity aversion - people avoid ambiguity\\n\n",
        "Framing effect - presenting lotteries in different ways yields different preferences (90% survival vs 10% death)\\n\n",
        "Anchoring effect - people like making relative utility judgements instead of absolute\\n\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"micromort\" : \"1/10^6 chance of death\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2512
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "51cf0135-c258-4dd1-c321-4e9bb9af0d47"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "\n",
              "Perfect information (ie no hidden cards), 2-player, Turn-taking Games\n",
              "\n",
              "MAX moves first\n",
              "\n",
              "Evaluation Function f(n):\n",
              "\n",
              "- Based on static features of board alone\n",
              "- f(n) > 0 MAX is winning in position n\n",
              "- f(n) = 0 tied\n",
              "- f(n) < 0 MIN is winning in position n\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "\n",
              "Minimax Algorithm:\n",
              "\n",
              "- DFS of game tree (nodes are positions, edges are plies)\n",
              "- Leaf nodes have utility values\n",
              "- MAX/MIN alternate levels of tree\n",
              "- MAX chooses node with largest value, MIN chooses node with smallest value\n",
              "- max depth m, b legal moves, $O(b^m)$ time, $O(bm) space\n",
              "Alpha-Beta Pruning:\n",
              "\n",
              "- Can calculate correct minimax algorithm without evaluating parts of tree (pruning)\n",
              "- alpha: MAX's current lower bound on outcome\n",
              "- beta: MIN's current upper bound on outcome\n",
              "- MAX never allows a move that could lead to a worse score than alpha\n",
              "- MIN never allows a move that could lead to a better score than beta\n",
              "\n",
              "Move ordering:\n",
              "\n",
              "- Runtime heavily depends on order you process moves in\n",
              "- Ideal alpha-beta pruning, only need to process $O(b^{m/2})$ nodes, so effective branching factor becomes $\\sqrt(b)$ \n",
              "- Using random move order will result in about $O(b^{3m/4})$ nodes\n",
              "- Can use iterative deepening search. Ply depth of 1, then order moves based on resulting utilities, then ply depth of 2, considering moves in that order, etc.\n",
              "\n",
              "\n",
              "Transposition table: Keeps track of game states and heuristic value of states so we don't have to recompute\n",
              "\n",
              "Type A Strategy: wide but shallow (fixed depth)\n",
              "\n",
              "Type B Strategy: narrow but deep (follow promising moves to end)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "Evaluation Functions:\n",
              "- Estimate expected utility of player when game is in state s\n",
              "- Can use features (ie. # of white pawns, # of white rooks, ...)\n",
              "- Can calculate expected utility based on prior games in this position (P1 won 82% of games in this position)\n",
              "- Can use weighted linear function of features\n",
              "\n",
              "Cutting off search:\n",
              "\n",
              "- Can cut off search after fixed depth, but evaluation function might swing drastically if we had looked one more level\n",
              "- Quiescent positions are when no move that drastically swings evaluation function exists\n",
              "- Quiescence search sometimes restricted to consider certain types of moves (ie capture moves) that will quickly resolve the uncertainties position\n",
              "- Horizon effect: opponent has move that is damaging and unavoidable, but you can stall with filler (sometimes bad) moves, pushing this devestating move over the cutoff horizon\n",
              "- Allow singular extensions: moves that are clearly better than all other moves in a position, even if this pushes us beyond the cutoff\n",
              "\n",
              "Forward Pruning (eliminate some moves):\n",
              "\n",
              "- Beam search: only consider n best moves according to evaluation function of the next states (greedy)\n",
              "- ProbCut: use statistics gained from prior experience to lessen the chance that the best move will be pruned\n",
              "- Late move reduction: works under assumption that move ordering has been done well (moves that appear later in the list of possible moves are less likely to be good moves)\n",
              "  - Reduce the depth to which we search these late moves, thereby saving time\n",
              "\n",
              "Lookup:\n",
              "\n",
              "- Can run retrograde minimax search from every possible position (of endgame), and create policy describing best move\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "Expectiminimax:\n",
              "- Add chance nodes. Value of chance node is expected value of all its children\n",
              "- Slow and expensive to run\n",
              "- Can still prune cleverly. If utilities are bounded between two values, then we can bound the value of a chance node without looking at all its children. \n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "\n",
              "Expected utility = possible utility values weighted by probability\n",
              "\n",
              "A rational agent should choose action that receives the maximum expected utility (MEU)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "\n",
              "Preference Constraints:\n",
              "- ORDERABILITY - agent must prefer A to B, prefer B to A, or be indifferent\n",
              "- TRANSITIVITY\n",
              "- CONTINUITY - If $A > B > C$ then there exists a probability such that the agent is indifferent between getting B and getting A with prob p and C with prob 1-p\n",
              "- SUBSTITUTABILITY - If A ~ B, then $[p, A; 1-p, C] \tilde [p, B; 1-p, C]$\n",
              "- MONOTONICITY - If A > B are only two outcomes of lottery, then the agent prefers lottery that has higher prob for A\n",
              "- DECOMPOSABILITY - compresses 2 lotteries into single one (using MR)\n",
              "\n",
              "Theorem: a utility function exists for any rational agent\n",
              "\n",
              "Value-utility function: value of options matters\n",
              "\n",
              "Ordinal-utility function: only ranking options matters\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "\n",
              "Preference elicitation - presenting choices and gathering preferences\n",
              "\n",
              "Normalized utilities - scale from $u_{\bot} = 0$ to $u_{T} = 1$\n",
              "\n",
              "Standard lottery - [p, u_{T}; 1-p, u_{\bot}]$ \n",
              "\n",
              "\n",
              "Value of a statistical life = $10 million\n",
              "\n",
              "Micromort\n",
              "\n",
              "QALY - quality-adjusted life year\n",
              "\n",
              "EMV - expected monetary value \n",
              "\n",
              "We say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\n",
              "\n",
              "risk-averse - prefer guarenteed payoff that is < EMV\n",
              "\n",
              "risk-seeking - prefer guarenteed payoff that is > EMV\n",
              "\n",
              "Certainty equivalent - amount you accept in place of a lottery\n",
              "\n",
              "Insurance premium - diff b/w certainty equivalent and EMV\n",
              "\n",
              "optimizer’s curse - tendency for the estimated expected utility of the best choice to be too high\n",
              "\n",
              "Certaintly effect - people want certainty\n",
              "\n",
              "Ambiguity aversion - people avoid ambiguity\n",
              "\n",
              "Framing effect - presenting lotteries in different ways yields different preferences (90% survival vs 10% death)\n",
              "\n",
              "Anchoring effect - people like making relative utility judgements instead of absolute\n",
              "\n",
              "\n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Micromort** - 1/10^6 chance of death\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": null,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "X - set of variables\\n\n",
        "D - set of domains, one for each variable\\n\n",
        "C - set of constraints\\n\n",
        "\n",
        "Unary constraint: one variable (ie $A \\neq 3$)\\n\n",
        "Binary constraint: two variables (ie $A > B$)\\n\n",
        "Any CSP can be transformed into a binary one.\\n\n",
        "\n",
        "Another way to convert a n-ary CSP to a binary one is the dual graph transformation: create a new graph in which there will be one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables.\\n\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "A single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\\n\n",
        "More formally, $X_i$ is arc-consistent with respect to another variable $X_j$ if for every value in the current domain $D_i$ there is some value in the domain $D_j$ that satisfies the binary constraint on the arc.\\n\n",
        "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\n",
        "Strongly k-consistent - k-consistent, (k-1)-consistent,...,1-consistent\\n\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Backtracking Search:\\n\n",
        "- Assign value to first var, then second, then third, etc. and backtrack if we violate constraint\n",
        "- d^n leaves (n variables, each with $\\leq d$ possible values)\\n\n",
        "Improvements:\\n\n",
        "- Heuristic 1: Most constrained value. Choose variable with fewest legal values to explore next\n",
        "- Heuristic 2: Tie breaker among constrained vars. Choose variable with most constraints on REMAINING variables\n",
        "- Heuristic 3: Given variable, assign the least constraining value (one that rules out fewest values in remaining vars)\n",
        "- Heuristic 4: Forward checking. Keep track of remaining legal values of unassigned variables. Terminate branch in any unassigned vars have no legal values.\\n\n",
        "Clever Backtracking:\\n\n",
        "- The backjumping method backtracks to the most recent assignment in the conflict set (variables currently making the assignment of our current variable impossible)\\n\n",
        "- Forward checking supplies the conflict set\\n\n",
        "\n",
        "Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good.\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "Min-conflicts:\\n\n",
        "- Start with complete assignment. Randomly choose variable. Set value to value with fewest conflicts with other variables.\n",
        "- Tabu search: keep track of visited states to avoid redundancy\n",
        "- Constraint weighting - can make some constraints more important to concentrate search on those.\n",
        "  - Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment.\\n\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "CSP Constraint Graphs that are trees can be solved quickly (toposort). Just iterate from right to left, fixing arcInc at each step. $O(nd^2)$\\n\n",
        "Cutset conditioning - fix values for certain vars such that remaining vars form a tree. \\n\n",
        "Tree decomp - a transformation of the original graph into a tree where each node in the tree consists of a set of variables\\n\n",
        "We would like to reduce the search space by a factor of d! by breaking the symmetry in assignments. We do this by introducing a symmetry-breaking constraint. For our example, we might impose an arbitrary ordering constraint, A < B < C , that requires the three values to be in alphabetical order. (Previous A = red, B = blue, C = red)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "Consistent assignment - violates no constraints\\n\n",
        "Complete assignmnet - every variable assigned\\n\n",
        "Solution = consistent + complete\\n\n",
        "\n",
        "Algo Structure:\\n\n",
        "- Constraint propagation(inference):\\n\n",
        "  - eliminate possible values for a variable if the value would violate local consistency\n",
        "\n",
        "X->Y is arc-consistent iff for every value x of X, there is some allowed y.\n",
        "To make two variables arc-consistent:\\n\n",
        "- Remove values from tail that don't satisfy arc consistency\n",
        "- If X loses some values, then need to recheck neighbors (recheck arc consistency)\n",
        "- This will detect failure earlier than forward checking\n",
        "\n",
        "Make_Arc_Consistent(i,j):\n",
        "- for each value v on X_i:\n",
        "  - if there is no label on X_j consistent with v, remove v from X_i\\n\n",
        "\n",
        "O(d^2) time\\n\n",
        "\n",
        "AC-3 Insights:\\n\n",
        "1. At each iteration we only need to examine those Xi where >= 1 neighbor of Xi has lost a value in the previous iteration.\\n\n",
        "2. If Xi loses a value bc of arcInc with Yj, dont need to check Xj on next iteration\\n\n",
        "3. Removing a value on Xi can only make Yj arcInc wrt Xi itself. Thus, only need to check that (j, i) is still arc consistent\\n\n",
        "\n",
        "All nodes can be connected to every other node, so each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1), i.e. O(n^2)\\n\n",
        "If there are d values, checking arc (i,j) takes O(d^2) time \\n\n",
        "Each arc (i,j) can only be inserted into the queue d times \\n\n",
        "Worst case complexity: O(n^2d^3)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "401fb30c-3e79-45c1-c80e-e92633036bc6"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "\n",
              "X - set of variables\n",
              "\n",
              "D - set of domains, one for each variable\n",
              "\n",
              "C - set of constraints\n",
              "\n",
              "\n",
              "Unary constraint: one variable (ie $A \n",
              "eq 3$)\n",
              "\n",
              "Binary constraint: two variables (ie $A > B$)\n",
              "\n",
              "Any CSP can be transformed into a binary one.\n",
              "\n",
              "\n",
              "Another way to convert a n-ary CSP to a binary one is the dual graph transformation: create a new graph in which there will be one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables.\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "\n",
              "A single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\n",
              "\n",
              "More formally, $X_i$ is arc-consistent with respect to another variable $X_j$ if for every value in the current domain $D_i$ there is some value in the domain $D_j$ that satisfies the binary constraint on the arc.\n",
              "\n",
              "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",
              "\n",
              "Strongly k-consistent - k-consistent, (k-1)-consistent,...,1-consistent\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "\n",
              "Backtracking Search:\n",
              "\n",
              "- Assign value to first var, then second, then third, etc. and backtrack if we violate constraint\n",
              "- d^n leaves (n variables, each with $\\leq d$ possible values)\n",
              "\n",
              "Improvements:\n",
              "\n",
              "- Heuristic 1: Most constrained value. Choose variable with fewest legal values to explore next\n",
              "- Heuristic 2: Tie breaker among constrained vars. Choose variable with most constraints on REMAINING variables\n",
              "- Heuristic 3: Given variable, assign the least constraining value (one that rules out fewest values in remaining vars)\n",
              "- Heuristic 4: Forward checking. Keep track of remaining legal values of unassigned variables. Terminate branch in any unassigned vars have no legal values.\n",
              "\n",
              "Clever Backtracking:\n",
              "\n",
              "- The backjumping method backtracks to the most recent assignment in the conflict set (variables currently making the assignment of our current variable impossible)\n",
              "\n",
              "- Forward checking supplies the conflict set\n",
              "\n",
              "\n",
              "Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good.\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "\n",
              "Min-conflicts:\n",
              "\n",
              "- Start with complete assignment. Randomly choose variable. Set value to value with fewest conflicts with other variables.\n",
              "- Tabu search: keep track of visited states to avoid redundancy\n",
              "- Constraint weighting - can make some constraints more important to concentrate search on those.\n",
              "  - Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment.\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              "\n",
              "CSP Constraint Graphs that are trees can be solved quickly (toposort). Just iterate from right to left, fixing arcInc at each step. $O(nd^2)$\n",
              "\n",
              "Cutset conditioning - fix values for certain vars such that remaining vars form a tree. \n",
              "\n",
              "Tree decomp - a transformation of the original graph into a tree where each node in the tree consists of a set of variables\n",
              "\n",
              "We would like to reduce the search space by a factor of d! by breaking the symmetry in assignments. We do this by introducing a symmetry-breaking constraint. For our example, we might impose an arbitrary ordering constraint, A < B < C , that requires the three values to be in alphabetical order. (Previous A = red, B = blue, C = red)\n",
              "\n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "Consistent assignment - violates no constraints\n",
              "\n",
              "Complete assignmnet - every variable assigned\n",
              "\n",
              "Solution = consistent + complete\n",
              "\n",
              "\n",
              "Algo Structure:\n",
              "\n",
              "- Constraint propagation(inference):\n",
              "\n",
              "  - eliminate possible values for a variable if the value would violate local consistency\n",
              "\n",
              "X->Y is arc-consistent iff for every value x of X, there is some allowed y.\n",
              "To make two variables arc-consistent:\n",
              "\n",
              "- Remove values from tail that don't satisfy arc consistency\n",
              "- If X loses some values, then need to recheck neighbors (recheck arc consistency)\n",
              "- This will detect failure earlier than forward checking\n",
              "\n",
              "Make_Arc_Consistent(i,j):\n",
              "- for each value v on X_i:\n",
              "  - if there is no label on X_j consistent with v, remove v from X_i\n",
              "\n",
              "\n",
              "O(d^2) time\n",
              "\n",
              "\n",
              "AC-3 Insights:\n",
              "\n",
              "1. At each iteration we only need to examine those Xi where >= 1 neighbor of Xi has lost a value in the previous iteration.\n",
              "\n",
              "2. If Xi loses a value bc of arcInc with Yj, dont need to check Xj on next iteration\n",
              "\n",
              "3. Removing a value on Xi can only make Yj arcInc wrt Xi itself. Thus, only need to check that (j, i) is still arc consistent\n",
              "\n",
              "\n",
              "All nodes can be connected to every other node, so each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1), i.e. O(n^2)\n",
              "\n",
              "If there are d values, checking arc (i,j) takes O(d^2) time \n",
              "\n",
              "Each arc (i,j) can only be inserted into the queue d times \n",
              "\n",
              "Worst case complexity: O(n^2d^3)\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": null,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"Knowledge-based-agent - use process of reasoning over an internal representation of knowledge to decide next action\\n\n",
        "KB:\\n\n",
        "- If a planet is far from its sun then it is cold. Planet(x) and sun(y) and far_from(x,y) -> cold(x)\\n\n",
        "- Axioms - given sentences\n",
        "- Derived sentences - concluded through inference\n",
        "Declarative - Starting with an empty knowledge base, the agent designer can Tell sentences one by one until the agent knows how to operate in its environment\\n\n",
        "Procedural - Program some desired behavior\\n\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\"Models are fixed mathematical abstractions that have a fixed set of truth values for each sentence\\n\n",
        "If a sentance a is in model m: m satisfies a / m is a model of a \\n\n",
        "M(a) = set of all models of a \\n\n",
        "Entailment:\\n\n",
        "A sentence can follow logically from another\\n\\\n",
        "a |= B (a intails B) iff M(a) subset M(B)\\n\n",
        "a is more specific/stronger than B\\n\n",
        "Logical inference:\\n\n",
        "Construct sentences that entail from current KB\\n\n",
        "\n",
        "We want our inference algos to be\\n\n",
        "- truth-preserving (sound): only conclude correct things\\n\n",
        "- complete: conclude all sentences entailed by KB\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"Logic\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "Search for Proof:\\n\n",
        "Initial State: initial KB\\n\n",
        "Actions: All inference rules applied to all sentences that match top half of IR\\n\n",
        "Result: Add bottom sentence to KB\\n\n",
        "Goal: A state that contains the sentence we are trying to prove\\n\n",
        "\n",
        "Resolution: Powerful Inference Rule\\n\n",
        "$(P_{11} \\lor P_{22} \\lor P_{31}) \\land \\lnot P_{22}$ yields $(P_{11} \\lor P_{31})$\\n\n",
        "$(l_1 \\lor ... \\lor l_k) , m )$ yields $(l_1 \\lor ... \\lor l_k)$ without m. \\n\n",
        "\n",
        "CNF:\\n\n",
        "1. Eliminate biconditional by replacing with 2 conditionals\\n\n",
        "2. Eliminate $a \\implies B$ by replacing with $\\lnot a \\lor B$\\n\n",
        "3. Move not inwards (eliminate double negation + apply demogans, distribute ands/ors)\\n\n",
        "\n",
        "Resolution Algo:\\n\n",
        "- Proof by contradiction: Show KB |= a by showing KB and not a is unsatisfiable\\n\n",
        "- Convert $KB \\land \\lnot a$ into CNF\n",
        "- Apply resolution rule to all clauses with complementary literals\n",
        "- If that new clause is not already present, add it to the set\n",
        "- Continue until:\n",
        "  - There are no new clauses that can be added. Case: KB does not entail a\n",
        "  - Two clauses resulve to the empty clause ($P \\land \\lnot P$). Case: KB entails a\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Monotonicity: If KB |= a, then KB and B |= a. Can add to KB without invalidating past inferences.\\n\n",
        "\n",
        "Definite Clause:\\n\n",
        "- Disjunction of literals where exactly one is positive\\n\n",
        "Horn Clause:\\n\n",
        "- Disjuction of literals where at least one is positive\n",
        "- Closed under resolution\\n\n",
        "\n",
        "Both these restrictive CNF forms have linear inference algos.\\n\n",
        "Forward/Backward Chaining:\\n\n",
        "Forward: Generate new conclusions as new percepts come in\\n\n",
        "Backward: Ask querry of KB, then algo tries to priove querry using KB\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "5f101f73-3f79-4a0a-9170-0447e16d490d"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "Knowledge-based-agent - use process of reasoning over an internal representation of knowledge to decide next action\n",
              "\n",
              "KB:\n",
              "\n",
              "- If a planet is far from its sun then it is cold. Planet(x) and sun(y) and far_from(x,y) -> cold(x)\n",
              "\n",
              "- Axioms - given sentences\n",
              "- Derived sentences - concluded through inference\n",
              "Declarative - Starting with an empty knowledge base, the agent designer can Tell sentences one by one until the agent knows how to operate in its environment\n",
              "\n",
              "Procedural - Program some desired behavior\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "Models are fixed mathematical abstractions that have a fixed set of truth values for each sentence\n",
              "\n",
              "If a sentance a is in model m: m satisfies a / m is a model of a \n",
              "\n",
              "M(a) = set of all models of a \n",
              "\n",
              "Entailment:\n",
              "\n",
              "A sentence can follow logically from another\n",
              "a |= B (a intails B) iff M(a) subset M(B)\n",
              "\n",
              "a is more specific/stronger than B\n",
              "\n",
              "Logical inference:\n",
              "\n",
              "Construct sentences that entail from current KB\n",
              "\n",
              "\n",
              "We want our inference algos to be\n",
              "\n",
              "- truth-preserving (sound): only conclude correct things\n",
              "\n",
              "- complete: conclude all sentences entailed by KB\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "Logic\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "Search for Proof:\n",
              "\n",
              "Initial State: initial KB\n",
              "\n",
              "Actions: All inference rules applied to all sentences that match top half of IR\n",
              "\n",
              "Result: Add bottom sentence to KB\n",
              "\n",
              "Goal: A state that contains the sentence we are trying to prove\n",
              "\n",
              "\n",
              "Resolution: Powerful Inference Rule\n",
              "\n",
              "$(P_{11} \\lor P_{22} \\lor P_{31}) \\land \\lnot P_{22}$ yields $(P_{11} \\lor P_{31})$\n",
              "\n",
              "$(l_1 \\lor ... \\lor l_k) , m )$ yields $(l_1 \\lor ... \\lor l_k)$ without m. \n",
              "\n",
              "\n",
              "CNF:\n",
              "\n",
              "1. Eliminate biconditional by replacing with 2 conditionals\n",
              "\n",
              "2. Eliminate $a \\implies B$ by replacing with $\\lnot a \\lor B$\n",
              "\n",
              "3. Move not inwards (eliminate double negation + apply demogans, distribute ands/ors)\n",
              "\n",
              "\n",
              "Resolution Algo:\n",
              "\n",
              "- Proof by contradiction: Show KB |= a by showing KB and not a is unsatisfiable\n",
              "\n",
              "- Convert $KB \\land \\lnot a$ into CNF\n",
              "- Apply resolution rule to all clauses with complementary literals\n",
              "- If that new clause is not already present, add it to the set\n",
              "- Continue until:\n",
              "  - There are no new clauses that can be added. Case: KB does not entail a\n",
              "  - Two clauses resulve to the empty clause ($P \\land \\lnot P$). Case: KB entails a\n",
              "\n",
              "\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "Monotonicity: If KB |= a, then KB and B |= a. Can add to KB without invalidating past inferences.\n",
              "\n",
              "\n",
              "Definite Clause:\n",
              "\n",
              "- Disjunction of literals where exactly one is positive\n",
              "\n",
              "Horn Clause:\n",
              "\n",
              "- Disjuction of literals where at least one is positive\n",
              "- Closed under resolution\n",
              "\n",
              "\n",
              "Both these restrictive CNF forms have linear inference algos.\n",
              "\n",
              "Forward/Backward Chaining:\n",
              "\n",
              "Forward: Generate new conclusions as new percepts come in\n",
              "\n",
              "Backward: Ask querry of KB, then algo tries to priove querry using KB\n",
              "\n",
              "\n",
              "## Module 7 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",
        "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": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 11595
        },
        "id": "T3cm1WV542_a",
        "outputId": "d41e2ad6-53d0-4154-9253-3cd10f31ea60"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "\n",
              "The problem of achieving agreement between our true preferences and the objective we put into the machine is called the value alignment problem: the values or objectives put into the machine must be aligned with those of the human.\n",
              "\n",
              "Ultimately, we want agents that are provably beneficial to humans.\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "\n",
              "Weak AI- machine acts as if it were intelligent\n",
              "\n",
              "Strong AI - machine actually is intelligent\n",
              "\n",
              "The embodied cognition approach claims that it makes no sense to consider the brain separately: cognition takes place within a body, which is embedded in an environment.\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              "\n",
              "Chinese Room:\n",
              "\n",
              "Imagine a human, who understands only English, inside a room that contains a rule book, written in English, and various stacks of paper. Pieces of paper containing indecipherable symbols are slipped under the door to the room. The human follows the instructions in the rule book, finding symbols in the stacks, writing symbols on new pieces of paper, rearranging the stacks, and so on. Eventually, the instructions will cause one or more symbols to be transcribed onto a piece of paper that is passed back to the outside world. From the outside, we see a system that is taking input in the form of Chinese sentences and generating fluent, intelligent Chinese responses.\n",
              "Argues computer doesn't understand Chinese, just like the human.\n",
              "\n",
              "\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",
              "Rational Agents:\n",
              "\n",
              "Agent: anything that perceives its environment through sensors and acts on its environmnet through actuators\n",
              "\n",
              "Percept: agent's perceptual inputs at any given instance\n",
              "\n",
              "Agent function f:P->a maps a sequence of percept vectors P to action a from set A\n",
              "\n",
              "Agent program runs on physical architecture to produce f. Agent = architecture + program\n",
              "\n",
              "Rational Agent: Selects action a to maximize its expected performance measure\n",
              "\n",
              "\n",
              "Fully Observable vs Partially Observable\n",
              "\n",
              "Deterministic vs Non-Deterministic vs Stochastic\n",
              "\n",
              "(Agent action+environment known, environment random, probabalistic outcome for each action)\n",
              "\n",
              "Episodic vs Sequential\n",
              "\n",
              "(Current dec. ind of past actions, current dec. effects future ones)\n",
              "\n",
              "Static vs Dynamic\n",
              "\n",
              "Discrete vs Continuous (#environment states, #actions)\n",
              "\n",
              "\n",
              "Hardest Case:\n",
              "\n",
              "- Continuous\n",
              "- Partially Observable\n",
              "- Stochastic\n",
              "- Multiagent\n",
              "\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",
              "* **Qualia** - intrinsic nature of experiences\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "-Strings, tuples are immutable\n",
              "\n",
              "-Lists are mutable, use y = x[:] to get a (shallow) copy\n",
              "\n",
              "-Dictionaries are unordered & work by hashing, so keys must be immutable\n",
              "\n",
              "-Variable number of non-keyword arguments:\n",
              "\n",
              "  *def func(*args): //unknown # of args\n",
              "\n",
              "  *def func(**kwargs): //dict of args\n",
              "\n",
              "-Class must have __init__\n",
              "\n",
              "-class child_class(parent_class):\n",
              "\n",
              "-Subclass can overwrite parent class methods\n",
              "\n",
              "-List comprehension:\n",
              "\n",
              "li = [3, 6, 2, 7, 1, 9]\n",
              "\n",
              "[elem * 2 for elem in li if elem > 4]\n",
              "\n",
              "-Sets: discard = no error, remove = error\n",
              "\n",
              "-Iterators use memory efficiently\n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Static typing** - Vars can only refer to objects of a declared type, JAVA, type errors caught at compile-time\n",
              "* **Dynamic typing** - Vars come into existence when first assigned, PYTHON, type errors caught at runtime\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "\n",
              "open-loop system: Once agent finds solution, it can ignore precepts (Fully-observable, deterministic)\n",
              "\n",
              "close-loop system: use when change model is incorrect, or nondeterministic environment\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "standardized problem: benchmark for researchers\n",
              "\n",
              "-sokoban puzzle, in which the agent’s goal is to push a number of boxes, scattered about the grid, to designated storage locations, $n*n!/(b!(n-b)!)$ states\n",
              "\n",
              "-grid world\n",
              "\n",
              "-sliding-tile\n",
              "\n",
              "-Donald Knuth factorial/root\n",
              "\n",
              "real-world problem:\n",
              "\n",
              "-route-finding problem (one desitination)\n",
              "\n",
              "-touring problem (must visit all nodes with path less than cost C ie. TSP)\n",
              "\n",
              "-VLSI layout (place/route components on chip)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "Best-first-search:\n",
              "\n",
              "Expand nodes in frontier according to some rule/priority function.\n",
              "\n",
              "Algorithm Measurements:\n",
              "\n",
              "-Completeness: find a solution when there is one, report failure when there isn't\n",
              "\n",
              "-Cost optimality: lowest-cost path?\n",
              "\n",
              "-Time optimality\n",
              "\n",
              "-Space complexity\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "BFS:\n",
              "\n",
              "- Expand to shallowest unexapnded node\n",
              "- Frontier is FIFO queue \n",
              "- Uses early goal test, checking whether a node is a solution as soon as it is generated, rather than the late goal test that best-first search use\n",
              "- $1+b + b^2 + ... + b^d = O(b^d)$ space and time (d = depth of shallowest goal)\n",
              "- Complete if b is finite, optimal if edge-cost = 1\n",
              "\n",
              "Uniform cost search (Dijkstras):\n",
              "\n",
              "- Process frontier from lowest-highest edge cost\n",
              "\n",
              "- C* (cost of optimal sol), $\\epsilon$ (smallest edge cost), $O(b^{1+C^*/\\epsilon})$ space and time\n",
              "- Complete, cost-optimal\n",
              "\n",
              "DFS:\n",
              "\n",
              "- Expand to deepest unexpanded node\n",
              "- Frontier is LIFO queue\n",
              "- Not complete (fails in infinite depth, spaces with loops), complete in finite spaces\n",
              "- $O(b^m)$ time, bad if $m >> d$, good in dense graphs. m is max length of any path in state space\n",
              "- $O(bm)$ space, keep track of nodes on path\n",
              "- Not optimal\n",
              "\n",
              "Bidirectional Search:\n",
              "\n",
              "- simultaneously searches forward from the initial state and backwards from the goal states\n",
              "- Optimal if uniform edge cost and BFS, or uniform cost search from each end\n",
              "- Otherwise, keep track of best solution so far\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "1. States, 2. Initial state, 3. Actions, 4. Transitions $(s, a_i) \\implies s_r$, 5. Path cost: additive, 6. Goal states\n",
              "Solution: sequence of actions from initial state to a goal state\n",
              "\n",
              "Optimal solution: Lowest Path cost\n",
              "\n",
              "\n",
              "Tree search:\n",
              "\n",
              "- Different paths to same node treated as distinct\n",
              "Graph search:\n",
              "\n",
              "- Keep track of states we have visited\n",
              "- Memory intensive\n",
              "\n",
              "\n",
              "Use BFS: possible inf. paths, some solutions have short path\n",
              "\n",
              "Use DFS: space is restricted, many possible solutions with long paths\n",
              "\n",
              "Depth-limited search:\n",
              "\n",
              "- DFS with depth limit (diameter) l\n",
              "- Optimal if l=d, incomplete if l < d, not optimal if l > d\n",
              "- $O(b^d)$ time and space\n",
              "\n",
              "\n",
              "Iterative Deepening Search:\n",
              "\n",
              "- Use depth-limited-search as subroutine, increasing l\n",
              "- Complete (if no inf paths)\n",
              "- Optimal if edge-cost = 1\n",
              "- $O(b^d)$ time, $O(bd)$ space\n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "Heuristic f(n)\n",
              "\n",
              "Greedy BFS:\n",
              "\n",
              "- Process frontier according to f(n)\n",
              "- UCS but with heuristic instead of cost function\n",
              "- Not optimal (tank a big cost in order to have small costs)\n",
              "- Not complete (can get stuck in loops)\n",
              "- O(|V|) space and time\n",
              "\n",
              "A*:\n",
              "\n",
              "- f(n) = g(n) + h(n) \n",
              "- Frontier as priority queue by increasing f(n)\n",
              "\n",
              "Admissibility:\n",
              "\n",
              "- h(n) never overestimates cost to reach goal\n",
              "- Admissibility => optimal\n",
              "- Inadmissible but one cost-optimal path on which h(n) is admissible for all nodes on the path => optimal\n",
              "- Inadmissible but optimal solution has cost C* and second-best has cost C2, if h(n) never overestimates by $>C_2-C^*$ => optimal\n",
              "\n",
              "Consistency:\n",
              "\n",
              "- For every node n and successor n' generated by action a, $h(n) \\leq c(n,a,n') + h(n')$\n",
              "- Triangle inequality\n",
              "- Consistent implies admissible\n",
              "- With a consistent heuristic, the first time we reach a state it will be on an optimal path, so we never have to re-add a state to the frontier\n",
              "\n",
              "\n",
              "Weighted A* provides this guarantee. In bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost, as long as we can find it quickly.\n",
              "\n",
              "\n",
              "Speedy Search\n",
              ":\n",
              "- h(n) = estimated number of actions required to reach a goal, regardless of the cost of those actions\n",
              "- unbounded-cost \n",
              "\n",
              "\n",
              "\n",
              "Memory Tricks:\n",
              "\n",
              "- Reference counts: keep track of how many times we've reached state, remove from reached table if count goes to 0. (ie grid world, only can reach state in 4 ways)\n",
              "- Beam search:\n",
              "  - Limits the size of the frontier. The easiest approach is to keep only the nodes with the best k-scores, discarding any other expanded nodes. \n",
              "\n",
              "- Iterative Deepening A* (IDA*):\n",
              "  - Cutoff is smallest f(n) of any node that exceeded cutoff on previous iteration\n",
              "- Recursive Best First Search (RBFS):\n",
              "  - DFS but keeps track of f-value of best alternate path available from any ancestor of the current node\n",
              "  - If the current node exceeds this limit, the recursion unwinds back to the alternative path\n",
              "  - As the recursion unwinds, RBFS replaces the f-value of each node along the path with a backed-up value (the best f-value of its children)\n",
              "  - RBFS remembers the f-value of the best leaf in the forgotten subtree and can therefore decide whether it’s worth reexpanding the subtree at some later time\n",
              "- Simplified Memory-bounded A* (SMA*):\n",
              "  - Proceeds just like A*, expanding the best leaf until memory is full\n",
              "  - If full, then drops worst leaf node (highest f-value)\n",
              "  - Backs up this f-value in parent, so we known quality of path in subtree should we need to expand it again later\n",
              "  - In bad executions, we can flip-flop between recovering deleted information\n",
              "  - Complete if depth is less than memory size (our solution can fit in memory)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "Effective branching factor: if A* generates N nodes and solution is depth d, then b* is branching factor of uniform tree depth d+1 with N+1 nodes\n",
              "\n",
              "Effective depth: A* reduces tree depth by this constant (compared to uninformed search tree)\n",
              "\n",
              "Dominance:\n",
              "\n",
              "- $h_2(n) \\geq h_1(n)$ for all n, and is better for search\n",
              "- Best heuristic: $h*(n)$ oracle heuristic, dominates all\n",
              "- Worst heuristic: h_{we're already here}(n) = 0, dominated by all\n",
              "\n",
              "Relaxed Problems: \n",
              "\n",
              "- Cost of optimal solution to a relaxed problem is an admissible heuristic for original problem\n",
              "- ie h_{out of place}(n), h_{manhattan dist} in 8-puzzle \n",
              "- Relaxed-problem is supergraph of original problem, since removing restrictions adds edges b/w states\n",
              "- These edges might be \"shortcuts\" in optimal solution in relaxed-problem that we cannot take in original problem\n",
              "\n",
              "\n",
              "If we have collection of admissible heuristics, $h(n) = $ max of all them\n",
              "\n",
              "Disjoint pattern databases:\n",
              "\n",
              "- Store exact solution cost to various subproblems (ie. 8-puzzle with tiles 1-2-3-4)\n",
              "- Take max of all these heuristics\n",
              "- If patterns are disjoint, then can add the heuristics (ie. tiles 1-2-3-4, and tiles 5-6-7-8)\n",
              "\n",
              "Landmarks:\n",
              "\n",
              "- Precompute optimal path to certain states called landmark points\n",
              "- Can also add shortcut edges (precomputed shortest distances between two states)\n",
              "- Differential heuristic: $h_{DH}(n) = max_L |C^*(n,L) - C*(goal, L)|$ is admissible\n",
              "- Precompute shortest path from each vertex to each landmark, and each landmark to goal\n",
              "\n",
              "Metalevel learning:\n",
              "\n",
              "- Learn from algorithm execution (internal state of program) to avoid exploring unpromising subtrees\n",
              "\n",
              "Learning:\n",
              "\n",
              "- Can learn by looking at examples of problem with multiple heuristics, and learning weights to create linear combo from them\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "\n",
              "Perfect information (ie no hidden cards), 2-player, Turn-taking Games\n",
              "\n",
              "MAX moves first\n",
              "\n",
              "Evaluation Function f(n):\n",
              "\n",
              "- Based on static features of board alone\n",
              "- f(n) > 0 MAX is winning in position n\n",
              "- f(n) = 0 tied\n",
              "- f(n) < 0 MIN is winning in position n\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "\n",
              "Minimax Algorithm:\n",
              "\n",
              "- DFS of game tree (nodes are positions, edges are plies)\n",
              "- Leaf nodes have utility values\n",
              "- MAX/MIN alternate levels of tree\n",
              "- MAX chooses node with largest value, MIN chooses node with smallest value\n",
              "- max depth m, b legal moves, $O(b^m)$ time, $O(bm) space\n",
              "Alpha-Beta Pruning:\n",
              "\n",
              "- Can calculate correct minimax algorithm without evaluating parts of tree (pruning)\n",
              "- alpha: MAX's current lower bound on outcome\n",
              "- beta: MIN's current upper bound on outcome\n",
              "- MAX never allows a move that could lead to a worse score than alpha\n",
              "- MIN never allows a move that could lead to a better score than beta\n",
              "\n",
              "Move ordering:\n",
              "\n",
              "- Runtime heavily depends on order you process moves in\n",
              "- Ideal alpha-beta pruning, only need to process $O(b^{m/2})$ nodes, so effective branching factor becomes $\\sqrt(b)$ \n",
              "- Using random move order will result in about $O(b^{3m/4})$ nodes\n",
              "- Can use iterative deepening search. Ply depth of 1, then order moves based on resulting utilities, then ply depth of 2, considering moves in that order, etc.\n",
              "\n",
              "\n",
              "Transposition table: Keeps track of game states and heuristic value of states so we don't have to recompute\n",
              "\n",
              "Type A Strategy: wide but shallow (fixed depth)\n",
              "\n",
              "Type B Strategy: narrow but deep (follow promising moves to end)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "Evaluation Functions:\n",
              "- Estimate expected utility of player when game is in state s\n",
              "- Can use features (ie. # of white pawns, # of white rooks, ...)\n",
              "- Can calculate expected utility based on prior games in this position (P1 won 82% of games in this position)\n",
              "- Can use weighted linear function of features\n",
              "\n",
              "Cutting off search:\n",
              "\n",
              "- Can cut off search after fixed depth, but evaluation function might swing drastically if we had looked one more level\n",
              "- Quiescent positions are when no move that drastically swings evaluation function exists\n",
              "- Quiescence search sometimes restricted to consider certain types of moves (ie capture moves) that will quickly resolve the uncertainties position\n",
              "- Horizon effect: opponent has move that is damaging and unavoidable, but you can stall with filler (sometimes bad) moves, pushing this devestating move over the cutoff horizon\n",
              "- Allow singular extensions: moves that are clearly better than all other moves in a position, even if this pushes us beyond the cutoff\n",
              "\n",
              "Forward Pruning (eliminate some moves):\n",
              "\n",
              "- Beam search: only consider n best moves according to evaluation function of the next states (greedy)\n",
              "- ProbCut: use statistics gained from prior experience to lessen the chance that the best move will be pruned\n",
              "- Late move reduction: works under assumption that move ordering has been done well (moves that appear later in the list of possible moves are less likely to be good moves)\n",
              "  - Reduce the depth to which we search these late moves, thereby saving time\n",
              "\n",
              "Lookup:\n",
              "\n",
              "- Can run retrograde minimax search from every possible position (of endgame), and create policy describing best move\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "Expectiminimax:\n",
              "- Add chance nodes. Value of chance node is expected value of all its children\n",
              "- Slow and expensive to run\n",
              "- Can still prune cleverly. If utilities are bounded between two values, then we can bound the value of a chance node without looking at all its children. \n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "\n",
              "Expected utility = possible utility values weighted by probability\n",
              "\n",
              "A rational agent should choose action that receives the maximum expected utility (MEU)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "\n",
              "Preference Constraints:\n",
              "- ORDERABILITY - agent must prefer A to B, prefer B to A, or be indifferent\n",
              "- TRANSITIVITY\n",
              "- CONTINUITY - If $A > B > C$ then there exists a probability such that the agent is indifferent between getting B and getting A with prob p and C with prob 1-p\n",
              "- SUBSTITUTABILITY - If A ~ B, then $[p, A; 1-p, C] \tilde [p, B; 1-p, C]$\n",
              "- MONOTONICITY - If A > B are only two outcomes of lottery, then the agent prefers lottery that has higher prob for A\n",
              "- DECOMPOSABILITY - compresses 2 lotteries into single one (using MR)\n",
              "\n",
              "Theorem: a utility function exists for any rational agent\n",
              "\n",
              "Value-utility function: value of options matters\n",
              "\n",
              "Ordinal-utility function: only ranking options matters\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "\n",
              "Preference elicitation - presenting choices and gathering preferences\n",
              "\n",
              "Normalized utilities - scale from $u_{\bot} = 0$ to $u_{T} = 1$\n",
              "\n",
              "Standard lottery - [p, u_{T}; 1-p, u_{\bot}]$ \n",
              "\n",
              "\n",
              "Value of a statistical life = $10 million\n",
              "\n",
              "Micromort\n",
              "\n",
              "QALY - quality-adjusted life year\n",
              "\n",
              "EMV - expected monetary value \n",
              "\n",
              "We say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\n",
              "\n",
              "risk-averse - prefer guarenteed payoff that is < EMV\n",
              "\n",
              "risk-seeking - prefer guarenteed payoff that is > EMV\n",
              "\n",
              "Certainty equivalent - amount you accept in place of a lottery\n",
              "\n",
              "Insurance premium - diff b/w certainty equivalent and EMV\n",
              "\n",
              "optimizer’s curse - tendency for the estimated expected utility of the best choice to be too high\n",
              "\n",
              "Certaintly effect - people want certainty\n",
              "\n",
              "Ambiguity aversion - people avoid ambiguity\n",
              "\n",
              "Framing effect - presenting lotteries in different ways yields different preferences (90% survival vs 10% death)\n",
              "\n",
              "Anchoring effect - people like making relative utility judgements instead of absolute\n",
              "\n",
              "\n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Micromort** - 1/10^6 chance of death\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "\n",
              "X - set of variables\n",
              "\n",
              "D - set of domains, one for each variable\n",
              "\n",
              "C - set of constraints\n",
              "\n",
              "\n",
              "Unary constraint: one variable (ie $A \n",
              "eq 3$)\n",
              "\n",
              "Binary constraint: two variables (ie $A > B$)\n",
              "\n",
              "Any CSP can be transformed into a binary one.\n",
              "\n",
              "\n",
              "Another way to convert a n-ary CSP to a binary one is the dual graph transformation: create a new graph in which there will be one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables.\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "\n",
              "A single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\n",
              "\n",
              "More formally, $X_i$ is arc-consistent with respect to another variable $X_j$ if for every value in the current domain $D_i$ there is some value in the domain $D_j$ that satisfies the binary constraint on the arc.\n",
              "\n",
              "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",
              "\n",
              "Strongly k-consistent - k-consistent, (k-1)-consistent,...,1-consistent\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "\n",
              "Backtracking Search:\n",
              "\n",
              "- Assign value to first var, then second, then third, etc. and backtrack if we violate constraint\n",
              "- d^n leaves (n variables, each with $\\leq d$ possible values)\n",
              "\n",
              "Improvements:\n",
              "\n",
              "- Heuristic 1: Most constrained value. Choose variable with fewest legal values to explore next\n",
              "- Heuristic 2: Tie breaker among constrained vars. Choose variable with most constraints on REMAINING variables\n",
              "- Heuristic 3: Given variable, assign the least constraining value (one that rules out fewest values in remaining vars)\n",
              "- Heuristic 4: Forward checking. Keep track of remaining legal values of unassigned variables. Terminate branch in any unassigned vars have no legal values.\n",
              "\n",
              "Clever Backtracking:\n",
              "\n",
              "- The backjumping method backtracks to the most recent assignment in the conflict set (variables currently making the assignment of our current variable impossible)\n",
              "\n",
              "- Forward checking supplies the conflict set\n",
              "\n",
              "\n",
              "Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good.\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "\n",
              "Min-conflicts:\n",
              "\n",
              "- Start with complete assignment. Randomly choose variable. Set value to value with fewest conflicts with other variables.\n",
              "- Tabu search: keep track of visited states to avoid redundancy\n",
              "- Constraint weighting - can make some constraints more important to concentrate search on those.\n",
              "  - Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment.\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              "\n",
              "CSP Constraint Graphs that are trees can be solved quickly (toposort). Just iterate from right to left, fixing arcInc at each step. $O(nd^2)$\n",
              "\n",
              "Cutset conditioning - fix values for certain vars such that remaining vars form a tree. \n",
              "\n",
              "Tree decomp - a transformation of the original graph into a tree where each node in the tree consists of a set of variables\n",
              "\n",
              "We would like to reduce the search space by a factor of d! by breaking the symmetry in assignments. We do this by introducing a symmetry-breaking constraint. For our example, we might impose an arbitrary ordering constraint, A < B < C , that requires the three values to be in alphabetical order. (Previous A = red, B = blue, C = red)\n",
              "\n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "Consistent assignment - violates no constraints\n",
              "\n",
              "Complete assignmnet - every variable assigned\n",
              "\n",
              "Solution = consistent + complete\n",
              "\n",
              "\n",
              "Algo Structure:\n",
              "\n",
              "- Constraint propagation(inference):\n",
              "\n",
              "  - eliminate possible values for a variable if the value would violate local consistency\n",
              "\n",
              "X->Y is arc-consistent iff for every value x of X, there is some allowed y.\n",
              "To make two variables arc-consistent:\n",
              "\n",
              "- Remove values from tail that don't satisfy arc consistency\n",
              "- If X loses some values, then need to recheck neighbors (recheck arc consistency)\n",
              "- This will detect failure earlier than forward checking\n",
              "\n",
              "Make_Arc_Consistent(i,j):\n",
              "- for each value v on X_i:\n",
              "  - if there is no label on X_j consistent with v, remove v from X_i\n",
              "\n",
              "\n",
              "O(d^2) time\n",
              "\n",
              "\n",
              "AC-3 Insights:\n",
              "\n",
              "1. At each iteration we only need to examine those Xi where >= 1 neighbor of Xi has lost a value in the previous iteration.\n",
              "\n",
              "2. If Xi loses a value bc of arcInc with Yj, dont need to check Xj on next iteration\n",
              "\n",
              "3. Removing a value on Xi can only make Yj arcInc wrt Xi itself. Thus, only need to check that (j, i) is still arc consistent\n",
              "\n",
              "\n",
              "All nodes can be connected to every other node, so each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1), i.e. O(n^2)\n",
              "\n",
              "If there are d values, checking arc (i,j) takes O(d^2) time \n",
              "\n",
              "Each arc (i,j) can only be inserted into the queue d times \n",
              "\n",
              "Worst case complexity: O(n^2d^3)\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",
              "Knowledge-based-agent - use process of reasoning over an internal representation of knowledge to decide next action\n",
              "\n",
              "KB:\n",
              "\n",
              "- If a planet is far from its sun then it is cold. Planet(x) and sun(y) and far_from(x,y) -> cold(x)\n",
              "\n",
              "- Axioms - given sentences\n",
              "- Derived sentences - concluded through inference\n",
              "Declarative - Starting with an empty knowledge base, the agent designer can Tell sentences one by one until the agent knows how to operate in its environment\n",
              "\n",
              "Procedural - Program some desired behavior\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "Models are fixed mathematical abstractions that have a fixed set of truth values for each sentence\n",
              "\n",
              "If a sentance a is in model m: m satisfies a / m is a model of a \n",
              "\n",
              "M(a) = set of all models of a \n",
              "\n",
              "Entailment:\n",
              "\n",
              "A sentence can follow logically from another\n",
              "a |= B (a intails B) iff M(a) subset M(B)\n",
              "\n",
              "a is more specific/stronger than B\n",
              "\n",
              "Logical inference:\n",
              "\n",
              "Construct sentences that entail from current KB\n",
              "\n",
              "\n",
              "We want our inference algos to be\n",
              "\n",
              "- truth-preserving (sound): only conclude correct things\n",
              "\n",
              "- complete: conclude all sentences entailed by KB\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "Logic\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "Search for Proof:\n",
              "\n",
              "Initial State: initial KB\n",
              "\n",
              "Actions: All inference rules applied to all sentences that match top half of IR\n",
              "\n",
              "Result: Add bottom sentence to KB\n",
              "\n",
              "Goal: A state that contains the sentence we are trying to prove\n",
              "\n",
              "\n",
              "Resolution: Powerful Inference Rule\n",
              "\n",
              "$(P_{11} \\lor P_{22} \\lor P_{31}) \\land \\lnot P_{22}$ yields $(P_{11} \\lor P_{31})$\n",
              "\n",
              "$(l_1 \\lor ... \\lor l_k) , m )$ yields $(l_1 \\lor ... \\lor l_k)$ without m. \n",
              "\n",
              "\n",
              "CNF:\n",
              "\n",
              "1. Eliminate biconditional by replacing with 2 conditionals\n",
              "\n",
              "2. Eliminate $a \\implies B$ by replacing with $\\lnot a \\lor B$\n",
              "\n",
              "3. Move not inwards (eliminate double negation + apply demogans, distribute ands/ors)\n",
              "\n",
              "\n",
              "Resolution Algo:\n",
              "\n",
              "- Proof by contradiction: Show KB |= a by showing KB and not a is unsatisfiable\n",
              "\n",
              "- Convert $KB \\land \\lnot a$ into CNF\n",
              "- Apply resolution rule to all clauses with complementary literals\n",
              "- If that new clause is not already present, add it to the set\n",
              "- Continue until:\n",
              "  - There are no new clauses that can be added. Case: KB does not entail a\n",
              "  - Two clauses resulve to the empty clause ($P \\land \\lnot P$). Case: KB entails a\n",
              "\n",
              "\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "Monotonicity: If KB |= a, then KB and B |= a. Can add to KB without invalidating past inferences.\n",
              "\n",
              "\n",
              "Definite Clause:\n",
              "\n",
              "- Disjunction of literals where exactly one is positive\n",
              "\n",
              "Horn Clause:\n",
              "\n",
              "- Disjuction of literals where at least one is positive\n",
              "- Closed under resolution\n",
              "\n",
              "\n",
              "Both these restrictive CNF forms have linear inference algos.\n",
              "\n",
              "Forward/Backward Chaining:\n",
              "\n",
              "Forward: Generate new conclusions as new percepts come in\n",
              "\n",
              "Backward: Ask querry of KB, then algo tries to priove querry using KB\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Concept** - definition\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": [
        "9xRbdqDox2zD",
        "46MQLR-Gx8dZ",
        "WHREsHSSyA-h",
        "F3FPMzG9yUls",
        "qVSQhTVSyYYO",
        "RYESi2kMybL8"
      ],
      "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
}
