{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "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",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "baa89068-27fc-492c-ff8b-40915b400d93"
      },
      "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)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "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",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2936cf0c-5a6b-490d-a083-238d642db2c7"
      },
      "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))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "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",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "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",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 719
        },
        "cellView": "form",
        "outputId": "334a898b-17c6-4fe4-dcfb-ecb282323792"
      },
      "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))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "- All data treated as objects\n",
        "- Objects are automatically garbage collected once unreachable\n",
        "- Strong typing: every object has a fixed type, and Python does not \n",
        "allow things that are incompatible with that type\n",
        "- Dynamic typing: Variables come into existence when they are first assigned.\n",
        "Type of a variable is automatically determined and can be updated if assigned again.\n",
        "Functions have no type signatures. Type errors only caught at runtime.\n",
        "\n",
        "- Java is static typing: variables can only refer to objects of a declared type.\n",
        "Methods use type significatures. \n",
        "\n",
        "- Immutable: Strings, tuple\n",
        "- Mutable: Lists, dictionaries\n",
        "\n",
        "References/Mutability:\n",
        "- `==` checks whether variables point to objects that have the same value\n",
        "- `is` checks whether variables point to the same object\n",
        "- `y=x[:]` gets a shallow copy of any sequence (new object of the same value)\n",
        "\n",
        "List operations:\n",
        "- `list.reverse()` reverse the list in place\n",
        "- `list.sort()` sort the list in place\n",
        "- `sorted(list)` returns a copy that is sorted\n",
        "\n",
        "Dictionaries:\n",
        "- Unordered and works by hashing\n",
        "- Keys must be immutable \n",
        "\n",
        "Function overloading:\n",
        "- No function overloading for Python\n",
        "- Function specified by name alone. Different functions cannot have the same name\n",
        "even if they have different arguments.\n",
        "- But operator overloading is possible using special methods in a class\n",
        "- Magic methods allow user defined classes to behave like built in types\n",
        "\n",
        "Arguments:\n",
        "- Non default arguments first, then default arguments. Otherwise syntax error.\n",
        "- `*args` for variable number of non-keyword arguments to your function\n",
        "- `**kwargs` for variable number of keyword arguments to your function\n",
        "\n",
        "First class objects:\n",
        "- Can be dynamically created, destroyed, passed to a function, returned as a value\n",
        "- Have all rights as other variables\n",
        "- Functions are first class objects\n",
        "\n",
        "First class citizens:\n",
        "- Can pass functions as arguments to other functions\n",
        "- Return functions as the value from other functions\n",
        "- Assign functions to variables or store them in data structures\n",
        "- Functions are first class citizens\n",
        "\n",
        "Main:\n",
        "- `__name__` is built in variaable which evaluates the name of the current module\n",
        "(name of the Python script)\n",
        "- `__name__` has value `__main__` for the source file that is being executed on the command line\n",
        "- Python does not have built in main method, so no `def main()`\n",
        "\n",
        "Iterators:\n",
        "- `__iter__` magic method converts objects to iterator objects (\"to be iterable\")\n",
        "- Iterators are objects with `__next__()` method (\"to be iterator\")\n",
        "- Python iterators do not have `hasnext()` method. They just catch the `StopIteration` exception instead.\n",
        "- Use memory efficiently\n",
        "\n",
        "Generators:\n",
        "- Generators are iterators (has `__next()__` method)\n",
        "- Functions that contain `yield` keyword automatically return generator when called\n",
        "- Maintains local state automatically\n",
        "- Values computed one at a time as needed\n",
        "- Avoid storing entire sequence in memory\n",
        "- Crucial for infinite sequences\n",
        "- Bad if you need to inspect individual values\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"duck typing\" : \"determines suitability of an object by determining prescence of methods\"\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e0c11fe8-1368-4e85-9019-c01b50a4dc6e"
      },
      "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))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\n- All data treated as objects\n- Objects are automatically garbage collected once unreachable\n- Strong typing: every object has a fixed type, and Python does not \nallow things that are incompatible with that type\n- Dynamic typing: Variables come into existence when they are first assigned.\nType of a variable is automatically determined and can be updated if assigned again.\nFunctions have no type signatures. Type errors only caught at runtime.\n\n- Java is static typing: variables can only refer to objects of a declared type.\nMethods use type significatures. \n\n- Immutable: Strings, tuple\n- Mutable: Lists, dictionaries\n\nReferences/Mutability:\n- `==` checks whether variables point to objects that have the same value\n- `is` checks whether variables point to the same object\n- `y=x[:]` gets a shallow copy of any sequence (new object of the same value)\n\nList operations:\n- `list.reverse()` reverse the list in place\n- `list.sort()` sort the list in place\n- `sorted(list)` returns a copy that is sorted\n\nDictionaries:\n- Unordered and works by hashing\n- Keys must be immutable \n\nFunction overloading:\n- No function overloading for Python\n- Function specified by name alone. Different functions cannot have the same name\neven if they have different arguments.\n- But operator overloading is possible using special methods in a class\n- Magic methods allow user defined classes to behave like built in types\n\nArguments:\n- Non default arguments first, then default arguments. Otherwise syntax error.\n- `*args` for variable number of non-keyword arguments to your function\n- `**kwargs` for variable number of keyword arguments to your function\n\nFirst class objects:\n- Can be dynamically created, destroyed, passed to a function, returned as a value\n- Have all rights as other variables\n- Functions are first class objects\n\nFirst class citizens:\n- Can pass functions as arguments to other functions\n- Return functions as the value from other functions\n- Assign functions to variables or store them in data structures\n- Functions are first class citizens\n\nMain:\n- `__name__` is built in variaable which evaluates the name of the current module\n(name of the Python script)\n- `__name__` has value `__main__` for the source file that is being executed on the command line\n- Python does not have built in main method, so no `def main()`\n\nIterators:\n- `__iter__` magic method converts objects to iterator objects (\"to be iterable\")\n- Iterators are objects with `__next__()` method (\"to be iterator\")\n- Python iterators do not have `hasnext()` method. They just catch the `StopIteration` exception instead.\n- Use memory efficiently\n\nGenerators:\n- Generators are iterators (has `__next()__` method)\n- Functions that contain `yield` keyword automatically return generator when called\n- Maintains local state automatically\n- Values computed one at a time as needed\n- Avoid storing entire sequence in memory\n- Crucial for infinite sequences\n- Bad if you need to inspect individual values\n\n\n## Module 2 Definitions\n* **Duck typing** - determines suitability of an object by determining prescence of methods\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \n",
        "- An agent that considers a sequence of actions to lead to goal state (via search) is a problem-solving agent\n",
        "- Problem-solving agents use atomic representations of states \n",
        "- Planning agents use factored or structured representations of states\n",
        "- In fully observable, deterministic, known environment: solution to problem is a fixed sequence of actions\n",
        "- Search: agent simulates sequences of actions in the model, until it finds sequence that reaches the goal \n",
        "- Solution: sequence of actions that lead to the goal \n",
        "- State space can be represented as graph: vertices (states) and edges (actions)\n",
        "\n",
        "Search problem components:\n",
        "- State space: Set of possible states for the environment\n",
        "- Initial state\n",
        "- Goal states\n",
        "- Actions available to agent: set of actions that can be executed in $s$\n",
        "- Transition model: returns the state that is the result of performing action $a$ in state $s$\n",
        "- Action cost function: cost of action $a$ in state $s$ to reach state $s'$\n",
        "\"\"\"\n",
        "\n",
        "chapter3_2 = \"\"\" \n",
        "Standardized problems: \n",
        "- Used to illustrate problem solving methods (grid world, sliding tiles)\n",
        "- Has concise, exact description\n",
        "- Suitable as a benchmark to compare performance of algorithms\n",
        "\n",
        "Real world problems:\n",
        "- One whose solutions people actually use (route-finding, robot navigationm touring problem)\n",
        "- Formulation is not standardized\n",
        "\"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\" \n",
        "State space:\n",
        "- Describes set of spaces in the world (can be infinite) and actions that transition from one state to another\n",
        "\n",
        "Search tree:\n",
        "- Describes paths between states, reaching towards the goal\n",
        "- Each node in the tree has unique path back to the root \n",
        "\n",
        "A node in tree has 4 components:\n",
        "- State: that node corresponds to \n",
        "- Parent: node that generated current node\n",
        "- Action: action applied to parent to generate current node\n",
        "- Path cost: total cost of path from initial state to current node \n",
        "\n",
        "Queue types:\n",
        "- Priority: removes node with minimum cost according to evaluation function. Used in best first.\n",
        "- FIFO: used in BFS \n",
        "- LIFO: used in DFS\n",
        "\n",
        "Graph search:\n",
        "- Search algorithm that checks for redundant paths\n",
        "- Needs to store previously seen states, requires more memory\n",
        "- Does not waste time going down redundant paths, saves time \n",
        "- examples: Best first search \n",
        "\n",
        "Tree-like search:\n",
        "- Search algorithm that does not check for redundant paths \n",
        "- Does not store previous states, requires less memory \n",
        "- Could potentially go down redundant path, which would waste time \n",
        "\n",
        "In both cases, state space is the same graph. We are just treating how to search it. \n",
        "\n",
        "Criteria for search:\n",
        "- Completeness: Will search find solution or correctly report failure if there is no solution?\n",
        "- Cost optimality: Will search find lowest path cost?\n",
        "- Time / space complexity\n",
        "\n",
        "Time and space:\n",
        "- Many graphs are represented implicitly instead of as explicit graph. Defined by initial state, actions, and transition model. Instead, measure with:\n",
        "- $d$: depth in optimal solution\n",
        "- $m$: max number of actions in any path \n",
        "- $b$: branching factor: number of successors of a node to consider \n",
        "\"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\" \n",
        "BFS:\n",
        "- Appropriate when actions have the same cost\n",
        "- Complete, even on infinite spaces\n",
        "- Cost optimal if all actions have same cost; not necessarily otherwise\n",
        "- Use evaluation $f(n) = $ depth of node / number of actions to reach node \n",
        "- Perform early goal test: checking if node is solution as soon as it is generated  \n",
        "- Total number of nodes generated: $1 + b + b^2 + ... + b^d = O(b^d)$, assuming solution at depth $d$\n",
        "- Time and space is $O(b^d)$. \n",
        "- All nodes generated remain in memory; memory requirement bigger issue than time requirement \n",
        "\n",
        "Uniform cost (Dijkstra):\n",
        "- Use evaluation function $g(n) =$ cost of path from root node to current node\n",
        "- Test for goal when you expand a node, not when a node is generated \n",
        "- Time and space complexity: $O(b^{1 + C^*/\\\\epsilon})$, which may be $>> O(b^d)$ because Dijkstra may explore large areas that have low cast actions\n",
        "before exploring paths with higher actions\n",
        "- If all action costs are equal, $b^{1 + C^*/\\\\epsilon} = b^{d+1}$\n",
        "\n",
        "DFS:\n",
        "- Tree like search that does not remember reached states (so it uses less memory)\n",
        "- Not cost optimal; returns first solution it finds \n",
        "- Incomplete: Can get stuck in infinite loops in cyclic state spaces. Or it can get stuck going down an infinite path even if there are no cycles.\n",
        "- DFS only complete and efficient in finite state spaces. Efficient in acyclic state spaces.\n",
        "- Space complexity $O(bm)$\n",
        "- Time complexity $O(b^m)$\n",
        "\n",
        "Depth-limited search:\n",
        "- DFS with depth limit $l$. Treat all nodes at depth $l$ as if they had no successors\n",
        "- Time complexity $O(b^l)$\n",
        "- Space complexity $O(bl)$\n",
        "- Incomplete if $l < d$, we don't reach solution because we don't go deep enough\n",
        "- Not optimal if $l > d$, we explored too deep \n",
        "- Optimal if $l = d$\n",
        "\n",
        "Iterative deepening:\n",
        "- Space complexity: $O(bd)$ if solution exists, or $O(bm)$ on finite state spaces without solution\n",
        "- Time complexity: $O(b^d)$ if solution exists, or $O(b^m)$ without solution\n",
        "- Optimal if all action costs are the same (like BFS)\n",
        "- Complete on finite acyclic / finite state spaces if you check for cycles \n",
        "\n",
        "Bidirectional search:\n",
        "- At the same time, search forward from initial state and backwards from goal state(s), with the idea that the\n",
        "two searches will meet\n",
        "- Idea: $b^{d/2} + b^{d/2} < b^{d}$\n",
        "- Need to keep track of two frontiers and two tables of reached states \n",
        "- Solution is found when two frontiers meet \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "```\n",
        "def breadth_first_search(graph: Graph, start: Location, goal: Location):\n",
        "    frontier <- initialize Queue()\n",
        "    put start in frontier\n",
        "    came_from: Dict[Location, Optional[Location]]\n",
        "    initialize came_from[start] = None\n",
        "    \n",
        "    while not frontier.empty():\n",
        "        current <- frontier.get()\n",
        "        \n",
        "        if current == goal:\n",
        "            break\n",
        "        \n",
        "        for next in graph.neighbors(current):\n",
        "            if next not in came_from:\n",
        "                frontier.put(next)\n",
        "                came_from[next] = current\n",
        "    \n",
        "    return came_from\n",
        "\n",
        "-----------------------------------------------------------------\n",
        "\n",
        "def dijkstra_search(graph: WeightedGraph, start: Location, goal: Location):\n",
        "    frontier <- initialize PriorityQueue()\n",
        "    put (start, 0) in frontier\n",
        "    came_from: Dict[Location, Optional[Location]] \n",
        "    cost_so_far: Dict[Location, float] \n",
        "    initialize came_from[start] = None\n",
        "    initialize cost_so_far[start] = 0\n",
        "    \n",
        "    while not frontier.empty():\n",
        "        current <- frontier.get()\n",
        "        \n",
        "        if current == goal:\n",
        "            break\n",
        "        \n",
        "        for next in graph.neighbors(current):\n",
        "            new_cost = cost_so_far[current] + graph.cost(current, next)\n",
        "            if next not in cost_so_far or new_cost < cost_so_far[next]:\n",
        "                update cost_so_far[next] = new_cost\n",
        "                priority = new_cost\n",
        "                frontier.put(next, priority)\n",
        "                update came_from[next] = current\n",
        "    \n",
        "    return came_from, cost_so_far\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "\"atomic representations\": \"states of the world considered whole (blackbox) with no internal structure visible\",\n",
        "\"factored representations\": \"states represented as assignments of values to variables\",\n",
        "\"informed search\": \"agent can estimate how far it is from goal\", \n",
        "\"uninformed search\": \"agent cannot estimate how far it is from goal\",\n",
        "\"open loop\": \"ignoring percepts\", \n",
        "\"closed loop\": \"monitoring percepts\",\n",
        "\"model\": \"abstract math formulation (not the real thing)\",\n",
        "\"late goal test\": \"check if node is goal when it is popped off the queue (best first search)\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4053b3b5-17ea-46f3-aa88-f73ab0fa6e8d"
      },
      "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))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \n- An agent that considers a sequence of actions to lead to goal state (via search) is a problem-solving agent\n- Problem-solving agents use atomic representations of states \n- Planning agents use factored or structured representations of states\n- In fully observable, deterministic, known environment: solution to problem is a fixed sequence of actions\n- Search: agent simulates sequences of actions in the model, until it finds sequence that reaches the goal \n- Solution: sequence of actions that lead to the goal \n- State space can be represented as graph: vertices (states) and edges (actions)\n\nSearch problem components:\n- State space: Set of possible states for the environment\n- Initial state\n- Goal states\n- Actions available to agent: set of actions that can be executed in $s$\n- Transition model: returns the state that is the result of performing action $a$ in state $s$\n- Action cost function: cost of action $a$ in state $s$ to reach state $s'$\n\n\n## AIMA Chapter 3.2 Example Problems\n \nStandardized problems: \n- Used to illustrate problem solving methods (grid world, sliding tiles)\n- Has concise, exact description\n- Suitable as a benchmark to compare performance of algorithms\n\nReal world problems:\n- One whose solutions people actually use (route-finding, robot navigationm touring problem)\n- Formulation is not standardized\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \nState space:\n- Describes set of spaces in the world (can be infinite) and actions that transition from one state to another\n\nSearch tree:\n- Describes paths between states, reaching towards the goal\n- Each node in the tree has unique path back to the root \n\nA node in tree has 4 components:\n- State: that node corresponds to \n- Parent: node that generated current node\n- Action: action applied to parent to generate current node\n- Path cost: total cost of path from initial state to current node \n\nQueue types:\n- Priority: removes node with minimum cost according to evaluation function. Used in best first.\n- FIFO: used in BFS \n- LIFO: used in DFS\n\nGraph search:\n- Search algorithm that checks for redundant paths\n- Needs to store previously seen states, requires more memory\n- Does not waste time going down redundant paths, saves time \n- examples: Best first search \n\nTree-like search:\n- Search algorithm that does not check for redundant paths \n- Does not store previous states, requires less memory \n- Could potentially go down redundant path, which would waste time \n\nIn both cases, state space is the same graph. We are just treating how to search it. \n\nCriteria for search:\n- Completeness: Will search find solution or correctly report failure if there is no solution?\n- Cost optimality: Will search find lowest path cost?\n- Time / space complexity\n\nTime and space:\n- Many graphs are represented implicitly instead of as explicit graph. Defined by initial state, actions, and transition model. Instead, measure with:\n- $d$: depth in optimal solution\n- $m$: max number of actions in any path \n- $b$: branching factor: number of successors of a node to consider \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nBFS:\n- Appropriate when actions have the same cost\n- Complete, even on infinite spaces\n- Cost optimal if all actions have same cost; not necessarily otherwise\n- Use evaluation $f(n) = $ depth of node / number of actions to reach node \n- Perform early goal test: checking if node is solution as soon as it is generated  \n- Total number of nodes generated: $1 + b + b^2 + ... + b^d = O(b^d)$, assuming solution at depth $d$\n- Time and space is $O(b^d)$. \n- All nodes generated remain in memory; memory requirement bigger issue than time requirement \n\nUniform cost (Dijkstra):\n- Use evaluation function $g(n) =$ cost of path from root node to current node\n- Test for goal when you expand a node, not when a node is generated \n- Time and space complexity: $O(b^{1 + C^*/\\epsilon})$, which may be $>> O(b^d)$ because Dijkstra may explore large areas that have low cast actions\nbefore exploring paths with higher actions\n- If all action costs are equal, $b^{1 + C^*/\\epsilon} = b^{d+1}$\n\nDFS:\n- Tree like search that does not remember reached states (so it uses less memory)\n- Not cost optimal; returns first solution it finds \n- Incomplete: Can get stuck in infinite loops in cyclic state spaces. Or it can get stuck going down an infinite path even if there are no cycles.\n- DFS only complete and efficient in finite state spaces. Efficient in acyclic state spaces.\n- Space complexity $O(bm)$\n- Time complexity $O(b^m)$\n\nDepth-limited search:\n- DFS with depth limit $l$. Treat all nodes at depth $l$ as if they had no successors\n- Time complexity $O(b^l)$\n- Space complexity $O(bl)$\n- Incomplete if $l < d$, we don't reach solution because we don't go deep enough\n- Not optimal if $l > d$, we explored too deep \n- Optimal if $l = d$\n\nIterative deepening:\n- Space complexity: $O(bd)$ if solution exists, or $O(bm)$ on finite state spaces without solution\n- Time complexity: $O(b^d)$ if solution exists, or $O(b^m)$ without solution\n- Optimal if all action costs are the same (like BFS)\n- Complete on finite acyclic / finite state spaces if you check for cycles \n\nBidirectional search:\n- At the same time, search forward from initial state and backwards from goal state(s), with the idea that the\ntwo searches will meet\n- Idea: $b^{d/2} + b^{d/2} < b^{d}$\n- Need to keep track of two frontiers and two tables of reached states \n- Solution is found when two frontiers meet \n\n\n## Module 3 Lecture Notes\n \n```\ndef breadth_first_search(graph: Graph, start: Location, goal: Location):\n    frontier <- initialize Queue()\n    put start in frontier\n    came_from: Dict[Location, Optional[Location]]\n    initialize came_from[start] = None\n    \n    while not frontier.empty():\n        current <- frontier.get()\n        \n        if current == goal:\n            break\n        \n        for next in graph.neighbors(current):\n            if next not in came_from:\n                frontier.put(next)\n                came_from[next] = current\n    \n    return came_from\n\n-----------------------------------------------------------------\n\ndef dijkstra_search(graph: WeightedGraph, start: Location, goal: Location):\n    frontier <- initialize PriorityQueue()\n    put (start, 0) in frontier\n    came_from: Dict[Location, Optional[Location]] \n    cost_so_far: Dict[Location, float] \n    initialize came_from[start] = None\n    initialize cost_so_far[start] = 0\n    \n    while not frontier.empty():\n        current <- frontier.get()\n        \n        if current == goal:\n            break\n        \n        for next in graph.neighbors(current):\n            new_cost = cost_so_far[current] + graph.cost(current, next)\n            if next not in cost_so_far or new_cost < cost_so_far[next]:\n                update cost_so_far[next] = new_cost\n                priority = new_cost\n                frontier.put(next, priority)\n                update came_from[next] = current\n    \n    return came_from, cost_so_far\n```\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Atomic representations** - states of the world considered whole (blackbox) with no internal structure visible\n* **Factored representations** - states represented as assignments of values to variables\n* **Informed search** - agent can estimate how far it is from goal\n* **Uninformed search** - agent cannot estimate how far it is from goal\n* **Open loop** - ignoring percepts\n* **Closed loop** - monitoring percepts\n* **Model** - abstract math formulation (not the real thing)\n* **Late goal test** - check if node is goal when it is popped off the queue (best first search)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "- Informed search: uses domain specfic hints (heuristic function) about location for goals. \n",
        "- $h(n)$: estimated least cost path from node $n$ to goal node \n",
        "- $g(n)$: cost so far of path from initial node to current node $n$\n",
        "\n",
        "Greedy:\n",
        "- Greedy best first expands node with the lowest $h(n)$, which is the node that seems closest to the goal.\n",
        "Greedy finds a solution without ever expanding a node that is not on the solution path, but it won't \n",
        "always find the optimal path\n",
        "- Greedy is complete in finite state spaces, but not complete in infinite state spaces\n",
        "- Greedy time and space complexity is $O(|V|)$ but can be reduced to $O(bm)$ with a good heurstic \n",
        "\n",
        "A-star:\n",
        "- A* is a best first search that uses $f(n) = g(n) + h(n)$\n",
        "- $f(n)$: estimated cost of the best path that continues from node $n$ to goal node \n",
        "- A* checks whether a node is a solution when the node is selected for expansion (because then the node is the \n",
        "lowest-cost node on the frontier)\n",
        "- A* complete\n",
        "- A* cost-optimal with admissible heuristic (but may OR may not be cost optimal with inadmissible one)\n",
        "- If C* is the cost of the optimal path, then A* will never expand nodes with $f(n) > C*$\n",
        "- Weighted A* search: $f(n) = g(n) + W \\\\cdot h(n)$ for $W > 1$ will find a solution that costs between $C*$ (optimal)\n",
        "and $W \\\\cdot C*$, but much faster and expands fewer nodes\n",
        "\n",
        "Consistency:\n",
        "- Consistency is a stronger claim than admissibility\n",
        "- Consistency: heuristic $h(n)$ is consistent if, for every node $n$ and successor $n'$ of $n$ generated by action $a$\n",
        "we have: $h(n) \\\\leq cost(n, a, n') + h(n')$ \n",
        "- $h$ is consistent if the cost of going to a successor node $n'$ plus the cost of the heuristic $h(n')$ (estimated remaining cost from $n'$ to goal node)\n",
        "is greater than or equal to $h(n)$\n",
        "- With consistency: the first time you reach a state it will be on an optimal path. You don't have to re-add a \n",
        "state to the frontier, and you don't have to change an entry with reached \n",
        "- With inconsistency: you may end up with multiple paths reaching the same state. You may end up with multiple\n",
        "nodes for that state in the frontier (if new paths are cheaper than previous paths)\n",
        "- Straight line heuristic is a consistent heuristic \n",
        "\n",
        "Search contours for A*:\n",
        "- Nodes inside a given contour have costs $\\\\leq$ contour value\n",
        "- A* fans out from start node and adds nodes in concentric bands of increasing $f$-cost. The contours stretch\n",
        "towards goal state and become more narrowly focused on optimal path \n",
        "- $f$-costs are not always monotonically increasing \n",
        "- $f$ path cost monotonically increasing if and only if the heuristic is consistent \n",
        "\n",
        "Search contours for Dijkstra:\n",
        "- Dijkstra (uniform-cost) has contours using $g$-cost. The contours are circular around start node and \n",
        "spreads out equally in all directions without preference toward goal \n",
        "- $g$-costs are monotonic: path costs always increase \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter3_6 = \"\"\" \n",
        "- Characterize the quality of a heuristic function using $b*:$ effective branching factor\n",
        "- $b*$ is the branching factor that a uniform tree of depth $d$ would have to have to contain $N+1$ nodes\n",
        "$N+1 = 1 + b* + (b*)^2 + ... + (b*)^d$\n",
        "- Well designed heuristics has $b*$ close to $1$\n",
        "- Can also characterize the quality of a heuristic function with how much it reduces the effective depth by, i.e.\n",
        "total search cost $O(b^{d-k_{h}})$ vs. $O(b^d)$\n",
        "- $h_2$ dominates $h_1$: for any node $n$, $h_2(n) \\\\geq h_1(n)$\n",
        "- In example above, A* will never expand more nodes using $h_2$\n",
        "\n",
        "Relaxed problems:\n",
        "- Graph of a relaxed problem is a supergraph of the original graph \n",
        "- The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "```\n",
        "def dijkstra_search(graph: WeightedGraph, start: Location, goal: Location):\n",
        "    frontier <- initalize PriorityQueue()\n",
        "    put (start, 0) in frontier\n",
        "    came_from: Dict[Location, Optional[Location]] \n",
        "    cost_so_far: Dict[Location, float] \n",
        "    initialize came_from[start] = None\n",
        "    initialize cost_so_far[start] = 0\n",
        "    \n",
        "    while not frontier.empty():\n",
        "        current <- frontier.get()\n",
        "        \n",
        "        if current == goal:\n",
        "            break\n",
        "        \n",
        "        for next in graph.neighbors(current):\n",
        "            new_cost = cost_so_far[current] + graph.cost(current, next)\n",
        "            if next not in cost_so_far or new_cost < cost_so_far[next]:\n",
        "                update cost_so_far[next] = new_cost\n",
        "                priority = new_cost\n",
        "                frontier.put(next, priority)\n",
        "                update came_from[next] = current\n",
        "    \n",
        "    return came_from, cost_so_far\n",
        "\n",
        "----------------------------------------------------------------------\n",
        "\n",
        "def heuristic(a: GridLocation, b: GridLocation) -> float:\n",
        "    (x1, y1) = a\n",
        "    (x2, y2) = b\n",
        "    return |x1 - x2| + |y1 - y2|\n",
        "\n",
        "def a_star_search(graph: WeightedGraph, start: Location, goal: Location):\n",
        "    frontier <- initialize PriorityQueue()\n",
        "    put (start, 0) in frontier\n",
        "    came_from: Dict[Location, Optional[Location]] \n",
        "    cost_so_far: Dict[Location, float]\n",
        "    initialize came_from[start] = None\n",
        "    initialize cost_so_far[start] = 0\n",
        "    \n",
        "    while not frontier.empty():\n",
        "        current <- frontier.get()\n",
        "        \n",
        "        if current == goal:\n",
        "            break\n",
        "        \n",
        "        for next in graph.neighbors(current):\n",
        "            new_cost = cost_so_far[current] + graph.cost(current, next)\n",
        "            if next not in cost_so_far or new_cost < cost_so_far[next]:\n",
        "                update cost_so_far[next] = new_cost\n",
        "                priority = new_cost + heuristic(next, goal)\n",
        "                frontier.put(next, priority)\n",
        "                update came_from[next] = current\n",
        "    \n",
        "    return came_from, cost_so_far\n",
        "```\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissible heuristic\" : \"never overestimates cost to goal i.e. optimistic\", \n",
        "\"optimally efficient\": \"any other algorithm using the same heuristic info would have to expand the same nodes\",\n",
        "\"satisficing\": \"solutions that are subptimal but good enough\",\n",
        "\"bounded suboptimal search\": \"find solution guaranteed to be within constant factor $W$ of optimal cost\",\n",
        "\"bounded cost search\": \"find solution whose cost is $< C$, a constant\", \n",
        "\"unbounded cost search\": \"accept solution of any cost, just find it quickly\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "2d6ead27-1e89-492b-fbd9-892bce1ab1bb"
      },
      "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))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n- Informed search: uses domain specfic hints (heuristic function) about location for goals. \n- $h(n)$: estimated least cost path from node $n$ to goal node \n- $g(n)$: cost so far of path from initial node to current node $n$\n\nGreedy:\n- Greedy best first expands node with the lowest $h(n)$, which is the node that seems closest to the goal.\nGreedy finds a solution without ever expanding a node that is not on the solution path, but it won't \nalways find the optimal path\n- Greedy is complete in finite state spaces, but not complete in infinite state spaces\n- Greedy time and space complexity is $O(|V|)$ but can be reduced to $O(bm)$ with a good heurstic \n\nA-star:\n- A* is a best first search that uses $f(n) = g(n) + h(n)$\n- $f(n)$: estimated cost of the best path that continues from node $n$ to goal node \n- A* checks whether a node is a solution when the node is selected for expansion (because then the node is the \nlowest-cost node on the frontier)\n- A* complete\n- A* cost-optimal with admissible heuristic (but may OR may not be cost optimal with inadmissible one)\n- If C* is the cost of the optimal path, then A* will never expand nodes with $f(n) > C*$\n- Weighted A* search: $f(n) = g(n) + W \\cdot h(n)$ for $W > 1$ will find a solution that costs between $C*$ (optimal)\nand $W \\cdot C*$, but much faster and expands fewer nodes\n\nConsistency:\n- Consistency is a stronger claim than admissibility\n- Consistency: heuristic $h(n)$ is consistent if, for every node $n$ and successor $n'$ of $n$ generated by action $a$\nwe have: $h(n) \\leq cost(n, a, n') + h(n')$ \n- $h$ is consistent if the cost of going to a successor node $n'$ plus the cost of the heuristic $h(n')$ (estimated remaining cost from $n'$ to goal node)\nis greater than or equal to $h(n)$\n- With consistency: the first time you reach a state it will be on an optimal path. You don't have to re-add a \nstate to the frontier, and you don't have to change an entry with reached \n- With inconsistency: you may end up with multiple paths reaching the same state. You may end up with multiple\nnodes for that state in the frontier (if new paths are cheaper than previous paths)\n- Straight line heuristic is a consistent heuristic \n\nSearch contours for A*:\n- Nodes inside a given contour have costs $\\leq$ contour value\n- A* fans out from start node and adds nodes in concentric bands of increasing $f$-cost. The contours stretch\ntowards goal state and become more narrowly focused on optimal path \n- $f$-costs are not always monotonically increasing \n- $f$ path cost monotonically increasing if and only if the heuristic is consistent \n\nSearch contours for Dijkstra:\n- Dijkstra (uniform-cost) has contours using $g$-cost. The contours are circular around start node and \nspreads out equally in all directions without preference toward goal \n- $g$-costs are monotonic: path costs always increase \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \n- Characterize the quality of a heuristic function using $b*:$ effective branching factor\n- $b*$ is the branching factor that a uniform tree of depth $d$ would have to have to contain $N+1$ nodes\n$N+1 = 1 + b* + (b*)^2 + ... + (b*)^d$\n- Well designed heuristics has $b*$ close to $1$\n- Can also characterize the quality of a heuristic function with how much it reduces the effective depth by, i.e.\ntotal search cost $O(b^{d-k_{h}})$ vs. $O(b^d)$\n- $h_2$ dominates $h_1$: for any node $n$, $h_2(n) \\geq h_1(n)$\n- In example above, A* will never expand more nodes using $h_2$\n\nRelaxed problems:\n- Graph of a relaxed problem is a supergraph of the original graph \n- The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n\n\n## Module 4 Lecture Notes\n \n```\ndef dijkstra_search(graph: WeightedGraph, start: Location, goal: Location):\n    frontier <- initalize PriorityQueue()\n    put (start, 0) in frontier\n    came_from: Dict[Location, Optional[Location]] \n    cost_so_far: Dict[Location, float] \n    initialize came_from[start] = None\n    initialize cost_so_far[start] = 0\n    \n    while not frontier.empty():\n        current <- frontier.get()\n        \n        if current == goal:\n            break\n        \n        for next in graph.neighbors(current):\n            new_cost = cost_so_far[current] + graph.cost(current, next)\n            if next not in cost_so_far or new_cost < cost_so_far[next]:\n                update cost_so_far[next] = new_cost\n                priority = new_cost\n                frontier.put(next, priority)\n                update came_from[next] = current\n    \n    return came_from, cost_so_far\n\n----------------------------------------------------------------------\n\ndef heuristic(a: GridLocation, b: GridLocation) -> float:\n    (x1, y1) = a\n    (x2, y2) = b\n    return |x1 - x2| + |y1 - y2|\n\ndef a_star_search(graph: WeightedGraph, start: Location, goal: Location):\n    frontier <- initialize PriorityQueue()\n    put (start, 0) in frontier\n    came_from: Dict[Location, Optional[Location]] \n    cost_so_far: Dict[Location, float]\n    initialize came_from[start] = None\n    initialize cost_so_far[start] = 0\n    \n    while not frontier.empty():\n        current <- frontier.get()\n        \n        if current == goal:\n            break\n        \n        for next in graph.neighbors(current):\n            new_cost = cost_so_far[current] + graph.cost(current, next)\n            if next not in cost_so_far or new_cost < cost_so_far[next]:\n                update cost_so_far[next] = new_cost\n                priority = new_cost + heuristic(next, goal)\n                frontier.put(next, priority)\n                update came_from[next] = current\n    \n    return came_from, cost_so_far\n```\n\n\n\n## Module 4 Definitions\n* **Admissible heuristic** - never overestimates cost to goal i.e. optimistic\n* **Optimally efficient** - any other algorithm using the same heuristic info would have to expand the same nodes\n* **Satisficing** - solutions that are subptimal but good enough\n* **Bounded suboptimal search** - find solution guaranteed to be within constant factor $W$ of optimal cost\n* **Bounded cost search** - find solution whose cost is $< C$, a constant\n* **Unbounded cost search** - accept solution of any cost, just find it quickly\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "A game can be fully defined with the following components:\n",
        "- Initial state\n",
        "- Player whose turn it is to move in state $s$\n",
        "- Set of legal moves in state $s$\n",
        "- Transition model: define the state resulting from taking action $a$ in state $s$\n",
        "- Terminal test \n",
        "- Utility function: defines final numeric value to player $p$ when game ends \n",
        "\n",
        "- Game tree: search tree that follows sequence of moves to a terminal state (may be infinite)\n",
        "\"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" \n",
        "- Given game tree, optimal strategy determined by computing minimax value of each state. \n",
        "- Minimax value is the utility (for MAX) of being in that state, assuming both players play optimally. \n",
        "- Minimax value of terminal state is just its utility.\n",
        "\n",
        "Analysis of mini-max:\n",
        "- Max depth of tree is $m$ and $b$ legal moves at each point\n",
        "- Time complexity $O(b^m)$\n",
        "- Space complexity is $O(bm)$ if you generate all actions at once, or $O(m)$ if you generate actions one at a time\n",
        "\n",
        "Alpha-Beta Pruning:\n",
        "- Pruning allows us to cut the exponent in half \n",
        "- Big idea: Consider node $n$. If a player has a better choice at the same level (as $n$) or higher up in the tree, then \n",
        "the player will never move to $n$.\n",
        "- With perfect move ordering, alpha-beta would only need to examine $O(b^{m/2})$ nodes\n",
        "\n",
        "- $\\\\alpha$: value of the best (highest-value) choice we have found so far at any choice point along the path for max (\"at least\")\n",
        "- $\\\\beta$: value of the best (lowest-value) choice we have found so far at any choice point along the path for min (\"at most\")\n",
        "\n",
        "- In game trees search, repeated states can occur due to transpositions: different permutations of move sequence that end up in the same position\n",
        "- Some games cannot be solved with alpha-beta pruning and clever move ordering. Two strategies exist:\n",
        "- Type A: \"wide but shallow\" (Chess)\n",
        "- Type B: \"deep but narrow\" (Go)\n",
        "\"\"\"\n",
        "\n",
        "chapter5_3 = \"\"\" \n",
        "- Heuristic evaluation function returns estimate of expected utility of state $s$ to player $p$\n",
        "- Forward pruning prunes moves that appear to be bad, but might possibly be good \n",
        "(this saves computational time but is risky because you may make an error).\n",
        "- One forward pruning method is beam search\n",
        "- Probabilistic cut: uses statistics to reduce chance that the best move is pruned. Prunes node that are *probably* outside\n",
        "the current $(\\\\alpha, \\\\beta)$ window.\n",
        "- Late move reduction: assumption that moves that appear later in the list of possible moves are less likely to be good ones.\n",
        "\"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\" \n",
        "- Due to the stochastic nature, positions do not have definite minimax values. You can only calculate the expected value\n",
        "of a position by averaging over all possible outcomes of the chance nodes. \n",
        "- Expectimax is considering all possible dice-roll sequences, which will take $O(b^{m} n^{m})$ where $n$ is the number\n",
        "of distinct dice rolls.\n",
        "- Pruning is possible with expectimax.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "```\n",
        "def alpha_beta():\n",
        "    # Runtime is O(b^m)\n",
        "    return max(alpha=-inf, beta=inf, limit)\n",
        "\n",
        "def alpha_beta_max(alpha, beta, limit):\n",
        "    if game is over or limit == 0:\n",
        "        return evaluation or heuristic function\n",
        "    \n",
        "    initialize val <- -inf\n",
        "    for move, new_game in max's successors:\n",
        "        new_move, new_val = alpha_beta_min(alpha, beta, limit - 1)\n",
        "\n",
        "    if new_val > val:\n",
        "        update val and best move <- new_val and move\n",
        "        alpha = max(alpha, val)\n",
        "    if val >= beta:\n",
        "        return best_move, val\n",
        "\n",
        "def alpha_beta_min():\n",
        "    if game is over or limit == 0:\n",
        "        return evaluation heuristic function\n",
        "    \n",
        "    initialize val = inf\n",
        "    for move, new_game in min's successors:\n",
        "        new_move, new_val = alpha_beta_max(alpha, beta, limit - 1)\n",
        "\n",
        "    if new_val < val:\n",
        "        update val and best move <- new_val and move \n",
        "        beta = min(beta, val)\n",
        "    if val <= alpha:\n",
        "        return best_move, val\n",
        "\n",
        "------------------------------------------------------------\n",
        "\n",
        "def minimax(node, depth, maximizingPlayer):\n",
        "\n",
        "    if depth = 0 or node is a terminal node then\n",
        "        return the heuristic value of node\n",
        "    if maximizingPlayer then\n",
        "        value := −∞\n",
        "        for each child of node do\n",
        "            value := max(value, minimax(child, depth − 1, FALSE))\n",
        "        return value\n",
        "    else (* minimizing player *)\n",
        "        value := +∞\n",
        "        for each child of node do\n",
        "            value := min(value, minimax(child, depth − 1, TRUE))\n",
        "        return value\n",
        "\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"synonym for fully observable\",\n",
        "\"quiescent\": \"positions in which there is no pending move that would dramatically swing the evaluation\",\n",
        "\"horizon effect\": \"program faces an opponent's move that causes serious damage and is unavoidable, but can only be temporarily delayed\" \n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "784e46bb-ded5-4a67-aa46-cff22fd344cd"
      },
      "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))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nA game can be fully defined with the following components:\n- Initial state\n- Player whose turn it is to move in state $s$\n- Set of legal moves in state $s$\n- Transition model: define the state resulting from taking action $a$ in state $s$\n- Terminal test \n- Utility function: defines final numeric value to player $p$ when game ends \n\n- Game tree: search tree that follows sequence of moves to a terminal state (may be infinite)\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n- Given game tree, optimal strategy determined by computing minimax value of each state. \n- Minimax value is the utility (for MAX) of being in that state, assuming both players play optimally. \n- Minimax value of terminal state is just its utility.\n\nAnalysis of mini-max:\n- Max depth of tree is $m$ and $b$ legal moves at each point\n- Time complexity $O(b^m)$\n- Space complexity is $O(bm)$ if you generate all actions at once, or $O(m)$ if you generate actions one at a time\n\nAlpha-Beta Pruning:\n- Pruning allows us to cut the exponent in half \n- Big idea: Consider node $n$. If a player has a better choice at the same level (as $n$) or higher up in the tree, then \nthe player will never move to $n$.\n- With perfect move ordering, alpha-beta would only need to examine $O(b^{m/2})$ nodes\n\n- $\\alpha$: value of the best (highest-value) choice we have found so far at any choice point along the path for max (\"at least\")\n- $\\beta$: value of the best (lowest-value) choice we have found so far at any choice point along the path for min (\"at most\")\n\n- In game trees search, repeated states can occur due to transpositions: different permutations of move sequence that end up in the same position\n- Some games cannot be solved with alpha-beta pruning and clever move ordering. Two strategies exist:\n- Type A: \"wide but shallow\" (Chess)\n- Type B: \"deep but narrow\" (Go)\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n- Heuristic evaluation function returns estimate of expected utility of state $s$ to player $p$\n- Forward pruning prunes moves that appear to be bad, but might possibly be good \n(this saves computational time but is risky because you may make an error).\n- One forward pruning method is beam search\n- Probabilistic cut: uses statistics to reduce chance that the best move is pruned. Prunes node that are *probably* outside\nthe current $(\\alpha, \\beta)$ window.\n- Late move reduction: assumption that moves that appear later in the list of possible moves are less likely to be good ones.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \n- Due to the stochastic nature, positions do not have definite minimax values. You can only calculate the expected value\nof a position by averaging over all possible outcomes of the chance nodes. \n- Expectimax is considering all possible dice-roll sequences, which will take $O(b^{m} n^{m})$ where $n$ is the number\nof distinct dice rolls.\n- Pruning is possible with expectimax.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \n```\ndef alpha_beta():\n    # Runtime is O(b^m)\n    return max(alpha=-inf, beta=inf, limit)\n\ndef alpha_beta_max(alpha, beta, limit):\n    if game is over or limit == 0:\n        return evaluation or heuristic function\n    \n    initialize val <- -inf\n    for move, new_game in max's successors:\n        new_move, new_val = alpha_beta_min(alpha, beta, limit - 1)\n\n    if new_val > val:\n        update val and best move <- new_val and move\n        alpha = max(alpha, val)\n    if val >= beta:\n        return best_move, val\n\ndef alpha_beta_min():\n    if game is over or limit == 0:\n        return evaluation heuristic function\n    \n    initialize val = inf\n    for move, new_game in min's successors:\n        new_move, new_val = alpha_beta_max(alpha, beta, limit - 1)\n\n    if new_val < val:\n        update val and best move <- new_val and move \n        beta = min(beta, val)\n    if val <= alpha:\n        return best_move, val\n\n------------------------------------------------------------\n\ndef minimax(node, depth, maximizingPlayer):\n\n    if depth = 0 or node is a terminal node then\n        return the heuristic value of node\n    if maximizingPlayer then\n        value := −∞\n        for each child of node do\n            value := max(value, minimax(child, depth − 1, FALSE))\n        return value\n    else (* minimizing player *)\n        value := +∞\n        for each child of node do\n            value := min(value, minimax(child, depth − 1, TRUE))\n        return value\n\n```\n\n\n## Module 5 Definitions\n* **Perfect information** - synonym for fully observable\n* **Quiescent** - positions in which there is no pending move that would dramatically swing the evaluation\n* **Horizon effect** - program faces an opponent's move that causes serious damage and is unavoidable, but can only be temporarily delayed\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "- CSP consists of three components: set of variables, set of domains, set of constraints that\n",
        "specify allowable combinations of values. CSPs deal with assignments of values to variables.\n",
        "A consistent assignment does not violate any constraints. A complete assignment is one where every\n",
        "variable is assigned a value. A solution is a complete, consistent assignment. \n",
        "\n",
        "- CSPs represents the conditions for a solution with constraints on the variables.\n",
        "\n",
        "- Visualize a CSP as a constraint graph: nodes are variables of the problem, edge connects any two\n",
        "variables in a constraint. \n",
        "\n",
        "- Every finite-domain (n-ary) constraint can be reduced to set of binary constraints. \n",
        "\"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\"\n",
        "- Constraint propagation uses constraints to reduce the number of legal values for a variable, which\n",
        "propagates reductions to the next variable, and so on. The key idea is local consistency. Enforcing local\n",
        "consistency results in inconsistent values being eliminated throughout the graph. Local consistency includes\n",
        "node, arc, path, and k-consistency. \n",
        "\n",
        "- Arc consistency: $X_i$ is arc consistent to $X_j$ if for every value in $D_i$ there is some value in $D_j$\n",
        "that satisfies the binary constraint on $(X_i, X_j)$. We reduce the domain of $X_i$ in order to make $X_i$ \n",
        "arc-consistent with $X_j$.\n",
        "\n",
        "- AC-3: Queue contains all arcs in the CSP. Make $X_i$ arc consistent with $X_j$ for arc $(X_i, X_j)$.\n",
        "If $D_i$ is unchanged, move on to next arc. Else, add to queue $(X_k, X_i)$ all the neighbors of $X_i$. \n",
        "Runtime is $O(cd^3)$, where $c=$ number of binary constraints/arcs and $d=$ domain size.\n",
        "\n",
        "- Path consistency: $\\{X_i, X_j\\}$ is path consistent to $X_m$ if for every assignment $\\{X_i=a, X_j=b\\}$ consistent with\n",
        "constraints on $\\{X_i, X_j\\}$, there is an assignment to $X_m$ that satisfies constraints $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$.\n",
        "\n",
        "- K-consistency: Given any set of $k-1$ variables and any consistent assignment to those variables, a consistent\n",
        "value can always be assigned to any $k^{th}$ variable, i.e. 1-consistency: given empty set, we can make any set of \n",
        "1 variable consistent.\n",
        "\n",
        "- Strongly k-consistent: If it is k-consistent, $k-1$ consistent, and .... $1-$consistent. \n",
        "Total runime is $O(dn^2)$ for *solving* CSP that is strongly n-consistent.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter6_3 = \"\"\"\n",
        "- Constraint propagation does not guarantee a solution. Sometimes you will have to search for a solution. \n",
        "Backtracking search works well for partial assignments. For a CSP with $n$ variables and domain size $d$,\n",
        "a complete assignment (all solutions) are leaf nodes at depth $n$. There are $d^n$ leaves.\n",
        "\n",
        "- In CSP search tree, you only need to consider a single variable at each node in the search tree (commutativity).\n",
        "But you need to determine how to choose which unassigned variable to pick next. You can use domain-independent \n",
        "heuristics for this. Simplest heuristics are choosing variables in order, or randomly.\n",
        "\n",
        "Variable selection:\n",
        "- Minimum remaining value heuristic: Choosing variable with the fewest \"legal\" values (most constrained/fail first).\n",
        "- Degree heuristic: Selecting variable with the largest number of constraints on other unassigned variables \n",
        "(highest degree in map coloring problem).\n",
        "\n",
        "Value selection:\n",
        "- Least constraining value heuristic: Prefer value that rules out fewest choices for neighboring values \n",
        "(leave max. flexibility for further variable assignment).\n",
        "\n",
        "Inference during search:\n",
        "- Forward checking: Establish arc consistency whenever $X$ is assigned a value. For each unassigned $Y$ that \n",
        "is connected to $X$ by constraint, delete from $Y$'s domain any value that is inconsistent with $X$. \n",
        "Problem with this is it does not look too far ahead.\n",
        "\n",
        "- MAC: Call AC-3 after $X_i$ is assigned a value, but only queue arcs $(X_j, X_i)$ for unassigned variables $X_j$\n",
        "that are neighbors of $X_i$. Then let AC-3 do constraint propagation the usual way. MAC is more powerful than\n",
        "forward checking because it propagates constraints when changes are made to the domains of variables. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter6_4 = \"\"\" \n",
        "- Local search: Start with complete state (each state assigns a value to every variable), and change the value of\n",
        "one variable one at a time, during the course of search. Ideally, change the value to something that brings us closer\n",
        "to the solution (i.e. min conflicts heuristics).\n",
        "\n",
        "- Min conflicts heuristic: Select the value that results in the min number of conflicts with other variables. Runtime\n",
        "is roughly independent of problem size. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter6_5 = \"\"\"\n",
        "- Decompose structure of problem into smaller subproblems so that it can be solved quickly.\n",
        "This uses the idea of independent subproblems, a solution for one independent subproblem combined with any solution for \n",
        "another independent subproblem yields a solution for the whole problem. Independence is determined by finding \n",
        "connected components of the constraint graph.\n",
        "\n",
        "- Without decomposition, total work is $O(d^n)$. With decomposition, total work is $O(nd^c / c)$, which is linear in $n$. \n",
        "Caveat here is that completely independent subproblems are rare. \n",
        "\n",
        "- Constraint graph is a tree when any two variables are connected by only one path. \n",
        "Any tree-structured CSP can be solved in linear time, in the number of variables. This uses\n",
        "directional arc consistency (DAC) for consistency.\n",
        "\n",
        "- General constraint graphs can be reduced to trees by removing nodes (cutset conditioning) \n",
        "or collapsing nodes together (tree decomposition).\n",
        "\n",
        "- Cutset conditioning: Assign a value to some set of variables S, delete from the domain of other variables any values\n",
        "that are inconsistent with the value chosen in S. The remaining variables (not in S) form a tree. \n",
        "\n",
        "- S is a cycle cutset: Subset of the CSP variables such that the constraint becomes a tree after you remove S. \n",
        "If the cycle cutset has size $c$ the total runtime is $O(d^c(n-c)d^2)$. You want the smallest $c$ for more efficiency.\n",
        "\n",
        "- Tree decomposition: transform the original graph into a tree where each node in the tree is a set of variables.\n",
        "Tree decomposition problems can be solved in $O(nd^2)$ time (Clarify?).\n",
        "\n",
        "- Tree decomposition transform the CSP into a tree of subproblems\n",
        "\n",
        "- Tree width $w$ of tree decomposition is one less than the size of the largest node.\n",
        "- Tree width of graph itself is the minimum width among all its tree decompositions.\n",
        "- Graph with tree width $w$ can be solved in $O(nd^{w+1})$ given corresponding tree decomposition.\n",
        "\n",
        "Cutset vs. tree decomposition:\n",
        "- Tree decomposition is faster, but requires memory exponential in $w$\n",
        "- Cutset conditioning is linear in memory\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"unary constraint\" : \"restricts the value of a single variable\",\n",
        "\"binary CSP\": \"a CSP with only unary and binary constraints (can be represented as constraint graph)\",\n",
        "\"global constraint\": \"involving an arbitrary number of variables (does not need to involve all variables)\",\n",
        "\"constrainted optimization problem\": \"CSPs with preferences (morning/afternoon)\",\n",
        "\"constraint learning\": \"finding a minimum set of variables from conflict set that causes the problem\",\n",
        "\"backjumping method\": \"backtracks to the most recent assignment in the conflict set\", \n",
        "\"chronological backtracking\": \"backtrack to the most recent decision point\"\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "4946c606-01d7-4a40-eb7b-361dd5049205"
      },
      "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))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \n- CSP consists of three components: set of variables, set of domains, set of constraints that\nspecify allowable combinations of values. CSPs deal with assignments of values to variables.\nA consistent assignment does not violate any constraints. A complete assignment is one where every\nvariable is assigned a value. A solution is a complete, consistent assignment. \n\n- CSPs represents the conditions for a solution with constraints on the variables.\n\n- Visualize a CSP as a constraint graph: nodes are variables of the problem, edge connects any two\nvariables in a constraint. \n\n- Every finite-domain (n-ary) constraint can be reduced to set of binary constraints. \n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- Constraint propagation uses constraints to reduce the number of legal values for a variable, which\npropagates reductions to the next variable, and so on. The key idea is local consistency. Enforcing local\nconsistency results in inconsistent values being eliminated throughout the graph. Local consistency includes\nnode, arc, path, and k-consistency. \n\n- Arc consistency: $X_i$ is arc consistent to $X_j$ if for every value in $D_i$ there is some value in $D_j$\nthat satisfies the binary constraint on $(X_i, X_j)$. We reduce the domain of $X_i$ in order to make $X_i$ \narc-consistent with $X_j$.\n\n- AC-3: Queue contains all arcs in the CSP. Make $X_i$ arc consistent with $X_j$ for arc $(X_i, X_j)$.\nIf $D_i$ is unchanged, move on to next arc. Else, add to queue $(X_k, X_i)$ all the neighbors of $X_i$. \nRuntime is $O(cd^3)$, where $c=$ number of binary constraints/arcs and $d=$ domain size.\n\n- Path consistency: $\\{X_i, X_j\\}$ is path consistent to $X_m$ if for every assignment $\\{X_i=a, X_j=b\\}$ consistent with\nconstraints on $\\{X_i, X_j\\}$, there is an assignment to $X_m$ that satisfies constraints $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$.\n\n- K-consistency: Given any set of $k-1$ variables and any consistent assignment to those variables, a consistent\nvalue can always be assigned to any $k^{th}$ variable, i.e. 1-consistency: given empty set, we can make any set of \n1 variable consistent.\n\n- Strongly k-consistent: If it is k-consistent, $k-1$ consistent, and .... $1-$consistent. \nTotal runime is $O(dn^2)$ for *solving* CSP that is strongly n-consistent.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n- Constraint propagation does not guarantee a solution. Sometimes you will have to search for a solution. \nBacktracking search works well for partial assignments. For a CSP with $n$ variables and domain size $d$,\na complete assignment (all solutions) are leaf nodes at depth $n$. There are $d^n$ leaves.\n\n- In CSP search tree, you only need to consider a single variable at each node in the search tree (commutativity).\nBut you need to determine how to choose which unassigned variable to pick next. You can use domain-independent \nheuristics for this. Simplest heuristics are choosing variables in order, or randomly.\n\nVariable selection:\n- Minimum remaining value heuristic: Choosing variable with the fewest \"legal\" values (most constrained/fail first).\n- Degree heuristic: Selecting variable with the largest number of constraints on other unassigned variables \n(highest degree in map coloring problem).\n\nValue selection:\n- Least constraining value heuristic: Prefer value that rules out fewest choices for neighboring values \n(leave max. flexibility for further variable assignment).\n\nInference during search:\n- Forward checking: Establish arc consistency whenever $X$ is assigned a value. For each unassigned $Y$ that \nis connected to $X$ by constraint, delete from $Y$'s domain any value that is inconsistent with $X$. \nProblem with this is it does not look too far ahead.\n\n- MAC: Call AC-3 after $X_i$ is assigned a value, but only queue arcs $(X_j, X_i)$ for unassigned variables $X_j$\nthat are neighbors of $X_i$. Then let AC-3 do constraint propagation the usual way. MAC is more powerful than\nforward checking because it propagates constraints when changes are made to the domains of variables. \n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \n- Local search: Start with complete state (each state assigns a value to every variable), and change the value of\none variable one at a time, during the course of search. Ideally, change the value to something that brings us closer\nto the solution (i.e. min conflicts heuristics).\n\n- Min conflicts heuristic: Select the value that results in the min number of conflicts with other variables. Runtime\nis roughly independent of problem size. \n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- Decompose structure of problem into smaller subproblems so that it can be solved quickly.\nThis uses the idea of independent subproblems, a solution for one independent subproblem combined with any solution for \nanother independent subproblem yields a solution for the whole problem. Independence is determined by finding \nconnected components of the constraint graph.\n\n- Without decomposition, total work is $O(d^n)$. With decomposition, total work is $O(nd^c / c)$, which is linear in $n$. \nCaveat here is that completely independent subproblems are rare. \n\n- Constraint graph is a tree when any two variables are connected by only one path. \nAny tree-structured CSP can be solved in linear time, in the number of variables. This uses\ndirectional arc consistency (DAC) for consistency.\n\n- General constraint graphs can be reduced to trees by removing nodes (cutset conditioning) \nor collapsing nodes together (tree decomposition).\n\n- Cutset conditioning: Assign a value to some set of variables S, delete from the domain of other variables any values\nthat are inconsistent with the value chosen in S. The remaining variables (not in S) form a tree. \n\n- S is a cycle cutset: Subset of the CSP variables such that the constraint becomes a tree after you remove S. \nIf the cycle cutset has size $c$ the total runtime is $O(d^c(n-c)d^2)$. You want the smallest $c$ for more efficiency.\n\n- Tree decomposition: transform the original graph into a tree where each node in the tree is a set of variables.\nTree decomposition problems can be solved in $O(nd^2)$ time (Clarify?).\n\n- Tree decomposition transform the CSP into a tree of subproblems\n\n- Tree width $w$ of tree decomposition is one less than the size of the largest node.\n- Tree width of graph itself is the minimum width among all its tree decompositions.\n- Graph with tree width $w$ can be solved in $O(nd^{w+1})$ given corresponding tree decomposition.\n\nCutset vs. tree decomposition:\n- Tree decomposition is faster, but requires memory exponential in $w$\n- Cutset conditioning is linear in memory\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Unary constraint** - restricts the value of a single variable\n* **Binary csp** - a CSP with only unary and binary constraints (can be represented as constraint graph)\n* **Global constraint** - involving an arbitrary number of variables (does not need to involve all variables)\n* **Constrainted optimization problem** - CSPs with preferences (morning/afternoon)\n* **Constraint learning** - finding a minimum set of variables from conflict set that causes the problem\n* **Backjumping method** - backtracks to the most recent assignment in the conflict set\n* **Chronological backtracking** - backtrack to the most recent decision point\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "- Knowledge base is a set of sentences. Each sentence expressed in 'knowledge representation language'\n",
        "and represents assertions about the world. When a sentence is given and doesn't need to be derived, it is an axiom.\n",
        "- Inference means deriving new sentences from old sentences \n",
        "- KB based agent programs maintains a knowledge based, which may initially contain background knowledge\n",
        "- Given percept, the KB agent adds the percept to its KB, asks KB what is the best action, and tells KB it has taken the action\n",
        "\"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\" \n",
        "Your summary here \n",
        "\"\"\"\n",
        "\n",
        "chapter7_3 = \"\"\" \n",
        "- KB sentences expressed according to the syntax of the representation language\n",
        "- Logic defines semantics (meanings of sentences), which define the truth of a sentence with respect to a possible world\n",
        "- Model corresponds to a \"possible world\". They are mathmatical abstractions, with a fixed truth value for every relevant sentence\n",
        "- $x + y = 4$ possible models are all possible assignments of nonnegative integers to $x, y$\n",
        "- If sentence $\\\\alpha$ is true in model $m$, then $m$ satisfies $\\\\alpha$, or $m$ is a model of $\\\\alpha$\n",
        "- $M(\\\\alpha)$: the set of all models of $\\\\alpha$. Meaning, the set of all models $m \\\\in M$ where $\\\\alpha$ is true in $m$\n",
        "\n",
        "Logical entailment:\n",
        "- $\\\\alpha \\\\vDash \\\\beta$ if and only if, in every model where $\\\\alpha$ is true, $\\\\beta$ is also true\n",
        "- $\\\\alpha \\\\vDash \\\\beta$ if and only if $M(\\\\alpha) \\\\subseteq M(\\\\beta)$\n",
        "- If $\\\\alpha \\\\vDash \\\\beta$ then $\\\\alpha$$ is a stronger assertion because it rules out more possible worlds\n",
        "\n",
        "Knowledge base:\n",
        "- KB can be set of sentences or single sentence that asserts multiple sentences\n",
        "- KB is false in models that contradict what the agent knows \n",
        "- Entailment is used to carry out logical inference (derive conclusions)\n",
        "- Set of all consequences of KB is a haystack, and $\\\\alpha$ is a needle. Entailment is like having the needle\n",
        "in the haystack, and inference is finding the needle. \n",
        "\n",
        "Soundness:\n",
        "- $KB \\\\vdash_i \\\\alpha_i$: $\\\\alpha$ is derived from KB by inference algorithm $i$\n",
        "- If inference algorithm derives only entailed sentences, then it is sound/truth preserving \n",
        "\n",
        "Completeness: \n",
        "- Inference algorithm is complete if it can derive all sentence that are entailed \n",
        "\"\"\"\n",
        "\n",
        "chapter7_4 = \"\"\" \n",
        "- Semantics for propositional logic must specify how to compute truth value of \n",
        "any sentence, given model\n",
        "- Sentences constructed from atomic sentences and five connectives \n",
        "(and, or, implied, biconditional, negation)\n",
        "- XOR: (p or q) and ~(p and q)\n",
        "\"\"\"\n",
        "\n",
        "chapter7_5 = \"\"\" \n",
        "- Previous sections determined entailment by model checking: Enumerate models \n",
        "\n",
        "and show that the sentence and show that sentence must hold in all models \n",
        "\n",
        "- Entailment can also be done by theorem proving: applying inference rules \n",
        "\n",
        "directly to sentence in KB to construct proof of the desired sentence. \n",
        "\n",
        "This is done without consulting models.\n",
        "\n",
        "- Theorem proving can be more efficient if number of models is large\n",
        "\n",
        "Logical equivalence: \n",
        "- Two sentences $\\\\alpha, \\\\beta$ are equivalent if they are true in the same set of models \n",
        "- $\\\\alpha \\\\equiv \\\\beta$ if and only if $\\\\alpha \\\\vDash \\\\beta$ and $\\\\beta \\\\vDash \\\\alpha$ \n",
        "\n",
        "Validity:\n",
        "- Validity are tautologies. A sentence is valid if it is true in all models \n",
        "- Deduction theorem: For any sentences $\\\\alpha, \\\\beta$, $\\\\alpha \\\\vDash \\\\beta$ if and only if\n",
        "the sentence $\\\\alpha \\\\implies \\\\beta$ is valid\n",
        "\n",
        "Satisfiability:\n",
        "- A sentence is satisfiable if it is true in some model (satisfied by some model)\n",
        "- Can be checked by enumerating all possible models, and find one that satisfies the sentence \n",
        "- $\\\\alpha \\\\vDash \\\\beta$ if and only if $\\\\alpha$ and $\\\\lnot \\\\beta$ is unsatisfiable (contradiction)\n",
        "\n",
        "Inference rules: \n",
        "- Modus ponens: $\\\\cfrac{\\\\alpha \\\\implies \\\\beta, \\\\alpha}{\\\\beta}$\n",
        "\n",
        "Whenever numerator is given, you can infer the denominator\n",
        "\n",
        "- And elimination: $\\\\cfrac{\\\\alpha \\\\wedge \\\\beta}{\\\\alpha}$ or $\\\\cfrac{\\\\alpha \\\\wedge \\\\beta}{\\\\beta}$\n",
        "\n",
        "From a conjunction, any of the conjuncts can be inferred\n",
        "\n",
        "Monotonicity: the set of entailed sentences can only increase as you add information to the KB\n",
        "- For any sentences $\\\\alpha, \\\\beta$, if $KB \\\\vDash \\\\alpha$ then KB and $\\\\beta \\\\vDash \\\\alpha$\n",
        "- New knowledge $\\\\beta$ may help agent draw additional conclusions, \n",
        "\n",
        "but cannot invalidate any conclusion already inferred by $\\\\alpha$\n",
        "\n",
        "Resolution:\n",
        "- Inferences rules are sound, but  not complete\n",
        "- Resolution is a single inference rule, that yields a complete inference algorithm \n",
        "when paired with any complete search algorithm\n",
        "- Only applies to clauses: disjunction of literals\n",
        "- Resolution: $\\\\cfrac{(l_1 \\\\vee l_2 \\\\vee l_3), \\\\lnot l_2}{l_1 \\\\vee l_3}$\n",
        "- Resolution algo is complete.\n",
        "\n",
        "CNF:\n",
        "- Every sentence of prop. logic is logically equivalent to a conjunction of clauses\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "```\n",
        "function PL-RESOLUTION(KB, α) returns true or false\n",
        " inputs: KB, the knowledge base, a sentence in propositional logic\n",
        "     α, the query, a sentence in propositional logic\n",
        "\n",
        " clauses ← the set of clauses in the CNF representation of KB ∧ ¬α\n",
        " new ← { }\n",
        " loop do\n",
        "   for each pair of clauses Ci, Cj in clauses do\n",
        "     resolvents ← PL-RESOLVE(Ci, Cj)\n",
        "     if resolvents contains the empty clause then return true\n",
        "     new ← new ∪ resolvents\n",
        "   if new ⊆ clauses then return false\n",
        "   clauses ← clauses ∪ new\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"syntax\" : \"structure of sentences\",\n",
        "\"semantics\": \"defines rules that determine truth of sentences with respect to model\",\n",
        "\"proof\": \"a chain of conclusions that leads to the desired goal\"   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e05f0a46-933b-4959-c5a9-cc2e6cc3fc68"
      },
      "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))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n- Knowledge base is a set of sentences. Each sentence expressed in 'knowledge representation language'\nand represents assertions about the world. When a sentence is given and doesn't need to be derived, it is an axiom.\n- Inference means deriving new sentences from old sentences \n- KB based agent programs maintains a knowledge based, which may initially contain background knowledge\n- Given percept, the KB agent adds the percept to its KB, asks KB what is the best action, and tells KB it has taken the action\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \nYour summary here \n\n\n## AIMA Chapter 7.3 Logic\n \n- KB sentences expressed according to the syntax of the representation language\n- Logic defines semantics (meanings of sentences), which define the truth of a sentence with respect to a possible world\n- Model corresponds to a \"possible world\". They are mathmatical abstractions, with a fixed truth value for every relevant sentence\n- $x + y = 4$ possible models are all possible assignments of nonnegative integers to $x, y$\n- If sentence $\\alpha$ is true in model $m$, then $m$ satisfies $\\alpha$, or $m$ is a model of $\\alpha$\n- $M(\\alpha)$: the set of all models of $\\alpha$. Meaning, the set of all models $m \\in M$ where $\\alpha$ is true in $m$\n\nLogical entailment:\n- $\\alpha \\vDash \\beta$ if and only if, in every model where $\\alpha$ is true, $\\beta$ is also true\n- $\\alpha \\vDash \\beta$ if and only if $M(\\alpha) \\subseteq M(\\beta)$\n- If $\\alpha \\vDash \\beta$ then $\\alpha$$ is a stronger assertion because it rules out more possible worlds\n\nKnowledge base:\n- KB can be set of sentences or single sentence that asserts multiple sentences\n- KB is false in models that contradict what the agent knows \n- Entailment is used to carry out logical inference (derive conclusions)\n- Set of all consequences of KB is a haystack, and $\\alpha$ is a needle. Entailment is like having the needle\nin the haystack, and inference is finding the needle. \n\nSoundness:\n- $KB \\vdash_i \\alpha_i$: $\\alpha$ is derived from KB by inference algorithm $i$\n- If inference algorithm derives only entailed sentences, then it is sound/truth preserving \n\nCompleteness: \n- Inference algorithm is complete if it can derive all sentence that are entailed \n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n- Semantics for propositional logic must specify how to compute truth value of \nany sentence, given model\n- Sentences constructed from atomic sentences and five connectives \n(and, or, implied, biconditional, negation)\n- XOR: (p or q) and ~(p and q)\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \n- Previous sections determined entailment by model checking: Enumerate models \n\nand show that the sentence and show that sentence must hold in all models \n\n- Entailment can also be done by theorem proving: applying inference rules \n\ndirectly to sentence in KB to construct proof of the desired sentence. \n\nThis is done without consulting models.\n\n- Theorem proving can be more efficient if number of models is large\n\nLogical equivalence: \n- Two sentences $\\alpha, \\beta$ are equivalent if they are true in the same set of models \n- $\\alpha \\equiv \\beta$ if and only if $\\alpha \\vDash \\beta$ and $\\beta \\vDash \\alpha$ \n\nValidity:\n- Validity are tautologies. A sentence is valid if it is true in all models \n- Deduction theorem: For any sentences $\\alpha, \\beta$, $\\alpha \\vDash \\beta$ if and only if\nthe sentence $\\alpha \\implies \\beta$ is valid\n\nSatisfiability:\n- A sentence is satisfiable if it is true in some model (satisfied by some model)\n- Can be checked by enumerating all possible models, and find one that satisfies the sentence \n- $\\alpha \\vDash \\beta$ if and only if $\\alpha$ and $\\lnot \\beta$ is unsatisfiable (contradiction)\n\nInference rules: \n- Modus ponens: $\\cfrac{\\alpha \\implies \\beta, \\alpha}{\\beta}$\n\nWhenever numerator is given, you can infer the denominator\n\n- And elimination: $\\cfrac{\\alpha \\wedge \\beta}{\\alpha}$ or $\\cfrac{\\alpha \\wedge \\beta}{\\beta}$\n\nFrom a conjunction, any of the conjuncts can be inferred\n\nMonotonicity: the set of entailed sentences can only increase as you add information to the KB\n- For any sentences $\\alpha, \\beta$, if $KB \\vDash \\alpha$ then KB and $\\beta \\vDash \\alpha$\n- New knowledge $\\beta$ may help agent draw additional conclusions, \n\nbut cannot invalidate any conclusion already inferred by $\\alpha$\n\nResolution:\n- Inferences rules are sound, but  not complete\n- Resolution is a single inference rule, that yields a complete inference algorithm \nwhen paired with any complete search algorithm\n- Only applies to clauses: disjunction of literals\n- Resolution: $\\cfrac{(l_1 \\vee l_2 \\vee l_3), \\lnot l_2}{l_1 \\vee l_3}$\n- Resolution algo is complete.\n\nCNF:\n- Every sentence of prop. logic is logically equivalent to a conjunction of clauses\n\n\n## Module 7 Lecture Notes\n \n```\nfunction PL-RESOLUTION(KB, α) returns true or false\n inputs: KB, the knowledge base, a sentence in propositional logic\n     α, the query, a sentence in propositional logic\n\n clauses ← the set of clauses in the CNF representation of KB ∧ ¬α\n new ← { }\n loop do\n   for each pair of clauses Ci, Cj in clauses do\n     resolvents ← PL-RESOLVE(Ci, Cj)\n     if resolvents contains the empty clause then return true\n     new ← new ∪ resolvents\n   if new ⊆ clauses then return false\n   clauses ← clauses ∪ new\n```\n\n\n## Module 7 Definitions\n* **Syntax** - structure of sentences\n* **Semantics** - defines rules that determine truth of sentences with respect to model\n* **Proof** - a chain of conclusions that leads to the desired goal\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "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",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "cellView": "form",
        "outputId": "8fa02983-4988-4f4f-bf59-0037e179126e"
      },
      "source": [
        "#@title\n",
        "# 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))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\n- All data treated as objects\n- Objects are automatically garbage collected once unreachable\n- Strong typing: every object has a fixed type, and Python does not \nallow things that are incompatible with that type\n- Dynamic typing: Variables come into existence when they are first assigned.\nType of a variable is automatically determined and can be updated if assigned again.\nFunctions have no type signatures. Type errors only caught at runtime.\n\n- Java is static typing: variables can only refer to objects of a declared type.\nMethods use type significatures. \n\n- Immutable: Strings, tuple\n- Mutable: Lists, dictionaries\n\nReferences/Mutability:\n- `==` checks whether variables point to objects that have the same value\n- `is` checks whether variables point to the same object\n- `y=x[:]` gets a shallow copy of any sequence (new object of the same value)\n\nList operations:\n- `list.reverse()` reverse the list in place\n- `list.sort()` sort the list in place\n- `sorted(list)` returns a copy that is sorted\n\nDictionaries:\n- Unordered and works by hashing\n- Keys must be immutable \n\nFunction overloading:\n- No function overloading for Python\n- Function specified by name alone. Different functions cannot have the same name\neven if they have different arguments.\n- But operator overloading is possible using special methods in a class\n- Magic methods allow user defined classes to behave like built in types\n\nArguments:\n- Non default arguments first, then default arguments. Otherwise syntax error.\n- `*args` for variable number of non-keyword arguments to your function\n- `**kwargs` for variable number of keyword arguments to your function\n\nFirst class objects:\n- Can be dynamically created, destroyed, passed to a function, returned as a value\n- Have all rights as other variables\n- Functions are first class objects\n\nFirst class citizens:\n- Can pass functions as arguments to other functions\n- Return functions as the value from other functions\n- Assign functions to variables or store them in data structures\n- Functions are first class citizens\n\nMain:\n- `__name__` is built in variaable which evaluates the name of the current module\n(name of the Python script)\n- `__name__` has value `__main__` for the source file that is being executed on the command line\n- Python does not have built in main method, so no `def main()`\n\nIterators:\n- `__iter__` magic method converts objects to iterator objects (\"to be iterable\")\n- Iterators are objects with `__next__()` method (\"to be iterator\")\n- Python iterators do not have `hasnext()` method. They just catch the `StopIteration` exception instead.\n- Use memory efficiently\n\nGenerators:\n- Generators are iterators (has `__next()__` method)\n- Functions that contain `yield` keyword automatically return generator when called\n- Maintains local state automatically\n- Values computed one at a time as needed\n- Avoid storing entire sequence in memory\n- Crucial for infinite sequences\n- Bad if you need to inspect individual values\n\n\n## Module 2 Definitions\n* **Duck typing** - determines suitability of an object by determining prescence of methods\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \n- An agent that considers a sequence of actions to lead to goal state (via search) is a problem-solving agent\n- Problem-solving agents use atomic representations of states \n- Planning agents use factored or structured representations of states\n- In fully observable, deterministic, known environment: solution to problem is a fixed sequence of actions\n- Search: agent simulates sequences of actions in the model, until it finds sequence that reaches the goal \n- Solution: sequence of actions that lead to the goal \n- State space can be represented as graph: vertices (states) and edges (actions)\n\nSearch problem components:\n- State space: Set of possible states for the environment\n- Initial state\n- Goal states\n- Actions available to agent: set of actions that can be executed in $s$\n- Transition model: returns the state that is the result of performing action $a$ in state $s$\n- Action cost function: cost of action $a$ in state $s$ to reach state $s'$\n\n\n## AIMA Chapter 3.2 Example Problems\n \nStandardized problems: \n- Used to illustrate problem solving methods (grid world, sliding tiles)\n- Has concise, exact description\n- Suitable as a benchmark to compare performance of algorithms\n\nReal world problems:\n- One whose solutions people actually use (route-finding, robot navigationm touring problem)\n- Formulation is not standardized\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \nState space:\n- Describes set of spaces in the world (can be infinite) and actions that transition from one state to another\n\nSearch tree:\n- Describes paths between states, reaching towards the goal\n- Each node in the tree has unique path back to the root \n\nA node in tree has 4 components:\n- State: that node corresponds to \n- Parent: node that generated current node\n- Action: action applied to parent to generate current node\n- Path cost: total cost of path from initial state to current node \n\nQueue types:\n- Priority: removes node with minimum cost according to evaluation function. Used in best first.\n- FIFO: used in BFS \n- LIFO: used in DFS\n\nGraph search:\n- Search algorithm that checks for redundant paths\n- Needs to store previously seen states, requires more memory\n- Does not waste time going down redundant paths, saves time \n- examples: Best first search \n\nTree-like search:\n- Search algorithm that does not check for redundant paths \n- Does not store previous states, requires less memory \n- Could potentially go down redundant path, which would waste time \n\nIn both cases, state space is the same graph. We are just treating how to search it. \n\nCriteria for search:\n- Completeness: Will search find solution or correctly report failure if there is no solution?\n- Cost optimality: Will search find lowest path cost?\n- Time / space complexity\n\nTime and space:\n- Many graphs are represented implicitly instead of as explicit graph. Defined by initial state, actions, and transition model. Instead, measure with:\n- $d$: depth in optimal solution\n- $m$: max number of actions in any path \n- $b$: branching factor: number of successors of a node to consider \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nBFS:\n- Appropriate when actions have the same cost\n- Complete, even on infinite spaces\n- Cost optimal if all actions have same cost; not necessarily otherwise\n- Use evaluation $f(n) = $ depth of node / number of actions to reach node \n- Perform early goal test: checking if node is solution as soon as it is generated  \n- Total number of nodes generated: $1 + b + b^2 + ... + b^d = O(b^d)$, assuming solution at depth $d$\n- Time and space is $O(b^d)$. \n- All nodes generated remain in memory; memory requirement bigger issue than time requirement \n\nUniform cost (Dijkstra):\n- Use evaluation function $g(n) =$ cost of path from root node to current node\n- Test for goal when you expand a node, not when a node is generated \n- Time and space complexity: $O(b^{1 + C^*/\\epsilon})$, which may be $>> O(b^d)$ because Dijkstra may explore large areas that have low cast actions\nbefore exploring paths with higher actions\n- If all action costs are equal, $b^{1 + C^*/\\epsilon} = b^{d+1}$\n\nDFS:\n- Tree like search that does not remember reached states (so it uses less memory)\n- Not cost optimal; returns first solution it finds \n- Incomplete: Can get stuck in infinite loops in cyclic state spaces. Or it can get stuck going down an infinite path even if there are no cycles.\n- DFS only complete and efficient in finite state spaces. Efficient in acyclic state spaces.\n- Space complexity $O(bm)$\n- Time complexity $O(b^m)$\n\nDepth-limited search:\n- DFS with depth limit $l$. Treat all nodes at depth $l$ as if they had no successors\n- Time complexity $O(b^l)$\n- Space complexity $O(bl)$\n- Incomplete if $l < d$, we don't reach solution because we don't go deep enough\n- Not optimal if $l > d$, we explored too deep \n- Optimal if $l = d$\n\nIterative deepening:\n- Space complexity: $O(bd)$ if solution exists, or $O(bm)$ on finite state spaces without solution\n- Time complexity: $O(b^d)$ if solution exists, or $O(b^m)$ without solution\n- Optimal if all action costs are the same (like BFS)\n- Complete on finite acyclic / finite state spaces if you check for cycles \n\nBidirectional search:\n- At the same time, search forward from initial state and backwards from goal state(s), with the idea that the\ntwo searches will meet\n- Idea: $b^{d/2} + b^{d/2} < b^{d}$\n- Need to keep track of two frontiers and two tables of reached states \n- Solution is found when two frontiers meet \n\n\n## Module 3 Lecture Notes\n \n```\ndef breadth_first_search(graph: Graph, start: Location, goal: Location):\n    frontier <- initialize Queue()\n    put start in frontier\n    came_from: Dict[Location, Optional[Location]]\n    initialize came_from[start] = None\n    \n    while not frontier.empty():\n        current <- frontier.get()\n        \n        if current == goal:\n            break\n        \n        for next in graph.neighbors(current):\n            if next not in came_from:\n                frontier.put(next)\n                came_from[next] = current\n    \n    return came_from\n\n-----------------------------------------------------------------\n\ndef dijkstra_search(graph: WeightedGraph, start: Location, goal: Location):\n    frontier <- initialize PriorityQueue()\n    put (start, 0) in frontier\n    came_from: Dict[Location, Optional[Location]] \n    cost_so_far: Dict[Location, float] \n    initialize came_from[start] = None\n    initialize cost_so_far[start] = 0\n    \n    while not frontier.empty():\n        current <- frontier.get()\n        \n        if current == goal:\n            break\n        \n        for next in graph.neighbors(current):\n            new_cost = cost_so_far[current] + graph.cost(current, next)\n            if next not in cost_so_far or new_cost < cost_so_far[next]:\n                update cost_so_far[next] = new_cost\n                priority = new_cost\n                frontier.put(next, priority)\n                update came_from[next] = current\n    \n    return came_from, cost_so_far\n```\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Atomic representations** - states of the world considered whole (blackbox) with no internal structure visible\n* **Factored representations** - states represented as assignments of values to variables\n* **Informed search** - agent can estimate how far it is from goal\n* **Uninformed search** - agent cannot estimate how far it is from goal\n* **Open loop** - ignoring percepts\n* **Closed loop** - monitoring percepts\n* **Model** - abstract math formulation (not the real thing)\n* **Late goal test** - check if node is goal when it is popped off the queue (best first search)\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n- Informed search: uses domain specfic hints (heuristic function) about location for goals. \n- $h(n)$: estimated least cost path from node $n$ to goal node \n- $g(n)$: cost so far of path from initial node to current node $n$\n\nGreedy:\n- Greedy best first expands node with the lowest $h(n)$, which is the node that seems closest to the goal.\nGreedy finds a solution without ever expanding a node that is not on the solution path, but it won't \nalways find the optimal path\n- Greedy is complete in finite state spaces, but not complete in infinite state spaces\n- Greedy time and space complexity is $O(|V|)$ but can be reduced to $O(bm)$ with a good heurstic \n\nA-star:\n- A* is a best first search that uses $f(n) = g(n) + h(n)$\n- $f(n)$: estimated cost of the best path that continues from node $n$ to goal node \n- A* checks whether a node is a solution when the node is selected for expansion (because then the node is the \nlowest-cost node on the frontier)\n- A* complete\n- A* cost-optimal with admissible heuristic (but may OR may not be cost optimal with inadmissible one)\n- If C* is the cost of the optimal path, then A* will never expand nodes with $f(n) > C*$\n- Weighted A* search: $f(n) = g(n) + W \\cdot h(n)$ for $W > 1$ will find a solution that costs between $C*$ (optimal)\nand $W \\cdot C*$, but much faster and expands fewer nodes\n\nConsistency:\n- Consistency is a stronger claim than admissibility\n- Consistency: heuristic $h(n)$ is consistent if, for every node $n$ and successor $n'$ of $n$ generated by action $a$\nwe have: $h(n) \\leq cost(n, a, n') + h(n')$ \n- $h$ is consistent if the cost of going to a successor node $n'$ plus the cost of the heuristic $h(n')$ (estimated remaining cost from $n'$ to goal node)\nis greater than or equal to $h(n)$\n- With consistency: the first time you reach a state it will be on an optimal path. You don't have to re-add a \nstate to the frontier, and you don't have to change an entry with reached \n- With inconsistency: you may end up with multiple paths reaching the same state. You may end up with multiple\nnodes for that state in the frontier (if new paths are cheaper than previous paths)\n- Straight line heuristic is a consistent heuristic \n\nSearch contours for A*:\n- Nodes inside a given contour have costs $\\leq$ contour value\n- A* fans out from start node and adds nodes in concentric bands of increasing $f$-cost. The contours stretch\ntowards goal state and become more narrowly focused on optimal path \n- $f$-costs are not always monotonically increasing \n- $f$ path cost monotonically increasing if and only if the heuristic is consistent \n\nSearch contours for Dijkstra:\n- Dijkstra (uniform-cost) has contours using $g$-cost. The contours are circular around start node and \nspreads out equally in all directions without preference toward goal \n- $g$-costs are monotonic: path costs always increase \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \n- Characterize the quality of a heuristic function using $b*:$ effective branching factor\n- $b*$ is the branching factor that a uniform tree of depth $d$ would have to have to contain $N+1$ nodes\n$N+1 = 1 + b* + (b*)^2 + ... + (b*)^d$\n- Well designed heuristics has $b*$ close to $1$\n- Can also characterize the quality of a heuristic function with how much it reduces the effective depth by, i.e.\ntotal search cost $O(b^{d-k_{h}})$ vs. $O(b^d)$\n- $h_2$ dominates $h_1$: for any node $n$, $h_2(n) \\geq h_1(n)$\n- In example above, A* will never expand more nodes using $h_2$\n\nRelaxed problems:\n- Graph of a relaxed problem is a supergraph of the original graph \n- The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n\n\n## Module 4 Lecture Notes\n \n```\ndef dijkstra_search(graph: WeightedGraph, start: Location, goal: Location):\n    frontier <- initalize PriorityQueue()\n    put (start, 0) in frontier\n    came_from: Dict[Location, Optional[Location]] \n    cost_so_far: Dict[Location, float] \n    initialize came_from[start] = None\n    initialize cost_so_far[start] = 0\n    \n    while not frontier.empty():\n        current <- frontier.get()\n        \n        if current == goal:\n            break\n        \n        for next in graph.neighbors(current):\n            new_cost = cost_so_far[current] + graph.cost(current, next)\n            if next not in cost_so_far or new_cost < cost_so_far[next]:\n                update cost_so_far[next] = new_cost\n                priority = new_cost\n                frontier.put(next, priority)\n                update came_from[next] = current\n    \n    return came_from, cost_so_far\n\n----------------------------------------------------------------------\n\ndef heuristic(a: GridLocation, b: GridLocation) -> float:\n    (x1, y1) = a\n    (x2, y2) = b\n    return |x1 - x2| + |y1 - y2|\n\ndef a_star_search(graph: WeightedGraph, start: Location, goal: Location):\n    frontier <- initialize PriorityQueue()\n    put (start, 0) in frontier\n    came_from: Dict[Location, Optional[Location]] \n    cost_so_far: Dict[Location, float]\n    initialize came_from[start] = None\n    initialize cost_so_far[start] = 0\n    \n    while not frontier.empty():\n        current <- frontier.get()\n        \n        if current == goal:\n            break\n        \n        for next in graph.neighbors(current):\n            new_cost = cost_so_far[current] + graph.cost(current, next)\n            if next not in cost_so_far or new_cost < cost_so_far[next]:\n                update cost_so_far[next] = new_cost\n                priority = new_cost + heuristic(next, goal)\n                frontier.put(next, priority)\n                update came_from[next] = current\n    \n    return came_from, cost_so_far\n```\n\n\n\n## Module 4 Definitions\n* **Admissible heuristic** - never overestimates cost to goal i.e. optimistic\n* **Optimally efficient** - any other algorithm using the same heuristic info would have to expand the same nodes\n* **Satisficing** - solutions that are subptimal but good enough\n* **Bounded suboptimal search** - find solution guaranteed to be within constant factor $W$ of optimal cost\n* **Bounded cost search** - find solution whose cost is $< C$, a constant\n* **Unbounded cost search** - accept solution of any cost, just find it quickly\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nA game can be fully defined with the following components:\n- Initial state\n- Player whose turn it is to move in state $s$\n- Set of legal moves in state $s$\n- Transition model: define the state resulting from taking action $a$ in state $s$\n- Terminal test \n- Utility function: defines final numeric value to player $p$ when game ends \n\n- Game tree: search tree that follows sequence of moves to a terminal state (may be infinite)\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n- Given game tree, optimal strategy determined by computing minimax value of each state. \n- Minimax value is the utility (for MAX) of being in that state, assuming both players play optimally. \n- Minimax value of terminal state is just its utility.\n\nAnalysis of mini-max:\n- Max depth of tree is $m$ and $b$ legal moves at each point\n- Time complexity $O(b^m)$\n- Space complexity is $O(bm)$ if you generate all actions at once, or $O(m)$ if you generate actions one at a time\n\nAlpha-Beta Pruning:\n- Pruning allows us to cut the exponent in half \n- Big idea: Consider node $n$. If a player has a better choice at the same level (as $n$) or higher up in the tree, then \nthe player will never move to $n$.\n- With perfect move ordering, alpha-beta would only need to examine $O(b^{m/2})$ nodes\n\n- $\\alpha$: value of the best (highest-value) choice we have found so far at any choice point along the path for max (\"at least\")\n- $\\beta$: value of the best (lowest-value) choice we have found so far at any choice point along the path for min (\"at most\")\n\n- In game trees search, repeated states can occur due to transpositions: different permutations of move sequence that end up in the same position\n- Some games cannot be solved with alpha-beta pruning and clever move ordering. Two strategies exist:\n- Type A: \"wide but shallow\" (Chess)\n- Type B: \"deep but narrow\" (Go)\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n- Heuristic evaluation function returns estimate of expected utility of state $s$ to player $p$\n- Forward pruning prunes moves that appear to be bad, but might possibly be good \n(this saves computational time but is risky because you may make an error).\n- One forward pruning method is beam search\n- Probabilistic cut: uses statistics to reduce chance that the best move is pruned. Prunes node that are *probably* outside\nthe current $(\\alpha, \\beta)$ window.\n- Late move reduction: assumption that moves that appear later in the list of possible moves are less likely to be good ones.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \n- Due to the stochastic nature, positions do not have definite minimax values. You can only calculate the expected value\nof a position by averaging over all possible outcomes of the chance nodes. \n- Expectimax is considering all possible dice-roll sequences, which will take $O(b^{m} n^{m})$ where $n$ is the number\nof distinct dice rolls.\n- Pruning is possible with expectimax.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \n```\ndef alpha_beta():\n    # Runtime is O(b^m)\n    return max(alpha=-inf, beta=inf, limit)\n\ndef alpha_beta_max(alpha, beta, limit):\n    if game is over or limit == 0:\n        return evaluation or heuristic function\n    \n    initialize val <- -inf\n    for move, new_game in max's successors:\n        new_move, new_val = alpha_beta_min(alpha, beta, limit - 1)\n\n    if new_val > val:\n        update val and best move <- new_val and move\n        alpha = max(alpha, val)\n    if val >= beta:\n        return best_move, val\n\ndef alpha_beta_min():\n    if game is over or limit == 0:\n        return evaluation heuristic function\n    \n    initialize val = inf\n    for move, new_game in min's successors:\n        new_move, new_val = alpha_beta_max(alpha, beta, limit - 1)\n\n    if new_val < val:\n        update val and best move <- new_val and move \n        beta = min(beta, val)\n    if val <= alpha:\n        return best_move, val\n\n------------------------------------------------------------\n\ndef minimax(node, depth, maximizingPlayer):\n\n    if depth = 0 or node is a terminal node then\n        return the heuristic value of node\n    if maximizingPlayer then\n        value := −∞\n        for each child of node do\n            value := max(value, minimax(child, depth − 1, FALSE))\n        return value\n    else (* minimizing player *)\n        value := +∞\n        for each child of node do\n            value := min(value, minimax(child, depth − 1, TRUE))\n        return value\n\n```\n\n\n## Module 5 Definitions\n* **Perfect information** - synonym for fully observable\n* **Quiescent** - positions in which there is no pending move that would dramatically swing the evaluation\n* **Horizon effect** - program faces an opponent's move that causes serious damage and is unavoidable, but can only be temporarily delayed\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \n- CSP consists of three components: set of variables, set of domains, set of constraints that\nspecify allowable combinations of values. CSPs deal with assignments of values to variables.\nA consistent assignment does not violate any constraints. A complete assignment is one where every\nvariable is assigned a value. A solution is a complete, consistent assignment. \n\n- CSPs represents the conditions for a solution with constraints on the variables.\n\n- Visualize a CSP as a constraint graph: nodes are variables of the problem, edge connects any two\nvariables in a constraint. \n\n- Every finite-domain (n-ary) constraint can be reduced to set of binary constraints. \n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- Constraint propagation uses constraints to reduce the number of legal values for a variable, which\npropagates reductions to the next variable, and so on. The key idea is local consistency. Enforcing local\nconsistency results in inconsistent values being eliminated throughout the graph. Local consistency includes\nnode, arc, path, and k-consistency. \n\n- Arc consistency: $X_i$ is arc consistent to $X_j$ if for every value in $D_i$ there is some value in $D_j$\nthat satisfies the binary constraint on $(X_i, X_j)$. We reduce the domain of $X_i$ in order to make $X_i$ \narc-consistent with $X_j$.\n\n- AC-3: Queue contains all arcs in the CSP. Make $X_i$ arc consistent with $X_j$ for arc $(X_i, X_j)$.\nIf $D_i$ is unchanged, move on to next arc. Else, add to queue $(X_k, X_i)$ all the neighbors of $X_i$. \nRuntime is $O(cd^3)$, where $c=$ number of binary constraints/arcs and $d=$ domain size.\n\n- Path consistency: $\\{X_i, X_j\\}$ is path consistent to $X_m$ if for every assignment $\\{X_i=a, X_j=b\\}$ consistent with\nconstraints on $\\{X_i, X_j\\}$, there is an assignment to $X_m$ that satisfies constraints $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$.\n\n- K-consistency: Given any set of $k-1$ variables and any consistent assignment to those variables, a consistent\nvalue can always be assigned to any $k^{th}$ variable, i.e. 1-consistency: given empty set, we can make any set of \n1 variable consistent.\n\n- Strongly k-consistent: If it is k-consistent, $k-1$ consistent, and .... $1-$consistent. \nTotal runime is $O(dn^2)$ for *solving* CSP that is strongly n-consistent.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n- Constraint propagation does not guarantee a solution. Sometimes you will have to search for a solution. \nBacktracking search works well for partial assignments. For a CSP with $n$ variables and domain size $d$,\na complete assignment (all solutions) are leaf nodes at depth $n$. There are $d^n$ leaves.\n\n- In CSP search tree, you only need to consider a single variable at each node in the search tree (commutativity).\nBut you need to determine how to choose which unassigned variable to pick next. You can use domain-independent \nheuristics for this. Simplest heuristics are choosing variables in order, or randomly.\n\nVariable selection:\n- Minimum remaining value heuristic: Choosing variable with the fewest \"legal\" values (most constrained/fail first).\n- Degree heuristic: Selecting variable with the largest number of constraints on other unassigned variables \n(highest degree in map coloring problem).\n\nValue selection:\n- Least constraining value heuristic: Prefer value that rules out fewest choices for neighboring values \n(leave max. flexibility for further variable assignment).\n\nInference during search:\n- Forward checking: Establish arc consistency whenever $X$ is assigned a value. For each unassigned $Y$ that \nis connected to $X$ by constraint, delete from $Y$'s domain any value that is inconsistent with $X$. \nProblem with this is it does not look too far ahead.\n\n- MAC: Call AC-3 after $X_i$ is assigned a value, but only queue arcs $(X_j, X_i)$ for unassigned variables $X_j$\nthat are neighbors of $X_i$. Then let AC-3 do constraint propagation the usual way. MAC is more powerful than\nforward checking because it propagates constraints when changes are made to the domains of variables. \n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \n- Local search: Start with complete state (each state assigns a value to every variable), and change the value of\none variable one at a time, during the course of search. Ideally, change the value to something that brings us closer\nto the solution (i.e. min conflicts heuristics).\n\n- Min conflicts heuristic: Select the value that results in the min number of conflicts with other variables. Runtime\nis roughly independent of problem size. \n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- Decompose structure of problem into smaller subproblems so that it can be solved quickly.\nThis uses the idea of independent subproblems, a solution for one independent subproblem combined with any solution for \nanother independent subproblem yields a solution for the whole problem. Independence is determined by finding \nconnected components of the constraint graph.\n\n- Without decomposition, total work is $O(d^n)$. With decomposition, total work is $O(nd^c / c)$, which is linear in $n$. \nCaveat here is that completely independent subproblems are rare. \n\n- Constraint graph is a tree when any two variables are connected by only one path. \nAny tree-structured CSP can be solved in linear time, in the number of variables. This uses\ndirectional arc consistency (DAC) for consistency.\n\n- General constraint graphs can be reduced to trees by removing nodes (cutset conditioning) \nor collapsing nodes together (tree decomposition).\n\n- Cutset conditioning: Assign a value to some set of variables S, delete from the domain of other variables any values\nthat are inconsistent with the value chosen in S. The remaining variables (not in S) form a tree. \n\n- S is a cycle cutset: Subset of the CSP variables such that the constraint becomes a tree after you remove S. \nIf the cycle cutset has size $c$ the total runtime is $O(d^c(n-c)d^2)$. You want the smallest $c$ for more efficiency.\n\n- Tree decomposition: transform the original graph into a tree where each node in the tree is a set of variables.\nTree decomposition problems can be solved in $O(nd^2)$ time (Clarify?).\n\n- Tree decomposition transform the CSP into a tree of subproblems\n\n- Tree width $w$ of tree decomposition is one less than the size of the largest node.\n- Tree width of graph itself is the minimum width among all its tree decompositions.\n- Graph with tree width $w$ can be solved in $O(nd^{w+1})$ given corresponding tree decomposition.\n\nCutset vs. tree decomposition:\n- Tree decomposition is faster, but requires memory exponential in $w$\n- Cutset conditioning is linear in memory\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Unary constraint** - restricts the value of a single variable\n* **Binary csp** - a CSP with only unary and binary constraints (can be represented as constraint graph)\n* **Global constraint** - involving an arbitrary number of variables (does not need to involve all variables)\n* **Constrainted optimization problem** - CSPs with preferences (morning/afternoon)\n* **Constraint learning** - finding a minimum set of variables from conflict set that causes the problem\n* **Backjumping method** - backtracks to the most recent assignment in the conflict set\n* **Chronological backtracking** - backtrack to the most recent decision point\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n- Knowledge base is a set of sentences. Each sentence expressed in 'knowledge representation language'\nand represents assertions about the world. When a sentence is given and doesn't need to be derived, it is an axiom.\n- Inference means deriving new sentences from old sentences \n- KB based agent programs maintains a knowledge based, which may initially contain background knowledge\n- Given percept, the KB agent adds the percept to its KB, asks KB what is the best action, and tells KB it has taken the action\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \nYour summary here \n\n\n## AIMA Chapter 7.3 Logic\n \n- KB sentences expressed according to the syntax of the representation language\n- Logic defines semantics (meanings of sentences), which define the truth of a sentence with respect to a possible world\n- Model corresponds to a \"possible world\". They are mathmatical abstractions, with a fixed truth value for every relevant sentence\n- $x + y = 4$ possible models are all possible assignments of nonnegative integers to $x, y$\n- If sentence $\\alpha$ is true in model $m$, then $m$ satisfies $\\alpha$, or $m$ is a model of $\\alpha$\n- $M(\\alpha)$: the set of all models of $\\alpha$. Meaning, the set of all models $m \\in M$ where $\\alpha$ is true in $m$\n\nLogical entailment:\n- $\\alpha \\vDash \\beta$ if and only if, in every model where $\\alpha$ is true, $\\beta$ is also true\n- $\\alpha \\vDash \\beta$ if and only if $M(\\alpha) \\subseteq M(\\beta)$\n- If $\\alpha \\vDash \\beta$ then $\\alpha$$ is a stronger assertion because it rules out more possible worlds\n\nKnowledge base:\n- KB can be set of sentences or single sentence that asserts multiple sentences\n- KB is false in models that contradict what the agent knows \n- Entailment is used to carry out logical inference (derive conclusions)\n- Set of all consequences of KB is a haystack, and $\\alpha$ is a needle. Entailment is like having the needle\nin the haystack, and inference is finding the needle. \n\nSoundness:\n- $KB \\vdash_i \\alpha_i$: $\\alpha$ is derived from KB by inference algorithm $i$\n- If inference algorithm derives only entailed sentences, then it is sound/truth preserving \n\nCompleteness: \n- Inference algorithm is complete if it can derive all sentence that are entailed \n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n- Semantics for propositional logic must specify how to compute truth value of \nany sentence, given model\n- Sentences constructed from atomic sentences and five connectives \n(and, or, implied, biconditional, negation)\n- XOR: (p or q) and ~(p and q)\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \n- Previous sections determined entailment by model checking: Enumerate models \n\nand show that the sentence and show that sentence must hold in all models \n\n- Entailment can also be done by theorem proving: applying inference rules \n\ndirectly to sentence in KB to construct proof of the desired sentence. \n\nThis is done without consulting models.\n\n- Theorem proving can be more efficient if number of models is large\n\nLogical equivalence: \n- Two sentences $\\alpha, \\beta$ are equivalent if they are true in the same set of models \n- $\\alpha \\equiv \\beta$ if and only if $\\alpha \\vDash \\beta$ and $\\beta \\vDash \\alpha$ \n\nValidity:\n- Validity are tautologies. A sentence is valid if it is true in all models \n- Deduction theorem: For any sentences $\\alpha, \\beta$, $\\alpha \\vDash \\beta$ if and only if\nthe sentence $\\alpha \\implies \\beta$ is valid\n\nSatisfiability:\n- A sentence is satisfiable if it is true in some model (satisfied by some model)\n- Can be checked by enumerating all possible models, and find one that satisfies the sentence \n- $\\alpha \\vDash \\beta$ if and only if $\\alpha$ and $\\lnot \\beta$ is unsatisfiable (contradiction)\n\nInference rules: \n- Modus ponens: $\\cfrac{\\alpha \\implies \\beta, \\alpha}{\\beta}$\n\nWhenever numerator is given, you can infer the denominator\n\n- And elimination: $\\cfrac{\\alpha \\wedge \\beta}{\\alpha}$ or $\\cfrac{\\alpha \\wedge \\beta}{\\beta}$\n\nFrom a conjunction, any of the conjuncts can be inferred\n\nMonotonicity: the set of entailed sentences can only increase as you add information to the KB\n- For any sentences $\\alpha, \\beta$, if $KB \\vDash \\alpha$ then KB and $\\beta \\vDash \\alpha$\n- New knowledge $\\beta$ may help agent draw additional conclusions, \n\nbut cannot invalidate any conclusion already inferred by $\\alpha$\n\nResolution:\n- Inferences rules are sound, but  not complete\n- Resolution is a single inference rule, that yields a complete inference algorithm \nwhen paired with any complete search algorithm\n- Only applies to clauses: disjunction of literals\n- Resolution: $\\cfrac{(l_1 \\vee l_2 \\vee l_3), \\lnot l_2}{l_1 \\vee l_3}$\n- Resolution algo is complete.\n\nCNF:\n- Every sentence of prop. logic is logically equivalent to a conjunction of clauses\n\n\n## Module 7 Lecture Notes\n \n```\nfunction PL-RESOLUTION(KB, α) returns true or false\n inputs: KB, the knowledge base, a sentence in propositional logic\n     α, the query, a sentence in propositional logic\n\n clauses ← the set of clauses in the CNF representation of KB ∧ ¬α\n new ← { }\n loop do\n   for each pair of clauses Ci, Cj in clauses do\n     resolvents ← PL-RESOLVE(Ci, Cj)\n     if resolvents contains the empty clause then return true\n     new ← new ∪ resolvents\n   if new ⊆ clauses then return false\n   clauses ← clauses ∪ new\n```\n\n\n## Module 7 Definitions\n* **Syntax** - structure of sentences\n* **Semantics** - defines rules that determine truth of sentences with respect to model\n* **Proof** - a chain of conclusions that leads to the desired goal\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}