{
  "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": "f591e023-3e6a-45fd-d62b-985d67866f71"
      },
      "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": "70453c26-805b-4e5a-843a-5d3ed792e1fa"
      },
      "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 = False"
      ],
      "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 = \"\"\" To pass the Turing test, a computer needs NLP, knowledge representation, automated reasoning, machine learning, computer vision \\\n",
        "(for total), and robotics (for total). Value alignment problem: values/objectives put into machine must be aligned with those in human. \"\"\" \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 = \"\"\" Measure a machine's ability to complete behavioral tests using the Turing test. \"\"\"\n",
        "chapter27_2 = \"\"\" Searle Chinese room suggests that computers don't have understanding. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Agent behaviors based on agent functions that map percept sequences to specific actions. Agent functions are abstract, whereas \\\n",
        "agent programs are actual implementations. \"\"\"\n",
        "chapter2_2 = \"\"\" Rational agent does the right thing. Better to make performance measures that tracks with what should be achieved in the \\\n",
        "environment, not how the agent should behave. \"\"\"\n",
        "chapter2_3 = \"\"\" Task environments are fully observable if sensors provide access to the complete environment state at all times (no need to \\\n",
        "maintain internal state). Noisy/inaccurate sensors lead to being partially observable, and no sensors is unobservable environment. Multiple agents \\\n",
        "exist if each agent tries to max a performance measure. Competitive multiagent environments (chess) vs. cooperative (driving, all agents \\\n",
        "avoiding crashes). Deterministic environment if next state is completely determined by current state, otherwise nondeterministic (stochastic if \\\n",
        "specific probabilities for outcomes). Episodic if the agent experiences episodes with percepts and single actions, with each episode being \\\n",
        "independent of others, whereas sequential has current decisions potentially affecting later ones. Static doesn't change during agent deliberation \\\n",
        "while dynamic may. Discrete vs. continuous states, times, percepts, and actions. Known environment has outcomes for actions given. \"\"\"\n",
        "chapter2_4 = \"\"\" Agent = architecture + program. Table-driven agent lookup does the job but is highly inefficient. Simple reflex agents base \\\n",
        "actions on current precept without consideration of precept history (requires fully observable, randomization may help if partially observable). \\\n",
        "Model-based reflex agents maintain internal state of percept history, requires transition model (how the world works) and sensor model (how \\\n",
        "state of world manifests in percepts). Goal-based agents require goal info for a desirable destination. Utility-based agents maximize utility \\\n",
        "function (most desirable way to get to destination). Learning agents built from critic, learning element, problem generator, and performance \\\n",
        "element \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Strong AI (actually thinking) vs. weak AI (simulating thinking). Create performance measure for what you want agent \\\n",
        "to achieve rather than how you think it should behave. For a given PEAS task environment, construct agent function to max expected value of \\\n",
        "performance measure and agent program that implements function on a specific architecture. Hardest environment is: continuous, partially observable \\\n",
        "stochastic, multiagent. Reflex agent makes action based on current percept (ignoring history), whereas problem solving agent plans ahead using search. \"\"\"\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 (sensors) and act (actuators) in an environment (rational agent achieves best (expected) outcome)\",\n",
        "\"percept\" : \"what the agent perceives\",\n",
        "\"autonomy\" : \"ability to learn to compensate for partial prior knowledge vs. solely relying on previous knowledge\",\n",
        "\"task environment\": \"problem to be solved with rational agents with specified performance measures, environment, actuators, sensors\",\n",
        "\"condition-action rule\": \"if-then rules\",\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": 1000
        },
        "cellView": "form",
        "outputId": "ad560045-b306-4b13-ae14-e6fb12160386"
      },
      "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 To pass the Turing test, a computer needs NLP, knowledge representation, automated reasoning, machine learning, computer vision (for total), and robotics (for total). Value alignment problem: values/objectives put into machine must be aligned with those in human. \n\n## AIMA Chapter 27.1 The Limits of AI\n Measure a machine's ability to complete behavioral tests using the Turing test. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Searle Chinese room suggests that computers don't have understanding. \n\n## AIMA 2.1 Agents and Environments\n Agent behaviors based on agent functions that map percept sequences to specific actions. Agent functions are abstract, whereas agent programs are actual implementations. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rational agent does the right thing. Better to make performance measures that tracks with what should be achieved in the environment, not how the agent should behave. \n\n## AIMA 2.3 The Nature of Environments\n Task environments are fully observable if sensors provide access to the complete environment state at all times (no need to maintain internal state). Noisy/inaccurate sensors lead to being partially observable, and no sensors is unobservable environment. Multiple agents exist if each agent tries to max a performance measure. Competitive multiagent environments (chess) vs. cooperative (driving, all agents avoiding crashes). Deterministic environment if next state is completely determined by current state, otherwise nondeterministic (stochastic if specific probabilities for outcomes). Episodic if the agent experiences episodes with percepts and single actions, with each episode being independent of others, whereas sequential has current decisions potentially affecting later ones. Static doesn't change during agent deliberation while dynamic may. Discrete vs. continuous states, times, percepts, and actions. Known environment has outcomes for actions given. \n\n## AIMA 2.4 The Structure of Agents\n Agent = architecture + program. Table-driven agent lookup does the job but is highly inefficient. Simple reflex agents base actions on current precept without consideration of precept history (requires fully observable, randomization may help if partially observable). Model-based reflex agents maintain internal state of percept history, requires transition model (how the world works) and sensor model (how state of world manifests in percepts). Goal-based agents require goal info for a desirable destination. Utility-based agents maximize utility function (most desirable way to get to destination). Learning agents built from critic, learning element, problem generator, and performance element \n\n## Module 1 Lecture Notes\n Strong AI (actually thinking) vs. weak AI (simulating thinking). Create performance measure for what you want agent to achieve rather than how you think it should behave. For a given PEAS task environment, construct agent function to max expected value of performance measure and agent program that implements function on a specific architecture. Hardest environment is: continuous, partially observable stochastic, multiagent. Reflex agent makes action based on current percept (ignoring history), whereas problem solving agent plans ahead using search. \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive (sensors) and act (actuators) in an environment (rational agent achieves best (expected) outcome)\n* **Percept** - what the agent perceives\n* **Autonomy** - ability to learn to compensate for partial prior knowledge vs. solely relying on previous knowledge\n* **Task environment** - problem to be solved with rational agents with specified performance measures, environment, actuators, sensors\n* **Condition-action rule** - if-then rules\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 = \"\"\" String formatting: print(\"%s has %d fingers\" % (\"Name\",5)). == checks if same value, `is` checks if same object. \\\n",
        "list.sort() is in place, list.sorted() makes copy. Keys must be immutable in dictionary. Functions can return multiple values in tuple. No \\\n",
        "function overloading but some operator overloading. Non-default arguments have to come first in defining function. Specifying keyword calls to \\\n",
        "arguments must come after non-keyword specified arguments. \\*args / \\*kwargs allows for variable number of non-keyword arguments (tuple of \\\n",
        "arguments) / keyword arguments (dict of keywords and values). Default parameter values evaluated only when def statement is first executed. Extend \\\n",
        "subclass by defining `class AI_Student(Student)`. **List comprehension** [expression for var_name in list if filter]. Can also have dict/set \\\n",
        "comprehensions. Iterable has __iter__ method, iterator has __next__ method. **Generators** are iterators; functions that have `yield` automatically \\\n",
        "return generator when called. Can iterate over generators in for loop / list comprehension, or can explicitly call __next__ and catch StopIteration. \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"strong typing\" : \"objects have fixed type (i.e. can't combine str and int with +)\",\n",
        "\"dynamic typing\" : \"don't have to declare type for variables, type when assigned\",\n",
        "\"mutability\" : \"whether object can be changed (lists mutable; str, tup, int, immutable\",\n",
        "\"dynamic scope\" : \"functions see most current value of variables\",\n",
        "\"duck typing\" : \"object is suitable as a certain type if it has that type's methods\"\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 383
        },
        "outputId": "5b76f23e-596d-48b7-9ab7-f5e2d7c3fc40"
      },
      "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 String formatting: print(\"%s has %d fingers\" % (\"Name\",5)). == checks if same value, `is` checks if same object. list.sort() is in place, list.sorted() makes copy. Keys must be immutable in dictionary. Functions can return multiple values in tuple. No function overloading but some operator overloading. Non-default arguments have to come first in defining function. Specifying keyword calls to arguments must come after non-keyword specified arguments. \\*args / \\*kwargs allows for variable number of non-keyword arguments (tuple of arguments) / keyword arguments (dict of keywords and values). Default parameter values evaluated only when def statement is first executed. Extend subclass by defining `class AI_Student(Student)`. **List comprehension** [expression for var_name in list if filter]. Can also have dict/set comprehensions. Iterable has __iter__ method, iterator has __next__ method. **Generators** are iterators; functions that have `yield` automatically return generator when called. Can iterate over generators in for loop / list comprehension, or can explicitly call __next__ and catch StopIteration. \n\n## Module 2 Definitions\n* **Strong typing** - objects have fixed type (i.e. can't combine str and int with +)\n* **Dynamic typing** - don't have to declare type for variables, type when assigned\n* **Mutability** - whether object can be changed (lists mutable; str, tup, int, immutable\n* **Dynamic scope** - functions see most current value of variables\n* **Duck typing** - object is suitable as a certain type if it has that type's 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 = \"\"\" Known, fully observable search follows process: goal formulation, problem formulation, search (to find solution sequence), \\\n",
        "execution. Open-loop system follows fixed actions without percepts during execution, closed-loop monitors percepts. Search problem contains: \\\n",
        "state space, initial state, goal states, goal test, actions (applicable in particular states), transition model (what each action does in a state), \\\n",
        "action (path) cost function. Action sequences forms a path, and the solution is a path from initial to goal. Optimal solution has lowest path cost. \"\"\"\n",
        "chapter3_2 = \"\"\" Standardized problems show problem-solving methods, whereas real-world problems have applicable solutions. \"\"\"\n",
        "chapter3_3 = \"\"\" Search algorithm represented by following search tree, where nodes are states and edges are actions. Expand search tree \\\n",
        "by considering successor nodes at the frontier (separating reached and not reached nodes). Nodes keep track of state, parent, action to get \\\n",
        "to state, and total path cost from initial state (g(n)). **Best-first search** chooses node on frontier with min value of f(n) evaluation \\\n",
        "function. Use queue to store frontier: priority (pops min cost node, used in best-first), FIFO (BFS), LIFO (DFS). Graph search checks for \\\n",
        "redundant paths (and stores reached nodes) while tree search does not. Measure problem-solving performance using: completeness (guaranteed \\\n",
        "to find solution or report failure), cost optimality (solution with lowest path cost), time complexity, space complexity. Have to systematically \\\n",
        "search infinite state space. Measure complexity using d = depth of optimal solution, m = max path length, b = branching factor (number of \\\n",
        "successors for a node). \"\"\"\n",
        "chapter3_4 = \"\"\" **BFS** made efficient with FIFO queue and early goal test (checking node for solution right when it is generated). BFS is cost-\\\n",
        "optimal (for unit costs) and complete, with time/space complexity of $O(b^d)$. Exponential bound search cannot be solved with uninformed except \\\n",
        "if problem very small. **Uniform-cost search/Dijkstra's** performs best-first search using path cost as evaluation function (late goal test when \\\n",
        "node is expanded). Uniform-cost search is cost-optimal and complete, with time/space complexity of $O(b^d)$. **DFS** is not cost-optimal nor \\\n",
        "complete. DFS has memory of $O(bm)$ since no reached storage, and time $O(b^m)$. Backtracking search uses only $O(m)$ memory. **Depth-limited search** has time \\\n",
        "$O(b^l)$ and space $O(bl)$, but $l$ needs to be deeper than solution. **Iterative deepening search** runs DLS with increasing values of $l$, with \\\n",
        "memory $O(bd)$ and time $O(b^d)$. IDS preferred for uninformed if state space is larger than memory and solution has unknown depth. **Bidirectional \\\n",
        "search** searches from both initial and goal with time/space $O(2b^{d/2})$.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Tree search: find all possible paths from initial state. Strategy is order of tree expansion, evaluated by: completeness, \\\n",
        "optimality, time complexity, space complexity. BFS node inserted into queue after goal test. DFS better if space restricted, BFS if possible infinite \\\n",
        "paths. DLS: if l < d then incomplete, l > d then not optimal. IDLS is as time efficient as BFS but more space efficient. \"\"\"\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 (sequence of actions to goal) via search\",\n",
        "\"planning agent\" : \"using factored/structured state representations\",\n",
        "\"search algorithm\" : \"input search problem, output solution or returns that there is no solution\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 826
        },
        "outputId": "b31a6259-ec1a-4741-de01-5d8b48cef49a"
      },
      "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 Known, fully observable search follows process: goal formulation, problem formulation, search (to find solution sequence), execution. Open-loop system follows fixed actions without percepts during execution, closed-loop monitors percepts. Search problem contains: state space, initial state, goal states, goal test, actions (applicable in particular states), transition model (what each action does in a state), action (path) cost function. Action sequences forms a path, and the solution is a path from initial to goal. Optimal solution has lowest path cost. \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problems show problem-solving methods, whereas real-world problems have applicable solutions. \n\n## AIMA Chapter 3.3 Search Algorithms\n Search algorithm represented by following search tree, where nodes are states and edges are actions. Expand search tree by considering successor nodes at the frontier (separating reached and not reached nodes). Nodes keep track of state, parent, action to get to state, and total path cost from initial state (g(n)). **Best-first search** chooses node on frontier with min value of f(n) evaluation function. Use queue to store frontier: priority (pops min cost node, used in best-first), FIFO (BFS), LIFO (DFS). Graph search checks for redundant paths (and stores reached nodes) while tree search does not. Measure problem-solving performance using: completeness (guaranteed to find solution or report failure), cost optimality (solution with lowest path cost), time complexity, space complexity. Have to systematically search infinite state space. Measure complexity using d = depth of optimal solution, m = max path length, b = branching factor (number of successors for a node). \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n **BFS** made efficient with FIFO queue and early goal test (checking node for solution right when it is generated). BFS is cost-optimal (for unit costs) and complete, with time/space complexity of $O(b^d)$. Exponential bound search cannot be solved with uninformed except if problem very small. **Uniform-cost search/Dijkstra's** performs best-first search using path cost as evaluation function (late goal test when node is expanded). Uniform-cost search is cost-optimal and complete, with time/space complexity of $O(b^d)$. **DFS** is not cost-optimal nor complete. DFS has memory of $O(bm)$ since no reached storage, and time $O(b^m)$. Backtracking search uses only $O(m)$ memory. **Depth-limited search** has time $O(b^l)$ and space $O(bl)$, but $l$ needs to be deeper than solution. **Iterative deepening search** runs DLS with increasing values of $l$, with memory $O(bd)$ and time $O(b^d)$. IDS preferred for uninformed if state space is larger than memory and solution has unknown depth. **Bidirectional search** searches from both initial and goal with time/space $O(2b^{d/2})$.\n\n## Module 3 Lecture Notes\n Tree search: find all possible paths from initial state. Strategy is order of tree expansion, evaluated by: completeness, optimality, time complexity, space complexity. BFS node inserted into queue after goal test. DFS better if space restricted, BFS if possible infinite paths. DLS: if l < d then incomplete, l > d then not optimal. IDLS is as time efficient as BFS but more space efficient. \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan (sequence of actions to goal) via search\n* **Planning agent** - using factored/structured state representations\n* **Search algorithm** - input search problem, output solution or returns that there is no solution\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 = \"\"\" **Greedy best-first search** expands nodes with lowest h(n), not complete nor optimal, time/space = $O(|V|)$ or $O(bm)$ with \\\n",
        "good h(n). **A\\* search** is best-first search using f(n) = g(n) + h(n), complete and optimal (if using admissible heuristic; inadmissable may or \\\n",
        "may not be optimal). *Proof*: AFC that f(n) > C\\* for some n on optimal path, but f(n) <= g\\*(n) + h\\*(n) due to admissibility, a contradiction. \\\n",
        "A\\* optimal path nodes are expanded with f(n) < C\\* and none > C\\*. Every consistent heuristic is admissible. A\\* with consistent heuristic is \\\n",
        "optimally efficient (all algos extending from initial with same h(n) must expand surely expanded nodes. Can weight h(n) more heavily for weighted \\\n",
        "A\\* search. A\\* search has time/space   complexity $O(b^d)$. \"\"\"\n",
        "chapter3_6 = \"\"\" Manhattan distance heuristic sums horizontal and vertical distances to goal positions. Calculate effective branching factor as \\\n",
        "b needed for solution depth d and N + 1 nodes (N + 1 = 1 + b + b^2 + ...), closer to 1 if well-designed heuristic. Heuristic dominates another \\\n",
        "(and is more efficient) if it is always bigger than the other but both are still admissible/consistent. Cost of optimal solution to relaxed \\\n",
        "problem must be admissible/consistent for actual. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" UCS does goal test when selected for expansion, not when added to frontier (enqueues before checking goal). \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"using h(x) as a hint about the location of goal states\",\n",
        "\"admissible/optimistic heuristic\" : \"never overestimates the cost to goal\",\n",
        "\"consistent heuristic\" : \"satisfies triangle inequality, h(n) must be less than cost of n to successor n' + h(n')\",\n",
        "\"satisficing solution\" : \"using inadmissible heuristic to find suboptimal but good enough solution\",\n",
        "\"relaxed problem\" : \"problem with less restrictions on actions\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 524
        },
        "cellView": "form",
        "outputId": "84a638b2-02da-46a5-fe75-4fe93a2ea0a0"
      },
      "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 **Greedy best-first search** expands nodes with lowest h(n), not complete nor optimal, time/space = $O(|V|)$ or $O(bm)$ with good h(n). **A\\* search** is best-first search using f(n) = g(n) + h(n), complete and optimal (if using admissible heuristic; inadmissable may or may not be optimal). *Proof*: AFC that f(n) > C\\* for some n on optimal path, but f(n) <= g\\*(n) + h\\*(n) due to admissibility, a contradiction. A\\* optimal path nodes are expanded with f(n) < C\\* and none > C\\*. Every consistent heuristic is admissible. A\\* with consistent heuristic is optimally efficient (all algos extending from initial with same h(n) must expand surely expanded nodes. Can weight h(n) more heavily for weighted A\\* search. A\\* search has time/space   complexity $O(b^d)$. \n\n## AIMA Chapter 3.6 Heuristic Functions\n Manhattan distance heuristic sums horizontal and vertical distances to goal positions. Calculate effective branching factor as b needed for solution depth d and N + 1 nodes (N + 1 = 1 + b + b^2 + ...), closer to 1 if well-designed heuristic. Heuristic dominates another (and is more efficient) if it is always bigger than the other but both are still admissible/consistent. Cost of optimal solution to relaxed problem must be admissible/consistent for actual. \n\n## Module 4 Lecture Notes\n UCS does goal test when selected for expansion, not when added to frontier (enqueues before checking goal). \n\n## Module 4 Definitions\n* **Informed search** - using h(x) as a hint about the location of goal states\n* **Admissible/optimistic heuristic** - never overestimates the cost to goal\n* **Consistent heuristic** - satisfies triangle inequality, h(n) must be less than cost of n to successor n' + h(n')\n* **Satisficing solution** - using inadmissible heuristic to find suboptimal but good enough solution\n* **Relaxed problem** - problem with less restrictions on actions\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 = \"\"\" Game defined as having: initial state, whose turn it is, set of actions, transition model (state resulting from action), \\\n",
        "terminal test, utility function. \"\"\"\n",
        "chapter5_2 = \"\"\" **Minimax search** finds minimax value (`MAX` utility for state assuming optimal play for both sides) of each state of game \\\n",
        "tree. Algorithm recurses down tree and backs up minimax values, using depth-first exploration, with time $O(b^m)$ and space $O(bm)$. Multiplayer \\\n",
        "games have vector of utility values. **Alpha-beta pruning** allows for cutting down exponent of time complexity. Prune off leaves/branches \\\n",
        "that are independent of minimax decision. $\\\\alpha$ is highest value choice so far along path, at least value for `MAX`. $\\\\beta$ is lowest \\\n",
        "value choice so far along path, at most value for `MIN`. `MAX-VALUE` checks if v >= beta, `MIN-VALUE` checks if v <= alpha. Effectiveness of \\\n",
        "alpha-beta pruning dependent on the order of states considered. Better to try the best moves for each player first for max pruning/efficiency. \\\n",
        "Transposition tables allow for lookup of moves that result in same state. Type A strategy is wide but shallow, exploring all moves to certain \\\n",
        "depth then using heuristic to estimate utility. Type B strategy is deep but narrow, follows good moves as deep as possible. \"\"\"\n",
        "chapter5_3 = \"\"\" Use heuristic evaluation function to find estimate of expected utility of a state to the player. Continue without cutoff until \\\n",
        "reached quiescent position (no pending move that shifts position greatly) to apply evaluation function. Can mitigate horizon effect (extending \\\n",
        "inevitable bad move) using singular extensions (clearly better moves even if search is about to be cut off). \"\"\"\n",
        "chapter5_5 = \"\"\" **Expectiminimax value** in stochastic games with chance nodes. Evaluation functions *must* have values that are positive linear \\\n",
        "transformation of expected utility. Time is $O(b^m n^m)$, where n is number of distinct rolls. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Want to maximize the expected utility function for a rational agent. \"\"\"\n",
        "chapter16_2 = \"\"\" Constraints for rational preference relations: orderability, transitivity, continuity (exists probabilty for A and C to get B if A \\\n",
        "> B > C), substitutabilty, monotonicity, decomposability. Value function / ordinal utility function only cares about ranking of states. \"\"\"\n",
        "chapter16_3 = \"\"\" Preference elicitation involves using observed preferences to identify utility function. Expected monetary value is weighted-\\\n",
        "average of the different outcomes by probability. Insurance premium is difference between EMV and certainty equivalent. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Evaluation function to assess how good a board position is based on static features (zero-sum means one function \\\n",
        "can describe goodness for both players). Minimax (worst case) backed-up value determined by values of children. `MAX` initializes value to -inf, `MIN` initializes \\\n",
        "to +inf. Alpha-beta pruning: $\\\\alpha$ is MAX's current lower bound on outcome, $\\\\beta$ is MIN's current upper bound on outcome. MAX doesn't allow \\\n",
        "move that has worse score than alpha, MIN doesn't allow move with higher score than beta. Stop evaluating branch when if MAX node, value $v \\\\geq \\\\beta$ \\\n",
        "is backed up or if MIN node, value $v \\\\leq \\\\alpha$ is backed up. MIN sets beta, MAX sets alpha. Objectivist/frequentist finds averages based \\\n",
        "on experimental observations, subjectivist/Bayesian learn probabilities based on past experience. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"adversarial search\" : \"search in competitive environment, multiple agents with conflicting goals\",\n",
        "\"perfect information\" : \"fully observable game\",\n",
        "\"zero-sum\" : \"benefits to one player are bad for the other\"   \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": "6dfcc91d-626e-41f8-a7a0-296dac024591"
      },
      "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 Game defined as having: initial state, whose turn it is, set of actions, transition model (state resulting from action), terminal test, utility function. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n **Minimax search** finds minimax value (`MAX` utility for state assuming optimal play for both sides) of each state of game tree. Algorithm recurses down tree and backs up minimax values, using depth-first exploration, with time $O(b^m)$ and space $O(bm)$. Multiplayer games have vector of utility values. **Alpha-beta pruning** allows for cutting down exponent of time complexity. Prune off leaves/branches that are independent of minimax decision. $\\alpha$ is highest value choice so far along path, at least value for `MAX`. $\\beta$ is lowest value choice so far along path, at most value for `MIN`. `MAX-VALUE` checks if v >= beta, `MIN-VALUE` checks if v <= alpha. Effectiveness of alpha-beta pruning dependent on the order of states considered. Better to try the best moves for each player first for max pruning/efficiency. Transposition tables allow for lookup of moves that result in same state. Type A strategy is wide but shallow, exploring all moves to certain depth then using heuristic to estimate utility. Type B strategy is deep but narrow, follows good moves as deep as possible. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Use heuristic evaluation function to find estimate of expected utility of a state to the player. Continue without cutoff until reached quiescent position (no pending move that shifts position greatly) to apply evaluation function. Can mitigate horizon effect (extending inevitable bad move) using singular extensions (clearly better moves even if search is about to be cut off). \n\n## AIMA Chapter 5.5 Stochastic Games\n **Expectiminimax value** in stochastic games with chance nodes. Evaluation functions *must* have values that are positive linear transformation of expected utility. Time is $O(b^m n^m)$, where n is number of distinct rolls. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Want to maximize the expected utility function for a rational agent. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Constraints for rational preference relations: orderability, transitivity, continuity (exists probabilty for A and C to get B if A > B > C), substitutabilty, monotonicity, decomposability. Value function / ordinal utility function only cares about ranking of states. \n\n## AIMA Chapter 16.3 Utility Functions\n Preference elicitation involves using observed preferences to identify utility function. Expected monetary value is weighted-average of the different outcomes by probability. Insurance premium is difference between EMV and certainty equivalent. \n\n## Module 5 Lecture Notes\n Evaluation function to assess how good a board position is based on static features (zero-sum means one function can describe goodness for both players). Minimax (worst case) backed-up value determined by values of children. `MAX` initializes value to -inf, `MIN` initializes to +inf. Alpha-beta pruning: $\\alpha$ is MAX's current lower bound on outcome, $\\beta$ is MIN's current upper bound on outcome. MAX doesn't allow move that has worse score than alpha, MIN doesn't allow move with higher score than beta. Stop evaluating branch when if MAX node, value $v \\geq \\beta$ is backed up or if MIN node, value $v \\leq \\alpha$ is backed up. MIN sets beta, MAX sets alpha. Objectivist/frequentist finds averages based on experimental observations, subjectivist/Bayesian learn probabilities based on past experience. \n\n## Module 5 Definitions\n* **Adversarial search** - search in competitive environment, multiple agents with conflicting goals\n* **Perfect information** - fully observable game\n* **Zero-sum** - benefits to one player are bad for the other\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 = \"\"\" CSPs use general heuristics (rather than domain-specific in search). CSPs have X set of variables, D set of domains for each \\\n",
        "variable, and C constraints. Consistent assignments do not violate any constraints. Complete assignments have every variable with a value. \\\n",
        "Solutions are complete and consistent assignments. Partial solutions are consistent partial assignments. \"\"\"\n",
        "chapter6_2 = \"\"\" Constraint propagation reduces possible values for variables using constraints. Local consistency for each part of the graph \\\n",
        "ensures global consistency. Node-consistent variable if its domain values are all consistent with its unary constraints. Arc-consistent variable \\\n",
        "if its domain values satisfy its binary constraints; $X_i$ is arc-consistent with $X_j$ if for all values in $D_i$ there is some value in $D_j$ \\\n",
        "satisfying binary constraint $(X_i, X_j)$. **AC-3 algorithm** enforces arc-consistency, starting with queue of all arcs (each binary \\\n",
        "constraint having 2 arcs), popping off arcs and making $X_i$ arc-consistent with $X_j$, adding arcs with $X_i$ as a neighbor again. AC-3 has time \\\n",
        "complexity $O(cd^2)$, where c = number of binary constraints and d = largest domain size. Path consistency considers implicit constraints by \\\n",
        "looking at set of 3 variables; $\\{X_i, X_j\\}$ path consistent with $X_m$ if for all valid assignments of $\\{X_i, X_j\\}$, there is assignment of \\\n",
        "$X_m$ to satisfy constraints $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$ for path $X_i, X_m, X_j$. k-consistent means for any consistent assignment of set \\\n",
        "of $k - 1$ variables, a consistent value can always be assigned to the $k$th variable; node, arc, path consistency is for $k = 1, 2, 3$. For \\\n",
        "strongly k-consistent CSP, runtime is $O(k^2 d)$ since you only check domain values for each variable to see if consistent with assignments for \\\n",
        "previous variables. Can check $Alldiff$ constraint violation simply by seeing if you have $m$ variables and $n$ possible assignments where \\\n",
        "$m > n$. Resource constraint $Atmost$ can check violation if lowest value in all domains sum to higher than constraint or remove domain \\\n",
        "values that are higher than constraint. Bounds constraint propagation for upper and lower bounds. \"\"\"\n",
        "chapter6_3 = \"\"\" Search for solution if constraint propagation is insufficient. (Chronological) Backtracking search uses DFS approach, can be improved using \\\n",
        "domain-independent heuristics. Minimum-remaining-values / most constrained heurisitic chooses variable with lowest number of possible moves. \\\n",
        "Degree / most constraining heuristic chooses based on variable that is involved in the most constraints. Least-constraining-value heuristic \\\n",
        "assigns value that rules out the lowest number of choices for neighbors. Forward checking inference removing from neighbors' domains inconsistent \\\n",
        "values when a variable is assigned. Forward checking doesn't propagate. Efficient to combine MRV and FC. Maintaining Arc Consistency (MAC) algo calls \\\n",
        "AC-3 on arcs with unassigned neighbors, interleaving search and inference. Backjumping keeps track of conflict set to jump back to variable responsible for problem (smart \\\n",
        "backtracking) (or conflict-directed backjumping keeping track of responsible variable and subsequent variables). Constraint learning finds \\\n",
        "min set of variables in conflict set causing problems, then add constraint to avoid this no-good assignment. \"\"\"\n",
        "chapter6_4 = \"\"\" **Min-conflicts heuristic** changes value of a randomly chosen variable to one that minimizes conflicts with other variables. \"\"\"\n",
        "chapter6_5 = \"\"\" Independent subproblems found as connected components in constraint graph. Separating out to independent subproblems can turn work \\\n",
        "into linear in $n$ rather than exponential. Tree-structured CSP takes linear time in number of variables. **Directional arc consistency (DAC)** with \\\n",
        "ordering of variables if every arc $X_i$ is arc-consistent with each arc $X_j$ for $j > i$. Solve tree-structured CSP: toposort, make DAC $O(n)$, \\\n",
        "compare up to d possible domain values for 2 variables $O(d^2)$, choose values down toposort linearly. **Cutset conditioning** reduces general CSP to \\\n",
        "tree structured: choose subset S of variables (cycle cutset) such that graph becomes tree without S; for each possible assignment of S, remove inconsistent values \\\n",
        "from domains and check to see if remaining CSP has solution (runtime $O(d^c (n - c) d^2)$, most efficient time saving if graph nearly a tree (c is \\\n",
        "small). **Tree decomposition** transforms graph to tree by grouping nodes together into tree nodes such that: every variable exists in a tree node; \\\n",
        "if two variables are connected by a constraint, then they must appear together in >=1 tree node; if variable is in >1 tree nodes, then it must appear \\\n",
        "in every node along the path between the nodes (runtime $O(nd^2)$, where n is number of tree nodes and d is largest domain size of tuples, efficient \\\n",
        "as long as d is small). Goal is to make tree subproblems (tree nodes) as small as possible. Tree width for specific tree decomposition is 1 less \\\n",
        "than size of largest tree node, tree width of graph is min width of all decompositions. Graph with bounded width w can be solved in polynomial time \\\n",
        "$O(n d^{w + 1})$. Cutset conditioning is more space efficient than tree decomposition, but is less time efficient. There is always tree width $w < c + 1$ \\\n",
        "for cycle-cutset size c, so tree decomposition more time efficient but is space exponential in w whereas cutset is linear. **Value symmetry** can \\\n",
        "reduce search space by vactor of d! with symmetry-breaking constraints by assigning arbitrary order to set of values that must be different. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CSPs automatically prune branches that violate constraints. CSP solvers combine both search (assign value to variable) \\\n",
        "and inference (constraint propagation to see if it would violate local consistency). \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"unary/binary/global constraint\" : \"restricting value of one/two/arbitrary number of variables\",\n",
        "\"strongly k-consistent\" : \"k-consistent, k - 1 consistent,..., 1-consistent\",\n",
        "\"commutativity\" : \"order of actions doesn't matter\",\n",
        "\"tabu search\" : \"prevent returning to short list of recently visited states on the same plateau\",\n",
        "\"constraint weighting\" : \"concentrate search on important constraints\"\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6623d175-9b5d-46ce-f072-b3dbb478a1bb"
      },
      "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 CSPs use general heuristics (rather than domain-specific in search). CSPs have X set of variables, D set of domains for each variable, and C constraints. Consistent assignments do not violate any constraints. Complete assignments have every variable with a value. Solutions are complete and consistent assignments. Partial solutions are consistent partial assignments. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint propagation reduces possible values for variables using constraints. Local consistency for each part of the graph ensures global consistency. Node-consistent variable if its domain values are all consistent with its unary constraints. Arc-consistent variable if its domain values satisfy its binary constraints; $X_i$ is arc-consistent with $X_j$ if for all values in $D_i$ there is some value in $D_j$ satisfying binary constraint $(X_i, X_j)$. **AC-3 algorithm** enforces arc-consistency, starting with queue of all arcs (each binary constraint having 2 arcs), popping off arcs and making $X_i$ arc-consistent with $X_j$, adding arcs with $X_i$ as a neighbor again. AC-3 has time complexity $O(cd^2)$, where c = number of binary constraints and d = largest domain size. Path consistency considers implicit constraints by looking at set of 3 variables; $\\{X_i, X_j\\}$ path consistent with $X_m$ if for all valid assignments of $\\{X_i, X_j\\}$, there is assignment of $X_m$ to satisfy constraints $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$ for path $X_i, X_m, X_j$. k-consistent means for any consistent assignment of set of $k - 1$ variables, a consistent value can always be assigned to the $k$th variable; node, arc, path consistency is for $k = 1, 2, 3$. For strongly k-consistent CSP, runtime is $O(k^2 d)$ since you only check domain values for each variable to see if consistent with assignments for previous variables. Can check $Alldiff$ constraint violation simply by seeing if you have $m$ variables and $n$ possible assignments where $m > n$. Resource constraint $Atmost$ can check violation if lowest value in all domains sum to higher than constraint or remove domain values that are higher than constraint. Bounds constraint propagation for upper and lower bounds. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Search for solution if constraint propagation is insufficient. (Chronological) Backtracking search uses DFS approach, can be improved using domain-independent heuristics. Minimum-remaining-values / most constrained heurisitic chooses variable with lowest number of possible moves. Degree / most constraining heuristic chooses based on variable that is involved in the most constraints. Least-constraining-value heuristic assigns value that rules out the lowest number of choices for neighbors. Forward checking inference removing from neighbors' domains inconsistent values when a variable is assigned. Forward checking doesn't propagate. Efficient to combine MRV and FC. Maintaining Arc Consistency (MAC) algo calls AC-3 on arcs with unassigned neighbors, interleaving search and inference. Backjumping keeps track of conflict set to jump back to variable responsible for problem (smart backtracking) (or conflict-directed backjumping keeping track of responsible variable and subsequent variables). Constraint learning finds min set of variables in conflict set causing problems, then add constraint to avoid this no-good assignment. \n\n## AIMA Chapter 6.4 Local Search for CSPs\n **Min-conflicts heuristic** changes value of a randomly chosen variable to one that minimizes conflicts with other variables. \n\n## AIMA Chapter 6.5 The Structure of Problems\n Independent subproblems found as connected components in constraint graph. Separating out to independent subproblems can turn work into linear in $n$ rather than exponential. Tree-structured CSP takes linear time in number of variables. **Directional arc consistency (DAC)** with ordering of variables if every arc $X_i$ is arc-consistent with each arc $X_j$ for $j > i$. Solve tree-structured CSP: toposort, make DAC $O(n)$, compare up to d possible domain values for 2 variables $O(d^2)$, choose values down toposort linearly. **Cutset conditioning** reduces general CSP to tree structured: choose subset S of variables (cycle cutset) such that graph becomes tree without S; for each possible assignment of S, remove inconsistent values from domains and check to see if remaining CSP has solution (runtime $O(d^c (n - c) d^2)$, most efficient time saving if graph nearly a tree (c is small). **Tree decomposition** transforms graph to tree by grouping nodes together into tree nodes such that: every variable exists in a tree node; if two variables are connected by a constraint, then they must appear together in >=1 tree node; if variable is in >1 tree nodes, then it must appear in every node along the path between the nodes (runtime $O(nd^2)$, where n is number of tree nodes and d is largest domain size of tuples, efficient as long as d is small). Goal is to make tree subproblems (tree nodes) as small as possible. Tree width for specific tree decomposition is 1 less than size of largest tree node, tree width of graph is min width of all decompositions. Graph with bounded width w can be solved in polynomial time $O(n d^{w + 1})$. Cutset conditioning is more space efficient than tree decomposition, but is less time efficient. There is always tree width $w < c + 1$ for cycle-cutset size c, so tree decomposition more time efficient but is space exponential in w whereas cutset is linear. **Value symmetry** can reduce search space by vactor of d! with symmetry-breaking constraints by assigning arbitrary order to set of values that must be different. \n\n## Module 6 Lecture Notes\n CSPs automatically prune branches that violate constraints. CSP solvers combine both search (assign value to variable) and inference (constraint propagation to see if it would violate local consistency). \n\n## Module 6 Definitions\n* **Unary/binary/global constraint** - restricting value of one/two/arbitrary number of variables\n* **Strongly k-consistent** - k-consistent, k - 1 consistent,..., 1-consistent\n* **Commutativity** - order of actions doesn't matter\n* **Tabu search** - prevent returning to short list of recently visited states on the same plateau\n* **Constraint weighting** - concentrate search on important constraints\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 = \"\"\" KB-agent adds percept to knowledge base, asks for best action, and tells KB that it has taken that action. Declarative approach ( \\\n",
        "tell sentences to agent) vs. procedural approach (encodes directly as program code) to system building. Can create mechanisms to learn for itself. \\\n",
        "Learning agent can be fully autonomous. \"\"\"\n",
        "chapter7_2 = \"\"\" Wumpas world is partially observable, deterministic, discrete, static, single-agent, and sequential.  \"\"\"\n",
        "chapter7_3 = \"\"\" If sentence $\\\\alpha$ is true in model $m$, then $m$ satisfies $\\\\alpha$ and $m$ is a model of $\\\\alpha$. $M(\\\\alpha)$ denotes set \\\n",
        "of all models of $\\\\alpha$. $\\\\alpha \\\\vDash \\\\beta$ if $\\\\alpha$ entails $\\\\beta \\\\text{ iff } M(\\\\alpha) \\\\subseteq M(\\\\beta)$ (iff every model in \\\n",
        "which $\\\\alpha$ is true, $\\\\beta$ is true). Logical inference algo called model checking creates all models to check that $\\\\alpha$ is true in all \\\n",
        "models where $KB$ is true (i.e. $M(KB) \\subseteq M(\\\\alpha)$). If inference algo $i$ can derive $\\\\alpha$ from $KB$, then $KB \\\\vdash_i \\\\alpha$. \\\n",
        "Desirable properties of inference algo: sound / truth preserving (inference algo that only derives entailed sentences [model checking is sound]); \\\n",
        "completeness (derive any sentences that are entailed). \"\"\"\n",
        "chapter7_4 = \"\"\" Atomic sentences are single propositional symbols (i.e. $W_{1, 3}$). $\\\\land$ is and conjunction, $\\\\lor$ is or disjunction. Inference \\\n",
        "algo for propositional logic has worst-case complexity exponential of size of input. \"\"\"\n",
        "chapter7_5 = \"\"\" Concepts for entailment: logical equivalence, validity, satisfiability. Sentences are equivalent iff they entail each other. \\\n",
        "Deduction theorem: $\\\\alpha \\\\vDash \\\\beta$ iff $\\\\alpha \\\\implies \\\\beta$ is valid. Satisfiability and validity: $\\\\alpha \\\\vDash \\\\beta$ iff \\\n",
        "$\\\\alpha \\\\land \\\\lnot \\\\beta$ is unsatisfiable (proof by contradiction). **Monotonicity**: entailed sentences set can only increase as info added to \\\n",
        "KB (if $KB \\\\vDash \\\\alpha$ then $KB \\\\land \\\\beta \\\\vDash \\\\alpha$). **Resolution** is inference rule that gets to complete inference algorithm when \\\n",
        "used with complete search algorithm. Unit/full resolution inference rule: if disjunction of literals and one (or more) is false, then we can reach resolvent of \\\n",
        "disjunction without the complementary negative literal(s). Resolution-based theorem prover can decide whether $\\\\alpha \\\\vDash \\\\beta$ since \\\n",
        "every sentence is logically equivalent to conjunction of clauses (where clauses are disjunctions of literals) in conjunctive normal form. \\\n",
        "**Resolution algorithm**: show $KB \\\\vDash \\\\alpha$ by showing $KB \\\\land \\\\lnot \\\\alpha$ is unsatisfiable (proof by contradiction); $KB \\\\land \\\\lnot \\\\alpha$ \\\n",
        "converted to CNF, then resolution rule on pairs of clauses until no new clauses added (KB doesn't entail $\\\\alpha$) or two clauses resolve to \\\n",
        "empty clause (KB entails $\\\\alpha$). Resolution algo terminates due to resolution closure being finite; ground resolution theorem shows if a set \\\n",
        "of clauses is unsatisfiable, then closure contains empty set; shows completeness. Definite clause: disjunction of literals where exactly one is \\\n",
        "positive. Horn clause: disjunction of literals where at most one is positive (goal clauses don't have positive literals). Definite clauses can \\\n",
        "be written as conjunction of positive literals (from originally negative literals) implies the only positive literal. Can find entailment with \\\n",
        "Horn clauses in linear time. **Forward chaining algorithm** is data-driven reasoning, adds conclusions from definite clauses until no further inferences can be made (\\\n",
        "sound and complete).**Backward chaining algorithm** is goal-directed reasoning, usually much less than linear time. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Inference algo is sound if it only derives entailed sentences, complete if it can derive all of the entailed sentences. \\\n",
        "Horn clauses are closed under resolution -- applying resolution to horn clause gets back a horn clause. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"use reasoning over internal representation of knowledge to determine actions\",\n",
        "\"knowledge base\" : \"set of sentences made up of knowledge representation language, forming axioms and derived sentences\",\n",
        "\"syntax\" : \"specifies well formed sentences\",\n",
        "\"semantics\" : \"sentence meaning\",\n",
        "\"model\" : \"specific possible world which has fixed truth values for every relevant sentence\",\n",
        "\"grounding\" : \"connection between processes of logical reasoning and the real world\",\n",
        "\"validity / tautology\" : \"necessarily true sentences for all models\",\n",
        "\"satisfiable\" : \"sentence is true in or satisfied by some model\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 999
        },
        "outputId": "9130b8be-ad9b-412a-be37-3c2256a95e51"
      },
      "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 KB-agent adds percept to knowledge base, asks for best action, and tells KB that it has taken that action. Declarative approach ( tell sentences to agent) vs. procedural approach (encodes directly as program code) to system building. Can create mechanisms to learn for itself. Learning agent can be fully autonomous. \n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpas world is partially observable, deterministic, discrete, static, single-agent, and sequential.  \n\n## AIMA Chapter 7.3 Logic\n If sentence $\\alpha$ is true in model $m$, then $m$ satisfies $\\alpha$ and $m$ is a model of $\\alpha$. $M(\\alpha)$ denotes set of all models of $\\alpha$. $\\alpha \\vDash \\beta$ if $\\alpha$ entails $\\beta \\text{ iff } M(\\alpha) \\subseteq M(\\beta)$ (iff every model in which $\\alpha$ is true, $\\beta$ is true). Logical inference algo called model checking creates all models to check that $\\alpha$ is true in all models where $KB$ is true (i.e. $M(KB) \\subseteq M(\\alpha)$). If inference algo $i$ can derive $\\alpha$ from $KB$, then $KB \\vdash_i \\alpha$. Desirable properties of inference algo: sound / truth preserving (inference algo that only derives entailed sentences [model checking is sound]); completeness (derive any sentences that are entailed). \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Atomic sentences are single propositional symbols (i.e. $W_{1, 3}$). $\\land$ is and conjunction, $\\lor$ is or disjunction. Inference algo for propositional logic has worst-case complexity exponential of size of input. \n\n## AIMA 7.5 Propositional Theorem Proving\n Concepts for entailment: logical equivalence, validity, satisfiability. Sentences are equivalent iff they entail each other. Deduction theorem: $\\alpha \\vDash \\beta$ iff $\\alpha \\implies \\beta$ is valid. Satisfiability and validity: $\\alpha \\vDash \\beta$ iff $\\alpha \\land \\lnot \\beta$ is unsatisfiable (proof by contradiction). **Monotonicity**: entailed sentences set can only increase as info added to KB (if $KB \\vDash \\alpha$ then $KB \\land \\beta \\vDash \\alpha$). **Resolution** is inference rule that gets to complete inference algorithm when used with complete search algorithm. Unit/full resolution inference rule: if disjunction of literals and one (or more) is false, then we can reach resolvent of disjunction without the complementary negative literal(s). Resolution-based theorem prover can decide whether $\\alpha \\vDash \\beta$ since every sentence is logically equivalent to conjunction of clauses (where clauses are disjunctions of literals) in conjunctive normal form. **Resolution algorithm**: show $KB \\vDash \\alpha$ by showing $KB \\land \\lnot \\alpha$ is unsatisfiable (proof by contradiction); $KB \\land \\lnot \\alpha$ converted to CNF, then resolution rule on pairs of clauses until no new clauses added (KB doesn't entail $\\alpha$) or two clauses resolve to empty clause (KB entails $\\alpha$). Resolution algo terminates due to resolution closure being finite; ground resolution theorem shows if a set of clauses is unsatisfiable, then closure contains empty set; shows completeness. Definite clause: disjunction of literals where exactly one is positive. Horn clause: disjunction of literals where at most one is positive (goal clauses don't have positive literals). Definite clauses can be written as conjunction of positive literals (from originally negative literals) implies the only positive literal. Can find entailment with Horn clauses in linear time. **Forward chaining algorithm** is data-driven reasoning, adds conclusions from definite clauses until no further inferences can be made (sound and complete).**Backward chaining algorithm** is goal-directed reasoning, usually much less than linear time. \n\n## Module 7 Lecture Notes\n Inference algo is sound if it only derives entailed sentences, complete if it can derive all of the entailed sentences. Horn clauses are closed under resolution -- applying resolution to horn clause gets back a horn clause. \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning over internal representation of knowledge to determine actions\n* **Knowledge base** - set of sentences made up of knowledge representation language, forming axioms and derived sentences\n* **Syntax** - specifies well formed sentences\n* **Semantics** - sentence meaning\n* **Model** - specific possible world which has fixed truth values for every relevant sentence\n* **Grounding** - connection between processes of logical reasoning and the real world\n* **Validity / tautology** - necessarily true sentences for all models\n* **Satisfiable** - sentence is true in or satisfied by some model\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",
        "outputId": "9a1d55a2-2751-47b6-d649-0912abbeb481"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "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 To pass the Turing test, a computer needs NLP, knowledge representation, automated reasoning, machine learning, computer vision (for total), and robotics (for total). Value alignment problem: values/objectives put into machine must be aligned with those in human. \n\n## AIMA Chapter 27.1 The Limits of AI\n Measure a machine's ability to complete behavioral tests using the Turing test. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Searle Chinese room suggests that computers don't have understanding. \n\n## AIMA 2.1 Agents and Environments\n Agent behaviors based on agent functions that map percept sequences to specific actions. Agent functions are abstract, whereas agent programs are actual implementations. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rational agent does the right thing. Better to make performance measures that tracks with what should be achieved in the environment, not how the agent should behave. \n\n## AIMA 2.3 The Nature of Environments\n Task environments are fully observable if sensors provide access to the complete environment state at all times (no need to maintain internal state). Noisy/inaccurate sensors lead to being partially observable, and no sensors is unobservable environment. Multiple agents exist if each agent tries to max a performance measure. Competitive multiagent environments (chess) vs. cooperative (driving, all agents avoiding crashes). Deterministic environment if next state is completely determined by current state, otherwise nondeterministic (stochastic if specific probabilities for outcomes). Episodic if the agent experiences episodes with percepts and single actions, with each episode being independent of others, whereas sequential has current decisions potentially affecting later ones. Static doesn't change during agent deliberation while dynamic may. Discrete vs. continuous states, times, percepts, and actions. Known environment has outcomes for actions given. \n\n## AIMA 2.4 The Structure of Agents\n Agent = architecture + program. Table-driven agent lookup does the job but is highly inefficient. Simple reflex agents base actions on current precept without consideration of precept history (requires fully observable, randomization may help if partially observable). Model-based reflex agents maintain internal state of percept history, requires transition model (how the world works) and sensor model (how state of world manifests in percepts). Goal-based agents require goal info for a desirable destination. Utility-based agents maximize utility function (most desirable way to get to destination). Learning agents built from critic, learning element, problem generator, and performance element \n\n## Module 1 Lecture Notes\n Strong AI (actually thinking) vs. weak AI (simulating thinking). Create performance measure for what you want agent to achieve rather than how you think it should behave. For a given PEAS task environment, construct agent function to max expected value of performance measure and agent program that implements function on a specific architecture. Hardest environment is: continuous, partially observable stochastic, multiagent. Reflex agent makes action based on current percept (ignoring history), whereas problem solving agent plans ahead using search. \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive (sensors) and act (actuators) in an environment (rational agent achieves best (expected) outcome)\n* **Percept** - what the agent perceives\n* **Autonomy** - ability to learn to compensate for partial prior knowledge vs. solely relying on previous knowledge\n* **Task environment** - problem to be solved with rational agents with specified performance measures, environment, actuators, sensors\n* **Condition-action rule** - if-then rules\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n String formatting: print(\"%s has %d fingers\" % (\"Name\",5)). == checks if same value, `is` checks if same object. list.sort() is in place, list.sorted() makes copy. Keys must be immutable in dictionary. Functions can return multiple values in tuple. No function overloading but some operator overloading. Non-default arguments have to come first in defining function. Specifying keyword calls to arguments must come after non-keyword specified arguments. \\*args / \\*kwargs allows for variable number of non-keyword arguments (tuple of arguments) / keyword arguments (dict of keywords and values). Default parameter values evaluated only when def statement is first executed. Extend subclass by defining `class AI_Student(Student)`. **List comprehension** [expression for var_name in list if filter]. Can also have dict/set comprehensions. Iterable has __iter__ method, iterator has __next__ method. **Generators** are iterators; functions that have `yield` automatically return generator when called. Can iterate over generators in for loop / list comprehension, or can explicitly call __next__ and catch StopIteration. \n\n## Module 2 Definitions\n* **Strong typing** - objects have fixed type (i.e. can't combine str and int with +)\n* **Dynamic typing** - don't have to declare type for variables, type when assigned\n* **Mutability** - whether object can be changed (lists mutable; str, tup, int, immutable\n* **Dynamic scope** - functions see most current value of variables\n* **Duck typing** - object is suitable as a certain type if it has that type's methods\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Known, fully observable search follows process: goal formulation, problem formulation, search (to find solution sequence), execution. Open-loop system follows fixed actions without percepts during execution, closed-loop monitors percepts. Search problem contains: state space, initial state, goal states, goal test, actions (applicable in particular states), transition model (what each action does in a state), action (path) cost function. Action sequences forms a path, and the solution is a path from initial to goal. Optimal solution has lowest path cost. \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problems show problem-solving methods, whereas real-world problems have applicable solutions. \n\n## AIMA Chapter 3.3 Search Algorithms\n Search algorithm represented by following search tree, where nodes are states and edges are actions. Expand search tree by considering successor nodes at the frontier (separating reached and not reached nodes). Nodes keep track of state, parent, action to get to state, and total path cost from initial state (g(n)). **Best-first search** chooses node on frontier with min value of f(n) evaluation function. Use queue to store frontier: priority (pops min cost node, used in best-first), FIFO (BFS), LIFO (DFS). Graph search checks for redundant paths (and stores reached nodes) while tree search does not. Measure problem-solving performance using: completeness (guaranteed to find solution or report failure), cost optimality (solution with lowest path cost), time complexity, space complexity. Have to systematically search infinite state space. Measure complexity using d = depth of optimal solution, m = max path length, b = branching factor (number of successors for a node). \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n **BFS** made efficient with FIFO queue and early goal test (checking node for solution right when it is generated). BFS is cost-optimal (for unit costs) and complete, with time/space complexity of $O(b^d)$. Exponential bound search cannot be solved with uninformed except if problem very small. **Uniform-cost search/Dijkstra's** performs best-first search using path cost as evaluation function (late goal test when node is expanded). Uniform-cost search is cost-optimal and complete, with time/space complexity of $O(b^d)$. **DFS** is not cost-optimal nor complete. DFS has memory of $O(bm)$ since no reached storage, and time $O(b^m)$. Backtracking search uses only $O(m)$ memory. **Depth-limited search** has time $O(b^l)$ and space $O(bl)$, but $l$ needs to be deeper than solution. **Iterative deepening search** runs DLS with increasing values of $l$, with memory $O(bd)$ and time $O(b^d)$. IDS preferred for uninformed if state space is larger than memory and solution has unknown depth. **Bidirectional search** searches from both initial and goal with time/space $O(2b^{d/2})$.\n\n## Module 3 Lecture Notes\n Tree search: find all possible paths from initial state. Strategy is order of tree expansion, evaluated by: completeness, optimality, time complexity, space complexity. BFS node inserted into queue after goal test. DFS better if space restricted, BFS if possible infinite paths. DLS: if l < d then incomplete, l > d then not optimal. IDLS is as time efficient as BFS but more space efficient. \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan (sequence of actions to goal) via search\n* **Planning agent** - using factored/structured state representations\n* **Search algorithm** - input search problem, output solution or returns that there is no solution\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n **Greedy best-first search** expands nodes with lowest h(n), not complete nor optimal, time/space = $O(|V|)$ or $O(bm)$ with good h(n). **A\\* search** is best-first search using f(n) = g(n) + h(n), complete and optimal (if using admissible heuristic; inadmissable may or may not be optimal). *Proof*: AFC that f(n) > C\\* for some n on optimal path, but f(n) <= g\\*(n) + h\\*(n) due to admissibility, a contradiction. A\\* optimal path nodes are expanded with f(n) < C\\* and none > C\\*. Every consistent heuristic is admissible. A\\* with consistent heuristic is optimally efficient (all algos extending from initial with same h(n) must expand surely expanded nodes. Can weight h(n) more heavily for weighted A\\* search. A\\* search has time/space   complexity $O(b^d)$. \n\n## AIMA Chapter 3.6 Heuristic Functions\n Manhattan distance heuristic sums horizontal and vertical distances to goal positions. Calculate effective branching factor as b needed for solution depth d and N + 1 nodes (N + 1 = 1 + b + b^2 + ...), closer to 1 if well-designed heuristic. Heuristic dominates another (and is more efficient) if it is always bigger than the other but both are still admissible/consistent. Cost of optimal solution to relaxed problem must be admissible/consistent for actual. \n\n## Module 4 Lecture Notes\n UCS does goal test when selected for expansion, not when added to frontier (enqueues before checking goal). \n\n## Module 4 Definitions\n* **Informed search** - using h(x) as a hint about the location of goal states\n* **Admissible/optimistic heuristic** - never overestimates the cost to goal\n* **Consistent heuristic** - satisfies triangle inequality, h(n) must be less than cost of n to successor n' + h(n')\n* **Satisficing solution** - using inadmissible heuristic to find suboptimal but good enough solution\n* **Relaxed problem** - problem with less restrictions on actions\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Game defined as having: initial state, whose turn it is, set of actions, transition model (state resulting from action), terminal test, utility function. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n **Minimax search** finds minimax value (`MAX` utility for state assuming optimal play for both sides) of each state of game tree. Algorithm recurses down tree and backs up minimax values, using depth-first exploration, with time $O(b^m)$ and space $O(bm)$. Multiplayer games have vector of utility values. **Alpha-beta pruning** allows for cutting down exponent of time complexity. Prune off leaves/branches that are independent of minimax decision. $\\alpha$ is highest value choice so far along path, at least value for `MAX`. $\\beta$ is lowest value choice so far along path, at most value for `MIN`. `MAX-VALUE` checks if v >= beta, `MIN-VALUE` checks if v <= alpha. Effectiveness of alpha-beta pruning dependent on the order of states considered. Better to try the best moves for each player first for max pruning/efficiency. Transposition tables allow for lookup of moves that result in same state. Type A strategy is wide but shallow, exploring all moves to certain depth then using heuristic to estimate utility. Type B strategy is deep but narrow, follows good moves as deep as possible. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Use heuristic evaluation function to find estimate of expected utility of a state to the player. Continue without cutoff until reached quiescent position (no pending move that shifts position greatly) to apply evaluation function. Can mitigate horizon effect (extending inevitable bad move) using singular extensions (clearly better moves even if search is about to be cut off). \n\n## AIMA Chapter 5.5 Stochastic Games\n **Expectiminimax value** in stochastic games with chance nodes. Evaluation functions *must* have values that are positive linear transformation of expected utility. Time is $O(b^m n^m)$, where n is number of distinct rolls. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Want to maximize the expected utility function for a rational agent. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Constraints for rational preference relations: orderability, transitivity, continuity (exists probabilty for A and C to get B if A > B > C), substitutabilty, monotonicity, decomposability. Value function / ordinal utility function only cares about ranking of states. \n\n## AIMA Chapter 16.3 Utility Functions\n Preference elicitation involves using observed preferences to identify utility function. Expected monetary value is weighted-average of the different outcomes by probability. Insurance premium is difference between EMV and certainty equivalent. \n\n## Module 5 Lecture Notes\n Evaluation function to assess how good a board position is based on static features (zero-sum means one function can describe goodness for both players). Minimax (worst case) backed-up value determined by values of children. `MAX` initializes value to -inf, `MIN` initializes to +inf. Alpha-beta pruning: $\\alpha$ is MAX's current lower bound on outcome, $\\beta$ is MIN's current upper bound on outcome. MAX doesn't allow move that has worse score than alpha, MIN doesn't allow move with higher score than beta. Stop evaluating branch when if MAX node, value $v \\geq \\beta$ is backed up or if MIN node, value $v \\leq \\alpha$ is backed up. MIN sets beta, MAX sets alpha. Objectivist/frequentist finds averages based on experimental observations, subjectivist/Bayesian learn probabilities based on past experience. \n\n## Module 5 Definitions\n* **Adversarial search** - search in competitive environment, multiple agents with conflicting goals\n* **Perfect information** - fully observable game\n* **Zero-sum** - benefits to one player are bad for the other\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSPs use general heuristics (rather than domain-specific in search). CSPs have X set of variables, D set of domains for each variable, and C constraints. Consistent assignments do not violate any constraints. Complete assignments have every variable with a value. Solutions are complete and consistent assignments. Partial solutions are consistent partial assignments. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint propagation reduces possible values for variables using constraints. Local consistency for each part of the graph ensures global consistency. Node-consistent variable if its domain values are all consistent with its unary constraints. Arc-consistent variable if its domain values satisfy its binary constraints; $X_i$ is arc-consistent with $X_j$ if for all values in $D_i$ there is some value in $D_j$ satisfying binary constraint $(X_i, X_j)$. **AC-3 algorithm** enforces arc-consistency, starting with queue of all arcs (each binary constraint having 2 arcs), popping off arcs and making $X_i$ arc-consistent with $X_j$, adding arcs with $X_i$ as a neighbor again. AC-3 has time complexity $O(cd^2)$, where c = number of binary constraints and d = largest domain size. Path consistency considers implicit constraints by looking at set of 3 variables; $\\{X_i, X_j\\}$ path consistent with $X_m$ if for all valid assignments of $\\{X_i, X_j\\}$, there is assignment of $X_m$ to satisfy constraints $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$ for path $X_i, X_m, X_j$. k-consistent means for any consistent assignment of set of $k - 1$ variables, a consistent value can always be assigned to the $k$th variable; node, arc, path consistency is for $k = 1, 2, 3$. For strongly k-consistent CSP, runtime is $O(k^2 d)$ since you only check domain values for each variable to see if consistent with assignments for previous variables. Can check $Alldiff$ constraint violation simply by seeing if you have $m$ variables and $n$ possible assignments where $m > n$. Resource constraint $Atmost$ can check violation if lowest value in all domains sum to higher than constraint or remove domain values that are higher than constraint. Bounds constraint propagation for upper and lower bounds. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Search for solution if constraint propagation is insufficient. (Chronological) Backtracking search uses DFS approach, can be improved using domain-independent heuristics. Minimum-remaining-values / most constrained heurisitic chooses variable with lowest number of possible moves. Degree / most constraining heuristic chooses based on variable that is involved in the most constraints. Least-constraining-value heuristic assigns value that rules out the lowest number of choices for neighbors. Forward checking inference removing from neighbors' domains inconsistent values when a variable is assigned. Forward checking doesn't propagate. Efficient to combine MRV and FC. Maintaining Arc Consistency (MAC) algo calls AC-3 on arcs with unassigned neighbors, interleaving search and inference. Backjumping keeps track of conflict set to jump back to variable responsible for problem (smart backtracking) (or conflict-directed backjumping keeping track of responsible variable and subsequent variables). Constraint learning finds min set of variables in conflict set causing problems, then add constraint to avoid this no-good assignment. \n\n## AIMA Chapter 6.4 Local Search for CSPs\n **Min-conflicts heuristic** changes value of a randomly chosen variable to one that minimizes conflicts with other variables. \n\n## AIMA Chapter 6.5 The Structure of Problems\n Independent subproblems found as connected components in constraint graph. Separating out to independent subproblems can turn work into linear in $n$ rather than exponential. Tree-structured CSP takes linear time in number of variables. **Directional arc consistency (DAC)** with ordering of variables if every arc $X_i$ is arc-consistent with each arc $X_j$ for $j > i$. Solve tree-structured CSP: toposort, make DAC $O(n)$, compare up to d possible domain values for 2 variables $O(d^2)$, choose values down toposort linearly. **Cutset conditioning** reduces general CSP to tree structured: choose subset S of variables (cycle cutset) such that graph becomes tree without S; for each possible assignment of S, remove inconsistent values from domains and check to see if remaining CSP has solution (runtime $O(d^c (n - c) d^2)$, most efficient time saving if graph nearly a tree (c is small). **Tree decomposition** transforms graph to tree by grouping nodes together into tree nodes such that: every variable exists in a tree node; if two variables are connected by a constraint, then they must appear together in >=1 tree node; if variable is in >1 tree nodes, then it must appear in every node along the path between the nodes (runtime $O(nd^2)$, where n is number of tree nodes and d is largest domain size of tuples, efficient as long as d is small). Goal is to make tree subproblems (tree nodes) as small as possible. Tree width for specific tree decomposition is 1 less than size of largest tree node, tree width of graph is min width of all decompositions. Graph with bounded width w can be solved in polynomial time $O(n d^{w + 1})$. Cutset conditioning is more space efficient than tree decomposition, but is less time efficient. There is always tree width $w < c + 1$ for cycle-cutset size c, so tree decomposition more time efficient but is space exponential in w whereas cutset is linear. **Value symmetry** can reduce search space by vactor of d! with symmetry-breaking constraints by assigning arbitrary order to set of values that must be different. \n\n## Module 6 Lecture Notes\n CSPs automatically prune branches that violate constraints. CSP solvers combine both search (assign value to variable) and inference (constraint propagation to see if it would violate local consistency). \n\n## Module 6 Definitions\n* **Unary/binary/global constraint** - restricting value of one/two/arbitrary number of variables\n* **Strongly k-consistent** - k-consistent, k - 1 consistent,..., 1-consistent\n* **Commutativity** - order of actions doesn't matter\n* **Tabu search** - prevent returning to short list of recently visited states on the same plateau\n* **Constraint weighting** - concentrate search on important constraints\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n KB-agent adds percept to knowledge base, asks for best action, and tells KB that it has taken that action. Declarative approach ( tell sentences to agent) vs. procedural approach (encodes directly as program code) to system building. Can create mechanisms to learn for itself. Learning agent can be fully autonomous. \n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpas world is partially observable, deterministic, discrete, static, single-agent, and sequential.  \n\n## AIMA Chapter 7.3 Logic\n If sentence $\\alpha$ is true in model $m$, then $m$ satisfies $\\alpha$ and $m$ is a model of $\\alpha$. $M(\\alpha)$ denotes set of all models of $\\alpha$. $\\alpha \\vDash \\beta$ if $\\alpha$ entails $\\beta \\text{ iff } M(\\alpha) \\subseteq M(\\beta)$ (iff every model in which $\\alpha$ is true, $\\beta$ is true). Logical inference algo called model checking creates all models to check that $\\alpha$ is true in all models where $KB$ is true (i.e. $M(KB) \\subseteq M(\\alpha)$). If inference algo $i$ can derive $\\alpha$ from $KB$, then $KB \\vdash_i \\alpha$. Desirable properties of inference algo: sound / truth preserving (inference algo that only derives entailed sentences [model checking is sound]); completeness (derive any sentences that are entailed). \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Atomic sentences are single propositional symbols (i.e. $W_{1, 3}$). $\\land$ is and conjunction, $\\lor$ is or disjunction. Inference algo for propositional logic has worst-case complexity exponential of size of input. \n\n## AIMA 7.5 Propositional Theorem Proving\n Concepts for entailment: logical equivalence, validity, satisfiability. Sentences are equivalent iff they entail each other. Deduction theorem: $\\alpha \\vDash \\beta$ iff $\\alpha \\implies \\beta$ is valid. Satisfiability and validity: $\\alpha \\vDash \\beta$ iff $\\alpha \\land \\lnot \\beta$ is unsatisfiable (proof by contradiction). **Monotonicity**: entailed sentences set can only increase as info added to KB (if $KB \\vDash \\alpha$ then $KB \\land \\beta \\vDash \\alpha$). **Resolution** is inference rule that gets to complete inference algorithm when used with complete search algorithm. Unit/full resolution inference rule: if disjunction of literals and one (or more) is false, then we can reach resolvent of disjunction without the complementary negative literal(s). Resolution-based theorem prover can decide whether $\\alpha \\vDash \\beta$ since every sentence is logically equivalent to conjunction of clauses (where clauses are disjunctions of literals) in conjunctive normal form. **Resolution algorithm**: show $KB \\vDash \\alpha$ by showing $KB \\land \\lnot \\alpha$ is unsatisfiable (proof by contradiction); $KB \\land \\lnot \\alpha$ converted to CNF, then resolution rule on pairs of clauses until no new clauses added (KB doesn't entail $\\alpha$) or two clauses resolve to empty clause (KB entails $\\alpha$). Resolution algo terminates due to resolution closure being finite; ground resolution theorem shows if a set of clauses is unsatisfiable, then closure contains empty set; shows completeness. Definite clause: disjunction of literals where exactly one is positive. Horn clause: disjunction of literals where at most one is positive (goal clauses don't have positive literals). Definite clauses can be written as conjunction of positive literals (from originally negative literals) implies the only positive literal. Can find entailment with Horn clauses in linear time. **Forward chaining algorithm** is data-driven reasoning, adds conclusions from definite clauses until no further inferences can be made (sound and complete).**Backward chaining algorithm** is goal-directed reasoning, usually much less than linear time. \n\n## Module 7 Lecture Notes\n Inference algo is sound if it only derives entailed sentences, complete if it can derive all of the entailed sentences. Horn clauses are closed under resolution -- applying resolution to horn clause gets back a horn clause. \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning over internal representation of knowledge to determine actions\n* **Knowledge base** - set of sentences made up of knowledge representation language, forming axioms and derived sentences\n* **Syntax** - specifies well formed sentences\n* **Semantics** - sentence meaning\n* **Model** - specific possible world which has fixed truth values for every relevant sentence\n* **Grounding** - connection between processes of logical reasoning and the real world\n* **Validity / tautology** - necessarily true sentences for all models\n* **Satisfiable** - sentence is true in or satisfied by some model\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}