{
  "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": 19,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "50bcaf51-255b-4577-df5e-ed8ba81878f8"
      },
      "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": 20,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "108820a1-c37d-43c2-d976-25723357d962"
      },
      "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": 21,
      "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": 22,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "- Agents specified by agent function $f: P \\to a$ that maps a sequence of percept vectors $P$ to an action $a \\in A$\n",
        "- Rational agents maximise their performance measure\n",
        "\n",
        "Components of Task Environment\n",
        "- PEAS (Performance, Environment, Actuators, Sensors)\n",
        "- Fully observable\n",
        "- Single vs multi-agent     \n",
        "- Deterministic vs stochastic   \n",
        "- Episodic vs sequential    \n",
        "- Static vs Dynamic   \n",
        "- Discrete vs Continuous   \n",
        "\n",
        "Consequentialism: Evaluate an agent's behaviour via its consequences\n",
        "\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 its environment through sensors and act in an environment via actuators\",\n",
        "\"percept\" : \"The content received by an agent's perceptual inputs\",\n",
        "\"Agent program\" : \"Runs on the physical architecture to produce the agent function $f$\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 23,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 725
        },
        "id": "gYYeNcdM_maE",
        "outputId": "456c2198-aa52-4121-ef79-ae5cf313da25"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              "\n",
              "- Agents specified by agent function $f: P \to a$ that maps a sequence of percept vectors $P$ to an action $a \\in A$\n",
              "- Rational agents maximise their performance measure\n",
              "\n",
              "Components of Task Environment\n",
              "- PEAS (Performance, Environment, Actuators, Sensors)\n",
              "- Fully observable\n",
              "- Single vs multi-agent     \n",
              "- Deterministic vs stochastic   \n",
              "- Episodic vs sequential    \n",
              "- Static vs Dynamic   \n",
              "- Discrete vs Continuous   \n",
              "\n",
              "Consequentialism: Evaluate an agent's behaviour via its consequences\n",
              "\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - Anything that can perceive its environment through sensors and act in an environment via actuators\n",
              "* **Percept** - The content received by an agent's perceptual inputs\n",
              "* **Agent program** - Runs on the physical architecture to produce the agent function $f$\n",
              "* **Etc.** - your definitions here\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 24,
      "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 = \"\"\"\n",
        "\n",
        "|          | Strings | Lists | Tuples |\n",
        "|----------|:---------:|:-------:|:--------:|\n",
        "| **Mutable?** |    No   |  Yes  |   No   |\n",
        "| **Mixed Types allowed?** |    N/A   |  Yes  |   Yes   |\n",
        "\n",
        "**Typing**\n",
        "- All data treated as **objects**\n",
        "- **Strong typing**: Every object has a fixed type (things like `'foo' + 2` are forbbiden)   \n",
        "- **Dynamic typing**: Type of variables evaluated at runtime, functions have no type signatures     \n",
        "- **Duck typing**: Presence of methods (as opposed to the object's type) determines whether we can call it on an objec\n",
        "\n",
        "\n",
        "\n",
        "**Dictionaries**\n",
        "- Unordered (hashmaps underneath -- keys must be **immutable**)\n",
        "- Constant average time add/lookup/update\n",
        "- `defaultdict` initializes nonexistent dictionary values\n",
        "\n",
        "**Functions**\n",
        "- No function overloading in Python\n",
        "- Functions specified by their name alone (function names must be unique)\n",
        "- Use `*args` in function definition to accept variable no. of non-keyword arguments\n",
        "- Use `*kwargs` to do the same for keyword arguments\n",
        "- **Dynamic scoping**: Functions see most current value of variables\n",
        "- Functions are **first-class** objects (functions can be passed as arguments, returned as values, assigned to variables and stored in data structures)\n",
        "\n",
        "**Subclasses**\n",
        "- `class AI_Student(Student):`\n",
        "- Redefining method in parent class: `parentClass.methodName(self, a, b, c)`\n",
        "\n",
        "**Constructors**\n",
        "- `def __init__(self):`\n",
        "\n",
        "**Dunder/Magic Methods**:\n",
        "- Allow user-defined classes to behave like built in types\n",
        "- Eg. implement operator overloading and define how the + operator works by implementing `__add__`\n",
        "\n",
        "**Slicing**\n",
        "- `a[:]` Returns a **shallow copy** of the list `a`\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 25,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 798
        },
        "id": "ydOK__lwWgdp",
        "outputId": "2e5d475a-d3d6-4204-b202-5a1bec59f0e8"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "\n",
              "|          | Strings | Lists | Tuples |\n",
              "|----------|:---------:|:-------:|:--------:|\n",
              "| **Mutable?** |    No   |  Yes  |   No   |\n",
              "| **Mixed Types allowed?** |    N/A   |  Yes  |   Yes   |\n",
              "\n",
              "**Typing**\n",
              "- All data treated as **objects**\n",
              "- **Strong typing**: Every object has a fixed type (things like `'foo' + 2` are forbbiden)   \n",
              "- **Dynamic typing**: Type of variables evaluated at runtime, functions have no type signatures     \n",
              "- **Duck typing**: Presence of methods (as opposed to the object's type) determines whether we can call it on an objec\n",
              "\n",
              "\n",
              "\n",
              "**Dictionaries**\n",
              "- Unordered (hashmaps underneath -- keys must be **immutable**)\n",
              "- Constant average time add/lookup/update\n",
              "- `defaultdict` initializes nonexistent dictionary values\n",
              "\n",
              "**Functions**\n",
              "- No function overloading in Python\n",
              "- Functions specified by their name alone (function names must be unique)\n",
              "- Use `*args` in function definition to accept variable no. of non-keyword arguments\n",
              "- Use `*kwargs` to do the same for keyword arguments\n",
              "- **Dynamic scoping**: Functions see most current value of variables\n",
              "- Functions are **first-class** objects (functions can be passed as arguments, returned as values, assigned to variables and stored in data structures)\n",
              "\n",
              "**Subclasses**\n",
              "- `class AI_Student(Student):`\n",
              "- Redefining method in parent class: `parentClass.methodName(self, a, b, c)`\n",
              "\n",
              "**Constructors**\n",
              "- `def __init__(self):`\n",
              "\n",
              "**Dunder/Magic Methods**:\n",
              "- Allow user-defined classes to behave like built in types\n",
              "- Eg. implement operator overloading and define how the + operator works by implementing `__add__`\n",
              "\n",
              "**Slicing**\n",
              "- `a[:]` Returns a **shallow copy** of the list `a`\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 26,
      "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",
        "Search problems consist of:   \n",
        "- State space     \n",
        "- Initial state     \n",
        "- Goal state(s)      \n",
        "- Set of actions available at each state      \n",
        "- Transition function (specifies result of each action)\n",
        "- Action cost function $c(s, a, s')$ (Cost of performing action $a$ to get from state $s \\to s'$) \n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "- We consider search algorithms that create a **search tree** from the state-space graph, where nodes correspond to states \\\n",
        "and edges are actions. Root of search tree is initial state.   \n",
        "- **Expanding** a node involves seeing what actions are available, \\\n",
        "and **generating** a **child/successor node** for each resulting state\n",
        "\n",
        "**Best-First Search** (Graph Search)     \n",
        "- Expand the node in the frontier that has the minimum $f(n)$ value, where $f(n)$ is the **evaluation function**\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "**BFS**    \n",
        "- Evaluation function $f(n)$ = depth of node    \n",
        "- Expands *shallowest* unexplored node    \n",
        "- Frontier is FIFO queue      \n",
        "- Runtime and space: $O(b^d)$ (exponential)   \n",
        "- Total no. of nodes generated is: $ 1 + b + b^2 + b^3 + \\ldots + b^d = O(b^d)$  (all nodes remain in memory)      \n",
        "- Complete and optimal if cost is 1 per step\n",
        "\n",
        "**DFS** \n",
        "- Expand *deepest* unexpanded node in frontier   \n",
        "- Frontier is stack (LIFO)\n",
        "- Doesn't keep track of visited states (tree search)      \n",
        "- Not optimal! DFS returns the first solution it finds (may not be cheapest)   \n",
        "- Not complete! Fails in infinite-depth spaces      \n",
        "- Runtime: $O(b^m)$ (Bad if no. of actions $m >> b$)   \n",
        "- Space: $O(bm)$ (Longest path has length $m$, and each node has at most $b$ successors)\n",
        "   \n",
        "**Depth-Limited Search**      \n",
        "- DFS with depth limit $l$ (all nodes at depth $l$ treated as if they have no successors)    \n",
        "- Prevents DFS from going down infinite-depth paths       \n",
        "- Runtime: $O(b^l)$          \n",
        "- Space: $O(bl)$   \n",
        "- If $l = d$, then optimal (if $l < d$, incomplete; if $l > d$, not optimal)    \n",
        "\n",
        "**Iterative Deepening Search**     \n",
        "- Repeatedly call Depth-Limited search with increasing $l$ until returns a solution    \n",
        "- Use when search space is larger than memory and depth of solution is unknown     \n",
        "- Complete and optimal (Finds the shallowest goal node)   \n",
        "- Runtime: $O(b^d)$ \n",
        "- Nodes constructed at each step: $$b + (b + b^2) + (b + b^2 + b^3) + \\ldots = db + (d - 1)b + \\ldots + (1)b^d = O(b^d)$$\n",
        "\n",
        "**Bidirectional Search**\n",
        "- Simultaneously search forward from initial state and backward from goal state(s)    \n",
        "- Maintain two frontiers and two evaluation functions, return solution when both frontiers meet    \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "- Nodes in a search tree are data structures of the form $(state, parent, children, action, path cost, depth)$\n",
        "- Nodes are different from states! (States represent physical configurations)     \n",
        "\n",
        "**BFS vs DFS**       \n",
        "- Use DFS if limited memory, search can be fine-tuned quickly, wrong paths can be terminated quickly     \n",
        "- Use BFS if possibly infinite paths, some solutions have short paths  \n",
        "- BFS is complete and optimal\n",
        "- DFS is *not* complete and *not* optimal    \n",
        "\n",
        "- **Graph Search**: Checks if a node has been visited before adding it to queue (maintains set of explored nodes)     \n",
        "- Graph search ensures that repeated states are repeated\n",
        "- Tree search doesn't keep track of visited states, so it requires less memory than graph search\n",
        "\n",
        "- Depth $d$: Depth of least cost solution   \n",
        "- Max depth of search space $m$      \n",
        "- Branching factor $b$: No. of successors of a node\n",
        "\n",
        "|           |    BFS   |    DFS   | Depth-Limited | Iterative Deepening | Bidirectional |\n",
        "|:---------:|:--------:|:--------:|:-------------:|:-------------------:|:---------------:|\n",
        "| **Complete?** |    Yes   |    No    |       No      |         Yes         |      Yes      |\n",
        "|    **Time**   | $O(b^d)$ | $O(b^m)$ |    $O(b^l)$   |       $O(b^d)$      |  $O(b^{d/2})$ |\n",
        "|   **Space**   | $O(b^d)$ |  $O(bm)$ |    $O(bl)$    |       $O(bd)$       |  $O(b^{d/2})$ |\n",
        "|  **Optimal?** |    Yes   |    No    |       No      |         Yes         |      Yes      |\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",
        "\"(3.1) Problem-solving agent\": \"an agent that can formulate a plan via search\",  \n",
        "\"(3.1) Reflex Agent\": \"Agent selects an action only based on *current* precept, ignores percept history\",\n",
        "\"(3.3) Frontier\": \"Set of unexpanded nodes\",\n",
        "\"(3.3) Completeness\": \"Algorithm is guaranteed to return a solution if one exists, and correctly reports failure otherwise\",\n",
        "\"(3.3) Optimality\": \"Solution returned has the lowest path cost among all solutions\",\n",
        "\"(3.4) Graph diameter\": \"Length of longest path in graph\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 27,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "eea0d950-84ea-455b-a171-314c5e2c02e3"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "\n",
              "Search problems consist of:   \n",
              "- State space     \n",
              "- Initial state     \n",
              "- Goal state(s)      \n",
              "- Set of actions available at each state      \n",
              "- Transition function (specifies result of each action)\n",
              "- Action cost function $c(s, a, s')$ (Cost of performing action $a$ to get from state $s \to s'$) \n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "- We consider search algorithms that create a **search tree** from the state-space graph, where nodes correspond to states and edges are actions. Root of search tree is initial state.   \n",
              "- **Expanding** a node involves seeing what actions are available, and **generating** a **child/successor node** for each resulting state\n",
              "\n",
              "**Best-First Search** (Graph Search)     \n",
              "- Expand the node in the frontier that has the minimum $f(n)$ value, where $f(n)$ is the **evaluation function**\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "**BFS**    \n",
              "- Evaluation function $f(n)$ = depth of node    \n",
              "- Expands *shallowest* unexplored node    \n",
              "- Frontier is FIFO queue      \n",
              "- Runtime and space: $O(b^d)$ (exponential)   \n",
              "- Total no. of nodes generated is: $ 1 + b + b^2 + b^3 + \\ldots + b^d = O(b^d)$  (all nodes remain in memory)      \n",
              "- Complete and optimal if cost is 1 per step\n",
              "\n",
              "**DFS** \n",
              "- Expand *deepest* unexpanded node in frontier   \n",
              "- Frontier is stack (LIFO)\n",
              "- Doesn't keep track of visited states (tree search)      \n",
              "- Not optimal! DFS returns the first solution it finds (may not be cheapest)   \n",
              "- Not complete! Fails in infinite-depth spaces      \n",
              "- Runtime: $O(b^m)$ (Bad if no. of actions $m >> b$)   \n",
              "- Space: $O(bm)$ (Longest path has length $m$, and each node has at most $b$ successors)\n",
              "   \n",
              "**Depth-Limited Search**      \n",
              "- DFS with depth limit $l$ (all nodes at depth $l$ treated as if they have no successors)    \n",
              "- Prevents DFS from going down infinite-depth paths       \n",
              "- Runtime: $O(b^l)$          \n",
              "- Space: $O(bl)$   \n",
              "- If $l = d$, then optimal (if $l < d$, incomplete; if $l > d$, not optimal)    \n",
              "\n",
              "**Iterative Deepening Search**     \n",
              "- Repeatedly call Depth-Limited search with increasing $l$ until returns a solution    \n",
              "- Use when search space is larger than memory and depth of solution is unknown     \n",
              "- Complete and optimal (Finds the shallowest goal node)   \n",
              "- Runtime: $O(b^d)$ \n",
              "- Nodes constructed at each step: $$b + (b + b^2) + (b + b^2 + b^3) + \\ldots = db + (d - 1)b + \\ldots + (1)b^d = O(b^d)$$\n",
              "\n",
              "**Bidirectional Search**\n",
              "- Simultaneously search forward from initial state and backward from goal state(s)    \n",
              "- Maintain two frontiers and two evaluation functions, return solution when both frontiers meet    \n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "- Nodes in a search tree are data structures of the form $(state, parent, children, action, path cost, depth)$\n",
              "- Nodes are different from states! (States represent physical configurations)     \n",
              "\n",
              "**BFS vs DFS**       \n",
              "- Use DFS if limited memory, search can be fine-tuned quickly, wrong paths can be terminated quickly     \n",
              "- Use BFS if possibly infinite paths, some solutions have short paths  \n",
              "- BFS is complete and optimal\n",
              "- DFS is *not* complete and *not* optimal    \n",
              "\n",
              "- **Graph Search**: Checks if a node has been visited before adding it to queue (maintains set of explored nodes)     \n",
              "- Graph search ensures that repeated states are repeated\n",
              "- Tree search doesn't keep track of visited states, so it requires less memory than graph search\n",
              "\n",
              "- Depth $d$: Depth of least cost solution   \n",
              "- Max depth of search space $m$      \n",
              "- Branching factor $b$: No. of successors of a node\n",
              "\n",
              "|           |    BFS   |    DFS   | Depth-Limited | Iterative Deepening | Bidirectional |\n",
              "|:---------:|:--------:|:--------:|:-------------:|:-------------------:|:---------------:|\n",
              "| **Complete?** |    Yes   |    No    |       No      |         Yes         |      Yes      |\n",
              "|    **Time**   | $O(b^d)$ | $O(b^m)$ |    $O(b^l)$   |       $O(b^d)$      |  $O(b^{d/2})$ |\n",
              "|   **Space**   | $O(b^d)$ |  $O(bm)$ |    $O(bl)$    |       $O(bd)$       |  $O(b^{d/2})$ |\n",
              "|  **Optimal?** |    Yes   |    No    |       No      |         Yes         |      Yes      |\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **(3.1) problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **(3.1) reflex agent** - Agent selects an action only based on *current* precept, ignores percept history\n",
              "* **(3.3) frontier** - Set of unexpanded nodes\n",
              "* **(3.3) completeness** - Algorithm is guaranteed to return a solution if one exists, and correctly reports failure otherwise\n",
              "* **(3.3) optimality** - Solution returned has the lowest path cost among all solutions\n",
              "* **(3.4) graph diameter** - Length of longest path in graph\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": 37,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "\n",
        "**Dijkstra's / Uniform Cost Search**     \n",
        "- Expand node with lowest path cost $g(n)$ (cost from initial state to node $n$)     \n",
        "- Frontier: priority queue ordered by $g(n)$    \n",
        "- Test if node is goal when it is expanded, not when it is added to frontier        \n",
        "- Updates a node's position in frontier if a cheaper path to the same node is found    \n",
        "- Always enqueues nodes before checking if its a goal (this allows us to prioritise lower cost paths)        \n",
        "- Runtime: $O(b^{1 + floor( C^* / \\epsilon ) })$     \n",
        "- Complete and optimal (first solution it finds is at the front of frontier so has cheapest cost) \n",
        "\n",
        "**Greedy Best-First Search**    \n",
        "- Variant of Best-First Search that expands the node with the lowest $h(n)$, i.e. evaluation function $f(n) = h(n)$      \n",
        "- Not optimal\n",
        "- UCS but with $f(n)$ instead of $g(n)$\n",
        "\n",
        "**A* Search**      \n",
        "- Evaluation function $f(n) = g(n) + h(n)$,     \n",
        "where $g(n)$ = path cost from initial state to node $n$,     \n",
        "$h(n)$ = *estimated* path cost from node $n$ to goal state (heuristic)   \n",
        "- Is complete\n",
        "- Optimal only when heuristic $h(n)$ is consistent \n",
        "\n",
        "- Every consistent heuristic is admissible (but converse does not hold)\n",
        "\n",
        "- Let $C^*$ be the cost of the optimal solution path     \n",
        "- **Surely expanded nodes**: nodes that can be reached from the initial state via a path where $f(n) < C^*$ for every node    \n",
        "- $A^*$ expands all surely expanded nodes  \n",
        "- $A^*$ is **optimally efficient**: Any other algorithm that start from the same intiial state and use the same heuristic, \\\n",
        "must expand all nodes that $A^*$ surely expands\n",
        "\n",
        "- Limitation: No. of nodes expanded by $A*$ can be exponential!\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "- If $h_1, h_2$ are admissible heuristics and $h_2(n) \\geq h_1(n)$ for all $n$, then $h_2$ **dominates** $h_1$    \n",
        "(i.e. $h_2$ is optimistic but more accurate than $h_1$)\n",
        "- Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
        "(Graph for relaxed problem includes more edges which serve as \"shortcuts\" to the goal state)\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"(3.5) Heuristic function $h(n)$\" : \"Estimate cost of the cheapest path from node $n$ to a goal state\",    \n",
        "\"(3.5) Admissible heuristic\": \"Never overestimates actual cost to reach goal\",\n",
        "\"(3.5) Consistent heuristic\": \"$h(n)$ is consistent if for every $n$ and all successors $n'$, $h(n) \\leq c(n, a, n') + h(n')$ (Triangle Inequality)\",\n",
        "\"(3.6) Relaxed problem\": \"Problem with fewer constraints than the original \"\n",
        "}\n",
        "\n",
        " "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 38,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "ee699064-3d8e-4d6b-8d83-7091d661e54f"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "\n",
              "**Dijkstra's / Uniform Cost Search**     \n",
              "- Expand node with lowest path cost $g(n)$ (cost from initial state to node $n$)     \n",
              "- Frontier: priority queue ordered by $g(n)$    \n",
              "- Test if node is goal when it is expanded, not when it is added to frontier        \n",
              "- Updates a node's position in frontier if a cheaper path to the same node is found    \n",
              "- Always enqueues nodes before checking if its a goal (this allows us to prioritise lower cost paths)        \n",
              "- Runtime: $O(b^{1 + floor( C^* / \\epsilon ) })$     \n",
              "- Complete and optimal (first solution it finds is at the front of frontier so has cheapest cost) \n",
              "\n",
              "**Greedy Best-First Search**    \n",
              "- Variant of Best-First Search that expands the node with the lowest $h(n)$, i.e. evaluation function $f(n) = h(n)$      \n",
              "- Not optimal\n",
              "- UCS but with $f(n)$ instead of $g(n)$\n",
              "\n",
              "**A* Search**      \n",
              "- Evaluation function $f(n) = g(n) + h(n)$,     \n",
              "where $g(n)$ = path cost from initial state to node $n$,     \n",
              "$h(n)$ = *estimated* path cost from node $n$ to goal state (heuristic)   \n",
              "- Is complete\n",
              "- Optimal only when heuristic $h(n)$ is consistent \n",
              "\n",
              "- Every consistent heuristic is admissible (but converse does not hold)\n",
              "\n",
              "- Let $C^*$ be the cost of the optimal solution path     \n",
              "- **Surely expanded nodes**: nodes that can be reached from the initial state via a path where $f(n) < C^*$ for every node    \n",
              "- $A^*$ expands all surely expanded nodes  \n",
              "- $A^*$ is **optimally efficient**: Any other algorithm that start from the same intiial state and use the same heuristic, must expand all nodes that $A^*$ surely expands\n",
              "\n",
              "- Limitation: No. of nodes expanded by $A*$ can be exponential!\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "- If $h_1, h_2$ are admissible heuristics and $h_2(n) \\geq h_1(n)$ for all $n$, then $h_2$ **dominates** $h_1$    \n",
              "(i.e. $h_2$ is optimistic but more accurate than $h_1$)\n",
              "- Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
              "(Graph for relaxed problem includes more edges which serve as \"shortcuts\" to the goal state)\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **(3.5) heuristic function $h(n)$** - Estimate cost of the cheapest path from node $n$ to a goal state\n",
              "* **(3.5) admissible heuristic** - Never overestimates actual cost to reach goal\n",
              "* **(3.5) consistent heuristic** - $h(n)$ is consistent if for every $n$ and all successors $n'$, $h(n) \\leq c(n, a, n') + h(n')$ (Triangle Inequality)\n",
              "* **(3.6) relaxed problem** - Problem with fewer constraints than the original \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": 30,
      "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, zero-sum games\n",
        "- Evaluation function $f(n)$ assigns numeric values to nodes in the game tree without reference to path      \n",
        "- $f(n) > 0$ means MAX is winning at state $n$, $f(n) < 0$ means MIN is winning    \n",
        "\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "**Minimax**      \n",
        "Minimax does a depth-first exploration of the game tree. Minimax goes to the leaves and recursively backs up the minimax values up through the tree. \n",
        "Runtime: $O(b^m)$, where $m$ = max depth of tree and $b$ = max no. of egal moves at each ndoe\n",
        "Space complexity: $O(bm)$ is all actions are generated at once\n",
        "\n",
        "Minimax for multi-player games: Return a utility vector for each node.     \n",
        "Backed-up value of node $n$ = utility vector of child that has the highest value for the player who makes a move at $n$ \n",
        "\n",
        "**Alpha-Beta Pruning**      \n",
        "- Alpha = highest already-explored value along the path from MAX's current position to the root (\"at least\")         \n",
        "- Beta = lowest already-explored value along the path from MIN's current position to the root (\"at most\")     \n",
        "- No. of game states is exponential in the game tree's depth     \n",
        "\n",
        "**Move ordering**\n",
        "- Maintain a *transposition table* to cache states' values and to avoid repeated states \n",
        "- **Type A strategy**: Consider all moves that lead to a certain depth in the game tree, then use an evaluation function to estimate states' utilities at that depth   \n",
        "- Type A explores \"wide but shallow\" area of the tree\n",
        "- **Type B strategy**: Ignore moves that result in low valuees, but follow promising paths as deep as possible     \n",
        "- Type B explores \"deep but narrow\" area of the tree\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "\n",
        "- To limit the computation time of Alpha-Beta pruning, we can apply a cut-off function \\\n",
        "that returns TRUE for quiescent state and FALSE otherwise. This **quiescence search** \\\n",
        "ensures that the search continues until we reach a quiescent search.      \n",
        "- **Horizon effect**: An opponent's move that has the potential to cause great damage looms over the horizon, \\\n",
        "but can be delayed via certain moves (eg. checkmate)      \n",
        "- **Singular extensions** can avoid the horizon effect. This involves searching deeper \\\n",
        "in the search tree if a node's value is significantly better than its siblings'. This reduces \\\n",
        "the effective branching factor.     \n",
        "\n",
        "- **Forward pruning** prunes subsequent moves that appear to be bad ones (Type B strategy).  \n",
        "- **Late move reduction** reduces the depth to which we search moves that appear later in the list (assuming they're bad ones).\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "- Game trees for stochastic trees include *chance nodes* alongside MAX & MIN nodes. \n",
        "Chance nodes are like MIN nodes but outcome is uncertain (assume they come along w/ probability distribution). \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "\n",
        "- **Maximum Expected Utility (MEU) Principle**: Rational agent should choose actions that maximise their expected utility         \n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "**Theorem**: Given any preferences satisfying the axioms of utility theory, there exists some real-valued function $U$ such that $$U(A) \\geq U(B) \\Longleftrightarrow A \\succeq B$$\n",
        "$$U([p_1, S_1; \\ldots; p_n, S_n]) = \\sum_{i = 1}^n p_iS_i$$\n",
        "\n",
        "- Positive affine transformations of the form $U'(S) = aU(S) + b$ don't change the utility function\n",
        "- If prizes are deterministic (no probability), only ordinal utility can be determined (i.e. only preferences matter, numbers don't matter)\n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "For a lottery $L = [p, \\$X; 1 - p, \\$Y]$, the **Expected Monetary Value** $EMV(L) = pX + (1 - p)Y$, \\\n",
        "with utility $U(L) = pU(\\$X) + (1 - p)U(\\$Y)$.    \n",
        "Usually, $U(L) < EMV(L)$. \n",
        "\n",
        "$\\hat{EU}(a) = $ *estimated* expected utility\n",
        "\n",
        "- **Preference elicitation**: Presenting a human with the **standard lottery** $[p, A; 1 - p, B]$ and adjusting $p$ such that preferences are indifferent \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"(5.2) Ply\" : \"One move made by one player\",    \n",
        "\"(5.2) Minimax value for a ndoe in a game tree\": \"Utility for MAX for that state, assuming both players play optimally\",\n",
        "\"(5.2) Transpositions\": \"Different permutations of the move sequence that end up in the same state\",\n",
        "\"(5.3) Evaluation function $eval(s, p)$\": \"Gives an *estimate* of the expected utility for player $p$ at state $s$ \",\n",
        "\"(5.3) Quiescent state\": \"A (stable) state where there is no subsequent state that would drastically change the next few moves\",\n",
        "\"(16. 3) Certainty equivalent\": \"The value an agent accepts in place of a lottery\",\n",
        "\"(16.3) Insurance premium\": \"Difference between a lottery's EMV and its certainty equivalent\",\n",
        "\"(16.3) Unbiased esimate\": \"Error between estimate and actual value is 0, i.e. $E(\\hat{EU}(A) - EU(A)) = 0$\",\n",
        "\"(16.3) Optimizer's curse\": \"Estimated expected utility is overly high\",\n",
        "\"(16.3) Certainty effect\": \"People prefer deterministic over stochastic games\",\n",
        "\"(16.3) Anchoring effect\": \"People prefer making relative utility judgements over absolute ones\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 31,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "6dc29c83-7b4a-4881-825b-58f375c61891"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "\n",
              "- Perfect information, zero-sum games\n",
              "- Evaluation function $f(n)$ assigns numeric values to nodes in the game tree without reference to path      \n",
              "- $f(n) > 0$ means MAX is winning at state $n$, $f(n) < 0$ means MIN is winning    \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "\n",
              "**Minimax**      \n",
              "Minimax does a depth-first exploration of the game tree. Minimax goes to the leaves and recursively backs up the minimax values up through the tree. \n",
              "Runtime: $O(b^m)$, where $m$ = max depth of tree and $b$ = max no. of egal moves at each ndoe\n",
              "Space complexity: $O(bm)$ is all actions are generated at once\n",
              "\n",
              "Minimax for multi-player games: Return a utility vector for each node.     \n",
              "Backed-up value of node $n$ = utility vector of child that has the highest value for the player who makes a move at $n$ \n",
              "\n",
              "**Alpha-Beta Pruning**      \n",
              "- Alpha = highest already-explored value along the path from MAX's current position to the root (\"at least\")         \n",
              "- Beta = lowest already-explored value along the path from MIN's current position to the root (\"at most\")     \n",
              "- No. of game states is exponential in the game tree's depth     \n",
              "\n",
              "**Move ordering**\n",
              "- Maintain a *transposition table* to cache states' values and to avoid repeated states \n",
              "- **Type A strategy**: Consider all moves that lead to a certain depth in the game tree, then use an evaluation function to estimate states' utilities at that depth   \n",
              "- Type A explores \"wide but shallow\" area of the tree\n",
              "- **Type B strategy**: Ignore moves that result in low valuees, but follow promising paths as deep as possible     \n",
              "- Type B explores \"deep but narrow\" area of the tree\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "\n",
              "- To limit the computation time of Alpha-Beta pruning, we can apply a cut-off function that returns TRUE for quiescent state and FALSE otherwise. This **quiescence search** ensures that the search continues until we reach a quiescent search.      \n",
              "- **Horizon effect**: An opponent's move that has the potential to cause great damage looms over the horizon, but can be delayed via certain moves (eg. checkmate)      \n",
              "- **Singular extensions** can avoid the horizon effect. This involves searching deeper in the search tree if a node's value is significantly better than its siblings'. This reduces the effective branching factor.     \n",
              "\n",
              "- **Forward pruning** prunes subsequent moves that appear to be bad ones (Type B strategy).  \n",
              "- **Late move reduction** reduces the depth to which we search moves that appear later in the list (assuming they're bad ones).\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "- Game trees for stochastic trees include *chance nodes* alongside MAX & MIN nodes. \n",
              "Chance nodes are like MIN nodes but outcome is uncertain (assume they come along w/ probability distribution). \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "\n",
              "\n",
              "- **Maximum Expected Utility (MEU) Principle**: Rational agent should choose actions that maximise their expected utility         \n",
              "\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "\n",
              "**Theorem**: Given any preferences satisfying the axioms of utility theory, there exists some real-valued function $U$ such that $$U(A) \\geq U(B) \\Longleftrightarrow A \\succeq B$$\n",
              "$$U([p_1, S_1; \\ldots; p_n, S_n]) = \\sum_{i = 1}^n p_iS_i$$\n",
              "\n",
              "- Positive affine transformations of the form $U'(S) = aU(S) + b$ don't change the utility function\n",
              "- If prizes are deterministic (no probability), only ordinal utility can be determined (i.e. only preferences matter, numbers don't matter)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "\n",
              "For a lottery $L = [p, \\$X; 1 - p, \\$Y]$, the **Expected Monetary Value** $EMV(L) = pX + (1 - p)Y$, with utility $U(L) = pU(\\$X) + (1 - p)U(\\$Y)$.    \n",
              "Usually, $U(L) < EMV(L)$. \n",
              "\n",
              "$\\hat{EU}(a) = $ *estimated* expected utility\n",
              "\n",
              "- **Preference elicitation**: Presenting a human with the **standard lottery** $[p, A; 1 - p, B]$ and adjusting $p$ such that preferences are indifferent \n",
              "\n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **(5.2) ply** - One move made by one player\n",
              "* **(5.2) minimax value for a ndoe in a game tree** - Utility for MAX for that state, assuming both players play optimally\n",
              "* **(5.2) transpositions** - Different permutations of the move sequence that end up in the same state\n",
              "* **(5.3) evaluation function $eval(s, p)$** - Gives an *estimate* of the expected utility for player $p$ at state $s$ \n",
              "* **(5.3) quiescent state** - A (stable) state where there is no subsequent state that would drastically change the next few moves\n",
              "* **(16. 3) certainty equivalent** - The value an agent accepts in place of a lottery\n",
              "* **(16.3) insurance premium** - Difference between a lottery's EMV and its certainty equivalent\n",
              "* **(16.3) unbiased esimate** - Error between estimate and actual value is 0, i.e. $E(\\hat{EU}(A) - EU(A)) = 0$\n",
              "* **(16.3) optimizer's curse** - Estimated expected utility is overly high\n",
              "* **(16.3) certainty effect** - People prefer deterministic over stochastic games\n",
              "* **(16.3) anchoring effect** - People prefer making relative utility judgements over absolute ones\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": 32,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"A CSP consists of a variable set $X$, a domain $D_i$ for each variable $X_i$ that specifies allowable values for $X_i$, and a set of constraints $C$.     \n",
        "\n",
        "Constraint graph has nodes = variables, and two nodes share an edge if they partake in the same constraint. \n",
        "Discrete variables: $n$ variables each with domain size $d$ -> $O(d^n)$ complete assignments \n",
        "\n",
        "CSPs as search problems:    \n",
        "- Initial state is empty assignment    \n",
        "- Successor function assigns values to any unassigned variable (if no constraint conflict)    \n",
        "- Goal test: Checks if current assignment si complete     \n",
        "- Path cost: path constant for each step   \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" AC-3 enforces arc consistency for all variables. AC-3 maintains a queue of all edges, \\\n",
        "and pops off an edge $(X_i, X_j)$ at each iteration and makes $X_i$ arc-consistent wrt $X_j$. Every time $X_i$'s domain $D_i$ \\\n",
        "is changed,  all other edges incident to $X_i$ are added to the queue. We do this since the change in $D_i$ might cause\n",
        "reductions in $D_k$. If $D_i$ becomes empty, then there is no consistent solution and AC-3 returns failure. \n",
        "\n",
        "Runtime: $O(cd^3)$, where $d$ = max domain size, $c$ = no. of edges\n",
        "Each arc inserted into queue at most $d$ times and checking consistency of an arc takes $O(d^2)$ time\n",
        "\n",
        "To make a CSP strongly n-consistent, choose a consistent value for $X_1$, then $X_2$, etc. \n",
        "(we can do this since its 1-consistent, 2-consistent, etc.)\n",
        "For each $X_i$, we search through $d$ values to find a value consistent with the other $n - 1$ variables, runtime is $O(n^2d)$\n",
        "\n",
        "Constraint satisfaction is NP-Complete in general.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "Backtracking search selects an unassigned variable, \\\n",
        "tries all values in that variables' domain and for each value \\\n",
        "recursively examines whether it belongs in a solution where all variables are \\\n",
        "assigned. If yes, the solution is returned, else the assignemnt is undone \\\n",
        "and the next value is attemped. (If all values fail, return failure.)     \n",
        "\n",
        "\n",
        "Forward checking establishes arc consistency for a variable $X$. When $X$ is assigned, \\\n",
        "for each unassigned variable $Y$ where $(X, Y)$ is a constraint, remove any values from $Y$'s domain \\\n",
        "that are inconsistent with $X$'s assigned value. \n",
        "(Forward checking facilitates using MRV heuristic to choose variables, but it \\\n",
        "doesn't detect all inconsistencies.)\n",
        "(Forward-checking search removes the need to do backjumping, since it removes \\\n",
        "inconsistent values from $Y$'s domain. \n",
        "\n",
        "MAC algorithm (Maintaining Arc Consistency): After $X_i$ is assigned, call AC-3, \\\n",
        "but only enqueue arcs $(X_j, X_i)$ where $X_j$ are unassigned neighbours of $X_i$. \\\n",
        "Then, backtrack if any variable's domain is $\\varemptyset$. MAC is more powerful \\\n",
        "than forward checking, since FC doesn't recursively propagate constraints when \\\n",
        "a variable's domain changes. \n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "Conflict-directed backjumping: For the current variable $X_j$ and its conflict set $conf(X_j)$, if every value for $X_j$ fails, backjump to the most recent variable $X_i$ in \\\n",
        "$conf(X_j)$ and set $conf(X_i) \\leftarrow conf(X_i) \\cup conf(X_j) \\setminus \\{X_i\\}$\n",
        "(Conflict set for $X_i$ is the set of preceding variables, along with any subsequent variables that caused $X_i$ to have no solution)\n",
        "\n",
        "Connected components of constraint graph correspond to subproblems of the CSP. \\\n",
        "If each CC has $c$ variables ($c$ is a constant where $c \\leq n$), then there are $n/c$ subproblems \\\n",
        "which each take $O(d^c)$ work to solve, where $d$ = size of each variable's domain. Then, the total work \\\n",
        "to solve the CSP is $O(d^c n/c)$, which is **linear** in the no. of variables. \\\n",
        "Without the decomposition, the total work is $O(d^n)$, which is exponential in $n$.                    \n",
        "\n",
        "**Lemma**: *Any constriant graph which is a **tree** can be solved in **linear** time (wrt the no. of variables)*            \n",
        "\n",
        "**Proof**: Pick any arbitrary node to be the root of the tree, then topologically sort the tree. Since a tree w/ $n$ nodes \\\n",
        "has $n - 1$ edges, we can make the tree directed arc-consistent in $O(n)$ steps, and at each step, we compare at most $d$ \\\n",
        "domain values for a pair of variables, so the total time is $O(nd^2)$, which is linear in $n$. \n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "Cutset conditioning algorithm:         \n",
        "1. Choose a subset $S$ of nodes in the constriant graph such that the graph becomes a tree after $S$ is removed. (Call $S$ a **cycle cutset.**)     \n",
        "2. For each assignemnt of values to variables in $S$ that satisfies all constraints on $S$, remove from other variables' domains values that are inconsistent with $S$'s assignment.     \n",
        "If the remaining CSP has a solution, return it along w/ the assignment for $S$.       \n",
        "Runtime: $O(d^c \\cdot (n - c)d^2)$, where $c$ = size of cycle cutset, $d$ = domain size for each variable      \n",
        "(Need to try $d^c$ combinations of values for variables in $S$, and for each combination we need to solve a tree problem involving $n - c$ variables)      \n",
        "\n",
        "**Tree decomposition**: Convert constraint graph into a tree, where each node in the tree is a set of variables s.t. :        \n",
        "- Each varible in the original CSP must appear in at least one tree node     \n",
        "- If $(X, Y)$ is a constraint in the original CSP, then $X$ and $Y$ must appear together (w/ the constraint) in a tree node    \n",
        "- If a variable appears in two tree nodes, it must appear in every node along the path connecting the two tree nodes    \n",
        "(i.e. a variable in a tree node must share the same value as the corresponding variable in the adjacent tree node) \n",
        "Runtime: After we perform tree decomposition, solving the problem takes $O(nd^2)$, where $n$ = no. of tree nodes, $d$ = max domain size of a tree node (where the domain is sets of tuples of variables)\n",
        "\n",
        "If a graph has tree width $w$, then we can solve the problem in $O(nd^{w + 1})$ if we choose the tree decomposition that has width $w$.     \n",
        "That is, if the constraint graph's tree width is finite, then we can solve it in polynomial time. \n",
        "\n",
        "**Lemma**: Whenever there exists a size $c$ cycle-cutset, there is also a tree width of size $w < c + 1$.      \n",
        "(Tree decomposition is quicker than cycle-cutset conditioning)    \n",
        "(But tree decomposition requires memory exponential in $w$, while cutset conditioning can be done in linear memory.)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "\n",
        "\n",
        "Backtracking search is a DFS that chooses values for one variable at a time, and backtracks when there are no values left to assign.    \n",
        "Runtime of AC-3 is $O(n^2d^3)$     \n",
        "(A complete graph has $O(n^2)$ edges and if each variable's domain size is $d$, maintaining arc consistency for the arc $(i, j)$ takes $O(d^2)$ time. \n",
        "Since each arc can only be inserted into the queue at most $d$ times, overall runtime is $O(n^2d^3)$.)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "# Chapter 6.1\n",
        "\"(6.1) Consistent assignment\" : \"Assignment that respects all constraints\",    \n",
        "\"(6.1) Complete assignment\": \"Assignment that assigns a value to each variable\",\n",
        "\"(6.1) Partial assignment\": \"Assignment where some variables are left unassigned\",\n",
        "\"(6.1) Partial solution\": \"A partial assignment that respects all constraints\",\n",
        "\"(6.1) Global constraint\": \"Constraint involving an arbitrary no. of variables\",\n",
        "\"(6.1) Constriant graph\": \"Nodes = variables, two variables that partake in the same constraint are linked by an edge\",\n",
        "\"(6.1) Binary CSP\": \"All constraints are either unary or binary\",\n",
        "\"(6.1) Linear Programming problems\": \"Continuous-domain CSPs where constraints are linear equalities/inequalities\",\n",
        "\"(6.1) Cryptarithmetic\": \"Arithmetic puzzles where the unknowns are letters that each represent a digit\",\n",
        "\"(6.1) Dual graph (Converting n-ary CSP -> binary CSP)\": \"New constraint graph where nodes = constraints and two nodes share an edge if two constraints share variables\",\n",
        "\"(6.1) Constrained optimization problem\": \"CSPs with preference constraints that require optimizing an objective function\",\n",
        "\n",
        "# Chapter 6.2\n",
        "\"(6.2) Node consistency\": \"All values in variable's (node) domain satisfy unary constraints\",\n",
        "\"(6.2) Arc consistency\": \"All values in variable's domain satisfy binary constraints\",\n",
        "\"(6.2) Path consistency\": \"$k$-Consistency with $k = 3$\",\n",
        "\"(6.2) $k$-consistency\": \"For any $k-1$ variables with a consistent assignment, a consistent value can be assigned to the $k$-th variable\",\n",
        "\"(6.2) Strongly k-consistent\": \"k consistent, k-1 consistent, ..., 1-consistent\",\n",
        "\"(6.2) Atmost constraint\": \"Constraint on resources available\",\n",
        "\"(6.2) Bounds propagation\": \"Represent domain of variables using upper/lower bounds, and change bounds as necessary\",\n",
        "\"(6.2) Bounds consistency\": \"For each $X$ whose values are bounded, for every other $Y$, $Y$ has a value that satisfies constraint $(X, Y)$\",\n",
        "\n",
        "# Chapter 6.3\n",
        "\"(6.3) Commutativity\": \"Order in which variables are assigned doesn't matter\",\n",
        "\"(6.3) Minimum Remaining Value (MRV) heuristic\": \"choose the variable with the fewest legal values, so that we can detect failure asap and prune the search tree\",\n",
        "\"(6.3) Degree heuristic\": \"choose the variable that partakes in the largest no. of constraints \\\n",
        "with other unassigned variables\",\n",
        "\"(6.3) Least constraining value heuristic\": \"Choose the value in a variable's domain that eliminates the fewest values for neighbouring nodes in constraint graph (fail last)\",\n",
        "\"(6.3) Chronological backtracking\": \"Examine the most recent decision point when backtracking\",\n",
        "\"(6.3) Conflict set for a variable\": \"Keep track of all assignments that are inconsistent with a value for $X$\",\n",
        "\"(6.3) Backjumping\": \"Backtrack to latest assignment in conflict set\",\n",
        "\"(6.3) No-good\": \"The smallest subset of variables (along with their values) from the conflict set that results in no solution\",\n",
        "\"(6.3) Constraint learning\": \"Keeping track of no-goods and forbidding such assignments in order to avoid running into them again\",\n",
        "\n",
        "# Chapter 6.4\n",
        "\"(6.4) Min-conflicts heuristic\": \"Assign a value to a conflicted variable that results in the min no. of conflicts w/ other variables\",\n",
        "\"(6.4) Plateau search\": \"Move sideways to another state with the same score\",\n",
        "\"(6.4) Tabu search\": \"Maintain a small list of recently visited states and prevent the algo. from re-visiting those states\",\n",
        "\"(6.4) Constraint weighting\": \"Weight constraints equally, then iteratively change a variable/value pair that minimizes the total weight of all violated constraints\",\n",
        "\"(6.4) Directional Arc Consistency (DAC)\": \"Ordered variables $X_1, X_2, \\ldots, X_n$ satisfy DAC iff every $X_i$ is arc-consistent with every $X_j$ ($j > i$)\",\n",
        "\n",
        "# Chapter 6.5\n",
        "\"(6.5) Tree width of a graph's tree decomposition\": \"Size of largest tree node - 1\", \n",
        "\"(6.5) Tree width of a graph\": \"Minimum tree width for all of the graph's tree decompositions\",\n",
        "\n",
        "\n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 33,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "1f2fdcd5-c628-4c62-bcb4-04448762898b"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "A CSP consists of a variable set $X$, a domain $D_i$ for each variable $X_i$ that specifies allowable values for $X_i$, and a set of constraints $C$.     \n",
              "\n",
              "Constraint graph has nodes = variables, and two nodes share an edge if they partake in the same constraint. \n",
              "Discrete variables: $n$ variables each with domain size $d$ -> $O(d^n)$ complete assignments \n",
              "\n",
              "CSPs as search problems:    \n",
              "- Initial state is empty assignment    \n",
              "- Successor function assigns values to any unassigned variable (if no constraint conflict)    \n",
              "- Goal test: Checks if current assignment si complete     \n",
              "- Path cost: path constant for each step   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " AC-3 enforces arc consistency for all variables. AC-3 maintains a queue of all edges, and pops off an edge $(X_i, X_j)$ at each iteration and makes $X_i$ arc-consistent wrt $X_j$. Every time $X_i$'s domain $D_i$ is changed,  all other edges incident to $X_i$ are added to the queue. We do this since the change in $D_i$ might cause\n",
              "reductions in $D_k$. If $D_i$ becomes empty, then there is no consistent solution and AC-3 returns failure. \n",
              "\n",
              "Runtime: $O(cd^3)$, where $d$ = max domain size, $c$ = no. of edges\n",
              "Each arc inserted into queue at most $d$ times and checking consistency of an arc takes $O(d^2)$ time\n",
              "\n",
              "To make a CSP strongly n-consistent, choose a consistent value for $X_1$, then $X_2$, etc. \n",
              "(we can do this since its 1-consistent, 2-consistent, etc.)\n",
              "For each $X_i$, we search through $d$ values to find a value consistent with the other $n - 1$ variables, runtime is $O(n^2d)$\n",
              "\n",
              "Constraint satisfaction is NP-Complete in general.\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " \n",
              "Backtracking search selects an unassigned variable, tries all values in that variables' domain and for each value recursively examines whether it belongs in a solution where all variables are assigned. If yes, the solution is returned, else the assignemnt is undone and the next value is attemped. (If all values fail, return failure.)     \n",
              "\n",
              "\n",
              "Forward checking establishes arc consistency for a variable $X$. When $X$ is assigned, for each unassigned variable $Y$ where $(X, Y)$ is a constraint, remove any values from $Y$'s domain that are inconsistent with $X$'s assigned value. \n",
              "(Forward checking facilitates using MRV heuristic to choose variables, but it doesn't detect all inconsistencies.)\n",
              "(Forward-checking search removes the need to do backjumping, since it removes inconsistent values from $Y$'s domain. \n",
              "\n",
              "MAC algorithm (Maintaining Arc Consistency): After $X_i$ is assigned, call AC-3, but only enqueue arcs $(X_j, X_i)$ where $X_j$ are unassigned neighbours of $X_i$. Then, backtrack if any variable's domain is $\u000baremptyset$. MAC is more powerful than forward checking, since FC doesn't recursively propagate constraints when a variable's domain changes. \n",
              "\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "\n",
              "Conflict-directed backjumping: For the current variable $X_j$ and its conflict set $conf(X_j)$, if every value for $X_j$ fails, backjump to the most recent variable $X_i$ in $conf(X_j)$ and set $conf(X_i) \\leftarrow conf(X_i) \\cup conf(X_j) \\setminus \\{X_i\\}$\n",
              "(Conflict set for $X_i$ is the set of preceding variables, along with any subsequent variables that caused $X_i$ to have no solution)\n",
              "\n",
              "Connected components of constraint graph correspond to subproblems of the CSP. If each CC has $c$ variables ($c$ is a constant where $c \\leq n$), then there are $n/c$ subproblems which each take $O(d^c)$ work to solve, where $d$ = size of each variable's domain. Then, the total work to solve the CSP is $O(d^c n/c)$, which is **linear** in the no. of variables. Without the decomposition, the total work is $O(d^n)$, which is exponential in $n$.                    \n",
              "\n",
              "**Lemma**: *Any constriant graph which is a **tree** can be solved in **linear** time (wrt the no. of variables)*            \n",
              "\n",
              "**Proof**: Pick any arbitrary node to be the root of the tree, then topologically sort the tree. Since a tree w/ $n$ nodes has $n - 1$ edges, we can make the tree directed arc-consistent in $O(n)$ steps, and at each step, we compare at most $d$ domain values for a pair of variables, so the total time is $O(nd^2)$, which is linear in $n$. \n",
              "\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              "\n",
              "Cutset conditioning algorithm:         \n",
              "1. Choose a subset $S$ of nodes in the constriant graph such that the graph becomes a tree after $S$ is removed. (Call $S$ a **cycle cutset.**)     \n",
              "2. For each assignemnt of values to variables in $S$ that satisfies all constraints on $S$, remove from other variables' domains values that are inconsistent with $S$'s assignment.     \n",
              "If the remaining CSP has a solution, return it along w/ the assignment for $S$.       \n",
              "Runtime: $O(d^c \\cdot (n - c)d^2)$, where $c$ = size of cycle cutset, $d$ = domain size for each variable      \n",
              "(Need to try $d^c$ combinations of values for variables in $S$, and for each combination we need to solve a tree problem involving $n - c$ variables)      \n",
              "\n",
              "**Tree decomposition**: Convert constraint graph into a tree, where each node in the tree is a set of variables s.t. :        \n",
              "- Each varible in the original CSP must appear in at least one tree node     \n",
              "- If $(X, Y)$ is a constraint in the original CSP, then $X$ and $Y$ must appear together (w/ the constraint) in a tree node    \n",
              "- If a variable appears in two tree nodes, it must appear in every node along the path connecting the two tree nodes    \n",
              "(i.e. a variable in a tree node must share the same value as the corresponding variable in the adjacent tree node) \n",
              "Runtime: After we perform tree decomposition, solving the problem takes $O(nd^2)$, where $n$ = no. of tree nodes, $d$ = max domain size of a tree node (where the domain is sets of tuples of variables)\n",
              "\n",
              "If a graph has tree width $w$, then we can solve the problem in $O(nd^{w + 1})$ if we choose the tree decomposition that has width $w$.     \n",
              "That is, if the constraint graph's tree width is finite, then we can solve it in polynomial time. \n",
              "\n",
              "**Lemma**: Whenever there exists a size $c$ cycle-cutset, there is also a tree width of size $w < c + 1$.      \n",
              "(Tree decomposition is quicker than cycle-cutset conditioning)    \n",
              "(But tree decomposition requires memory exponential in $w$, while cutset conditioning can be done in linear memory.)\n",
              "\n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "\n",
              "\n",
              "Backtracking search is a DFS that chooses values for one variable at a time, and backtracks when there are no values left to assign.    \n",
              "Runtime of AC-3 is $O(n^2d^3)$     \n",
              "(A complete graph has $O(n^2)$ edges and if each variable's domain size is $d$, maintaining arc consistency for the arc $(i, j)$ takes $O(d^2)$ time. \n",
              "Since each arc can only be inserted into the queue at most $d$ times, overall runtime is $O(n^2d^3)$.)\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **(6.1) consistent assignment** - Assignment that respects all constraints\n",
              "* **(6.1) complete assignment** - Assignment that assigns a value to each variable\n",
              "* **(6.1) partial assignment** - Assignment where some variables are left unassigned\n",
              "* **(6.1) partial solution** - A partial assignment that respects all constraints\n",
              "* **(6.1) global constraint** - Constraint involving an arbitrary no. of variables\n",
              "* **(6.1) constriant graph** - Nodes = variables, two variables that partake in the same constraint are linked by an edge\n",
              "* **(6.1) binary csp** - All constraints are either unary or binary\n",
              "* **(6.1) linear programming problems** - Continuous-domain CSPs where constraints are linear equalities/inequalities\n",
              "* **(6.1) cryptarithmetic** - Arithmetic puzzles where the unknowns are letters that each represent a digit\n",
              "* **(6.1) dual graph (converting n-ary csp -> binary csp)** - New constraint graph where nodes = constraints and two nodes share an edge if two constraints share variables\n",
              "* **(6.1) constrained optimization problem** - CSPs with preference constraints that require optimizing an objective function\n",
              "* **(6.2) node consistency** - All values in variable's (node) domain satisfy unary constraints\n",
              "* **(6.2) arc consistency** - All values in variable's domain satisfy binary constraints\n",
              "* **(6.2) path consistency** - $k$-Consistency with $k = 3$\n",
              "* **(6.2) $k$-consistency** - For any $k-1$ variables with a consistent assignment, a consistent value can be assigned to the $k$-th variable\n",
              "* **(6.2) strongly k-consistent** - k consistent, k-1 consistent, ..., 1-consistent\n",
              "* **(6.2) atmost constraint** - Constraint on resources available\n",
              "* **(6.2) bounds propagation** - Represent domain of variables using upper/lower bounds, and change bounds as necessary\n",
              "* **(6.2) bounds consistency** - For each $X$ whose values are bounded, for every other $Y$, $Y$ has a value that satisfies constraint $(X, Y)$\n",
              "* **(6.3) commutativity** - Order in which variables are assigned doesn't matter\n",
              "* **(6.3) minimum remaining value (mrv) heuristic** - choose the variable with the fewest legal values, so that we can detect failure asap and prune the search tree\n",
              "* **(6.3) degree heuristic** - choose the variable that partakes in the largest no. of constraints with other unassigned variables\n",
              "* **(6.3) least constraining value heuristic** - Choose the value in a variable's domain that eliminates the fewest values for neighbouring nodes in constraint graph (fail last)\n",
              "* **(6.3) chronological backtracking** - Examine the most recent decision point when backtracking\n",
              "* **(6.3) conflict set for a variable** - Keep track of all assignments that are inconsistent with a value for $X$\n",
              "* **(6.3) backjumping** - Backtrack to latest assignment in conflict set\n",
              "* **(6.3) no-good** - The smallest subset of variables (along with their values) from the conflict set that results in no solution\n",
              "* **(6.3) constraint learning** - Keeping track of no-goods and forbidding such assignments in order to avoid running into them again\n",
              "* **(6.4) min-conflicts heuristic** - Assign a value to a conflicted variable that results in the min no. of conflicts w/ other variables\n",
              "* **(6.4) plateau search** - Move sideways to another state with the same score\n",
              "* **(6.4) tabu search** - Maintain a small list of recently visited states and prevent the algo. from re-visiting those states\n",
              "* **(6.4) constraint weighting** - Weight constraints equally, then iteratively change a variable/value pair that minimizes the total weight of all violated constraints\n",
              "* **(6.4) directional arc consistency (dac)** - Ordered variables $X_1, X_2, \\ldots, X_n$ satisfy DAC iff every $X_i$ is arc-consistent with every $X_j$ ($j > i$)\n",
              "* **(6.5) tree width of a graph's tree decomposition** - Size of largest tree node - 1\n",
              "* **(6.5) tree width of a graph** - Minimum tree width for all of the graph's tree decompositions\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": 34,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "**Propositional Logic**\n",
        "- Defines the **semantics** (meaning) of a sentence, and the semantics defines the truth of a sentence wrt a possible world (**model**)\n",
        "- If sentence $a$ is true in model $m$, say that $m$ satisfies $a$ or $m$ is a model of $a$\n",
        "- Let $M(a)$ denote the set of all models of $a$\n",
        "\n",
        "**Logical Entailment**\n",
        "- $a$ entails $b$ means sentence $a$ follows logically from $b$\n",
        "- Write $a \\models b$ to denote $a$ entails $b$\n",
        "- By definition, $a \\models b \\Longleftrightarrow M(a) \\subseteq M(b)$ (i.e. $a$ is more specific than $b$ and rules out more possible worlds)\n",
        "- If inference algorithm $i$ concludes that $a$ is true, write $KB ⊢_i a$ to denote that $a$ is derived from $KB$ by $i$\n",
        "\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "- Sentences $a$ and $b$ are **logically equivalent** if they are true in the same set of models (i.e. they entail each other)\n",
        "- Write $a \\equiv b$ \n",
        "- By definition, $a \\equiv b \\Longleftrightarrow a \\models b \\wedge b \\models a$ \n",
        "\n",
        "- **Monotonicity**: If $KB \\models a$ then $KB \\wedge b \\models a$ (i.e. we can add sentences to the KB without invalidating previously inferred sentences)\n",
        "- **Monotonicity implies Soundness*\n",
        "\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "Search algorithms can be used to find a sequence of steps that constitute a proof:    \n",
        "- Initial state: Initial Knowledge Base     \n",
        "- Actions: All inference rules applied to the sentence matching the top half of the inference rule     \n",
        "- Result: Add the sentence in the bottom of the inference rule    \n",
        "- Goal: A state containing the sentence we wish to prove \n",
        "\n",
        "**Converting sentences into CNF** \n",
        "1. Eliminate $\\Longleftrightarrow$, replace $a \\Longleftrightarrow b$ with $(a \\Longleftrightarrow b) \\wedge (b \\Longleftrightarrow a)$     \n",
        "2. Eliminate $\\Rightarrow$, replace $a \\Rightarrow b$ with $¬ a ~v ~b$\n",
        "3. Move ¬ inwards and apply De Morgan's \n",
        "4. Apply distributivity law to distribute v over $\\wedge$ when possible (i.e want to form ANDs of ORs)     \n",
        "\n",
        "\n",
        "**Resolution Algorithm**     \n",
        "- To show $KB \\models a$, we show that $KB \\wedge ¬a$ is unsatisfiable \n",
        "1.) Convert $KB \\wedge ¬a$ into CNF \n",
        "2.) Apply resolution rule to resulting clauses, i.e. reslve every pair that contains complementary literals to produce a new clause\n",
        "3.) Add new clause to the sentence if it is not already present \n",
        "4.) Continue until either:   \n",
        "- there are no new clauses that can be added (i.e. KB doesn't entail $a$)\n",
        "- Two contradictory unit clauses resolve to yield the empty clause (i.e. KB entails $a$)\n",
        "\n",
        "**Definite clause**\n",
        "- Disjunction of literals where *exactly* one is positive\"\n",
        "\n",
        "**Horn Clause**\n",
        "- Disjunction of literals where at most one is positive (includes definitive clauses and **goal clauses**, which are clauses with no positive literals)\n",
        "- Closed under resolution\n",
        "\n",
        "**KBs with only definite clauses**\n",
        "- Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is one positive literal\n",
        "- Inference with Horn clauses cam be done through forward/backward-chaining algorithms     \n",
        "- Deciding entailment with Horn clauses can be done in linear time (wrt the KB's size)\n",
        "\n",
        "**Forward Chaining** (Data-driven reasoning)   \n",
        "- Start with positive literals (known facts) in the KB, and if all premises of an implication are known, its conclusion is added to the set of known facts. \n",
        "Continue until no further inferences can be made.   \n",
        "- Sound (every inference is an application of Modus Ponens)   \n",
        "- Complete (every entailed atomic sentence is derived)\n",
        "\n",
        "**Backward Chaining** (Goal-directed reasoning)\n",
        "- Work backwards from a query $q$, find implications in the KB whose conclusion is $q$. If all premises of an implication can be proven true, then $q$ is true. \n",
        "\n",
        "\n",
        "**Resolution Closure $RC(S)$**    \n",
        "- $RC(S)$ is the set of all clauses derivable via repeatedly applying the resolution rule to clauses in $S$ (or their deriatives)\n",
        "\n",
        "**Ground Resolution Theorem**   \n",
        "- **Theorem**: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"(7.1) Knowledge Base\" : \"Sentences written according to the **syntax** of a knowledge representation language\",    \n",
        "\"(7.1) Axiom\": \"Sentence in a KB taken as given (not derived from other sentences)\",\n",
        "\"(7.3) Models\": \"Fixed set of truth values for each sentence in a KB\",\n",
        "\"(7.3) Logical Inference\": \"Process of applying entailment to sentences to derive conclusions\",\n",
        "\"(7.3) Soundness/Truth-Preserving\": \"An inference algorithm is sound if it only derives entailed sentences\",\n",
        "\"(7.3) Completeness\": \"An inference algorithm is complete if it can derive all sentences that are entailed\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 35,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "ea67a7b2-8bcc-46be-c6ab-823fe56d513a"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "\n",
              "**Propositional Logic**\n",
              "- Defines the **semantics** (meaning) of a sentence, and the semantics defines the truth of a sentence wrt a possible world (**model**)\n",
              "- If sentence $a$ is true in model $m$, say that $m$ satisfies $a$ or $m$ is a model of $a$\n",
              "- Let $M(a)$ denote the set of all models of $a$\n",
              "\n",
              "**Logical Entailment**\n",
              "- $a$ entails $b$ means sentence $a$ follows logically from $b$\n",
              "- Write $a \\models b$ to denote $a$ entails $b$\n",
              "- By definition, $a \\models b \\Longleftrightarrow M(a) \\subseteq M(b)$ (i.e. $a$ is more specific than $b$ and rules out more possible worlds)\n",
              "- If inference algorithm $i$ concludes that $a$ is true, write $KB ⊢_i a$ to denote that $a$ is derived from $KB$ by $i$\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "\n",
              "- Sentences $a$ and $b$ are **logically equivalent** if they are true in the same set of models (i.e. they entail each other)\n",
              "- Write $a \\equiv b$ \n",
              "- By definition, $a \\equiv b \\Longleftrightarrow a \\models b \\wedge b \\models a$ \n",
              "\n",
              "- **Monotonicity**: If $KB \\models a$ then $KB \\wedge b \\models a$ (i.e. we can add sentences to the KB without invalidating previously inferred sentences)\n",
              "- **Monotonicity implies Soundness*\n",
              "\n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "Search algorithms can be used to find a sequence of steps that constitute a proof:    \n",
              "- Initial state: Initial Knowledge Base     \n",
              "- Actions: All inference rules applied to the sentence matching the top half of the inference rule     \n",
              "- Result: Add the sentence in the bottom of the inference rule    \n",
              "- Goal: A state containing the sentence we wish to prove \n",
              "\n",
              "**Converting sentences into CNF** \n",
              "1. Eliminate $\\Longleftrightarrow$, replace $a \\Longleftrightarrow b$ with $(a \\Longleftrightarrow b) \\wedge (b \\Longleftrightarrow a)$     \n",
              "2. Eliminate $\\Rightarrow$, replace $a \\Rightarrow b$ with $¬ a ~v ~b$\n",
              "3. Move ¬ inwards and apply De Morgan's \n",
              "4. Apply distributivity law to distribute v over $\\wedge$ when possible (i.e want to form ANDs of ORs)     \n",
              "\n",
              "\n",
              "**Resolution Algorithm**     \n",
              "- To show $KB \\models a$, we show that $KB \\wedge ¬a$ is unsatisfiable \n",
              "1.) Convert $KB \\wedge ¬a$ into CNF \n",
              "2.) Apply resolution rule to resulting clauses, i.e. reslve every pair that contains complementary literals to produce a new clause\n",
              "3.) Add new clause to the sentence if it is not already present \n",
              "4.) Continue until either:   \n",
              "- there are no new clauses that can be added (i.e. KB doesn't entail $a$)\n",
              "- Two contradictory unit clauses resolve to yield the empty clause (i.e. KB entails $a$)\n",
              "\n",
              "**Definite clause**\n",
              "- Disjunction of literals where *exactly* one is positive\"\n",
              "\n",
              "**Horn Clause**\n",
              "- Disjunction of literals where at most one is positive (includes definitive clauses and **goal clauses**, which are clauses with no positive literals)\n",
              "- Closed under resolution\n",
              "\n",
              "**KBs with only definite clauses**\n",
              "- Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is one positive literal\n",
              "- Inference with Horn clauses cam be done through forward/backward-chaining algorithms     \n",
              "- Deciding entailment with Horn clauses can be done in linear time (wrt the KB's size)\n",
              "\n",
              "**Forward Chaining** (Data-driven reasoning)   \n",
              "- Start with positive literals (known facts) in the KB, and if all premises of an implication are known, its conclusion is added to the set of known facts. \n",
              "Continue until no further inferences can be made.   \n",
              "- Sound (every inference is an application of Modus Ponens)   \n",
              "- Complete (every entailed atomic sentence is derived)\n",
              "\n",
              "**Backward Chaining** (Goal-directed reasoning)\n",
              "- Work backwards from a query $q$, find implications in the KB whose conclusion is $q$. If all premises of an implication can be proven true, then $q$ is true. \n",
              "\n",
              "\n",
              "**Resolution Closure $RC(S)$**    \n",
              "- $RC(S)$ is the set of all clauses derivable via repeatedly applying the resolution rule to clauses in $S$ (or their deriatives)\n",
              "\n",
              "**Ground Resolution Theorem**   \n",
              "- **Theorem**: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause\n",
              "\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **(7.1) knowledge base** - Sentences written according to the **syntax** of a knowledge representation language\n",
              "* **(7.1) axiom** - Sentence in a KB taken as given (not derived from other sentences)\n",
              "* **(7.3) models** - Fixed set of truth values for each sentence in a KB\n",
              "* **(7.3) logical inference** - Process of applying entailment to sentences to derive conclusions\n",
              "* **(7.3) soundness/truth-preserving** - An inference algorithm is sound if it only derives entailed sentences\n",
              "* **(7.3) completeness** - An inference algorithm is complete if it can derive all sentences that are entailed\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": 36,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "ff57bdb5-2c60-4d54-faf3-b7425998f446"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              "\n",
              "- Agents specified by agent function $f: P \to a$ that maps a sequence of percept vectors $P$ to an action $a \\in A$\n",
              "- Rational agents maximise their performance measure\n",
              "\n",
              "Components of Task Environment\n",
              "- PEAS (Performance, Environment, Actuators, Sensors)\n",
              "- Fully observable\n",
              "- Single vs multi-agent     \n",
              "- Deterministic vs stochastic   \n",
              "- Episodic vs sequential    \n",
              "- Static vs Dynamic   \n",
              "- Discrete vs Continuous   \n",
              "\n",
              "Consequentialism: Evaluate an agent's behaviour via its consequences\n",
              "\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - Anything that can perceive its environment through sensors and act in an environment via actuators\n",
              "* **Percept** - The content received by an agent's perceptual inputs\n",
              "* **Agent program** - Runs on the physical architecture to produce the agent function $f$\n",
              "* **Etc.** - your definitions here\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "\n",
              "|          | Strings | Lists | Tuples |\n",
              "|----------|:---------:|:-------:|:--------:|\n",
              "| **Mutable?** |    No   |  Yes  |   No   |\n",
              "| **Mixed Types allowed?** |    N/A   |  Yes  |   Yes   |\n",
              "\n",
              "**Typing**\n",
              "- All data treated as **objects**\n",
              "- **Strong typing**: Every object has a fixed type (things like `'foo' + 2` are forbbiden)   \n",
              "- **Dynamic typing**: Type of variables evaluated at runtime, functions have no type signatures     \n",
              "- **Duck typing**: Presence of methods (as opposed to the object's type) determines whether we can call it on an objec\n",
              "\n",
              "\n",
              "\n",
              "**Dictionaries**\n",
              "- Unordered (hashmaps underneath -- keys must be **immutable**)\n",
              "- Constant average time add/lookup/update\n",
              "- `defaultdict` initializes nonexistent dictionary values\n",
              "\n",
              "**Functions**\n",
              "- No function overloading in Python\n",
              "- Functions specified by their name alone (function names must be unique)\n",
              "- Use `*args` in function definition to accept variable no. of non-keyword arguments\n",
              "- Use `*kwargs` to do the same for keyword arguments\n",
              "- **Dynamic scoping**: Functions see most current value of variables\n",
              "- Functions are **first-class** objects (functions can be passed as arguments, returned as values, assigned to variables and stored in data structures)\n",
              "\n",
              "**Subclasses**\n",
              "- `class AI_Student(Student):`\n",
              "- Redefining method in parent class: `parentClass.methodName(self, a, b, c)`\n",
              "\n",
              "**Constructors**\n",
              "- `def __init__(self):`\n",
              "\n",
              "**Dunder/Magic Methods**:\n",
              "- Allow user-defined classes to behave like built in types\n",
              "- Eg. implement operator overloading and define how the + operator works by implementing `__add__`\n",
              "\n",
              "**Slicing**\n",
              "- `a[:]` Returns a **shallow copy** of the list `a`\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "\n",
              "Search problems consist of:   \n",
              "- State space     \n",
              "- Initial state     \n",
              "- Goal state(s)      \n",
              "- Set of actions available at each state      \n",
              "- Transition function (specifies result of each action)\n",
              "- Action cost function $c(s, a, s')$ (Cost of performing action $a$ to get from state $s \to s'$) \n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "- We consider search algorithms that create a **search tree** from the state-space graph, where nodes correspond to states and edges are actions. Root of search tree is initial state.   \n",
              "- **Expanding** a node involves seeing what actions are available, and **generating** a **child/successor node** for each resulting state\n",
              "\n",
              "**Best-First Search** (Graph Search)     \n",
              "- Expand the node in the frontier that has the minimum $f(n)$ value, where $f(n)$ is the **evaluation function**\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "**BFS**    \n",
              "- Evaluation function $f(n)$ = depth of node    \n",
              "- Expands *shallowest* unexplored node    \n",
              "- Frontier is FIFO queue      \n",
              "- Runtime and space: $O(b^d)$ (exponential)   \n",
              "- Total no. of nodes generated is: $ 1 + b + b^2 + b^3 + \\ldots + b^d = O(b^d)$  (all nodes remain in memory)      \n",
              "- Complete and optimal if cost is 1 per step\n",
              "\n",
              "**DFS** \n",
              "- Expand *deepest* unexpanded node in frontier   \n",
              "- Frontier is stack (LIFO)\n",
              "- Doesn't keep track of visited states (tree search)      \n",
              "- Not optimal! DFS returns the first solution it finds (may not be cheapest)   \n",
              "- Not complete! Fails in infinite-depth spaces      \n",
              "- Runtime: $O(b^m)$ (Bad if no. of actions $m >> b$)   \n",
              "- Space: $O(bm)$ (Longest path has length $m$, and each node has at most $b$ successors)\n",
              "   \n",
              "**Depth-Limited Search**      \n",
              "- DFS with depth limit $l$ (all nodes at depth $l$ treated as if they have no successors)    \n",
              "- Prevents DFS from going down infinite-depth paths       \n",
              "- Runtime: $O(b^l)$          \n",
              "- Space: $O(bl)$   \n",
              "- If $l = d$, then optimal (if $l < d$, incomplete; if $l > d$, not optimal)    \n",
              "\n",
              "**Iterative Deepening Search**     \n",
              "- Repeatedly call Depth-Limited search with increasing $l$ until returns a solution    \n",
              "- Use when search space is larger than memory and depth of solution is unknown     \n",
              "- Complete and optimal (Finds the shallowest goal node)   \n",
              "- Runtime: $O(b^d)$ \n",
              "- Nodes constructed at each step: $$b + (b + b^2) + (b + b^2 + b^3) + \\ldots = db + (d - 1)b + \\ldots + (1)b^d = O(b^d)$$\n",
              "\n",
              "**Bidirectional Search**\n",
              "- Simultaneously search forward from initial state and backward from goal state(s)    \n",
              "- Maintain two frontiers and two evaluation functions, return solution when both frontiers meet    \n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "- Nodes in a search tree are data structures of the form $(state, parent, children, action, path cost, depth)$\n",
              "- Nodes are different from states! (States represent physical configurations)     \n",
              "\n",
              "**BFS vs DFS**       \n",
              "- Use DFS if limited memory, search can be fine-tuned quickly, wrong paths can be terminated quickly     \n",
              "- Use BFS if possibly infinite paths, some solutions have short paths  \n",
              "- BFS is complete and optimal\n",
              "- DFS is *not* complete and *not* optimal    \n",
              "\n",
              "- **Graph Search**: Checks if a node has been visited before adding it to queue (maintains set of explored nodes)     \n",
              "- Graph search ensures that repeated states are repeated\n",
              "- Tree search doesn't keep track of visited states, so it requires less memory than graph search\n",
              "\n",
              "- Depth $d$: Depth of least cost solution   \n",
              "- Max depth of search space $m$      \n",
              "- Branching factor $b$: No. of successors of a node\n",
              "\n",
              "|           |    BFS   |    DFS   | Depth-Limited | Iterative Deepening | Bidirectional |\n",
              "|:---------:|:--------:|:--------:|:-------------:|:-------------------:|:---------------:|\n",
              "| **Complete?** |    Yes   |    No    |       No      |         Yes         |      Yes      |\n",
              "|    **Time**   | $O(b^d)$ | $O(b^m)$ |    $O(b^l)$   |       $O(b^d)$      |  $O(b^{d/2})$ |\n",
              "|   **Space**   | $O(b^d)$ |  $O(bm)$ |    $O(bl)$    |       $O(bd)$       |  $O(b^{d/2})$ |\n",
              "|  **Optimal?** |    Yes   |    No    |       No      |         Yes         |      Yes      |\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **(3.1) problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **(3.1) reflex agent** - Agent selects an action only based on *current* precept, ignores percept history\n",
              "* **(3.3) frontier** - Set of unexpanded nodes\n",
              "* **(3.3) completeness** - Algorithm is guaranteed to return a solution if one exists, and correctly reports failure otherwise\n",
              "* **(3.3) optimality** - Solution returned has the lowest path cost among all solutions\n",
              "* **(3.4) graph diameter** - Length of longest path in graph\n",
              "\n",
              "\n",
              "## WARNING: Your definition of '(3.5) Consistent heuristic' is too long!\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "\n",
              "**Dijkstra's / Uniform Cost Search**     \n",
              "- Expand node with lowest path cost $g(n)$ (cost from initial state to node $n$)     \n",
              "- Frontier: priority queue ordered by $g(n)$    \n",
              "- Test if node is goal when it is expanded, not when it is added to frontier        \n",
              "- Updates a node's position in frontier if a cheaper path to the same node is found    \n",
              "- Always enqueues nodes before checking if its a goal (this allows us to prioritise lower cost paths)        \n",
              "- Runtime: $O(b^{1 + floor( C^* / \\epsilon ) })$     \n",
              "- Complete and optimal (first solution it finds is at the front of frontier so has cheapest cost) \n",
              "\n",
              "**Greedy Best-First Search**    \n",
              "- Variant of Best-First Search that expands the node with the lowest $h(n)$, i.e. evaluation function $f(n) = h(n)$      \n",
              "- Not optimal\n",
              "- UCS but with $f(n)$ instead of $g(n)$\n",
              "\n",
              "**A* Search**      \n",
              "- Evaluation function $f(n) = g(n) + h(n)$,     \n",
              "where $g(n)$ = path cost from initial state to node $n$,     \n",
              "$h(n)$ = *estimated* path cost from node $n$ to goal state (heuristic)   \n",
              "- Is complete\n",
              "- Optimal only when heuristic $h(n)$ is consistent \n",
              "\n",
              "- Every consistent heuristic is admissible (but converse does not hold)\n",
              "\n",
              "- Let $C^*$ be the cost of the optimal solution path     \n",
              "- **Surely expanded nodes**: nodes that can be reached from the initial state via a path where $f(n) < C^*$ for every node    \n",
              "- $A^*$ expands all surely expanded nodes  \n",
              "- $A^*$ is **optimally efficient**: Any other algorithm that start from the same intiial state and use the same heuristic, must expand all nodes that $A^*$ surely expands\n",
              "\n",
              "- Limitation: No. of nodes expanded by $A*$ can be exponential!\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "- If $h_1, h_2$ are admissible heuristics and $h_2(n) \\geq h_1(n)$ for all $n$, then $h_2$ **dominates** $h_1$    \n",
              "(i.e. $h_2$ is optimistic but more accurate than $h_1$)\n",
              "- Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
              "(Graph for relaxed problem includes more edges which serve as \"shortcuts\" to the goal state)\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **(3.5) heuristic function $h(n)$** - Estimate cost of the cheapest path from node $n$ to a goal state\n",
              "* **(3.5) admissible heuristic** - Never overestimates actual cost to reach goal\n",
              "* **(3.5) consistent heuristic** - $h(n)$ is consistent if for every $n$ and all successors $n'$, we have $h(n) \\leq c(n, a, n') + h(n')$ (Triangle Inequality)\n",
              "* **(3.6) relaxed problem** - Problem with fewer constraints than the original \n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "\n",
              "- Perfect information, zero-sum games\n",
              "- Evaluation function $f(n)$ assigns numeric values to nodes in the game tree without reference to path      \n",
              "- $f(n) > 0$ means MAX is winning at state $n$, $f(n) < 0$ means MIN is winning    \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "\n",
              "**Minimax**      \n",
              "Minimax does a depth-first exploration of the game tree. Minimax goes to the leaves and recursively backs up the minimax values up through the tree. \n",
              "Runtime: $O(b^m)$, where $m$ = max depth of tree and $b$ = max no. of egal moves at each ndoe\n",
              "Space complexity: $O(bm)$ is all actions are generated at once\n",
              "\n",
              "Minimax for multi-player games: Return a utility vector for each node.     \n",
              "Backed-up value of node $n$ = utility vector of child that has the highest value for the player who makes a move at $n$ \n",
              "\n",
              "**Alpha-Beta Pruning**      \n",
              "- Alpha = highest already-explored value along the path from MAX's current position to the root (\"at least\")         \n",
              "- Beta = lowest already-explored value along the path from MIN's current position to the root (\"at most\")     \n",
              "- No. of game states is exponential in the game tree's depth     \n",
              "\n",
              "**Move ordering**\n",
              "- Maintain a *transposition table* to cache states' values and to avoid repeated states \n",
              "- **Type A strategy**: Consider all moves that lead to a certain depth in the game tree, then use an evaluation function to estimate states' utilities at that depth   \n",
              "- Type A explores \"wide but shallow\" area of the tree\n",
              "- **Type B strategy**: Ignore moves that result in low valuees, but follow promising paths as deep as possible     \n",
              "- Type B explores \"deep but narrow\" area of the tree\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "\n",
              "- To limit the computation time of Alpha-Beta pruning, we can apply a cut-off function that returns TRUE for quiescent state and FALSE otherwise. This **quiescence search** ensures that the search continues until we reach a quiescent search.      \n",
              "- **Horizon effect**: An opponent's move that has the potential to cause great damage looms over the horizon, but can be delayed via certain moves (eg. checkmate)      \n",
              "- **Singular extensions** can avoid the horizon effect. This involves searching deeper in the search tree if a node's value is significantly better than its siblings'. This reduces the effective branching factor.     \n",
              "\n",
              "- **Forward pruning** prunes subsequent moves that appear to be bad ones (Type B strategy).  \n",
              "- **Late move reduction** reduces the depth to which we search moves that appear later in the list (assuming they're bad ones).\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "- Game trees for stochastic trees include *chance nodes* alongside MAX & MIN nodes. \n",
              "Chance nodes are like MIN nodes but outcome is uncertain (assume they come along w/ probability distribution). \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "\n",
              "\n",
              "- **Maximum Expected Utility (MEU) Principle**: Rational agent should choose actions that maximise their expected utility         \n",
              "\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "\n",
              "**Theorem**: Given any preferences satisfying the axioms of utility theory, there exists some real-valued function $U$ such that $$U(A) \\geq U(B) \\Longleftrightarrow A \\succeq B$$\n",
              "$$U([p_1, S_1; \\ldots; p_n, S_n]) = \\sum_{i = 1}^n p_iS_i$$\n",
              "\n",
              "- Positive affine transformations of the form $U'(S) = aU(S) + b$ don't change the utility function\n",
              "- If prizes are deterministic (no probability), only ordinal utility can be determined (i.e. only preferences matter, numbers don't matter)\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "\n",
              "For a lottery $L = [p, \\$X; 1 - p, \\$Y]$, the **Expected Monetary Value** $EMV(L) = pX + (1 - p)Y$, with utility $U(L) = pU(\\$X) + (1 - p)U(\\$Y)$.    \n",
              "Usually, $U(L) < EMV(L)$. \n",
              "\n",
              "$\\hat{EU}(a) = $ *estimated* expected utility\n",
              "\n",
              "- **Preference elicitation**: Presenting a human with the **standard lottery** $[p, A; 1 - p, B]$ and adjusting $p$ such that preferences are indifferent \n",
              "\n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **(5.2) ply** - One move made by one player\n",
              "* **(5.2) minimax value for a ndoe in a game tree** - Utility for MAX for that state, assuming both players play optimally\n",
              "* **(5.2) transpositions** - Different permutations of the move sequence that end up in the same state\n",
              "* **(5.3) evaluation function $eval(s, p)$** - Gives an *estimate* of the expected utility for player $p$ at state $s$ \n",
              "* **(5.3) quiescent state** - A (stable) state where there is no subsequent state that would drastically change the next few moves\n",
              "* **(16. 3) certainty equivalent** - The value an agent accepts in place of a lottery\n",
              "* **(16.3) insurance premium** - Difference between a lottery's EMV and its certainty equivalent\n",
              "* **(16.3) unbiased esimate** - Error between estimate and actual value is 0, i.e. $E(\\hat{EU}(A) - EU(A)) = 0$\n",
              "* **(16.3) optimizer's curse** - Estimated expected utility is overly high\n",
              "* **(16.3) certainty effect** - People prefer deterministic over stochastic games\n",
              "* **(16.3) anchoring effect** - People prefer making relative utility judgements over absolute ones\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "A CSP consists of a variable set $X$, a domain $D_i$ for each variable $X_i$ that specifies allowable values for $X_i$, and a set of constraints $C$.     \n",
              "\n",
              "Constraint graph has nodes = variables, and two nodes share an edge if they partake in the same constraint. \n",
              "Discrete variables: $n$ variables each with domain size $d$ -> $O(d^n)$ complete assignments \n",
              "\n",
              "CSPs as search problems:    \n",
              "- Initial state is empty assignment    \n",
              "- Successor function assigns values to any unassigned variable (if no constraint conflict)    \n",
              "- Goal test: Checks if current assignment si complete     \n",
              "- Path cost: path constant for each step   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " AC-3 enforces arc consistency for all variables. AC-3 maintains a queue of all edges, and pops off an edge $(X_i, X_j)$ at each iteration and makes $X_i$ arc-consistent wrt $X_j$. Every time $X_i$'s domain $D_i$ is changed,  all other edges incident to $X_i$ are added to the queue. We do this since the change in $D_i$ might cause\n",
              "reductions in $D_k$. If $D_i$ becomes empty, then there is no consistent solution and AC-3 returns failure. \n",
              "\n",
              "Runtime: $O(cd^3)$, where $d$ = max domain size, $c$ = no. of edges\n",
              "Each arc inserted into queue at most $d$ times and checking consistency of an arc takes $O(d^2)$ time\n",
              "\n",
              "To make a CSP strongly n-consistent, choose a consistent value for $X_1$, then $X_2$, etc. \n",
              "(we can do this since its 1-consistent, 2-consistent, etc.)\n",
              "For each $X_i$, we search through $d$ values to find a value consistent with the other $n - 1$ variables, runtime is $O(n^2d)$\n",
              "\n",
              "Constraint satisfaction is NP-Complete in general.\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " \n",
              "Backtracking search selects an unassigned variable, tries all values in that variables' domain and for each value recursively examines whether it belongs in a solution where all variables are assigned. If yes, the solution is returned, else the assignemnt is undone and the next value is attemped. (If all values fail, return failure.)     \n",
              "\n",
              "\n",
              "Forward checking establishes arc consistency for a variable $X$. When $X$ is assigned, for each unassigned variable $Y$ where $(X, Y)$ is a constraint, remove any values from $Y$'s domain that are inconsistent with $X$'s assigned value. \n",
              "(Forward checking facilitates using MRV heuristic to choose variables, but it doesn't detect all inconsistencies.)\n",
              "(Forward-checking search removes the need to do backjumping, since it removes inconsistent values from $Y$'s domain. \n",
              "\n",
              "MAC algorithm (Maintaining Arc Consistency): After $X_i$ is assigned, call AC-3, but only enqueue arcs $(X_j, X_i)$ where $X_j$ are unassigned neighbours of $X_i$. Then, backtrack if any variable's domain is $\u000baremptyset$. MAC is more powerful than forward checking, since FC doesn't recursively propagate constraints when a variable's domain changes. \n",
              "\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "\n",
              "Conflict-directed backjumping: For the current variable $X_j$ and its conflict set $conf(X_j)$, if every value for $X_j$ fails, backjump to the most recent variable $X_i$ in $conf(X_j)$ and set $conf(X_i) \\leftarrow conf(X_i) \\cup conf(X_j) \\setminus \\{X_i\\}$\n",
              "(Conflict set for $X_i$ is the set of preceding variables, along with any subsequent variables that caused $X_i$ to have no solution)\n",
              "\n",
              "Connected components of constraint graph correspond to subproblems of the CSP. If each CC has $c$ variables ($c$ is a constant where $c \\leq n$), then there are $n/c$ subproblems which each take $O(d^c)$ work to solve, where $d$ = size of each variable's domain. Then, the total work to solve the CSP is $O(d^c n/c)$, which is **linear** in the no. of variables. Without the decomposition, the total work is $O(d^n)$, which is exponential in $n$.                    \n",
              "\n",
              "**Lemma**: *Any constriant graph which is a **tree** can be solved in **linear** time (wrt the no. of variables)*            \n",
              "\n",
              "**Proof**: Pick any arbitrary node to be the root of the tree, then topologically sort the tree. Since a tree w/ $n$ nodes has $n - 1$ edges, we can make the tree directed arc-consistent in $O(n)$ steps, and at each step, we compare at most $d$ domain values for a pair of variables, so the total time is $O(nd^2)$, which is linear in $n$. \n",
              "\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              "\n",
              "Cutset conditioning algorithm:         \n",
              "1. Choose a subset $S$ of nodes in the constriant graph such that the graph becomes a tree after $S$ is removed. (Call $S$ a **cycle cutset.**)     \n",
              "2. For each assignemnt of values to variables in $S$ that satisfies all constraints on $S$, remove from other variables' domains values that are inconsistent with $S$'s assignment.     \n",
              "If the remaining CSP has a solution, return it along w/ the assignment for $S$.       \n",
              "Runtime: $O(d^c \\cdot (n - c)d^2)$, where $c$ = size of cycle cutset, $d$ = domain size for each variable      \n",
              "(Need to try $d^c$ combinations of values for variables in $S$, and for each combination we need to solve a tree problem involving $n - c$ variables)      \n",
              "\n",
              "**Tree decomposition**: Convert constraint graph into a tree, where each node in the tree is a set of variables s.t. :        \n",
              "- Each varible in the original CSP must appear in at least one tree node     \n",
              "- If $(X, Y)$ is a constraint in the original CSP, then $X$ and $Y$ must appear together (w/ the constraint) in a tree node    \n",
              "- If a variable appears in two tree nodes, it must appear in every node along the path connecting the two tree nodes    \n",
              "(i.e. a variable in a tree node must share the same value as the corresponding variable in the adjacent tree node) \n",
              "Runtime: After we perform tree decomposition, solving the problem takes $O(nd^2)$, where $n$ = no. of tree nodes, $d$ = max domain size of a tree node (where the domain is sets of tuples of variables)\n",
              "\n",
              "If a graph has tree width $w$, then we can solve the problem in $O(nd^{w + 1})$ if we choose the tree decomposition that has width $w$.     \n",
              "That is, if the constraint graph's tree width is finite, then we can solve it in polynomial time. \n",
              "\n",
              "**Lemma**: Whenever there exists a size $c$ cycle-cutset, there is also a tree width of size $w < c + 1$.      \n",
              "(Tree decomposition is quicker than cycle-cutset conditioning)    \n",
              "(But tree decomposition requires memory exponential in $w$, while cutset conditioning can be done in linear memory.)\n",
              "\n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "\n",
              "\n",
              "Backtracking search is a DFS that chooses values for one variable at a time, and backtracks when there are no values left to assign.    \n",
              "Runtime of AC-3 is $O(n^2d^3)$     \n",
              "(A complete graph has $O(n^2)$ edges and if each variable's domain size is $d$, maintaining arc consistency for the arc $(i, j)$ takes $O(d^2)$ time. \n",
              "Since each arc can only be inserted into the queue at most $d$ times, overall runtime is $O(n^2d^3)$.)\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **(6.1) consistent assignment** - Assignment that respects all constraints\n",
              "* **(6.1) complete assignment** - Assignment that assigns a value to each variable\n",
              "* **(6.1) partial assignment** - Assignment where some variables are left unassigned\n",
              "* **(6.1) partial solution** - A partial assignment that respects all constraints\n",
              "* **(6.1) global constraint** - Constraint involving an arbitrary no. of variables\n",
              "* **(6.1) constriant graph** - Nodes = variables, two variables that partake in the same constraint are linked by an edge\n",
              "* **(6.1) binary csp** - All constraints are either unary or binary\n",
              "* **(6.1) linear programming problems** - Continuous-domain CSPs where constraints are linear equalities/inequalities\n",
              "* **(6.1) cryptarithmetic** - Arithmetic puzzles where the unknowns are letters that each represent a digit\n",
              "* **(6.1) dual graph (converting n-ary csp -> binary csp)** - New constraint graph where nodes = constraints and two nodes share an edge if two constraints share variables\n",
              "* **(6.1) constrained optimization problem** - CSPs with preference constraints that require optimizing an objective function\n",
              "* **(6.2) node consistency** - All values in variable's (node) domain satisfy unary constraints\n",
              "* **(6.2) arc consistency** - All values in variable's domain satisfy binary constraints\n",
              "* **(6.2) path consistency** - $k$-Consistency with $k = 3$\n",
              "* **(6.2) $k$-consistency** - For any $k-1$ variables with a consistent assignment, a consistent value can be assigned to the $k$-th variable\n",
              "* **(6.2) strongly k-consistent** - k consistent, k-1 consistent, ..., 1-consistent\n",
              "* **(6.2) atmost constraint** - Constraint on resources available\n",
              "* **(6.2) bounds propagation** - Represent domain of variables using upper/lower bounds, and change bounds as necessary\n",
              "* **(6.2) bounds consistency** - For each $X$ whose values are bounded, for every other $Y$, $Y$ has a value that satisfies constraint $(X, Y)$\n",
              "* **(6.3) commutativity** - Order in which variables are assigned doesn't matter\n",
              "* **(6.3) minimum remaining value (mrv) heuristic** - choose the variable with the fewest legal values, so that we can detect failure asap and prune the search tree\n",
              "* **(6.3) degree heuristic** - choose the variable that partakes in the largest no. of constraints with other unassigned variables\n",
              "* **(6.3) least constraining value heuristic** - Choose the value in a variable's domain that eliminates the fewest values for neighbouring nodes in constraint graph (fail last)\n",
              "* **(6.3) chronological backtracking** - Examine the most recent decision point when backtracking\n",
              "* **(6.3) conflict set for a variable** - Keep track of all assignments that are inconsistent with a value for $X$\n",
              "* **(6.3) backjumping** - Backtrack to latest assignment in conflict set\n",
              "* **(6.3) no-good** - The smallest subset of variables (along with their values) from the conflict set that results in no solution\n",
              "* **(6.3) constraint learning** - Keeping track of no-goods and forbidding such assignments in order to avoid running into them again\n",
              "* **(6.4) min-conflicts heuristic** - Assign a value to a conflicted variable that results in the min no. of conflicts w/ other variables\n",
              "* **(6.4) plateau search** - Move sideways to another state with the same score\n",
              "* **(6.4) tabu search** - Maintain a small list of recently visited states and prevent the algo. from re-visiting those states\n",
              "* **(6.4) constraint weighting** - Weight constraints equally, then iteratively change a variable/value pair that minimizes the total weight of all violated constraints\n",
              "* **(6.4) directional arc consistency (dac)** - Ordered variables $X_1, X_2, \\ldots, X_n$ satisfy DAC iff every $X_i$ is arc-consistent with every $X_j$ ($j > i$)\n",
              "* **(6.5) tree width of a graph's tree decomposition** - Size of largest tree node - 1\n",
              "* **(6.5) tree width of a graph** - Minimum tree width for all of the graph's tree decompositions\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "\n",
              "**Propositional Logic**\n",
              "- Defines the **semantics** (meaning) of a sentence, and the semantics defines the truth of a sentence wrt a possible world (**model**)\n",
              "- If sentence $a$ is true in model $m$, say that $m$ satisfies $a$ or $m$ is a model of $a$\n",
              "- Let $M(a)$ denote the set of all models of $a$\n",
              "\n",
              "**Logical Entailment**\n",
              "- $a$ entails $b$ means sentence $a$ follows logically from $b$\n",
              "- Write $a \\models b$ to denote $a$ entails $b$\n",
              "- By definition, $a \\models b \\Longleftrightarrow M(a) \\subseteq M(b)$ (i.e. $a$ is more specific than $b$ and rules out more possible worlds)\n",
              "- If inference algorithm $i$ concludes that $a$ is true, write $KB ⊢_i a$ to denote that $a$ is derived from $KB$ by $i$\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "\n",
              "- Sentences $a$ and $b$ are **logically equivalent** if they are true in the same set of models (i.e. they entail each other)\n",
              "- Write $a \\equiv b$ \n",
              "- By definition, $a \\equiv b \\Longleftrightarrow a \\models b \\wedge b \\models a$ \n",
              "\n",
              "- **Monotonicity**: If $KB \\models a$ then $KB \\wedge b \\models a$ (i.e. we can add sentences to the KB without invalidating previously inferred sentences)\n",
              "- **Monotonicity implies Soundness*\n",
              "\n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "Search algorithms can be used to find a sequence of steps that constitute a proof:    \n",
              "- Initial state: Initial Knowledge Base     \n",
              "- Actions: All inference rules applied to the sentence matching the top half of the inference rule     \n",
              "- Result: Add the sentence in the bottom of the inference rule    \n",
              "- Goal: A state containing the sentence we wish to prove \n",
              "\n",
              "**Converting sentences into CNF** \n",
              "1. Eliminate $\\Longleftrightarrow$, replace $a \\Longleftrightarrow b$ with $(a \\Longleftrightarrow b) \\wedge (b \\Longleftrightarrow a)$     \n",
              "2. Eliminate $\\Rightarrow$, replace $a \\Rightarrow b$ with $¬ a ~v ~b$\n",
              "3. Move ¬ inwards and apply De Morgan's \n",
              "4. Apply distributivity law to distribute v over $\\wedge$ when possible (i.e want to form ANDs of ORs)     \n",
              "\n",
              "\n",
              "**Resolution Algorithm**     \n",
              "- To show $KB \\models a$, we show that $KB \\wedge ¬a$ is unsatisfiable \n",
              "1.) Convert $KB \\wedge ¬a$ into CNF \n",
              "2.) Apply resolution rule to resulting clauses, i.e. reslve every pair that contains complementary literals to produce a new clause\n",
              "3.) Add new clause to the sentence if it is not already present \n",
              "4.) Continue until either:   \n",
              "- there are no new clauses that can be added (i.e. KB doesn't entail $a$)\n",
              "- Two contradictory unit clauses resolve to yield the empty clause (i.e. KB entails $a$)\n",
              "\n",
              "**Definite clause**\n",
              "- Disjunction of literals where *exactly* one is positive\"\n",
              "\n",
              "**Horn Clause**\n",
              "- Disjunction of literals where at most one is positive (includes definitive clauses and **goal clauses**, which are clauses with no positive literals)\n",
              "- Closed under resolution\n",
              "\n",
              "**KBs with only definite clauses**\n",
              "- Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is one positive literal\n",
              "- Inference with Horn clauses cam be done through forward/backward-chaining algorithms     \n",
              "- Deciding entailment with Horn clauses can be done in linear time (wrt the KB's size)\n",
              "\n",
              "**Forward Chaining** (Data-driven reasoning)   \n",
              "- Start with positive literals (known facts) in the KB, and if all premises of an implication are known, its conclusion is added to the set of known facts. \n",
              "Continue until no further inferences can be made.   \n",
              "- Sound (every inference is an application of Modus Ponens)   \n",
              "- Complete (every entailed atomic sentence is derived)\n",
              "\n",
              "**Backward Chaining** (Goal-directed reasoning)\n",
              "- Work backwards from a query $q$, find implications in the KB whose conclusion is $q$. If all premises of an implication can be proven true, then $q$ is true. \n",
              "\n",
              "\n",
              "**Resolution Closure $RC(S)$**    \n",
              "- $RC(S)$ is the set of all clauses derivable via repeatedly applying the resolution rule to clauses in $S$ (or their deriatives)\n",
              "\n",
              "**Ground Resolution Theorem**   \n",
              "- **Theorem**: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause\n",
              "\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **(7.1) knowledge base** - Sentences written according to the **syntax** of a knowledge representation language\n",
              "* **(7.1) axiom** - Sentence in a KB taken as given (not derived from other sentences)\n",
              "* **(7.3) models** - Fixed set of truth values for each sentence in a KB\n",
              "* **(7.3) logical inference** - Process of applying entailment to sentences to derive conclusions\n",
              "* **(7.3) soundness/truth-preserving** - An inference algorithm is sound if it only derives entailed sentences\n",
              "* **(7.3) completeness** - An inference algorithm is complete if it can derive all sentences that are entailed\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": [],
      "name": "Ernest FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": []
    },
    "interpreter": {
      "hash": "b0fa6594d8f4cbf19f97940f81e996739fb7646882a419484c72d19e05852a7e"
    },
    "kernelspec": {
      "display_name": "Python 3.9.7 64-bit",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.9.7"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
