{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for 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": "d82c7119-0616-4aa1-f213-b51de2fd418b"
      },
      "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": 99,
      "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": "b9165a56-7379-4bd8-84c9-f25b42f1cfe8"
      },
      "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": 100,
      "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": 101,
      "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 = \"\"\"\n",
        "- rationality is: internal thought processes and reasonings vs intelligent behaviors\n",
        "\n",
        "- Acting humanly: **Turing test**\n",
        "\n",
        "  - if a human can't distinguish the answers done by human and computer (physical simulation isn't necessary)\n",
        "\n",
        "  - total Turing test: requires interaction between human and object in real world\n",
        "\n",
        "- Thinking humanly: cognitive method approach\n",
        "\n",
        "  - intervined with cognitive science\n",
        "\n",
        "- Thinking rationally: laws of thought\n",
        "\n",
        "  - Aristotle, logic\n",
        "\n",
        "- Acting rationally: rational agent\n",
        "\n",
        "  - something acts to achieve the best (expected) outcome\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "- **week AI** (machines would act as if they are intelligent) vs **strong AI** (machines are actually conciously thinking)\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "- **the Chinese room**\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "- agents: perceive the environment throught **sensors**, and act on it throug **actuator** (human, robot, software) \n",
        "\n",
        "  - agent's choice on actions depends on its built-in knowledge and the entire percept sequence observed in the environment (to-date)\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "- rational agent: maximize its performance measure\n",
        "\n",
        "- omniscience: knows the actual outcome (impossible)\n",
        "\n",
        "- requires agent to gather information and learning (become automonous)\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "- **task environment** (PEAS)\n",
        "\n",
        "  - performance measure\n",
        "\n",
        "  - environment\n",
        "\n",
        "  - actuators\n",
        "\n",
        "  - sensors\n",
        "\n",
        "- properties of task environment:\n",
        "\n",
        "  - fully observable vs. partially observable\n",
        "\n",
        "  - single agent vs. multiagent\n",
        "\n",
        "  - deterministic vs. nondeterministic (stochastic) (if next state is deterministic based on current state and the action to take)\n",
        "\n",
        "  - episodic vs. sequential (experience in atmoic episodes (one percept in one state, states are not dependent), vs current decision can affect future)\n",
        "\n",
        "  - static vs. dynamic (if the environment is changing when agent is deliberating)\n",
        "\n",
        "  - discrete vs. continuous (if states are discrete)\n",
        "\n",
        "  - known vs. unknown (if the agent knows about the laws of the world)\n",
        "\n",
        "- hardest problem: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "- agent = architecture + program (take percept as input and action as output)\n",
        "\n",
        "- simple reflex agent: select actions on the current, ignoring the past (work if environment is fully observable)\n",
        "\n",
        "- model-based reflex agent: keep track of the past with internal states\n",
        "\n",
        "  - transition model (how the world changes) + sensor model (how changes are reflected in agent's percept)\n",
        "\n",
        "- goal-based agent\n",
        "\n",
        "  - search and planning\n",
        "\n",
        "- utility-based agent (expected utility for performance measure)\n",
        "\n",
        "- learning agent\n",
        "\n",
        "- problem-solving agent: must plan ahead, consider a sequence of action that form a path to a goal state (search)\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"rationality\": \"doing the right thing\",\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"the content the agent's sensor perceives\",\n",
        "\"agent function\" : \"map percept to action (abstract mathematical description)\",\n",
        "\"agent program\": \"implement agent function (within some physical system)\",\n",
        "\"consequentialism\": \"evaluate agent's action by its consequence\",\n",
        "\"performance measure\": \"evaluate states resulted from an action\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 102,
      "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": "0e3fd350-73e8-45fd-b93b-f2e09d0d1330"
      },
      "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": 103,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n- rationality is: internal thought processes and reasonings vs intelligent behaviors\n\n- Acting humanly: **Turing test**\n\n  - if a human can't distinguish the answers done by human and computer (physical simulation isn't necessary)\n\n  - total Turing test: requires interaction between human and object in real world\n\n- Thinking humanly: cognitive method approach\n\n  - intervined with cognitive science\n\n- Thinking rationally: laws of thought\n\n  - Aristotle, logic\n\n- Acting rationally: rational agent\n\n  - something acts to achieve the best (expected) outcome\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n- **week AI** (machines would act as if they are intelligent) vs **strong AI** (machines are actually conciously thinking)\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n- **the Chinese room**\n\n\n## AIMA 2.1 Agents and Environments\n\n- agents: perceive the environment throught **sensors**, and act on it throug **actuator** (human, robot, software) \n\n  - agent's choice on actions depends on its built-in knowledge and the entire percept sequence observed in the environment (to-date)\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n- rational agent: maximize its performance measure\n\n- omniscience: knows the actual outcome (impossible)\n\n- requires agent to gather information and learning (become automonous)\n\n\n## AIMA 2.3 The Nature of Environments\n\n- **task environment** (PEAS)\n\n  - performance measure\n\n  - environment\n\n  - actuators\n\n  - sensors\n\n- properties of task environment:\n\n  - fully observable vs. partially observable\n\n  - single agent vs. multiagent\n\n  - deterministic vs. nondeterministic (stochastic) (if next state is deterministic based on current state and the action to take)\n\n  - episodic vs. sequential (experience in atmoic episodes (one percept in one state, states are not dependent), vs current decision can affect future)\n\n  - static vs. dynamic (if the environment is changing when agent is deliberating)\n\n  - discrete vs. continuous (if states are discrete)\n\n  - known vs. unknown (if the agent knows about the laws of the world)\n\n- hardest problem: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown\n\n\n## AIMA 2.4 The Structure of Agents\n\n- agent = architecture + program (take percept as input and action as output)\n\n- simple reflex agent: select actions on the current, ignoring the past (work if environment is fully observable)\n\n- model-based reflex agent: keep track of the past with internal states\n\n  - transition model (how the world changes) + sensor model (how changes are reflected in agent's percept)\n\n- goal-based agent\n\n  - search and planning\n\n- utility-based agent (expected utility for performance measure)\n\n- learning agent\n\n- problem-solving agent: must plan ahead, consider a sequence of action that form a path to a goal state (search)\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Rationality** - doing the right thing\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the content the agent's sensor perceives\n* **Agent function** - map percept to action (abstract mathematical description)\n* **Agent program** - implement agent function (within some physical system)\n* **Consequentialism** - evaluate agent's action by its consequence\n* **Performance measure** - evaluate states resulted from an action\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "- immutable: string, tuple\n",
        "\n",
        "- mutable: list\n",
        "\n",
        "- t = ['a', 'b', 'c', 'd', 'e'], t[1:-1:2] = ['b', 'c', 'd']\n",
        "\n",
        "- t.insert('b', 2); t => ['a', 'b', 'b', 'c', 'd', 'e']\n",
        "\n",
        "- t.count('b') => 2\n",
        "\n",
        "- key arguments must be after positional arguments\n",
        "\n",
        "- **args and kwargs**\n",
        "\n",
        "```\n",
        "def myfun(positional, *args, **kwargs):\n",
        "  print(positional)\n",
        "  if args:\n",
        "    print(args)\n",
        "  if kwargs:\n",
        "    print(kwargs)\n",
        "\n",
        "myfun(\"hi\", \"the\", \"best\", \"food\", \"is\", \"tacos\", shell=\"soft\", meat=\"beef\")\n",
        ">>> hi\n",
        "    ('the', 'best', 'food', 'is', 'tacos’)\n",
        "    {'shell': 'soft', 'meat': 'beef'}\n",
        "```\n",
        "\n",
        "- **multiple inheritance**\n",
        "\n",
        "```\n",
        "class A(object):\n",
        "  def foo(self):\n",
        "    print('Foo!')\n",
        "class B(object):\n",
        "  def foo(self):\n",
        "    print('Foo?')\n",
        "  def bar(self):\n",
        "    print('Bar!')\n",
        "class C(A, B):\n",
        "  def foobar(self):\n",
        "    super().foo() # Foo!\n",
        "    super().bar() # Bar!\n",
        "```\n",
        "\n",
        "- benefits of generators:\n",
        "\n",
        "  - Maintains local state automatically\n",
        "  \n",
        "  - Values are computed one at a time, as they’re needed\n",
        "  \n",
        "  - Avoids storing the entire sequence in memory\n",
        "\n",
        "  - Crucial for infinite sequences\n",
        "  \n",
        "  - Bad if you need to inspect the individual values\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"Duck typing\": \"establishes suitability of an object by determining presence of methods\",\n",
        "}"
      ],
      "execution_count": 104,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 911
        },
        "outputId": "5d35e027-d182-4332-fe12-97d39430248c"
      },
      "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": 105,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\n- immutable: string, tuple\n\n- mutable: list\n\n- t = ['a', 'b', 'c', 'd', 'e'], t[1:-1:2] = ['b', 'c', 'd']\n\n- t.insert('b', 2); t => ['a', 'b', 'b', 'c', 'd', 'e']\n\n- t.count('b') => 2\n\n- key arguments must be after positional arguments\n\n- **args and kwargs**\n\n```\ndef myfun(positional, *args, **kwargs):\n  print(positional)\n  if args:\n    print(args)\n  if kwargs:\n    print(kwargs)\n\nmyfun(\"hi\", \"the\", \"best\", \"food\", \"is\", \"tacos\", shell=\"soft\", meat=\"beef\")\n>>> hi\n    ('the', 'best', 'food', 'is', 'tacos’)\n    {'shell': 'soft', 'meat': 'beef'}\n```\n\n- **multiple inheritance**\n\n```\nclass A(object):\n  def foo(self):\n    print('Foo!')\nclass B(object):\n  def foo(self):\n    print('Foo?')\n  def bar(self):\n    print('Bar!')\nclass C(A, B):\n  def foobar(self):\n    super().foo() # Foo!\n    super().bar() # Bar!\n```\n\n- benefits of generators:\n\n  - Maintains local state automatically\n  \n  - Values are computed one at a time, as they’re needed\n  \n  - Avoids storing the entire sequence in memory\n\n  - Crucial for infinite sequences\n  \n  - Bad if you need to inspect the individual values\n\n\n## Module 2 Definitions\n* **Duck typing** - establishes suitability of an object by determining presence of methods\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "- search problem (fully observable, deterministic, known environment):\n",
        "\n",
        "  - state space: possible states\n",
        "\n",
        "  - inital state\n",
        "\n",
        "  - goal state\n",
        "\n",
        "  - actions\n",
        "\n",
        "  - transition model\n",
        "\n",
        "  - action cost function\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "- **standardize problem**: to exercise problem-solving method\n",
        "\n",
        "  - **grid world**: 2d arrays of square cells where agent can move from cell to cell\n",
        "\n",
        "    - e.g. vacuum world, sokoban puzzle, sliding-tile puzzle (8-puzzle)\n",
        "\n",
        "- **real-world problem**: whose solution people actually use in real life \n",
        "\n",
        "  - route-finding problem, airline scheduling, routing video streams in computer network\n",
        "\n",
        "  - touring problem (traveling salesperson problem), VLSI layout, robot navigation, automatic assembly sequencing\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "- **search algorithm**: takes a search problem and returns a solution, or failure if no solution\n",
        "\n",
        "- **best-first search**: choose the node with some minimum value of f(n), evaluation function (informed search)\n",
        "\n",
        "  - on each iteration, pop a node with the minimum f(n) (**priority queue**), return it if it is the goal, or get its successors\n",
        "  \n",
        "    - add each successor to the frontier if it has not been reached bofre, or if the cost of the path to it is lower than before\n",
        "\n",
        "- **redundant path**: cycle, or worse path to get to the same state\n",
        "\n",
        "  - best-first search remembers all previous reached states, appropriate when there are lots of redundant states\n",
        "\n",
        "  - **graph search**: checks for redundant paths\n",
        "  \n",
        "  - **tree-like search**: not checking redundant paths (less memory)\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "- breath-first search (FIFO queue, reached is set rather than map):\n",
        "\n",
        "  - complete, optimal, find a solution with minimum actions\n",
        "\n",
        "  - **early goal test**: check if a node is a solution as soon as it is generated (best-first search does **late goal test**) \n",
        "\n",
        "  - time and space complexity: $O(b^d)$\n",
        "\n",
        "  - appropriate when:\n",
        "  \n",
        "    - possible infinite path\n",
        "\n",
        "    - some solution have short paths\n",
        "\n",
        "    - can quickly discard unlikely path\n",
        "\n",
        "- Dijkstra's algorithm (**uniform-cost search**): best-first search where f(n) = g(n)\n",
        "\n",
        "  - complete and cost-optimal\n",
        "\n",
        "  - space and time complexity: $O(b^{1+\\\\lfloor C^*/e \\\\rfloor})$, where C* is the cost of optimal solution, e is the lower bound on the cost of each action\n",
        "\n",
        "    - if all action costs are equal, complexity = $O(b^{1+d})$, which is similar to breath-first search\n",
        "\n",
        "  - breath-first search explores equally in all directions\n",
        "\n",
        "  - uniform-cost search prioritize which paths to explore\n",
        "\n",
        "- depth-first search (like a tree-like search, not keep a table of reached, , LIFO frontier)\n",
        "\n",
        "  - not optimal, incomplete\n",
        "\n",
        "  - time complexity proportional to the number of states, memory complexity $O(bm)$, where b is the branching factor and m is the maximum depth\n",
        "\n",
        "  - appropriate when:\n",
        "\n",
        "    - space is restricted\n",
        "\n",
        "    - there are many possible solutions with long path, and wrong path are usually terminated quickly\n",
        "\n",
        "    - search can be fine-tuned quickly \n",
        "\n",
        "  - **back-tracking search**: use even less memory, only one successor generated at a time, rather than all successors\n",
        "\n",
        "    - successor generated by modifying the current state, rather than allocating new memory for a brand-new state\n",
        "\n",
        "    - memory complexity $O(m)$\n",
        "\n",
        "- **depth-limited search** (tree-like search)\n",
        "\n",
        "  - time complexity $O(b^l)$ and space complexity $O(bl)$\n",
        "\n",
        "  - eliminate cycles, but not optimal, incomplete\n",
        "\n",
        "  - no infinite-path problem\n",
        "\n",
        "- **literative deepening search**:\n",
        "\n",
        "  - optimal, and complete\n",
        "\n",
        "  - memory complexity: $O(bd)$ if there is a solution, or $O(bm)$ if there isn't\n",
        "\n",
        "  - time complexity: $O(b^d)$ if there is solution, or $O(b^m)$ if there isn't\n",
        "\n",
        "  - appropriate when:\n",
        "\n",
        "    - search space is larger than can fit in memory and the depth of the solution is not known\n",
        "\n",
        "- bidirectional search: search from the initial state and the goal state\n",
        "\n",
        "  - complete and optimal\n",
        "\n",
        "  - need 2 frontiers and 2 reached table\n",
        "\n",
        "  - $O(b^{d/2}+b^{d/2})\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "- state is a phyiscal configuration, node is part of the tree\n",
        "\n",
        "- uninformed: use only information available in the problem definition (all nodes in the frontier look equally the same)\n",
        "\n",
        "- informed: some nodes might be better than other\n",
        "\n",
        "\n",
        "| criterion | breath-first | uniform-cost | depth-first | depth-limited | iterative deepening | bidirectional |\n",
        "| ----------| ------------ | ------------ | ----------- | ------------- | ------------------- | ------------- |\n",
        "| complete? | Yes          | Yes          | No          | No            | Yes                 | Yes           |\n",
        "| optimal?  | Yes          | Yes          | No          | No            | No                  | Yes           |\n",
        "| time      | $O(b^d)$     | $O(b^{1+\\\\lfloor C^*/e \\\\rfloor})$| $O(b^m)$ | $O(b^l)$ | $O(b^d)$         | $O(b^{d/2})$  |\n",
        "| space     | $O(b^d)$     | $O(b^{1+\\\\lfloor C^*/e \\\\rfloor})$| $O(bm)$ | $O(bl)$ | $O(bd)$            | $O(b^{d/2})$  |         \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "\"path\": \"a sequence of actions\",\n",
        "\"solution\": \"path from initial state to the goal state\",\n",
        "\"optimal solution\": \"solution with the lowest cost\",\n",
        "\"frontier\": \"states that are available for expanding\",\n",
        "\"completeness\": \"a complete algorithm must systematically check every state that is reachable from the initial state\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 106,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e5cddbad-58ac-444e-a12e-5f693bc64d53"
      },
      "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": 107,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n- search problem (fully observable, deterministic, known environment):\n\n  - state space: possible states\n\n  - inital state\n\n  - goal state\n\n  - actions\n\n  - transition model\n\n  - action cost function\n\n\n## AIMA Chapter 3.2 Example Problems\n\n- **standardize problem**: to exercise problem-solving method\n\n  - **grid world**: 2d arrays of square cells where agent can move from cell to cell\n\n    - e.g. vacuum world, sokoban puzzle, sliding-tile puzzle (8-puzzle)\n\n- **real-world problem**: whose solution people actually use in real life \n\n  - route-finding problem, airline scheduling, routing video streams in computer network\n\n  - touring problem (traveling salesperson problem), VLSI layout, robot navigation, automatic assembly sequencing\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n- **search algorithm**: takes a search problem and returns a solution, or failure if no solution\n\n- **best-first search**: choose the node with some minimum value of f(n), evaluation function (informed search)\n\n  - on each iteration, pop a node with the minimum f(n) (**priority queue**), return it if it is the goal, or get its successors\n  \n    - add each successor to the frontier if it has not been reached bofre, or if the cost of the path to it is lower than before\n\n- **redundant path**: cycle, or worse path to get to the same state\n\n  - best-first search remembers all previous reached states, appropriate when there are lots of redundant states\n\n  - **graph search**: checks for redundant paths\n  \n  - **tree-like search**: not checking redundant paths (less memory)\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n- breath-first search (FIFO queue, reached is set rather than map):\n\n  - complete, optimal, find a solution with minimum actions\n\n  - **early goal test**: check if a node is a solution as soon as it is generated (best-first search does **late goal test**) \n\n  - time and space complexity: $O(b^d)$\n\n  - appropriate when:\n  \n    - possible infinite path\n\n    - some solution have short paths\n\n    - can quickly discard unlikely path\n\n- Dijkstra's algorithm (**uniform-cost search**): best-first search where f(n) = g(n)\n\n  - complete and cost-optimal\n\n  - space and time complexity: $O(b^{1+\\lfloor C^*/e \\rfloor})$, where C* is the cost of optimal solution, e is the lower bound on the cost of each action\n\n    - if all action costs are equal, complexity = $O(b^{1+d})$, which is similar to breath-first search\n\n  - breath-first search explores equally in all directions\n\n  - uniform-cost search prioritize which paths to explore\n\n- depth-first search (like a tree-like search, not keep a table of reached, , LIFO frontier)\n\n  - not optimal, incomplete\n\n  - time complexity proportional to the number of states, memory complexity $O(bm)$, where b is the branching factor and m is the maximum depth\n\n  - appropriate when:\n\n    - space is restricted\n\n    - there are many possible solutions with long path, and wrong path are usually terminated quickly\n\n    - search can be fine-tuned quickly \n\n  - **back-tracking search**: use even less memory, only one successor generated at a time, rather than all successors\n\n    - successor generated by modifying the current state, rather than allocating new memory for a brand-new state\n\n    - memory complexity $O(m)$\n\n- **depth-limited search** (tree-like search)\n\n  - time complexity $O(b^l)$ and space complexity $O(bl)$\n\n  - eliminate cycles, but not optimal, incomplete\n\n  - no infinite-path problem\n\n- **literative deepening search**:\n\n  - optimal, and complete\n\n  - memory complexity: $O(bd)$ if there is a solution, or $O(bm)$ if there isn't\n\n  - time complexity: $O(b^d)$ if there is solution, or $O(b^m)$ if there isn't\n\n  - appropriate when:\n\n    - search space is larger than can fit in memory and the depth of the solution is not known\n\n- bidirectional search: search from the initial state and the goal state\n\n  - complete and optimal\n\n  - need 2 frontiers and 2 reached table\n\n  - $O(b^{d/2}+b^{d/2})\n\n\n## Module 3 Lecture Notes\n\n- state is a phyiscal configuration, node is part of the tree\n\n- uninformed: use only information available in the problem definition (all nodes in the frontier look equally the same)\n\n- informed: some nodes might be better than other\n\n\n| criterion | breath-first | uniform-cost | depth-first | depth-limited | iterative deepening | bidirectional |\n| ----------| ------------ | ------------ | ----------- | ------------- | ------------------- | ------------- |\n| complete? | Yes          | Yes          | No          | No            | Yes                 | Yes           |\n| optimal?  | Yes          | Yes          | No          | No            | No                  | Yes           |\n| time      | $O(b^d)$     | $O(b^{1+\\lfloor C^*/e \\rfloor})$| $O(b^m)$ | $O(b^l)$ | $O(b^d)$         | $O(b^{d/2})$  |\n| space     | $O(b^d)$     | $O(b^{1+\\lfloor C^*/e \\rfloor})$| $O(bm)$ | $O(bl)$ | $O(bd)$            | $O(b^{d/2})$  |         \n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** - a sequence of actions\n* **Solution** - path from initial state to the goal state\n* **Optimal solution** - solution with the lowest cost\n* **Frontier** - states that are available for expanding\n* **Completeness** - a complete algorithm must systematically check every state that is reachable from the initial state\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "- **Greedy best-first search**: expands node with the lowest h(n) (i.e. f(n)=h(n))\n",
        "\n",
        "  - not optimal, but complete\n",
        "\n",
        "  - worst case time and space complexity is $O(|V|)$\n",
        "\n",
        "- **A* search**: expands node with the lowest f(n) = g(n) + h(n) (estimated cost of the best path that continues from $n$ to goal)\n",
        "\n",
        "  - complete, and optimal if h(n) is **admissible** (never overestimate the cost to goal, optimistic)\n",
        "\n",
        "    - with an inadmissible heuristic, A* search may or may not be optimal\n",
        "\n",
        "  - **consistent**: $h(n) \\leq c(n,a,n')+h(n') (triangle inequality)\n",
        "\n",
        "    - every consistent heuristic is admissible (but not vice versa)\n",
        "\n",
        "  - A* search is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution\n",
        "\n",
        "- Weighted A* search:  f(n) = g(n) + W*h(n), where W > 1\n",
        "\n",
        "- Algorithm to conserve memory usage:\n",
        "\n",
        "  - beam search: limit the size of frontier, keep k nodes with best f-scores (incomplete and suboptimal)\n",
        "\n",
        "    - or keep nodes within x of the best f-score\n",
        "\n",
        "  - iterative-deepning A* search (IDA*): depth first, no need to reach all states, useful if memory is limited\n",
        "\n",
        "    - search an f-contour, find a node just beyond that contour, and uses that node's f-cost as the next contour\n",
        "\n",
        "  - recursive best-first search (RBFS): keep track of the f-value of the best alternative path, if current node exceeds the limit, the recursion goes back to the alternative path\n",
        "\n",
        "    - space complexity if linear, optimal if h(n) is admissible\n",
        "\n",
        "  - IDA* and RBFS may go to the same states many times\n",
        "\n",
        "  - SMA*: expands the best leaf and deletes the worst leaf (complete)\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "- **manhattan distance**: # of moves from desired location\n",
        "\n",
        "- to describe the quality of a heuristic:\n",
        "\n",
        "  - b* (**effective branching factor**): $N+1 = 1+ b* +(b*)^2+ .. +(b*)^d$, where N is total number of nodes, d is solution depth\n",
        "\n",
        "    - b* closer to 1 is better\n",
        "\n",
        "  - or reducing **effective depth** is better\n",
        "\n",
        "- h2 is always better than h1, than h2 **dominates** h1\n",
        "\n",
        "  - A* using h2 will never expand more nodes than h1\n",
        "\n",
        "- **relaxed problem**: problem with fewer restrictions\n",
        "\n",
        "  - the cost of a relaxed problem is admissible heuristic for the original problem\n",
        "\n",
        "- admissible heuristic can also generate from the cost of **subproblem**\n",
        "\n",
        "  - **pattern database**: store solution cost of every subproblem\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "- inadmissible heuristic break optimality by pushing good plans too far back in the frontier, which means they never get expands\n",
        "\n",
        "- admissible slows down bad plans but never outweighs true cost, that means true best plan always gets expanded\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\": \"uses domain specific knowledge about the goals in order to find solution more efficiently than uninformed one\",\n",
        "\"heuristic function\" : \"estimated cost of the cheapest path from state at node n to a goal state\",    \n",
        "\"bounded suboptimal search\": \"solution guaranteed to be within a constant factor W of the optimal cost\",\n",
        "\"bounded-cost search\": \"solution whose cost is less than C\",\n",
        "\"unbounded-cost search\": \"solution of any cost, find it as soon as possible\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 108,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "a24333b5-78d8-4899-866e-4e3e27d5df54"
      },
      "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": 109,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n- **Greedy best-first search**: expands node with the lowest h(n) (i.e. f(n)=h(n))\n\n  - not optimal, but complete\n\n  - worst case time and space complexity is $O(|V|)$\n\n- **A* search**: expands node with the lowest f(n) = g(n) + h(n) (estimated cost of the best path that continues from $n$ to goal)\n\n  - complete, and optimal if h(n) is **admissible** (never overestimate the cost to goal, optimistic)\n\n    - with an inadmissible heuristic, A* search may or may not be optimal\n\n  - **consistent**: $h(n) \\leq c(n,a,n')+h(n') (triangle inequality)\n\n    - every consistent heuristic is admissible (but not vice versa)\n\n  - A* search is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution\n\n- Weighted A* search:  f(n) = g(n) + W*h(n), where W > 1\n\n- Algorithm to conserve memory usage:\n\n  - beam search: limit the size of frontier, keep k nodes with best f-scores (incomplete and suboptimal)\n\n    - or keep nodes within x of the best f-score\n\n  - iterative-deepning A* search (IDA*): depth first, no need to reach all states, useful if memory is limited\n\n    - search an f-contour, find a node just beyond that contour, and uses that node's f-cost as the next contour\n\n  - recursive best-first search (RBFS): keep track of the f-value of the best alternative path, if current node exceeds the limit, the recursion goes back to the alternative path\n\n    - space complexity if linear, optimal if h(n) is admissible\n\n  - IDA* and RBFS may go to the same states many times\n\n  - SMA*: expands the best leaf and deletes the worst leaf (complete)\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n- **manhattan distance**: # of moves from desired location\n\n- to describe the quality of a heuristic:\n\n  - b* (**effective branching factor**): $N+1 = 1+ b* +(b*)^2+ .. +(b*)^d$, where N is total number of nodes, d is solution depth\n\n    - b* closer to 1 is better\n\n  - or reducing **effective depth** is better\n\n- h2 is always better than h1, than h2 **dominates** h1\n\n  - A* using h2 will never expand more nodes than h1\n\n- **relaxed problem**: problem with fewer restrictions\n\n  - the cost of a relaxed problem is admissible heuristic for the original problem\n\n- admissible heuristic can also generate from the cost of **subproblem**\n\n  - **pattern database**: store solution cost of every subproblem\n\n\n\n## Module 4 Lecture Notes\n\n- inadmissible heuristic break optimality by pushing good plans too far back in the frontier, which means they never get expands\n\n- admissible slows down bad plans but never outweighs true cost, that means true best plan always gets expanded\n\n\n## Module 4 Definitions\n* **Informed search** - uses domain specific knowledge about the goals in order to find solution more efficiently than uninformed one\n* **Heuristic function** - estimated cost of the cheapest path from state at node n to a goal state\n* **Bounded suboptimal search** - solution guaranteed to be within a constant factor W of the optimal cost\n* **Bounded-cost search** - solution whose cost is less than C\n* **Unbounded-cost search** - solution of any cost, find it as soon as possible\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "- The elements of games:\n",
        "\n",
        "  - initial state\n",
        "\n",
        "  - the player whose turn it is to move in state $s$\n",
        "\n",
        "  - the set of legal move in state $s$\n",
        "\n",
        "  - transition model, which defines the state resulting from taking action $a$ in state $s$\n",
        "\n",
        "  - terminal test, which is true if game is over\n",
        "\n",
        "  - utility function, the final numeric value to player $p$ when game ends\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "- *minimax search*:\n",
        "\n",
        "  - complete depth-first exploration\n",
        "\n",
        "  - time complexity: $O(b^m)$, where $m$ is the maximum depth, and $b$ number of legal moves\n",
        "\n",
        "  - space complexity: $O(bm)$ --generate all actions at once, $O(m)$ --generate action one at a time\n",
        "\n",
        "- alpha-beta pruning\n",
        "\n",
        "  - alpha: (at least) the best (highest) value we have found so far for MAX \n",
        "\n",
        "  - beta: (at most) the best (lowest) value we have found so far for MIN\n",
        "\n",
        "  - updates the value of alpha and beta as it goes along and prunes the remaining branches at a node as soon as the value of the current node\\\n",
        "    is known to be worse than the current alpha or beta\n",
        "\n",
        "- the effectiveness of alpha-beta pruning depends on the order in which the states are checked\n",
        "\n",
        "  - if we can try the successors that are likely to be the best, then time complexity would be $O(b^{m/2})$\n",
        "\n",
        "  - **killer move** heuristic: try the best move first\n",
        "\n",
        "  - **transposition**: different permutations of move sequence that end up in the same position\n",
        "\n",
        "- **type A strategy** (chess): consider all possible moves to a certain depth then use heuristic function to estimate the utility of states \\\n",
        "  at that depth (wide but shallow)\n",
        "\n",
        "- **type B strategy** (Go): ingores bad moves and move as far as possible (deep but narrow)  \n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "- to cut of the search early\n",
        "\n",
        "  - replace utility function with *evaluation function*\n",
        "\n",
        "  - replace terminal test with *cutoff test*\n",
        "\n",
        "- evluation function: return an estimate of the expected utility of state $s$ to player $p$\n",
        "\n",
        "  - terminal state: $eval(s,p) = utility(s,p)$\n",
        "\n",
        "  - nonterminal state:  $utility(loss,p) \\leq eval(s,p) \\leq utility(win,p)$\n",
        "\n",
        "- based on the static features of the board\n",
        "\n",
        "  - **expected value**: probability times values\n",
        "\n",
        "  - **weighted linear function**: weights times feature values\n",
        "\n",
        "    - assuming features are independent\n",
        "\n",
        "- cutoff test:\n",
        "\n",
        "  - set a fixed depth limit, test returns true if depth exceeds the limit\n",
        "\n",
        "  - apply iterative deepening\n",
        "\n",
        "  - may lead to errors\n",
        "  \n",
        "    - evaluation function can only apply when the position is **quiescent**: no pending move would widely swing the evaluation\n",
        "\n",
        "    - for non-quiescent positions, cutoff test returns false => **quiescent search**\n",
        "\n",
        "  - **horizon effect**: use delaying tactics in face of opponent's unavoidable damaging move\n",
        "\n",
        "    - **singular extension**: allow moves that are \"clearly better\" even the search would normally be cutoff at that point\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "- **stochastic games**: bring unpreditablity by introducign a random event (rolling a dice)\n",
        "\n",
        "  - backgammon: a stochastic game combined both luck and skill\n",
        "\n",
        "    - tree has chance nodes in addition to MAX, MIN nodes\n",
        "\n",
        "    - needs to calculate the **expected value** of a position\n",
        "\n",
        "- **expectiminimax values**: MAX, MIN, expected value for chance. ($O(b^mn^m), $b$ is branching factor, $m$ is maximum depth, and $n$ is distict number of rolls)\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "- $P(result(a)=s') = \\\\sum_s P(s)P(s'|s,a)$\n",
        "\n",
        "- $EU(a)=\\\\sum_{s'}P(result(a)=s')$\n",
        "\n",
        "- $action = \\\\argmax_a EU(a)$\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"fully observation\",\n",
        "\"zero-sum\": \"what is good for one player is bad for the other\",  \n",
        "\"foward-pruning\": \"prune moves that look bad but are actually good\",\n",
        "\"beam search (foward-pruning)\": \"consider only n best moves rather than all on each ply\",\n",
        "\"last move reduction (foward-pruning)\": \"with well ordering of moves, moves appear last are less likely to be good\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 110,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6c7b9cd1-cc8d-46a1-93ad-e4cf3c46732a"
      },
      "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": 111,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n- The elements of games:\n\n  - initial state\n\n  - the player whose turn it is to move in state $s$\n\n  - the set of legal move in state $s$\n\n  - transition model, which defines the state resulting from taking action $a$ in state $s$\n\n  - terminal test, which is true if game is over\n\n  - utility function, the final numeric value to player $p$ when game ends\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n- *minimax search*:\n\n  - complete depth-first exploration\n\n  - time complexity: $O(b^m)$, where $m$ is the maximum depth, and $b$ number of legal moves\n\n  - space complexity: $O(bm)$ --generate all actions at once, $O(m)$ --generate action one at a time\n\n- alpha-beta pruning\n\n  - alpha: (at least) the best (highest) value we have found so far for MAX \n\n  - beta: (at most) the best (lowest) value we have found so far for MIN\n\n  - updates the value of alpha and beta as it goes along and prunes the remaining branches at a node as soon as the value of the current node    is known to be worse than the current alpha or beta\n\n- the effectiveness of alpha-beta pruning depends on the order in which the states are checked\n\n  - if we can try the successors that are likely to be the best, then time complexity would be $O(b^{m/2})$\n\n  - **killer move** heuristic: try the best move first\n\n  - **transposition**: different permutations of move sequence that end up in the same position\n\n- **type A strategy** (chess): consider all possible moves to a certain depth then use heuristic function to estimate the utility of states   at that depth (wide but shallow)\n\n- **type B strategy** (Go): ingores bad moves and move as far as possible (deep but narrow)  \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n- to cut of the search early\n\n  - replace utility function with *evaluation function*\n\n  - replace terminal test with *cutoff test*\n\n- evluation function: return an estimate of the expected utility of state $s$ to player $p$\n\n  - terminal state: $eval(s,p) = utility(s,p)$\n\n  - nonterminal state:  $utility(loss,p) \\leq eval(s,p) \\leq utility(win,p)$\n\n- based on the static features of the board\n\n  - **expected value**: probability times values\n\n  - **weighted linear function**: weights times feature values\n\n    - assuming features are independent\n\n- cutoff test:\n\n  - set a fixed depth limit, test returns true if depth exceeds the limit\n\n  - apply iterative deepening\n\n  - may lead to errors\n  \n    - evaluation function can only apply when the position is **quiescent**: no pending move would widely swing the evaluation\n\n    - for non-quiescent positions, cutoff test returns false => **quiescent search**\n\n  - **horizon effect**: use delaying tactics in face of opponent's unavoidable damaging move\n\n    - **singular extension**: allow moves that are \"clearly better\" even the search would normally be cutoff at that point\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n- **stochastic games**: bring unpreditablity by introducign a random event (rolling a dice)\n\n  - backgammon: a stochastic game combined both luck and skill\n\n    - tree has chance nodes in addition to MAX, MIN nodes\n\n    - needs to calculate the **expected value** of a position\n\n- **expectiminimax values**: MAX, MIN, expected value for chance. ($O(b^mn^m), $b$ is branching factor, $m$ is maximum depth, and $n$ is distict number of rolls)\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n- $P(result(a)=s') = \\sum_s P(s)P(s'|s,a)$\n\n- $EU(a)=\\sum_{s'}P(result(a)=s')$\n\n- $action = \\argmax_a EU(a)$\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Perfect information** - fully observation\n* **Zero-sum** - what is good for one player is bad for the other\n* **Foward-pruning** - prune moves that look bad but are actually good\n* **Beam search (foward-pruning)** - consider only n best moves rather than all on each ply\n* **Last move reduction (foward-pruning)** - with well ordering of moves, moves appear last are less likely to be good\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "- A CSP consists of X (set of variables), D (set of domain, one for each variable), C (set of constraints that specify allowable combinations of values)\n",
        "\n",
        "  - C = (scope, rel), where scope is tuple of variables in the constraints, rel is a **relation** that defines the values these variables can take\n",
        "\n",
        "  - CSP deals with **assignment** of values to variables\n",
        "\n",
        "- **consistent**: assignment doesn't violate constraints\n",
        "\n",
        "- **complete assignment**: every variable is assigned a value\n",
        "\n",
        "  - **solution**: a consistent and complete assignment\n",
        "\n",
        "- **partial assignment**: some variables are unassigned\n",
        "\n",
        "  - **partial solution**: partial assignment that is consistent\n",
        "\n",
        "- solution to CSPs can be found by a **general purpose algorithm**\n",
        "\n",
        "- **constraint graph**: nodes = variables, edges = connect any two variables in a constraint (binary CSP with unary and binary constraints)\n",
        "\n",
        "- benefits of CSP:\n",
        "\n",
        "  - easy to formulate a problem as CSP\n",
        "\n",
        "  - CSP solvers are fast and efficient\n",
        "\n",
        "  - CSP prune off the branches that violate the constraints\n",
        "\n",
        "- variations of CSP:\n",
        "\n",
        "  - domains:\n",
        "  \n",
        "    - discrete, finite domains (map-coloring, scheduling, 8-queens)\n",
        "\n",
        "    - discrete, infinite domains (set of strings or integers)\n",
        "\n",
        "    - continuous domains (linear programming problems)\n",
        "\n",
        "  - constraints:\n",
        "\n",
        "    - unary constraint: restricts the value of a single variable\n",
        "\n",
        "    - binary constraint: relates two variables\n",
        "\n",
        "    - **global constraint**: involves arbitrary number of variables (Sudoku, cryptarithmetic)\n",
        "\n",
        "      - **constraint hypergraph**: ordinary nodes = variables, hypernodes = n-ary constraints\n",
        "\n",
        "    - preference constraint: indicate which solution is preferred (encoded as cost => **constrained optimization problem** (COP))\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "- **local consistency**: the process of enforcing local consistency can eliminate inconsistent values throughout the graph\n",
        "\n",
        "  - **node consistency**: a variable is node consistent, if all values in the domain satisfy variable's unary constraints\n",
        "\n",
        "  - **arc consistency**: if all values in the domain satify variable's binary constraints\n",
        "\n",
        "    - $X_i$ is arc-consistent with respect to $X_j$ if for every value in domain $D_i$, there is some value in $D_j$ that satisfies the binary constraints\\\n",
        "      on $arc(X_i, X_j)$\n",
        "\n",
        "    - a graph is arc-consistent if every variable is arc-consistent with every other variable\n",
        "\n",
        "  - **path consistency**: ${X_i, X_j}$ is path-consistent with respect to $X_m$ if, for every assignment of ${X_i, X_j}$ pair with constraints on ${X_i, X_j}$,\\\n",
        "    there is an assignment to $X_m$ that satisfies constraints on ${X_i, X_m}$ and ${X_m, X_j}$\n",
        "\n",
        "- AC-3: enforcing arc consistency ($n$ variables, $d$ domain size, $c$ constraints, checking consistency for each arc is $O(d^2)$, total worst-case is $O(n^2d^3)$)\n",
        "\n",
        "  - queue: contains all arc in CSP\n",
        "\n",
        "  - pop off arbitrary $arc(X_i, X_j)$, and makes $X_i$ arc-consistent with $X_j$\n",
        "\n",
        "    - if $D_i$ unchanged, move to next arc\n",
        "\n",
        "    - else, add all $arc(X_k, X_i)$ to the queue, where $X_k$ is a neighbor of $X_i$\n",
        "\n",
        "      - if $D_k$ is revised down to nothing, then CSP has no consistent solution => return failure\n",
        "\n",
        "      - else, keep checking until queue is empty\n",
        "\n",
        "- **k-consistency**: for any set of $k-1$ variables and for any consistent assignment assigned to these variables, a consistent value can always be assigned\\\n",
        "  to any $kth$ variable\n",
        "\n",
        "  - **strongly k-consistent$: if it is k-consistent, and (k-1)-consistent, ... to 1-consistent\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "- backtrack search: depth-first search for CSPs with single-value assignment\n",
        "\n",
        "  - choose values for one valuable at a time and backtrack when a variable has no legal values left to assign\n",
        "\n",
        "  - branching factor at root: $n*d$, branching factor at the next level: $(n-1)*d$\n",
        "\n",
        "  - tree has $(n!*d^n)$ leaves => **commucative** => ($d^n$) leaves\n",
        "  \n",
        "  - this is **chronological backtracking** because the most recent decision point is revisited\n",
        "\n",
        "- improvement with domain-specific heuristics:\n",
        "\n",
        "  - **minimum-remaining-values** heuristic (MRV, the order in which variables are examined -- fail first): choose the next variable with fewest \"legal\" values (the most constrained variable)\n",
        "\n",
        "  - **degree** heuristic (reduce branching factor, first variable to choose): select the variable that has the largest number of constraints on other variables (most constraining variable)\n",
        "\n",
        "  - **least-constraining-value** heuristic (the order in which values are examined, given a variable -- fail last): choose the one ruling out the fewest choices for the neighboring\\\n",
        "    variables in the constraint graph\n",
        "\n",
        "- inference -- **forward checking**\n",
        "\n",
        "  - for each unassigned variable Y that is connected to X by a constraint, delete from Y's domain any value inconsistent with the one chosen for X\n",
        "\n",
        "- stronger inference -- **Maintaining Arc Constraint (MAC)**\n",
        "\n",
        "  - inference call AC-3, and start with only X's neighbors\n",
        "\n",
        "- conflict set: a set of assignments that are in conflict with some value of a variable\n",
        "\n",
        "  - **backjumping**: backtracks to the most recent assignment in the conflict set\n",
        "\n",
        "  - **conflict-direct backjumping**: \n",
        "  \n",
        "    - conflict set is the set of preceding variables that cause a group of variables to have no consistent solution\n",
        "\n",
        "    - backjump to the most recent variable in the conflict set, and recompute the conflict set of this variable\n",
        "\n",
        "- constraint learning: finding a minimum set of variables (**no-good**) from the conflict set that causes the failure\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "- local search use a complete-state formulation, each state assigns a value to each variable, and the search changes a variable at a time\n",
        "\n",
        "- **min conflict**: select the value that results in the minimum number of conflicts with other variables\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "- decompose large problem into subproblems (reduce time complexity)\n",
        "\n",
        "  - **independent subproblems**\n",
        "\n",
        "- any tree-structured CSP can be solved in time linear in the number of variables\n",
        "\n",
        "  - just march down the directed arc-consistent graph, and choose any remaining value\n",
        "\n",
        "- cutset conditioning: $O(d^c*(n-c)d^2)$\n",
        "\n",
        "- tree decomposition: $O(nd^{w+1})$, efficient if tree-width is small\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint propogation\" : \"use constraints to reduce the legal values for a variable, then reduce those for another variable\",   \n",
        "\"commucative\": \"the problem is commucative if the order of applications of set of actions does not matter\",\n",
        "\"directional arc consistent\": \"tree CSP in the ordering of $X_i$, $X_2$, .., $X_n$, and every $X_i$ is arc-consistent with each $X_j$ for $j>i$\",\n",
        "\"topology sort\": \"pick root first, then choose the orderings of variables such that each variable appears after its parent\"\n",
        "}\n"
      ],
      "execution_count": 112,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "19f6324c-1798-4539-8878-82246b337276"
      },
      "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": 113,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n- A CSP consists of X (set of variables), D (set of domain, one for each variable), C (set of constraints that specify allowable combinations of values)\n\n  - C = (scope, rel), where scope is tuple of variables in the constraints, rel is a **relation** that defines the values these variables can take\n\n  - CSP deals with **assignment** of values to variables\n\n- **consistent**: assignment doesn't violate constraints\n\n- **complete assignment**: every variable is assigned a value\n\n  - **solution**: a consistent and complete assignment\n\n- **partial assignment**: some variables are unassigned\n\n  - **partial solution**: partial assignment that is consistent\n\n- solution to CSPs can be found by a **general purpose algorithm**\n\n- **constraint graph**: nodes = variables, edges = connect any two variables in a constraint (binary CSP with unary and binary constraints)\n\n- benefits of CSP:\n\n  - easy to formulate a problem as CSP\n\n  - CSP solvers are fast and efficient\n\n  - CSP prune off the branches that violate the constraints\n\n- variations of CSP:\n\n  - domains:\n  \n    - discrete, finite domains (map-coloring, scheduling, 8-queens)\n\n    - discrete, infinite domains (set of strings or integers)\n\n    - continuous domains (linear programming problems)\n\n  - constraints:\n\n    - unary constraint: restricts the value of a single variable\n\n    - binary constraint: relates two variables\n\n    - **global constraint**: involves arbitrary number of variables (Sudoku, cryptarithmetic)\n\n      - **constraint hypergraph**: ordinary nodes = variables, hypernodes = n-ary constraints\n\n    - preference constraint: indicate which solution is preferred (encoded as cost => **constrained optimization problem** (COP))\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- **local consistency**: the process of enforcing local consistency can eliminate inconsistent values throughout the graph\n\n  - **node consistency**: a variable is node consistent, if all values in the domain satisfy variable's unary constraints\n\n  - **arc consistency**: if all values in the domain satify variable's binary constraints\n\n    - $X_i$ is arc-consistent with respect to $X_j$ if for every value in domain $D_i$, there is some value in $D_j$ that satisfies the binary constraints      on $arc(X_i, X_j)$\n\n    - a graph is arc-consistent if every variable is arc-consistent with every other variable\n\n  - **path consistency**: ${X_i, X_j}$ is path-consistent with respect to $X_m$ if, for every assignment of ${X_i, X_j}$ pair with constraints on ${X_i, X_j}$,    there is an assignment to $X_m$ that satisfies constraints on ${X_i, X_m}$ and ${X_m, X_j}$\n\n- AC-3: enforcing arc consistency ($n$ variables, $d$ domain size, $c$ constraints, checking consistency for each arc is $O(d^2)$, total worst-case is $O(n^2d^3)$)\n\n  - queue: contains all arc in CSP\n\n  - pop off arbitrary $arc(X_i, X_j)$, and makes $X_i$ arc-consistent with $X_j$\n\n    - if $D_i$ unchanged, move to next arc\n\n    - else, add all $arc(X_k, X_i)$ to the queue, where $X_k$ is a neighbor of $X_i$\n\n      - if $D_k$ is revised down to nothing, then CSP has no consistent solution => return failure\n\n      - else, keep checking until queue is empty\n\n- **k-consistency**: for any set of $k-1$ variables and for any consistent assignment assigned to these variables, a consistent value can always be assigned  to any $kth$ variable\n\n  - **strongly k-consistent$: if it is k-consistent, and (k-1)-consistent, ... to 1-consistent\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n- backtrack search: depth-first search for CSPs with single-value assignment\n\n  - choose values for one valuable at a time and backtrack when a variable has no legal values left to assign\n\n  - branching factor at root: $n*d$, branching factor at the next level: $(n-1)*d$\n\n  - tree has $(n!*d^n)$ leaves => **commucative** => ($d^n$) leaves\n  \n  - this is **chronological backtracking** because the most recent decision point is revisited\n\n- improvement with domain-specific heuristics:\n\n  - **minimum-remaining-values** heuristic (MRV, the order in which variables are examined -- fail first): choose the next variable with fewest \"legal\" values (the most constrained variable)\n\n  - **degree** heuristic (reduce branching factor, first variable to choose): select the variable that has the largest number of constraints on other variables (most constraining variable)\n\n  - **least-constraining-value** heuristic (the order in which values are examined, given a variable -- fail last): choose the one ruling out the fewest choices for the neighboring    variables in the constraint graph\n\n- inference -- **forward checking**\n\n  - for each unassigned variable Y that is connected to X by a constraint, delete from Y's domain any value inconsistent with the one chosen for X\n\n- stronger inference -- **Maintaining Arc Constraint (MAC)**\n\n  - inference call AC-3, and start with only X's neighbors\n\n- conflict set: a set of assignments that are in conflict with some value of a variable\n\n  - **backjumping**: backtracks to the most recent assignment in the conflict set\n\n  - **conflict-direct backjumping**: \n  \n    - conflict set is the set of preceding variables that cause a group of variables to have no consistent solution\n\n    - backjump to the most recent variable in the conflict set, and recompute the conflict set of this variable\n\n- constraint learning: finding a minimum set of variables (**no-good**) from the conflict set that causes the failure\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n- local search use a complete-state formulation, each state assigns a value to each variable, and the search changes a variable at a time\n\n- **min conflict**: select the value that results in the minimum number of conflicts with other variables\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- decompose large problem into subproblems (reduce time complexity)\n\n  - **independent subproblems**\n\n- any tree-structured CSP can be solved in time linear in the number of variables\n\n  - just march down the directed arc-consistent graph, and choose any remaining value\n\n- cutset conditioning: $O(d^c*(n-c)d^2)$\n\n- tree decomposition: $O(nd^{w+1})$, efficient if tree-width is small\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Constraint propogation** - use constraints to reduce the legal values for a variable, then reduce those for another variable\n* **Commucative** - the problem is commucative if the order of applications of set of actions does not matter\n* **Directional arc consistent** - tree CSP in the ordering of $X_i$, $X_2$, .., $X_n$, and every $X_i$ is arc-consistent with each $X_j$ for $j>i$\n* **Topology sort** - pick root first, then choose the orderings of variables such that each variable appears after its parent\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "- A KB contains some **background information** about the world\n",
        "\n",
        "  - a knowledge-based agent can add info to KB through its observations through the world (TELL)\\\n",
        "\n",
        "  - the agent can also query the KB and ask it to derive new knowledge about what actions to take (ASK)\\\n",
        "\n",
        "  - then the agent (TELL) the KB which action was chosen, so that it can be executed\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "- Wampa world (deterministic, discrete, static, single-agent, sequential, partially observable)\n",
        "\n",
        "  - contains a cave consisting of rooms, wampa, pits, and Luke (gold)\n",
        "\n",
        "    - environment: 4x4, start in the sqaure [1.1]\n",
        "\n",
        "    - performance measure: +1000 for securing Luke and leaving, -1000 for falling into a pit or eaten by wampa, etc\n",
        "\n",
        "    - actuators: Forward, TurnLeft, TurnRight, Grab (pick up Luke), Shoot, Climb (out of the cave, works in [1,1])\n",
        "\n",
        "    - sensors: Stench (adjacent to Wampa), Breeze (adjacent to a pit), Gasp (in sqaure with Luke), Bump (walk into wall), Scream (Wampa is killed)\n",
        "\n",
        "  - in each step, the agent draw conclusion from the available info\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "- in logics, every sentence (has syntax and semantic) has to be either true or false (**truth**) in each possible world (**model**)\n",
        "\n",
        "- if a sentence $\\\\alpha$ is true in model $m$, then $m$ satisfies $\\\\alpha$, or $m$ is a model of $\\\\alpha$\n",
        "\n",
        "  - $M(\\\\alpha)$ := set of all models of $\\\\alpha$\n",
        "\n",
        "- **entailment**: a sentence logically follow from another sentence\n",
        "\n",
        "  - $\\\\alpha$ entails $\\\\beta$, iff in every model in which $\\\\alpha$ is true, then $\\\\beta$ is true\n",
        "\n",
        "  - $\\\\alpha \\\\models \\\\beta$ iff $M(\\\\alpha) \\\\subseteq M(\\\\beta)$\n",
        "\n",
        "    - alpha is a stronger assertion, rules out more possible world\n",
        "\n",
        "- **logical inference**: entailment can be applied to derive conclusions\n",
        "\n",
        "  - $KB \\\\vdash_i \\\\alpha$, an inference alogrithm $i$ derived $\\\\alpha$ from $KB$, or $\\\\alpha$ is derived from $KB$ by $i$\n",
        "\n",
        "  - **sound** (true-preserving): an inference algorithm that derives only entailed sentences\n",
        "\n",
        "  - **complete**: an inference algorithm that can derive any sentence that is entailed\n",
        "\n",
        "- if KB is true in real world, then any sentence derived from KB by a sound inference algorithm is also true in real world\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "- **atomic sentences**: consist of a single proposition symbol (that can be true or false)\n",
        "\n",
        "- **complex sentences**: constructed from simpler sentences, with parentheses and **logical connectives** (not, and, or, implies, iff) \n",
        "\n",
        "- a model simply sets the truth value for each proposition\n",
        "\n",
        "  - $\\\\neg P$ is true, iff $P$ is false in $m$\n",
        "\n",
        "  - $P\\\\land Q$ is true, iff both $P$ and $Q$ is true in $m$\n",
        "\n",
        "  - $P\\\\lor Q$ is true, iff either $P$ or $Q$ is true in $m$\n",
        "\n",
        "  - $P\\\\implies Q$ is true unless $P$ is true and $Q$ is false in $m$\n",
        "\n",
        "  - $P\\\\iff Q$ is true iff both $P$ and $Q$ is true or both false in $m$\n",
        "\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "- **logical equivalence**: two sentences are logically equivalent if they are true in the same set of models\n",
        "\n",
        "  - $\\\\alpha \\\\equiv \\\\beta$ iff $\\\\alpha \\\\models \\\\beta$ and $\\\\beta \\\\models \\\\alpha$\n",
        "\n",
        "- **validity**: a sentence is valid (=**tautology**) if it is true in all models\n",
        "\n",
        "- **satisfiability**: a sentence is satisfiable if it is true in some models\n",
        "\n",
        "  - $\\\\alpha$ is valid iff $\\\\neg\\\\alpha$ is unsatisfiable\n",
        "\n",
        "  - $\\\\alpha$ is satisfiable iff $\\\\neg\\\\alpha$ is not valid\n",
        "\n",
        "  - $\\\\alpha \\\\models \\\\beta$ iff ($\\\\alpha \\\\land \\\\neg \\\\beta$) is unsatisfiable (proof by contradiction)\n",
        "\n",
        "- **monotonicity**: the set of entailed sentences can only increase as info is added to the knowledge base\n",
        "\n",
        "  - if we add additional info to the KB, it doesn't invalidate any other info that we've already inferred\n",
        "\n",
        "- **resolution**\n",
        "\n",
        "- **factoring**: remove multiple copies of literals\n",
        "\n",
        "- **conjunctive normal form**: conjunction of clauses (disjunctions of literals) ($(P\\\\lor Q) \\\\land (R\\\\lor S))\n",
        "\n",
        "- KB with only **definite clauses**:\n",
        "\n",
        "  - $\\\\neg P \\\\lor \\\\neg Q \\\\lor R \\\\equiv (P \\\\land Q) \\\\implies R$\n",
        "\n",
        "  - inference can be done by forward-chaining and backward-chaining\n",
        "\n",
        "  - deciding entailment can be done in linear time with respect to the size of KB\n",
        "\n",
        "- **forward chaining** (data-driven reasoning): start with premises\n",
        "\n",
        "- **backward chaining** (goal-directed reasoning): start with conclusion, find implication\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "- standard logical equivalence\n",
        "\n",
        "  - $\\\\alpha \\\\land \\\\beta \\\\equiv \\\\beta \\\\land \\\\alpha$, commutativtiy of $\\\\land$\n",
        "\n",
        "  - $\\\\alpha \\\\lor \\\\beta \\\\equiv \\\\beta \\\\lor \\\\alpha$, commutativtiy of $\\\\lor$\n",
        "\n",
        "  - $(\\\\alpha \\\\land \\\\beta) \\\\land \\\\gamma \\\\equiv \\\\alpha \\\\land (\\\\beta \\\\land \\\\gamma)$, associativity of $\\\\land$\n",
        "\n",
        "  - $(\\\\alpha \\\\lor \\\\beta) \\\\lor \\\\gamma \\\\equiv \\\\alpha \\\\lor (\\\\beta \\\\lor \\\\gamma)$, associativity of $\\\\lor$\n",
        "\n",
        "  - $\\\\neg(\\\\neg \\\\alpha) \\\\equiv \\\\alpha$, double-negative elimination\n",
        "\n",
        "  - $\\\\alpha \\\\implies \\\\beta \\\\equiv \\\\neg \\\\beta \\\\implies \\\\neg \\\\alpha$, contraposition\n",
        "\n",
        "  - $\\\\alpha \\\\implies \\\\beta \\\\equiv \\\\neg \\\\alpha \\\\lor \\\\beta$, implication elimination\n",
        "\n",
        "  - $\\\\alpha \\\\iff \\\\beta \\\\equiv (\\\\alpha\\\\implies\\\\beta)\\\\land(\\\\beta\\\\implies\\\\alpha)$, biconditional elimination\n",
        "\n",
        "  - $\\\\neg(\\\\alpha\\\\lor\\\\beta) \\\\equiv \\\\neg\\\\alpha\\\\land\\\\neg\\\\beta$, De Morgan\n",
        "\n",
        "  - $\\\\neg(\\\\alpha\\\\land\\\\beta) \\\\equiv \\\\neg\\\\alpha\\\\lor\\\\neg\\\\beta$, De Morgan\n",
        "\n",
        "  - $(\\\\alpha \\\\land \\\\beta) \\\\lor \\\\gamma \\\\equiv (\\\\alpha \\\\lor \\\\gamma) \\\\land (\\\\beta \\\\lor \\\\gamma)$, distributivity of $\\\\lor$ over $\\\\land$\n",
        "\n",
        "  - $(\\\\alpha \\\\lor \\\\beta) \\\\land \\\\gamma \\\\equiv (\\\\alpha \\\\land \\\\gamma) \\\\lor (\\\\beta \\\\land \\\\gamma)$, distributivity of $\\\\land$ over $\\\\lor$\n",
        "\n",
        "- inference rules\n",
        "\n",
        "  - $(\\\\alpha\\\\implies\\\\beta, \\\\alpha)/\\\\beta$, Modus Ponens\n",
        "\n",
        "  - $(\\\\alpha \\\\land \\\\beta)/\\\\beta$, and-elimination\n",
        "\n",
        "- resolution\n",
        "\n",
        "  - $(l_1\\\\lor .. \\\\lor l_k, m)/l_1\\\\lor .. \\\\lor l_{i-1}\\\\lor l_{i+1} \\\\lor .. \\\\lor l_k$, unit resolution, where $l_i$ and $m$ are conplementary\n",
        "\n",
        "  -  $(l_1\\\\lor .. \\\\lor l_k, m_1\\\\lor .. \\\\lor m_n)/l_1\\\\lor .. \\\\lor l_{i-1}\\\\lor l_{i+1} \\\\lor .. \\\\lor l_k \\\\lor m_1\\\\lor .. \\\\lor m_{j-1}\\\\lor m_{j+1} \\\\lor .. \\\\lor m_n$,\\\n",
        "     full resolution, where $l_i$ and $m_j$ are conplementary\n",
        "\n",
        "  - can only resolve one pair at a time\n",
        "\n",
        "- resolution algorithm, complete (contradiction, to show $KB\\\\models \\\\alpha$, show $KB\\\\land \\\\alpha$ is unsatisfiable)\n",
        "\n",
        "  - convert $KB\\\\land \\\\alpha$ into CNF\n",
        "\n",
        "  - apply resolution rule to the resulting clauses\n",
        "\n",
        "  - if new clause isn't already present, add it to the set\n",
        "\n",
        "  - continue until one of two things happens:\n",
        "\n",
        "    - there are no new clauses that can be added, then KB does not entail $\\\\alpha$\n",
        "\n",
        "    - two caluses resolve to yield empty clause (they are conplementary), KB entails $\\\\alpha$ \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agent\" : \"use reasoning over a representation of knowledge to decide what action to take\",\n",
        "\"knowledge base (KB)\": \"set of sentences, each sentence is expressed in a knowledge representation language and represents some assertions about the world\",\n",
        "\"axiom\": \"given without being derived from other sentences\",\n",
        "\"inference\": \"derive new sentences from the old\",\n",
        "\"logic\": \"a general class of representations\",\n",
        "\"model checking\": \"enumerate models and show a sentence must hold in all models\",\n",
        "\"theorem proving\": \"apply rules of inference directly to sentences to construct proof without consulting models\",\n",
        "\"definite clause\": \"disjunction of literals of which exactly one is positive\",\n",
        "\"Horn clause1\": \"disjunction of literals of which at most one is positive, which is closed under resolution\",\n",
        "\"Horn clause2\": \"(if you resolve two Horn clause, you get a Horn clause)\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 114,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ec9b29a8-61ca-4afb-bc5b-c804657f2310"
      },
      "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": 115,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n- A KB contains some **background information** about the world\n\n  - a knowledge-based agent can add info to KB through its observations through the world (TELL)\n  - the agent can also query the KB and ask it to derive new knowledge about what actions to take (ASK)\n  - then the agent (TELL) the KB which action was chosen, so that it can be executed\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n- Wampa world (deterministic, discrete, static, single-agent, sequential, partially observable)\n\n  - contains a cave consisting of rooms, wampa, pits, and Luke (gold)\n\n    - environment: 4x4, start in the sqaure [1.1]\n\n    - performance measure: +1000 for securing Luke and leaving, -1000 for falling into a pit or eaten by wampa, etc\n\n    - actuators: Forward, TurnLeft, TurnRight, Grab (pick up Luke), Shoot, Climb (out of the cave, works in [1,1])\n\n    - sensors: Stench (adjacent to Wampa), Breeze (adjacent to a pit), Gasp (in sqaure with Luke), Bump (walk into wall), Scream (Wampa is killed)\n\n  - in each step, the agent draw conclusion from the available info\n\n\n## AIMA Chapter 7.3 Logic\n\n- in logics, every sentence (has syntax and semantic) has to be either true or false (**truth**) in each possible world (**model**)\n\n- if a sentence $\\alpha$ is true in model $m$, then $m$ satisfies $\\alpha$, or $m$ is a model of $\\alpha$\n\n  - $M(\\alpha)$ := set of all models of $\\alpha$\n\n- **entailment**: a sentence logically follow from another sentence\n\n  - $\\alpha$ entails $\\beta$, iff in every model in which $\\alpha$ is true, then $\\beta$ is true\n\n  - $\\alpha \\models \\beta$ iff $M(\\alpha) \\subseteq M(\\beta)$\n\n    - alpha is a stronger assertion, rules out more possible world\n\n- **logical inference**: entailment can be applied to derive conclusions\n\n  - $KB \\vdash_i \\alpha$, an inference alogrithm $i$ derived $\\alpha$ from $KB$, or $\\alpha$ is derived from $KB$ by $i$\n\n  - **sound** (true-preserving): an inference algorithm that derives only entailed sentences\n\n  - **complete**: an inference algorithm that can derive any sentence that is entailed\n\n- if KB is true in real world, then any sentence derived from KB by a sound inference algorithm is also true in real world\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n- **atomic sentences**: consist of a single proposition symbol (that can be true or false)\n\n- **complex sentences**: constructed from simpler sentences, with parentheses and **logical connectives** (not, and, or, implies, iff) \n\n- a model simply sets the truth value for each proposition\n\n  - $\\neg P$ is true, iff $P$ is false in $m$\n\n  - $P\\land Q$ is true, iff both $P$ and $Q$ is true in $m$\n\n  - $P\\lor Q$ is true, iff either $P$ or $Q$ is true in $m$\n\n  - $P\\implies Q$ is true unless $P$ is true and $Q$ is false in $m$\n\n  - $P\\iff Q$ is true iff both $P$ and $Q$ is true or both false in $m$\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n- **logical equivalence**: two sentences are logically equivalent if they are true in the same set of models\n\n  - $\\alpha \\equiv \\beta$ iff $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$\n\n- **validity**: a sentence is valid (=**tautology**) if it is true in all models\n\n- **satisfiability**: a sentence is satisfiable if it is true in some models\n\n  - $\\alpha$ is valid iff $\\neg\\alpha$ is unsatisfiable\n\n  - $\\alpha$ is satisfiable iff $\\neg\\alpha$ is not valid\n\n  - $\\alpha \\models \\beta$ iff ($\\alpha \\land \\neg \\beta$) is unsatisfiable (proof by contradiction)\n\n- **monotonicity**: the set of entailed sentences can only increase as info is added to the knowledge base\n\n  - if we add additional info to the KB, it doesn't invalidate any other info that we've already inferred\n\n- **resolution**\n\n- **factoring**: remove multiple copies of literals\n\n- **conjunctive normal form**: conjunction of clauses (disjunctions of literals) ($(P\\lor Q) \\land (R\\lor S))\n\n- KB with only **definite clauses**:\n\n  - $\\neg P \\lor \\neg Q \\lor R \\equiv (P \\land Q) \\implies R$\n\n  - inference can be done by forward-chaining and backward-chaining\n\n  - deciding entailment can be done in linear time with respect to the size of KB\n\n- **forward chaining** (data-driven reasoning): start with premises\n\n- **backward chaining** (goal-directed reasoning): start with conclusion, find implication\n\n\n\n## Module 7 Lecture Notes\n\n- standard logical equivalence\n\n  - $\\alpha \\land \\beta \\equiv \\beta \\land \\alpha$, commutativtiy of $\\land$\n\n  - $\\alpha \\lor \\beta \\equiv \\beta \\lor \\alpha$, commutativtiy of $\\lor$\n\n  - $(\\alpha \\land \\beta) \\land \\gamma \\equiv \\alpha \\land (\\beta \\land \\gamma)$, associativity of $\\land$\n\n  - $(\\alpha \\lor \\beta) \\lor \\gamma \\equiv \\alpha \\lor (\\beta \\lor \\gamma)$, associativity of $\\lor$\n\n  - $\\neg(\\neg \\alpha) \\equiv \\alpha$, double-negative elimination\n\n  - $\\alpha \\implies \\beta \\equiv \\neg \\beta \\implies \\neg \\alpha$, contraposition\n\n  - $\\alpha \\implies \\beta \\equiv \\neg \\alpha \\lor \\beta$, implication elimination\n\n  - $\\alpha \\iff \\beta \\equiv (\\alpha\\implies\\beta)\\land(\\beta\\implies\\alpha)$, biconditional elimination\n\n  - $\\neg(\\alpha\\lor\\beta) \\equiv \\neg\\alpha\\land\\neg\\beta$, De Morgan\n\n  - $\\neg(\\alpha\\land\\beta) \\equiv \\neg\\alpha\\lor\\neg\\beta$, De Morgan\n\n  - $(\\alpha \\land \\beta) \\lor \\gamma \\equiv (\\alpha \\lor \\gamma) \\land (\\beta \\lor \\gamma)$, distributivity of $\\lor$ over $\\land$\n\n  - $(\\alpha \\lor \\beta) \\land \\gamma \\equiv (\\alpha \\land \\gamma) \\lor (\\beta \\land \\gamma)$, distributivity of $\\land$ over $\\lor$\n\n- inference rules\n\n  - $(\\alpha\\implies\\beta, \\alpha)/\\beta$, Modus Ponens\n\n  - $(\\alpha \\land \\beta)/\\beta$, and-elimination\n\n- resolution\n\n  - $(l_1\\lor .. \\lor l_k, m)/l_1\\lor .. \\lor l_{i-1}\\lor l_{i+1} \\lor .. \\lor l_k$, unit resolution, where $l_i$ and $m$ are conplementary\n\n  -  $(l_1\\lor .. \\lor l_k, m_1\\lor .. \\lor m_n)/l_1\\lor .. \\lor l_{i-1}\\lor l_{i+1} \\lor .. \\lor l_k \\lor m_1\\lor .. \\lor m_{j-1}\\lor m_{j+1} \\lor .. \\lor m_n$,     full resolution, where $l_i$ and $m_j$ are conplementary\n\n  - can only resolve one pair at a time\n\n- resolution algorithm, complete (contradiction, to show $KB\\models \\alpha$, show $KB\\land \\alpha$ is unsatisfiable)\n\n  - convert $KB\\land \\alpha$ into CNF\n\n  - apply resolution rule to the resulting clauses\n\n  - if new clause isn't already present, add it to the set\n\n  - continue until one of two things happens:\n\n    - there are no new clauses that can be added, then KB does not entail $\\alpha$\n\n    - two caluses resolve to yield empty clause (they are conplementary), KB entails $\\alpha$ \n\n\n\n\n## Module 7 Definitions\n* **Knowledge-based agent** - use reasoning over a representation of knowledge to decide what action to take\n* **Knowledge base (kb)** - set of sentences, each sentence is expressed in a knowledge representation language and represents some assertions about the world\n* **Axiom** - given without being derived from other sentences\n* **Inference** - derive new sentences from the old\n* **Logic** - a general class of representations\n* **Model checking** - enumerate models and show a sentence must hold in all models\n* **Theorem proving** - apply rules of inference directly to sentences to construct proof without consulting models\n* **Definite clause** - disjunction of literals of which exactly one is positive\n* **Horn clause1** - disjunction of literals of which at most one is positive, which is closed under resolution\n* **Horn clause2** - (if you resolve two Horn clause, you get a Horn clause)\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": "bb2ef9a7-bda0-4224-8f8b-ad3cd48c03f1"
      },
      "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": 116,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n- rationality is: internal thought processes and reasonings vs intelligent behaviors\n\n- Acting humanly: **Turing test**\n\n  - if a human can't distinguish the answers done by human and computer (physical simulation isn't necessary)\n\n  - total Turing test: requires interaction between human and object in real world\n\n- Thinking humanly: cognitive method approach\n\n  - intervined with cognitive science\n\n- Thinking rationally: laws of thought\n\n  - Aristotle, logic\n\n- Acting rationally: rational agent\n\n  - something acts to achieve the best (expected) outcome\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n- **week AI** (machines would act as if they are intelligent) vs **strong AI** (machines are actually conciously thinking)\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n- **the Chinese room**\n\n\n## AIMA 2.1 Agents and Environments\n\n- agents: perceive the environment throught **sensors**, and act on it throug **actuator** (human, robot, software) \n\n  - agent's choice on actions depends on its built-in knowledge and the entire percept sequence observed in the environment (to-date)\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n- rational agent: maximize its performance measure\n\n- omniscience: knows the actual outcome (impossible)\n\n- requires agent to gather information and learning (become automonous)\n\n\n## AIMA 2.3 The Nature of Environments\n\n- **task environment** (PEAS)\n\n  - performance measure\n\n  - environment\n\n  - actuators\n\n  - sensors\n\n- properties of task environment:\n\n  - fully observable vs. partially observable\n\n  - single agent vs. multiagent\n\n  - deterministic vs. nondeterministic (stochastic) (if next state is deterministic based on current state and the action to take)\n\n  - episodic vs. sequential (experience in atmoic episodes (one percept in one state, states are not dependent), vs current decision can affect future)\n\n  - static vs. dynamic (if the environment is changing when agent is deliberating)\n\n  - discrete vs. continuous (if states are discrete)\n\n  - known vs. unknown (if the agent knows about the laws of the world)\n\n- hardest problem: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown\n\n\n## AIMA 2.4 The Structure of Agents\n\n- agent = architecture + program (take percept as input and action as output)\n\n- simple reflex agent: select actions on the current, ignoring the past (work if environment is fully observable)\n\n- model-based reflex agent: keep track of the past with internal states\n\n  - transition model (how the world changes) + sensor model (how changes are reflected in agent's percept)\n\n- goal-based agent\n\n  - search and planning\n\n- utility-based agent (expected utility for performance measure)\n\n- learning agent\n\n- problem-solving agent: must plan ahead, consider a sequence of action that form a path to a goal state (search)\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Rationality** - doing the right thing\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the content the agent's sensor perceives\n* **Agent function** - map percept to action (abstract mathematical description)\n* **Agent program** - implement agent function (within some physical system)\n* **Consequentialism** - evaluate agent's action by its consequence\n* **Performance measure** - evaluate states resulted from an action\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\n- immutable: string, tuple\n\n- mutable: list\n\n- t = ['a', 'b', 'c', 'd', 'e'], t[1:-1:2] = ['b', 'c', 'd']\n\n- t.insert('b', 2); t => ['a', 'b', 'b', 'c', 'd', 'e']\n\n- t.count('b') => 2\n\n- key arguments must be after positional arguments\n\n- **args and kwargs**\n\n```\ndef myfun(positional, *args, **kwargs):\n  print(positional)\n  if args:\n    print(args)\n  if kwargs:\n    print(kwargs)\n\nmyfun(\"hi\", \"the\", \"best\", \"food\", \"is\", \"tacos\", shell=\"soft\", meat=\"beef\")\n>>> hi\n    ('the', 'best', 'food', 'is', 'tacos’)\n    {'shell': 'soft', 'meat': 'beef'}\n```\n\n- **multiple inheritance**\n\n```\nclass A(object):\n  def foo(self):\n    print('Foo!')\nclass B(object):\n  def foo(self):\n    print('Foo?')\n  def bar(self):\n    print('Bar!')\nclass C(A, B):\n  def foobar(self):\n    super().foo() # Foo!\n    super().bar() # Bar!\n```\n\n- benefits of generators:\n\n  - Maintains local state automatically\n  \n  - Values are computed one at a time, as they’re needed\n  \n  - Avoids storing the entire sequence in memory\n\n  - Crucial for infinite sequences\n  \n  - Bad if you need to inspect the individual values\n\n\n## Module 2 Definitions\n* **Duck typing** - establishes suitability of an object by determining presence of methods\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n- search problem (fully observable, deterministic, known environment):\n\n  - state space: possible states\n\n  - inital state\n\n  - goal state\n\n  - actions\n\n  - transition model\n\n  - action cost function\n\n\n## AIMA Chapter 3.2 Example Problems\n\n- **standardize problem**: to exercise problem-solving method\n\n  - **grid world**: 2d arrays of square cells where agent can move from cell to cell\n\n    - e.g. vacuum world, sokoban puzzle, sliding-tile puzzle (8-puzzle)\n\n- **real-world problem**: whose solution people actually use in real life \n\n  - route-finding problem, airline scheduling, routing video streams in computer network\n\n  - touring problem (traveling salesperson problem), VLSI layout, robot navigation, automatic assembly sequencing\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n- **search algorithm**: takes a search problem and returns a solution, or failure if no solution\n\n- **best-first search**: choose the node with some minimum value of f(n), evaluation function (informed search)\n\n  - on each iteration, pop a node with the minimum f(n) (**priority queue**), return it if it is the goal, or get its successors\n  \n    - add each successor to the frontier if it has not been reached bofre, or if the cost of the path to it is lower than before\n\n- **redundant path**: cycle, or worse path to get to the same state\n\n  - best-first search remembers all previous reached states, appropriate when there are lots of redundant states\n\n  - **graph search**: checks for redundant paths\n  \n  - **tree-like search**: not checking redundant paths (less memory)\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n- breath-first search (FIFO queue, reached is set rather than map):\n\n  - complete, optimal, find a solution with minimum actions\n\n  - **early goal test**: check if a node is a solution as soon as it is generated (best-first search does **late goal test**) \n\n  - time and space complexity: $O(b^d)$\n\n  - appropriate when:\n  \n    - possible infinite path\n\n    - some solution have short paths\n\n    - can quickly discard unlikely path\n\n- Dijkstra's algorithm (**uniform-cost search**): best-first search where f(n) = g(n)\n\n  - complete and cost-optimal\n\n  - space and time complexity: $O(b^{1+\\lfloor C^*/e \\rfloor})$, where C* is the cost of optimal solution, e is the lower bound on the cost of each action\n\n    - if all action costs are equal, complexity = $O(b^{1+d})$, which is similar to breath-first search\n\n  - breath-first search explores equally in all directions\n\n  - uniform-cost search prioritize which paths to explore\n\n- depth-first search (like a tree-like search, not keep a table of reached, , LIFO frontier)\n\n  - not optimal, incomplete\n\n  - time complexity proportional to the number of states, memory complexity $O(bm)$, where b is the branching factor and m is the maximum depth\n\n  - appropriate when:\n\n    - space is restricted\n\n    - there are many possible solutions with long path, and wrong path are usually terminated quickly\n\n    - search can be fine-tuned quickly \n\n  - **back-tracking search**: use even less memory, only one successor generated at a time, rather than all successors\n\n    - successor generated by modifying the current state, rather than allocating new memory for a brand-new state\n\n    - memory complexity $O(m)$\n\n- **depth-limited search** (tree-like search)\n\n  - time complexity $O(b^l)$ and space complexity $O(bl)$\n\n  - eliminate cycles, but not optimal, incomplete\n\n  - no infinite-path problem\n\n- **literative deepening search**:\n\n  - optimal, and complete\n\n  - memory complexity: $O(bd)$ if there is a solution, or $O(bm)$ if there isn't\n\n  - time complexity: $O(b^d)$ if there is solution, or $O(b^m)$ if there isn't\n\n  - appropriate when:\n\n    - search space is larger than can fit in memory and the depth of the solution is not known\n\n- bidirectional search: search from the initial state and the goal state\n\n  - complete and optimal\n\n  - need 2 frontiers and 2 reached table\n\n  - $O(b^{d/2}+b^{d/2})\n\n\n## Module 3 Lecture Notes\n\n- state is a phyiscal configuration, node is part of the tree\n\n- uninformed: use only information available in the problem definition (all nodes in the frontier look equally the same)\n\n- informed: some nodes might be better than other\n\n\n| criterion | breath-first | uniform-cost | depth-first | depth-limited | iterative deepening | bidirectional |\n| ----------| ------------ | ------------ | ----------- | ------------- | ------------------- | ------------- |\n| complete? | Yes          | Yes          | No          | No            | Yes                 | Yes           |\n| optimal?  | Yes          | Yes          | No          | No            | No                  | Yes           |\n| time      | $O(b^d)$     | $O(b^{1+\\lfloor C^*/e \\rfloor})$| $O(b^m)$ | $O(b^l)$ | $O(b^d)$         | $O(b^{d/2})$  |\n| space     | $O(b^d)$     | $O(b^{1+\\lfloor C^*/e \\rfloor})$| $O(bm)$ | $O(bl)$ | $O(bd)$            | $O(b^{d/2})$  |         \n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** - a sequence of actions\n* **Solution** - path from initial state to the goal state\n* **Optimal solution** - solution with the lowest cost\n* **Frontier** - states that are available for expanding\n* **Completeness** - a complete algorithm must systematically check every state that is reachable from the initial state\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n- **Greedy best-first search**: expands node with the lowest h(n) (i.e. f(n)=h(n))\n\n  - not optimal, but complete\n\n  - worst case time and space complexity is $O(|V|)$\n\n- **A* search**: expands node with the lowest f(n) = g(n) + h(n) (estimated cost of the best path that continues from $n$ to goal)\n\n  - complete, and optimal if h(n) is **admissible** (never overestimate the cost to goal, optimistic)\n\n    - with an inadmissible heuristic, A* search may or may not be optimal\n\n  - **consistent**: $h(n) \\leq c(n,a,n')+h(n') (triangle inequality)\n\n    - every consistent heuristic is admissible (but not vice versa)\n\n  - A* search is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution\n\n- Weighted A* search:  f(n) = g(n) + W*h(n), where W > 1\n\n- Algorithm to conserve memory usage:\n\n  - beam search: limit the size of frontier, keep k nodes with best f-scores (incomplete and suboptimal)\n\n    - or keep nodes within x of the best f-score\n\n  - iterative-deepning A* search (IDA*): depth first, no need to reach all states, useful if memory is limited\n\n    - search an f-contour, find a node just beyond that contour, and uses that node's f-cost as the next contour\n\n  - recursive best-first search (RBFS): keep track of the f-value of the best alternative path, if current node exceeds the limit, the recursion goes back to the alternative path\n\n    - space complexity if linear, optimal if h(n) is admissible\n\n  - IDA* and RBFS may go to the same states many times\n\n  - SMA*: expands the best leaf and deletes the worst leaf (complete)\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n- **manhattan distance**: # of moves from desired location\n\n- to describe the quality of a heuristic:\n\n  - b* (**effective branching factor**): $N+1 = 1+ b* +(b*)^2+ .. +(b*)^d$, where N is total number of nodes, d is solution depth\n\n    - b* closer to 1 is better\n\n  - or reducing **effective depth** is better\n\n- h2 is always better than h1, than h2 **dominates** h1\n\n  - A* using h2 will never expand more nodes than h1\n\n- **relaxed problem**: problem with fewer restrictions\n\n  - the cost of a relaxed problem is admissible heuristic for the original problem\n\n- admissible heuristic can also generate from the cost of **subproblem**\n\n  - **pattern database**: store solution cost of every subproblem\n\n\n\n## Module 4 Lecture Notes\n\n- inadmissible heuristic break optimality by pushing good plans too far back in the frontier, which means they never get expands\n\n- admissible slows down bad plans but never outweighs true cost, that means true best plan always gets expanded\n\n\n## Module 4 Definitions\n* **Informed search** - uses domain specific knowledge about the goals in order to find solution more efficiently than uninformed one\n* **Heuristic function** - estimated cost of the cheapest path from state at node n to a goal state\n* **Bounded suboptimal search** - solution guaranteed to be within a constant factor W of the optimal cost\n* **Bounded-cost search** - solution whose cost is less than C\n* **Unbounded-cost search** - solution of any cost, find it as soon as possible\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n- The elements of games:\n\n  - initial state\n\n  - the player whose turn it is to move in state $s$\n\n  - the set of legal move in state $s$\n\n  - transition model, which defines the state resulting from taking action $a$ in state $s$\n\n  - terminal test, which is true if game is over\n\n  - utility function, the final numeric value to player $p$ when game ends\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n- *minimax search*:\n\n  - complete depth-first exploration\n\n  - time complexity: $O(b^m)$, where $m$ is the maximum depth, and $b$ number of legal moves\n\n  - space complexity: $O(bm)$ --generate all actions at once, $O(m)$ --generate action one at a time\n\n- alpha-beta pruning\n\n  - alpha: (at least) the best (highest) value we have found so far for MAX \n\n  - beta: (at most) the best (lowest) value we have found so far for MIN\n\n  - updates the value of alpha and beta as it goes along and prunes the remaining branches at a node as soon as the value of the current node    is known to be worse than the current alpha or beta\n\n- the effectiveness of alpha-beta pruning depends on the order in which the states are checked\n\n  - if we can try the successors that are likely to be the best, then time complexity would be $O(b^{m/2})$\n\n  - **killer move** heuristic: try the best move first\n\n  - **transposition**: different permutations of move sequence that end up in the same position\n\n- **type A strategy** (chess): consider all possible moves to a certain depth then use heuristic function to estimate the utility of states   at that depth (wide but shallow)\n\n- **type B strategy** (Go): ingores bad moves and move as far as possible (deep but narrow)  \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n- to cut of the search early\n\n  - replace utility function with *evaluation function*\n\n  - replace terminal test with *cutoff test*\n\n- evluation function: return an estimate of the expected utility of state $s$ to player $p$\n\n  - terminal state: $eval(s,p) = utility(s,p)$\n\n  - nonterminal state:  $utility(loss,p) \\leq eval(s,p) \\leq utility(win,p)$\n\n- based on the static features of the board\n\n  - **expected value**: probability times values\n\n  - **weighted linear function**: weights times feature values\n\n    - assuming features are independent\n\n- cutoff test:\n\n  - set a fixed depth limit, test returns true if depth exceeds the limit\n\n  - apply iterative deepening\n\n  - may lead to errors\n  \n    - evaluation function can only apply when the position is **quiescent**: no pending move would widely swing the evaluation\n\n    - for non-quiescent positions, cutoff test returns false => **quiescent search**\n\n  - **horizon effect**: use delaying tactics in face of opponent's unavoidable damaging move\n\n    - **singular extension**: allow moves that are \"clearly better\" even the search would normally be cutoff at that point\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n- **stochastic games**: bring unpreditablity by introducign a random event (rolling a dice)\n\n  - backgammon: a stochastic game combined both luck and skill\n\n    - tree has chance nodes in addition to MAX, MIN nodes\n\n    - needs to calculate the **expected value** of a position\n\n- **expectiminimax values**: MAX, MIN, expected value for chance. ($O(b^mn^m), $b$ is branching factor, $m$ is maximum depth, and $n$ is distict number of rolls)\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n- $P(result(a)=s') = \\sum_s P(s)P(s'|s,a)$\n\n- $EU(a)=\\sum_{s'}P(result(a)=s')$\n\n- $action = \\argmax_a EU(a)$\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Perfect information** - fully observation\n* **Zero-sum** - what is good for one player is bad for the other\n* **Foward-pruning** - prune moves that look bad but are actually good\n* **Beam search (foward-pruning)** - consider only n best moves rather than all on each ply\n* **Last move reduction (foward-pruning)** - with well ordering of moves, moves appear last are less likely to be good\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n- A CSP consists of X (set of variables), D (set of domain, one for each variable), C (set of constraints that specify allowable combinations of values)\n\n  - C = (scope, rel), where scope is tuple of variables in the constraints, rel is a **relation** that defines the values these variables can take\n\n  - CSP deals with **assignment** of values to variables\n\n- **consistent**: assignment doesn't violate constraints\n\n- **complete assignment**: every variable is assigned a value\n\n  - **solution**: a consistent and complete assignment\n\n- **partial assignment**: some variables are unassigned\n\n  - **partial solution**: partial assignment that is consistent\n\n- solution to CSPs can be found by a **general purpose algorithm**\n\n- **constraint graph**: nodes = variables, edges = connect any two variables in a constraint (binary CSP with unary and binary constraints)\n\n- benefits of CSP:\n\n  - easy to formulate a problem as CSP\n\n  - CSP solvers are fast and efficient\n\n  - CSP prune off the branches that violate the constraints\n\n- variations of CSP:\n\n  - domains:\n  \n    - discrete, finite domains (map-coloring, scheduling, 8-queens)\n\n    - discrete, infinite domains (set of strings or integers)\n\n    - continuous domains (linear programming problems)\n\n  - constraints:\n\n    - unary constraint: restricts the value of a single variable\n\n    - binary constraint: relates two variables\n\n    - **global constraint**: involves arbitrary number of variables (Sudoku, cryptarithmetic)\n\n      - **constraint hypergraph**: ordinary nodes = variables, hypernodes = n-ary constraints\n\n    - preference constraint: indicate which solution is preferred (encoded as cost => **constrained optimization problem** (COP))\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- **local consistency**: the process of enforcing local consistency can eliminate inconsistent values throughout the graph\n\n  - **node consistency**: a variable is node consistent, if all values in the domain satisfy variable's unary constraints\n\n  - **arc consistency**: if all values in the domain satify variable's binary constraints\n\n    - $X_i$ is arc-consistent with respect to $X_j$ if for every value in domain $D_i$, there is some value in $D_j$ that satisfies the binary constraints      on $arc(X_i, X_j)$\n\n    - a graph is arc-consistent if every variable is arc-consistent with every other variable\n\n  - **path consistency**: ${X_i, X_j}$ is path-consistent with respect to $X_m$ if, for every assignment of ${X_i, X_j}$ pair with constraints on ${X_i, X_j}$,    there is an assignment to $X_m$ that satisfies constraints on ${X_i, X_m}$ and ${X_m, X_j}$\n\n- AC-3: enforcing arc consistency ($n$ variables, $d$ domain size, $c$ constraints, checking consistency for each arc is $O(d^2)$, total worst-case is $O(n^2d^3)$)\n\n  - queue: contains all arc in CSP\n\n  - pop off arbitrary $arc(X_i, X_j)$, and makes $X_i$ arc-consistent with $X_j$\n\n    - if $D_i$ unchanged, move to next arc\n\n    - else, add all $arc(X_k, X_i)$ to the queue, where $X_k$ is a neighbor of $X_i$\n\n      - if $D_k$ is revised down to nothing, then CSP has no consistent solution => return failure\n\n      - else, keep checking until queue is empty\n\n- **k-consistency**: for any set of $k-1$ variables and for any consistent assignment assigned to these variables, a consistent value can always be assigned  to any $kth$ variable\n\n  - **strongly k-consistent$: if it is k-consistent, and (k-1)-consistent, ... to 1-consistent\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n- backtrack search: depth-first search for CSPs with single-value assignment\n\n  - choose values for one valuable at a time and backtrack when a variable has no legal values left to assign\n\n  - branching factor at root: $n*d$, branching factor at the next level: $(n-1)*d$\n\n  - tree has $(n!*d^n)$ leaves => **commucative** => ($d^n$) leaves\n  \n  - this is **chronological backtracking** because the most recent decision point is revisited\n\n- improvement with domain-specific heuristics:\n\n  - **minimum-remaining-values** heuristic (MRV, the order in which variables are examined -- fail first): choose the next variable with fewest \"legal\" values (the most constrained variable)\n\n  - **degree** heuristic (reduce branching factor, first variable to choose): select the variable that has the largest number of constraints on other variables (most constraining variable)\n\n  - **least-constraining-value** heuristic (the order in which values are examined, given a variable -- fail last): choose the one ruling out the fewest choices for the neighboring    variables in the constraint graph\n\n- inference -- **forward checking**\n\n  - for each unassigned variable Y that is connected to X by a constraint, delete from Y's domain any value inconsistent with the one chosen for X\n\n- stronger inference -- **Maintaining Arc Constraint (MAC)**\n\n  - inference call AC-3, and start with only X's neighbors\n\n- conflict set: a set of assignments that are in conflict with some value of a variable\n\n  - **backjumping**: backtracks to the most recent assignment in the conflict set\n\n  - **conflict-direct backjumping**: \n  \n    - conflict set is the set of preceding variables that cause a group of variables to have no consistent solution\n\n    - backjump to the most recent variable in the conflict set, and recompute the conflict set of this variable\n\n- constraint learning: finding a minimum set of variables (**no-good**) from the conflict set that causes the failure\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n- local search use a complete-state formulation, each state assigns a value to each variable, and the search changes a variable at a time\n\n- **min conflict**: select the value that results in the minimum number of conflicts with other variables\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- decompose large problem into subproblems (reduce time complexity)\n\n  - **independent subproblems**\n\n- any tree-structured CSP can be solved in time linear in the number of variables\n\n  - just march down the directed arc-consistent graph, and choose any remaining value\n\n- cutset conditioning: $O(d^c*(n-c)d^2)$\n\n- tree decomposition: $O(nd^{w+1})$, efficient if tree-width is small\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Constraint propogation** - use constraints to reduce the legal values for a variable, then reduce those for another variable\n* **Commucative** - the problem is commucative if the order of applications of set of actions does not matter\n* **Directional arc consistent** - tree CSP in the ordering of $X_i$, $X_2$, .., $X_n$, and every $X_i$ is arc-consistent with each $X_j$ for $j>i$\n* **Topology sort** - pick root first, then choose the orderings of variables such that each variable appears after its parent\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \n- A KB contains some **background information** about the world\n\n  - a knowledge-based agent can add info to KB through its observations through the world (TELL)\n  - the agent can also query the KB and ask it to derive new knowledge about what actions to take (ASK)\n  - then the agent (TELL) the KB which action was chosen, so that it can be executed\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n- Wampa world (deterministic, discrete, static, single-agent, sequential, partially observable)\n\n  - contains a cave consisting of rooms, wampa, pits, and Luke (gold)\n\n    - environment: 4x4, start in the sqaure [1.1]\n\n    - performance measure: +1000 for securing Luke and leaving, -1000 for falling into a pit or eaten by wampa, etc\n\n    - actuators: Forward, TurnLeft, TurnRight, Grab (pick up Luke), Shoot, Climb (out of the cave, works in [1,1])\n\n    - sensors: Stench (adjacent to Wampa), Breeze (adjacent to a pit), Gasp (in sqaure with Luke), Bump (walk into wall), Scream (Wampa is killed)\n\n  - in each step, the agent draw conclusion from the available info\n\n\n## AIMA Chapter 7.3 Logic\n\n- in logics, every sentence (has syntax and semantic) has to be either true or false (**truth**) in each possible world (**model**)\n\n- if a sentence $\\alpha$ is true in model $m$, then $m$ satisfies $\\alpha$, or $m$ is a model of $\\alpha$\n\n  - $M(\\alpha)$ := set of all models of $\\alpha$\n\n- **entailment**: a sentence logically follow from another sentence\n\n  - $\\alpha$ entails $\\beta$, iff in every model in which $\\alpha$ is true, then $\\beta$ is true\n\n  - $\\alpha \\models \\beta$ iff $M(\\alpha) \\subseteq M(\\beta)$\n\n    - alpha is a stronger assertion, rules out more possible world\n\n- **logical inference**: entailment can be applied to derive conclusions\n\n  - $KB \\vdash_i \\alpha$, an inference alogrithm $i$ derived $\\alpha$ from $KB$, or $\\alpha$ is derived from $KB$ by $i$\n\n  - **sound** (true-preserving): an inference algorithm that derives only entailed sentences\n\n  - **complete**: an inference algorithm that can derive any sentence that is entailed\n\n- if KB is true in real world, then any sentence derived from KB by a sound inference algorithm is also true in real world\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n- **atomic sentences**: consist of a single proposition symbol (that can be true or false)\n\n- **complex sentences**: constructed from simpler sentences, with parentheses and **logical connectives** (not, and, or, implies, iff) \n\n- a model simply sets the truth value for each proposition\n\n  - $\\neg P$ is true, iff $P$ is false in $m$\n\n  - $P\\land Q$ is true, iff both $P$ and $Q$ is true in $m$\n\n  - $P\\lor Q$ is true, iff either $P$ or $Q$ is true in $m$\n\n  - $P\\implies Q$ is true unless $P$ is true and $Q$ is false in $m$\n\n  - $P\\iff Q$ is true iff both $P$ and $Q$ is true or both false in $m$\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n- **logical equivalence**: two sentences are logically equivalent if they are true in the same set of models\n\n  - $\\alpha \\equiv \\beta$ iff $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$\n\n- **validity**: a sentence is valid (=**tautology**) if it is true in all models\n\n- **satisfiability**: a sentence is satisfiable if it is true in some models\n\n  - $\\alpha$ is valid iff $\\neg\\alpha$ is unsatisfiable\n\n  - $\\alpha$ is satisfiable iff $\\neg\\alpha$ is not valid\n\n  - $\\alpha \\models \\beta$ iff ($\\alpha \\land \\neg \\beta$) is unsatisfiable (proof by contradiction)\n\n- **monotonicity**: the set of entailed sentences can only increase as info is added to the knowledge base\n\n  - if we add additional info to the KB, it doesn't invalidate any other info that we've already inferred\n\n- **resolution**\n\n- **factoring**: remove multiple copies of literals\n\n- **conjunctive normal form**: conjunction of clauses (disjunctions of literals) ($(P\\lor Q) \\land (R\\lor S))\n\n- KB with only **definite clauses**:\n\n  - $\\neg P \\lor \\neg Q \\lor R \\equiv (P \\land Q) \\implies R$\n\n  - inference can be done by forward-chaining and backward-chaining\n\n  - deciding entailment can be done in linear time with respect to the size of KB\n\n- **forward chaining** (data-driven reasoning): start with premises\n\n- **backward chaining** (goal-directed reasoning): start with conclusion, find implication\n\n\n\n## Module 7 Lecture Notes\n\n- standard logical equivalence\n\n  - $\\alpha \\land \\beta \\equiv \\beta \\land \\alpha$, commutativtiy of $\\land$\n\n  - $\\alpha \\lor \\beta \\equiv \\beta \\lor \\alpha$, commutativtiy of $\\lor$\n\n  - $(\\alpha \\land \\beta) \\land \\gamma \\equiv \\alpha \\land (\\beta \\land \\gamma)$, associativity of $\\land$\n\n  - $(\\alpha \\lor \\beta) \\lor \\gamma \\equiv \\alpha \\lor (\\beta \\lor \\gamma)$, associativity of $\\lor$\n\n  - $\\neg(\\neg \\alpha) \\equiv \\alpha$, double-negative elimination\n\n  - $\\alpha \\implies \\beta \\equiv \\neg \\beta \\implies \\neg \\alpha$, contraposition\n\n  - $\\alpha \\implies \\beta \\equiv \\neg \\alpha \\lor \\beta$, implication elimination\n\n  - $\\alpha \\iff \\beta \\equiv (\\alpha\\implies\\beta)\\land(\\beta\\implies\\alpha)$, biconditional elimination\n\n  - $\\neg(\\alpha\\lor\\beta) \\equiv \\neg\\alpha\\land\\neg\\beta$, De Morgan\n\n  - $\\neg(\\alpha\\land\\beta) \\equiv \\neg\\alpha\\lor\\neg\\beta$, De Morgan\n\n  - $(\\alpha \\land \\beta) \\lor \\gamma \\equiv (\\alpha \\lor \\gamma) \\land (\\beta \\lor \\gamma)$, distributivity of $\\lor$ over $\\land$\n\n  - $(\\alpha \\lor \\beta) \\land \\gamma \\equiv (\\alpha \\land \\gamma) \\lor (\\beta \\land \\gamma)$, distributivity of $\\land$ over $\\lor$\n\n- inference rules\n\n  - $(\\alpha\\implies\\beta, \\alpha)/\\beta$, Modus Ponens\n\n  - $(\\alpha \\land \\beta)/\\beta$, and-elimination\n\n- resolution\n\n  - $(l_1\\lor .. \\lor l_k, m)/l_1\\lor .. \\lor l_{i-1}\\lor l_{i+1} \\lor .. \\lor l_k$, unit resolution, where $l_i$ and $m$ are conplementary\n\n  -  $(l_1\\lor .. \\lor l_k, m_1\\lor .. \\lor m_n)/l_1\\lor .. \\lor l_{i-1}\\lor l_{i+1} \\lor .. \\lor l_k \\lor m_1\\lor .. \\lor m_{j-1}\\lor m_{j+1} \\lor .. \\lor m_n$,     full resolution, where $l_i$ and $m_j$ are conplementary\n\n  - can only resolve one pair at a time\n\n- resolution algorithm, complete (contradiction, to show $KB\\models \\alpha$, show $KB\\land \\alpha$ is unsatisfiable)\n\n  - convert $KB\\land \\alpha$ into CNF\n\n  - apply resolution rule to the resulting clauses\n\n  - if new clause isn't already present, add it to the set\n\n  - continue until one of two things happens:\n\n    - there are no new clauses that can be added, then KB does not entail $\\alpha$\n\n    - two caluses resolve to yield empty clause (they are conplementary), KB entails $\\alpha$ \n\n\n\n\n## Module 7 Definitions\n* **Knowledge-based agent** - use reasoning over a representation of knowledge to decide what action to take\n* **Knowledge base (kb)** - set of sentences, each sentence is expressed in a knowledge representation language and represents some assertions about the world\n* **Axiom** - given without being derived from other sentences\n* **Inference** - derive new sentences from the old\n* **Logic** - a general class of representations\n* **Model checking** - enumerate models and show a sentence must hold in all models\n* **Theorem proving** - apply rules of inference directly to sentences to construct proof without consulting models\n* **Definite clause** - disjunction of literals of which exactly one is positive\n* **Horn clause1** - disjunction of literals of which at most one is positive, which is closed under resolution\n* **Horn clause2** - (if you resolve two Horn clause, you get a Horn clause)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}