{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of DRAFT 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 500 word summary of the lectures for each model.\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": "d52e3af7-4b19-40ca-f563-76df8934fdd2"
      },
      "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": 3,
      "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": "863fb02f-23cd-4f1a-df87-a28a2a1e3aab"
      },
      "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": 4,
      "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": 5,
      "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",
        "chapter1_1 = \"\"\" We can define AI from different perspectives. There are two dimensions: human vs. rational and thought vs. behavior. \\n \n",
        "Acting humanly: The Turing test approach (NLP, knowledge representation, automated reasoning, ML; Total Turing Test : CV, robotics) \\n\n",
        "Thinking humanly: The cognitive modeling approach (introspection, psychological experiments, brain imaging, cognitive science) \\n\n",
        "Thinking rationally: The logic approach (syllogisms, logic, probability)\\n\n",
        "Acting rationally: The rational agent approach (standard model (to achieve an objective), limited rationality) \\n\n",
        "Beneficial machines where objective can not be specified (value alignment problem, provably beneficial)\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 = \"\"\" Weak AI：machines could act as if they were intelligent \\n\n",
        "Strong AI: general AI which can solve an arbitrarily wide variety of tasks \\n\n",
        "Good Old-Fashioned AI: logical agent for qualification problem \\n\n",
        "Not all tasks can be achieved by the AI because of the informality of the behavior (eg. human's informal guidelines), machine's disability and mathematical limit (Godel Theorem).\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" \n",
        "The process of thinking is not important, the result matters.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" A rational agent is one that does the right thing. We need a criterion to measure the performance of the agent. \\n \n",
        "For each possible #percept sequence#, a rational agent should select an #action# that is expected to maximize its #performance measure#, given the #prior knowledge# the agent has.\n",
        "Omniscience is impossible in the reality. So the agent needs information gathering and learn from it. Rationality maximizes expected performance. Autonomy means the agent does not rely on the prior knowledge.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" PEAS (Performance, Environment, Actuators, Sensors) \\n\n",
        "The environment may be partially observable. or unobservable. \\n\n",
        "The environment can be multi-agent (competitive or cooperative). \\n\n",
        "The next state of the environment can be nondeterministic. \\n\n",
        "The behavior can be episodic or sequential.\n",
        "The enviroment can be static, semidynamic (environment itself does not change, but the performance measurement changes) or dynamic. \\n\n",
        "The time can be discrete or continuous. \\n\n",
        "The prior knowledge can be known or unknown.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture \\n\n",
        "The agent programs take the current percept as input from the sensors and return an action to the actuators. The agent = architecture + program.\\n\n",
        "Agents need internal state, transition model and sensor model and choose action according to the utility to achieve the goal. \\n\n",
        "Learning agents require the reward and penalty. \\n\n",
        "The transitions between states can be atomic, factored and structured.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Brain in the tank.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"gathering information from an environment\",\n",
        "\"utility\" : \"performance measurement\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 6,
      "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": "ea8f9f83-4e91-4a7b-a4c6-2d19b57676db"
      },
      "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.2 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",
        "    if(len(summary) > 3000 or len(summary.split(' ')) > 500):\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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n We can define AI from different perspectives. There are two dimensions: human vs. rational and thought vs. behavior. \n \nActing humanly: The Turing test approach (NLP, knowledge representation, automated reasoning, ML; Total Turing Test : CV, robotics) \n\nThinking humanly: The cognitive modeling approach (introspection, psychological experiments, brain imaging, cognitive science) \n\nThinking rationally: The logic approach (syllogisms, logic, probability)\n\nActing rationally: The rational agent approach (standard model (to achieve an objective), limited rationality) \n\nBeneficial machines where objective can not be specified (value alignment problem, provably beneficial)\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Weak AI：machines could act as if they were intelligent \n\nStrong AI: general AI which can solve an arbitrarily wide variety of tasks \n\nGood Old-Fashioned AI: logical agent for qualification problem \n\nNot all tasks can be achieved by the AI because of the informality of the behavior (eg. human's informal guidelines), machine's disability and mathematical limit (Godel Theorem).\n\n\n## AIMA Chapter 27.2 Can Machines Really Think?\n \nThe process of thinking is not important, the result matters.\n\n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n A rational agent is one that does the right thing. We need a criterion to measure the performance of the agent. \n \nFor each possible #percept sequence#, a rational agent should select an #action# that is expected to maximize its #performance measure#, given the #prior knowledge# the agent has.\nOmniscience is impossible in the reality. So the agent needs information gathering and learn from it. Rationality maximizes expected performance. Autonomy means the agent does not rely on the prior knowledge.\n\n\n## AIMA 2.3 The Nature of Environments\n PEAS (Performance, Environment, Actuators, Sensors) \n\nThe environment may be partially observable. or unobservable. \n\nThe environment can be multi-agent (competitive or cooperative). \n\nThe next state of the environment can be nondeterministic. \n\nThe behavior can be episodic or sequential.\nThe enviroment can be static, semidynamic (environment itself does not change, but the performance measurement changes) or dynamic. \n\nThe time can be discrete or continuous. \n\nThe prior knowledge can be known or unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture \n\nThe agent programs take the current percept as input from the sensors and return an action to the actuators. The agent = architecture + program.\n\nAgents need internal state, transition model and sensor model and choose action according to the utility to achieve the goal. \n\nLearning agents require the reward and penalty. \n\nThe transitions between states can be atomic, factored and structured.\n\n\n## Module 1 Lecture Notes\n Brain in the tank.\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - gathering information from an environment\n* **Utility** - performance measurement\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 = \"\"\" Objects of built-in types like (int, float, bool, str, tuple, unicode) are immutable and hashable.\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"If an object is mutable, its state can be changed after declared.\",\n",
        "}"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "1b8b9cfd-b156-4daa-b6e5-ed5c89745bd5"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Objects of built-in types like (int, float, bool, str, tuple, unicode) are immutable and hashable.\n\n\n## Module 2 Definitions\n* **Mutability** - If an object is mutable, its state can be changed after declared.\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 = \"\"\" Goal formulation, Problem formulation, Search (for solution), Execution \\n\n",
        "A search problem is made up of state space (a directed graph), initial state, goal states, action space, transition model, action cost function \\n\n",
        "A sequence of actions forms a path, and a solution is a path from the initial state to a goal state.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" The state space can be infinite. \n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\" The search algorithm superimposes a search tree over the state-space graph. \\n\n",
        "The state space describes the (possibly infinite) set of states in the world \\n\n",
        "The actions allow transitions from one state to another. \\n\n",
        "The search tree describes paths between states, reaching towards the goal. \\n\n",
        "The search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root. \\n\n",
        "\n",
        "```\n",
        "def Best_First_Search():\n",
        "    frontier = [initial_state]\n",
        "    reached = []\n",
        "    while frontier:\n",
        "        cur = frontier.pop()\n",
        "        if isGoal(cur): \n",
        "            return True \n",
        "        for s in cur.successors: \n",
        "            if s.state is not in reached or s.cost < reached[s.state]: ### cost = history_path + action cost\n",
        "              reached[s.state] = s \n",
        "              frontier.add(s) \n",
        "    return False \n",
        "```\n",
        "\n",
        "Best-first search: priority queue frontier \\n\n",
        "If the action costs are uniform, we can use BFS and DFS \\n\n",
        "BFS: FIFO queue frontier \\n\n",
        "DFS: LIFO stack frontier \\n\n",
        "We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check. \\n\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" An uninformed search algorithm is given no clue about how close a state is to the goal. \\n\n",
        "BFS is complete and cost-optimal for the problem where actions have identical cost. \\n\n",
        "Both time and space complexity are $O(b^d)$. \\n\n",
        "Dijkstra's algorithm/ uniform-cost search (Best_First_Search) ### uniform-cost is refered to uniform-depth (BFS) \\n\n",
        "Uniform-cost search is complete if all action costs are $\\\\ge \\\\epsilon > 0$ \\n\n",
        "Both time and space complexity are $O(b^{1 + \\\\frac{C^*}{\\\\epsilon}})$ \\n\n",
        "Depth-first search is not cost-optimal; it returns the first solution it finds, even if it is not cheapest. \\n\n",
        "For finite state spaces that are trees DFS is efficient and complete. (For cyclic graph, DFS is not complete) \\n\n",
        "Backtracking search uses less memory. Only one successor is generated at a time and undo the action after we have DFS it. \\n\n",
        "Time complexity: $O(b^m)$ and space complexity: $O(bm)$ \\n\n",
        "Iterative Deepening search is complete and cost-optimal. (Depth-limited is not, but iterative deepening is based on depth-limited) \\n\n",
        "Bidirectional is complete and cost-optimal if both directions are breadth-first or uniform-cost.\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Path: a sequence of actions leading from one state $s_j$ to another state $s_k$ \\n\n",
        "Solution: a path from the initial state $s_i$ to a state sf that satisfies the goal test\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",
        "\"open-loop system\" : \"system without percepts\",\n",
        "\"close-loop system\" : \"system monitors the percepts\",\n",
        "\"completeness\" : \"whether the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not.\",\n",
        "\"optimality/admissibility\" : \"whether the algorithm can find the solution with lowest cost\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "63c8d20d-b567-4e06-bdfe-2a987bfdf2f4"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'completeness' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Goal formulation, Problem formulation, Search (for solution), Execution \n\nA search problem is made up of state space (a directed graph), initial state, goal states, action space, transition model, action cost function \n\nA sequence of actions forms a path, and a solution is a path from the initial state to a goal state.\n\n\n## AIMA Chapter 3.2 Example Problems\n The state space can be infinite. \n\n\n## AIMA Chapter 3.3 Search Algorithms\n The search algorithm superimposes a search tree over the state-space graph. \n\nThe state space describes the (possibly infinite) set of states in the world \n\nThe actions allow transitions from one state to another. \n\nThe search tree describes paths between states, reaching towards the goal. \n\nThe search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root. \n\n\n```\ndef Best_First_Search():\n    frontier = [initial_state]\n    reached = []\n    while frontier:\n        cur = frontier.pop()\n        if isGoal(cur): \n            return True \n        for s in cur.successors: \n            if s.state is not in reached or s.cost < reached[s.state]: ### cost = history_path + action cost\n              reached[s.state] = s \n              frontier.add(s) \n    return False \n```\n\nBest-first search: priority queue frontier \n\nIf the action costs are uniform, we can use BFS and DFS \n\nBFS: FIFO queue frontier \n\nDFS: LIFO stack frontier \n\nWe call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check. \n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n An uninformed search algorithm is given no clue about how close a state is to the goal. \n\nBFS is complete and cost-optimal for the problem where actions have identical cost. \n\nBoth time and space complexity are $O(b^d)$. \n\nDijkstra's algorithm/ uniform-cost search (Best_First_Search) ### uniform-cost is refered to uniform-depth (BFS) \n\nUniform-cost search is complete if all action costs are $\\ge \\epsilon > 0$ \n\nBoth time and space complexity are $O(b^{1 + \\frac{C^*}{\\epsilon}})$ \n\nDepth-first search is not cost-optimal; it returns the first solution it finds, even if it is not cheapest. \n\nFor finite state spaces that are trees DFS is efficient and complete. (For cyclic graph, DFS is not complete) \n\nBacktracking search uses less memory. Only one successor is generated at a time and undo the action after we have DFS it. \n\nTime complexity: $O(b^m)$ and space complexity: $O(bm)$ \n\nIterative Deepening search is complete and cost-optimal. (Depth-limited is not, but iterative deepening is based on depth-limited) \n\nBidirectional is complete and cost-optimal if both directions are breadth-first or uniform-cost.\n\n\n\n## Module 3 Lecture Notes\n Path: a sequence of actions leading from one state $s_j$ to another state $s_k$ \n\nSolution: a path from the initial state $s_i$ to a state sf that satisfies the goal test\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open-loop system** - system without percepts\n* **Close-loop system** - system monitors the percepts\n* **Completeness** - whether the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not.\n* **Optimality/admissibility** - whether the algorithm can find the solution with lowest cost\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",
        "Uninformed search can only access problem definition. \\n\n",
        "Informed search has a heuristic function which estimates cost of the cheapest path from the state to the goal state. \\n\n",
        "Greedy: worst case $O(|V|)$ and best case is DFS \\n\n",
        "A* search is complete and cost-optimal if the heuristic is admissible. \\n\n",
        "Admissible heuristic: $h(n) \\le h^*(n) $ \\n (where $h^*(n)$ is the real cost to the goal state) \\n\n",
        "The proof: \\n\n",
        "Assume all action costs are $\\\\ge \\\\epsilon > 0$\n",
        "Suppose the optimal path has cost $C^*$, but A* returns $C>C^*$ \\n\n",
        "There must be some node $n$ which is on the real optimal path and is unexpanded. \\n\n",
        "(If all the nodes on the optimal path had been expanded, then we would have returned that optimal solution)\\n\n",
        "$f(n) > C > C^*$ (### otherwise $n$ would have been expanded ###) \\n\n",
        "$f(n) = g(n) + h(n) \\le g(n) + h^*(n)$ (admissibility) \\n\n",
        "$f(n) \\le C^*$ \\n (contradiction) \\n\n",
        "Stronger property for graph search is consistency. (triangle inequality) \\n \n",
        "With a consistent heuristic, the first time A* reaches a state it will be on an optimal path. (optimally efficient) \\n\n",
        "The $g$ should be monotonic because the action cost is positive. \\n\n",
        "A* expands all nodes $f(n) < C^*$, might expands some nodes $f(n) = C^*$, never expands nodes $f(n) > C^*$. \\n\n",
        "Weighted A* (enforce the algorithm to be greedy) \\n\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" Misplaced tiles and Manhattan distance are fairly good heuristics. \\n\n",
        "Heuristics can be generated from relaxed problems.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Another proof: \\n\n",
        "Claim that $n$ which is an ancestor of optimal $A$ will be expanded before sub-optimal $B$ \\n\n",
        "$f(n) \\le f(A)$ (admissibility) \\n\n",
        "$f(A) \\le f(B)$ (B is sub-optimal) \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissibility\" : \"an admissible heuristic is one that never overestimates the cost to reach a goal: $h(n) \\le h^*(n)$\", \n",
        "\"consistency\" :  \"$h(n) \\le c(n, a, n') + h(n')$\",\n",
        "\"surely expanded nodes\" : \"$f(n) < C^*\" \n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 891
        },
        "cellView": "form",
        "outputId": "c3dd21f2-b9a8-43fd-adb9-4b42de0f2f46"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nUninformed search can only access problem definition. \n\nInformed search has a heuristic function which estimates cost of the cheapest path from the state to the goal state. \n\nGreedy: worst case $O(|V|)$ and best case is DFS \n\nA* search is complete and cost-optimal if the heuristic is admissible. \n\nAdmissible heuristic: $h(n) \\le h^*(n) $ \n (where $h^*(n)$ is the real cost to the goal state) \n\nThe proof: \n\nAssume all action costs are $\\ge \\epsilon > 0$\nSuppose the optimal path has cost $C^*$, but A* returns $C>C^*$ \n\nThere must be some node $n$ which is on the real optimal path and is unexpanded. \n\n(If all the nodes on the optimal path had been expanded, then we would have returned that optimal solution)\n\n$f(n) > C > C^*$ (### otherwise $n$ would have been expanded ###) \n\n$f(n) = g(n) + h(n) \\le g(n) + h^*(n)$ (admissibility) \n\n$f(n) \\le C^*$ \n (contradiction) \n\nStronger property for graph search is consistency. (triangle inequality) \n \nWith a consistent heuristic, the first time A* reaches a state it will be on an optimal path. (optimally efficient) \n\nThe $g$ should be monotonic because the action cost is positive. \n\nA* expands all nodes $f(n) < C^*$, might expands some nodes $f(n) = C^*$, never expands nodes $f(n) > C^*$. \n\nWeighted A* (enforce the algorithm to be greedy) \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Misplaced tiles and Manhattan distance are fairly good heuristics. \n\nHeuristics can be generated from relaxed problems.\n\n\n## Module 4 Lecture Notes\n Another proof: \n\nClaim that $n$ which is an ancestor of optimal $A$ will be expanded before sub-optimal $B$ \n\n$f(n) \\le f(A)$ (admissibility) \n\n$f(A) \\le f(B)$ (B is sub-optimal) \n\n\n\n## Module 4 Definitions\n* **Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal: $h(n) \\le h^*(n)$\n* **Consistency** - $h(n) \\le c(n, a, n') + h(n')$\n* **Surely expanded nodes** - $f(n) < C^*\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 = \"\"\" Two-player, deterministic, turn-taking, perfect information, zero-sum game.\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" Minimax. Two players MAX & MIN. \\n\n",
        "Alpha–Beta Pruning \\n\n",
        "Alpha: MAX's current lower bound on MAX's outcome \\n\n",
        "Beta: MIN's current upper bound on MIN's outcome \\n\n",
        "MAX will never allow a move that could lead to a worse score (for MAX) than $\\\\alpha$ \\n\n",
        "MIN will never allow a move that could lead to a better score (for MAX) than $\\\\beta$ \\n\n",
        "Therefore, stop evaluating a branch whenever: \\n\n",
        "When evaluating a MAX node: a value $v \\\\ge \\\\beta$ (MIN will never select that MAX node) \\n\n",
        "When evaluating a MIN node: a value $v \\\\le \\\\alpha$ (Max will never select that MIN node) \\n\n",
        "```\n",
        "def AlphaBeta(node, depth, alpha, beta, MAX):\n",
        "    if depth == 0 or node.isTerminal():\n",
        "        return node\n",
        "    if MAX:\n",
        "        value = -inf\n",
        "        for s in node.successors:\n",
        "            value = max(value, AlphaBeta(s, depth-1, alpha, beta, False))\n",
        "            if value >= beta:\n",
        "                break ### prune the branch\n",
        "            alpha = max(alpha, value)\n",
        "        return value\n",
        "    else:\n",
        "        value = inf\n",
        "        for s in node.successors:\n",
        "            value = min(value, AlphaBeta(s, depth-1, alpha, beta, True))\n",
        "            if value <= alpha:\n",
        "                break ### prune the branch\n",
        "            beta = min(beta, value)\n",
        "        return value\n",
        "### initial call\n",
        "AlphaBeta(origin, depth, -inf, inf, True)\n",
        "```\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" Beam search (Forward Pruning) \n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" Expectimax search : calculate expectation at chance node\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" $P(s'|a) = \\\\sum_{s} P(s)P(s'|s,a)$ \\n\n",
        "Expected utility of action $a$: $ EU(a) = \\\\sum_{s'}P(s'|a)U(s') $ \\n\n",
        "action = $\\\\argmax_a EU(a)$ \\n\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" Rational preferences lead to utility.\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" Human judgment is usually irrational.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "Use Epectimax search to save time and space.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"fully observable\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "098f39f6-2eea-4d68-8dfc-943c81137311"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Two-player, deterministic, turn-taking, perfect information, zero-sum game.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax. Two players MAX & MIN. \n\nAlpha–Beta Pruning \n\nAlpha: MAX's current lower bound on MAX's outcome \n\nBeta: MIN's current upper bound on MIN's outcome \n\nMAX will never allow a move that could lead to a worse score (for MAX) than $\\alpha$ \n\nMIN will never allow a move that could lead to a better score (for MAX) than $\\beta$ \n\nTherefore, stop evaluating a branch whenever: \n\nWhen evaluating a MAX node: a value $v \\ge \\beta$ (MIN will never select that MAX node) \n\nWhen evaluating a MIN node: a value $v \\le \\alpha$ (Max will never select that MIN node) \n\n```\ndef AlphaBeta(node, depth, alpha, beta, MAX):\n    if depth == 0 or node.isTerminal():\n        return node\n    if MAX:\n        value = -inf\n        for s in node.successors:\n            value = max(value, AlphaBeta(s, depth-1, alpha, beta, False))\n            if value >= beta:\n                break ### prune the branch\n            alpha = max(alpha, value)\n        return value\n    else:\n        value = inf\n        for s in node.successors:\n            value = min(value, AlphaBeta(s, depth-1, alpha, beta, True))\n            if value <= alpha:\n                break ### prune the branch\n            beta = min(beta, value)\n        return value\n### initial call\nAlphaBeta(origin, depth, -inf, inf, True)\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Beam search (Forward Pruning) \n\n\n## AIMA Chapter 5.5 Stochastic Games\n Expectimax search : calculate expectation at chance node\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n $P(s'|a) = \\sum_{s} P(s)P(s'|s,a)$ \n\nExpected utility of action $a$: $ EU(a) = \\sum_{s'}P(s'|a)U(s') $ \n\naction = $\\argmax_a EU(a)$ \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Rational preferences lead to utility.\n\n\n## AIMA Chapter 16.3 Utility Functions\n Human judgment is usually irrational.\n\n\n## Module 5 Lecture Notes\n \nUse Epectimax search to save time and space.\n\n\n## Module 5 Definitions\n* **Perfect information** - fully observable\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 = \"\"\" CSP consists of $X$, $D$ and $C$. $X$ is set of variables, $D$ is set of domains for variables, $C$ is set of constraints. \\n\n",
        "In general, CSP is NP-complete problem. \\n\n",
        "The best-known category of continuous-domain CSPs is that of linear programming problems, which is also called COP (constrained optimization problem) \\n\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"Local consistency & Constraint propagation \\n\n",
        "Node consistency (unary constraints), Arc consistency tightens down the domains using the binary constraints. \\n\n",
        "Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.) \\n\n",
        "```\n",
        "def AC3(X, D, ARC):\n",
        "    worklist = {(x,y) | arc(x,y) exists}\n",
        "    while worklist:\n",
        "        cur = worklist.pop()\n",
        "        if arc_reduce(x,y):\n",
        "            for arc in ARC:\n",
        "                if (arc[1] == cur[0]) and (arc[0] != cur[1]): ### (z , x) | z != y\n",
        "                    worklist.append(arc)\n",
        "\n",
        "def arc_reduce(x,y):\n",
        "    if len(D(y)) == 1:\n",
        "        c = D(y)[0]\n",
        "        if c in D(x):\n",
        "            D(x).remove(c)\n",
        "            return True\n",
        "    return False\n",
        "```\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" When inference fails, we can make a tentative assignment and then keep inference. \\n\n",
        "If the inference turns out that it is a wrong assignment, then we can backtracking.\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "We can first make a random assignment. \\n\n",
        "Randomly choose the min-conflicted variable and modift its value to satisfy the constraints. \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\" According to structure of CSP, we can implement some tricks to simplify the problem. \\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Heuristic 1: Most constrained variable \\n\n",
        "Heuristic 2: Most constraining variable \\n\n",
        "Heuristic 3: Least constraining value \\n\n",
        "Heuristic 4: Forward checking (Arc consistency & AC-3) \\n\n",
        "AC-3's worst case complexity: $O(n^2d^3)$ (the number of arcs is $O(n^2)$ and checking an arc costs $O(d^2)$ (an arc may need to be checked d times)) \\n\n",
        "For planar constraint graphs, the number of arcs is $O(n)$\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"K-consistency\" : \"A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any the kth variable\",    \n",
        "}\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b0b9fe1e-3f9f-4aea-8d24-658dd94ce012"
      },
      "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": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'K-consistency' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP consists of $X$, $D$ and $C$. $X$ is set of variables, $D$ is set of domains for variables, $C$ is set of constraints. \n\nIn general, CSP is NP-complete problem. \n\nThe best-known category of continuous-domain CSPs is that of linear programming problems, which is also called COP (constrained optimization problem) \n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nLocal consistency & Constraint propagation \n\nNode consistency (unary constraints), Arc consistency tightens down the domains using the binary constraints. \n\nPath consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.) \n\n```\ndef AC3(X, D, ARC):\n    worklist = {(x,y) | arc(x,y) exists}\n    while worklist:\n        cur = worklist.pop()\n        if arc_reduce(x,y):\n            for arc in ARC:\n                if (arc[1] == cur[0]) and (arc[0] != cur[1]): ### (z , x) | z != y\n                    worklist.append(arc)\n\ndef arc_reduce(x,y):\n    if len(D(y)) == 1:\n        c = D(y)[0]\n        if c in D(x):\n            D(x).remove(c)\n            return True\n    return False\n```\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n When inference fails, we can make a tentative assignment and then keep inference. \n\nIf the inference turns out that it is a wrong assignment, then we can backtracking.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nWe can first make a random assignment. \n\nRandomly choose the min-conflicted variable and modift its value to satisfy the constraints. \n\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n According to structure of CSP, we can implement some tricks to simplify the problem. \n\n\n\n## Module 6 Lecture Notes\n Heuristic 1: Most constrained variable \n\nHeuristic 2: Most constraining variable \n\nHeuristic 3: Least constraining value \n\nHeuristic 4: Forward checking (Arc consistency & AC-3) \n\nAC-3's worst case complexity: $O(n^2d^3)$ (the number of arcs is $O(n^2)$ and checking an arc costs $O(d^2)$ (an arc may need to be checked d times)) \n\nFor planar constraint graphs, the number of arcs is $O(n)$\n\n\n## Module 6 Definitions\n* **K-consistency** - A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any the kth variable\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 = \"\"\" Knowledge base \\n\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" PEAS description: Performance measurement, Environment, Actuator, Sensor\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" A logic must also define the semantics. The semantics defines the truth of each sentence. \\n\n",
        "Entailment: $\\\\alpha \\\\models \\\\beta$ iff in every model where $\\\\alpha$ is true, $\\\\beta$ is also true ($M(\\\\alpha) \\\\subset M(\\\\beta)$)\\n\n",
        "If an algorithm $i$ can derive $\\\\alpha$ from $KB$, we write $KB \\\\vdash_i \\\\alpha$\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" The syntax of propositional logic defines the allowable sentences. \\n\n",
        "The atomic sentences consist of a single proposition symbol. Each such symbol (e.g. $P$, $Q$) stands for a proposition that can be true or false. \\n\n",
        "Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. \\n\n",
        "not : $\\\\neg$ (negation) \\n\n",
        "and : $\\\\wedge$ ($\\\\wedge$ looks like \"A\" for \"And\") $P \\\\wedge Q$ is called a conjunction. \\n\n",
        "or ： $\\\\vee$ $P \\\\vee Q$ is called a disjunction. \\n\n",
        "imply : $\\\\Rightarrow$ \\n\n",
        "if and only if: $\\\\Leftrightarrow$\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" logical equivalence: $\\\\alpha \\\\equiv \\\\beta$ iff $\\\\alpha \\\\models \\\\beta$ and $\\\\beta \\\\models \\\\alpha$ \\n\n",
        "$(\\\\alpha \\\\wedge \\\\beta) \\\\equiv (\\\\beta \\\\wedge \\\\alpha)$ \\n\n",
        "$(\\\\alpha \\\\vee \\\\beta) \\\\equiv (\\\\beta \\\\vee \\\\alpha)$ \\n\n",
        "$((\\\\alpha \\\\wedge \\\\beta) \\\\wedge \\\\gamma) \\\\equiv (\\\\alpha \\\\wedge (\\\\beta \\\\wedge \\\\gamma))$ \\n\n",
        "$((\\\\alpha \\\\vee \\\\beta) \\\\vee \\\\gamma) \\\\equiv (\\\\alpha \\\\vee (\\\\beta \\\\vee \\\\gamma))$ \\n\n",
        "$\\\\neg(\\\\neg \\\\alpha) \\equiv \\\\alpha$ \\n\n",
        "$(\\\\alpha \\\\Rightarrow \\\\beta) \\\\equiv (\\\\neg\\\\beta \\\\Rightarrow \\\\neg\\\\alpha)$ \\n\n",
        "$(\\\\alpha \\\\Rightarrow \\\\beta) \\\\equiv (\\\\neg \\\\alpha \\\\vee \\\\beta)$ \\n\n",
        "$(\\\\alpha \\\\Leftrightarrow \\\\beta) \\\\equiv ((\\\\alpha \\\\Rightarrow \\\\beta) \\\\wedge (\\\\beta \\\\Leftrightarrow \\\\alpha))$ \\n\n",
        "$\\\\neg(\\\\alpha \\\\wedge \\\\beta) \\\\equiv (\\\\neg\\\\alpha \\\\vee \\\\neg \\\\beta)$ (De Morgan)\\n\n",
        "$\\\\neg(\\\\alpha \\\\vee \\\\beta) \\\\equiv (\\\\neg\\\\alpha \\\\wedge \\\\neg \\\\beta)$ (De Morgan)\\n\n",
        "$(\\\\alpha \\\\wedge (\\\\beta \\\\vee \\\\gamma)) \\\\equiv ((\\\\alpha \\\\wedge \\\\beta) \\\\vee ( \\\\alpha \\\\wedge \\\\gamma))$ \\n\n",
        "$(\\\\alpha \\\\vee (\\\\beta \\\\wedge \\\\gamma)) \\\\equiv ((\\\\alpha \\\\vee \\\\beta) \\\\wedge ( \\\\alpha \\\\vee \\\\gamma))$ \\n\n",
        "\n",
        "For any sentences $P$ and $Q$, $P \\\\models Q$ if and only if $P \\\\Rightarrow Q$ is valid. \\n\n",
        "Inference rules: \\n\n",
        "$\\\\frac{\\\\alpha \\\\Rightarrow \\\\beta, \\\\alpha}{\\\\beta}$ \\n\n",
        "$\\\\frac{\\\\alpha \\\\wedge \\\\beta}{\\\\beta}$ \\n\n",
        "All logical equivalences can be used as inference rules. \\n\n",
        "Logical systems is monotonicity, the set of entailed sentences can only increase as information is added to the knowledge base. \\n\n",
        "If $KB \\\\models \\\\alpha$ then $KB \\\\wedge \\\\beta \\\\models \\\\alpha$ \\n\n",
        "Resolution: $\\\\frac{(P_1 \\\\vee \\\\cdots \\\\vee P_k) \\\\wedge \\\\neg P_i}{P_1 \\\\vee \\\\cdots \\\\vee P_{i-1} \\\\vee P_{i+1} \\\\vee \\\\cdots \\\\vee P_k}$ \\n\n",
        "The resolution algorithm is complete.\n",
        "Every definite clause can be written as an implication whose premise is a conjunction of positive literals whose conclusion is a positive literal. \\n\n",
        "$(\\\\alpha \\\\Rightarrow \\\\beta) \\\\equiv (\\\\neg \\\\alpha \\\\vee \\\\beta)$ \\n\n",
        "Forward Chaining Algorithm：\n",
        "```\n",
        "def FC(KB, q):\n",
        "    count = {number of clause c's premise}\n",
        "    inferred = {whether symbol s has been inferred}\n",
        "    queue =[initially symbols known to be true]\n",
        "    while queue:\n",
        "        p = queue.pop()\n",
        "        if p == q:\n",
        "            return True\n",
        "        if inferred[p] is False:\n",
        "            inferred[p] == True\n",
        "            for c in {c| where p is in c.Premise}:\n",
        "                count[c] -= 1\n",
        "                if count[c] == 0:\n",
        "                    queue.append(c.Conclusion) ### c is a definite clause $(\\alpha \\\\Rightarrow \\\\beta)$\n",
        "    return False\n",
        "```\n",
        "Forward chaining is complete and sound. \\n\n",
        "Deciding entailment with Horn clauses can be done in time that is linear in the size of knowledge base. \\n\n",
        "Backward chaining is goal-directed reasoning.\n",
        "\"\"\"\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Construct CNF: \\n\n",
        "1. Eliminate $\\\\Leftrightarrow$ by $(\\\\alpha \\\\Leftrightarrow \\\\beta) \\\\equiv ((\\\\alpha \\\\Rightarrow \\\\beta) \\\\wedge (\\\\beta \\\\Leftrightarrow \\\\alpha))$ \\n\n",
        "2. Eliminate $\\\\Rightarrow$ by $(\\\\alpha \\\\Rightarrow \\\\beta) \\\\equiv (\\\\neg \\\\alpha \\\\vee \\\\beta)$ \\n\n",
        "3. Move $\\\\neg$ inwards (only before literals) by De Morgan and double-negation. \\n\n",
        "4. Distribute $\\\\vee$ over $\\wedge$ wherever possible. \\n\n",
        "Resolution Algorithm: \\n\n",
        "To show $KB \\\\models \\\\alpha$, we can show that $KB \\\\wedge \\\\neg\\\\alpha$ is unsatisfiable. \\n\n",
        "1. Convert $KB \\\\wedge \\\\neg\\\\alpha$ into CNF\n",
        "2. Repeat resolution for each pairs of disjunctions until one of two things happens:\n",
        "a) There are no new clauses that can be added. In this case, the KB does not entail $\\\\alpha$\n",
        "b) Two clauses resolve to yield the empty clause (comes from contradiction), in which case the KB does entail $\\\\alpha$\n",
        "Resolution is sound and complete. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Soundness\" : \"the inference algorithm should only derive entailed sentences\", \n",
        "\"Completeness\" : \"An inference algorithm is complete if it can derive all sentences that are entailed.\",\n",
        "\"Validity\" : \"A sentence is valid if it is true in all models. For example, $P \\\\vee \\\\neg P$ is valid.\",\n",
        "\"Satisfiability\" : \"A sentence is satisfiable if it is true in, orsatisfied by some models (assignment).\",\n",
        "\"CNF (Conjunctive Normal Form)\" : \"Every sentence of propositional logic is logically equivalent to a conjunction of clauses which are disjunctions of literals.\",\n",
        "\"Definite clause\" : \"disjunction of literals where exactly one is positive\",\n",
        "\"Horn clause\" : \"disjunction of literals where at most one is positive\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e30ed752-6e1a-4519-f8c2-35fe01d065ce"
      },
      "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": 19,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge base \n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n PEAS description: Performance measurement, Environment, Actuator, Sensor\n\n\n## AIMA Chapter 7.3 Logic\n A logic must also define the semantics. The semantics defines the truth of each sentence. \n\nEntailment: $\\alpha \\models \\beta$ iff in every model where $\\alpha$ is true, $\\beta$ is also true ($M(\\alpha) \\subset M(\\beta)$)\n\nIf an algorithm $i$ can derive $\\alpha$ from $KB$, we write $KB \\vdash_i \\alpha$\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. \n\nThe atomic sentences consist of a single proposition symbol. Each such symbol (e.g. $P$, $Q$) stands for a proposition that can be true or false. \n\nComplex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. \n\nnot : $\\neg$ (negation) \n\nand : $\\wedge$ ($\\wedge$ looks like \"A\" for \"And\") $P \\wedge Q$ is called a conjunction. \n\nor ： $\\vee$ $P \\vee Q$ is called a disjunction. \n\nimply : $\\Rightarrow$ \n\nif and only if: $\\Leftrightarrow$\n\n\n## AIMA 7.5 Propositional Theorem Proving\n logical equivalence: $\\alpha \\equiv \\beta$ iff $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$ \n\n$(\\alpha \\wedge \\beta) \\equiv (\\beta \\wedge \\alpha)$ \n\n$(\\alpha \\vee \\beta) \\equiv (\\beta \\vee \\alpha)$ \n\n$((\\alpha \\wedge \\beta) \\wedge \\gamma) \\equiv (\\alpha \\wedge (\\beta \\wedge \\gamma))$ \n\n$((\\alpha \\vee \\beta) \\vee \\gamma) \\equiv (\\alpha \\vee (\\beta \\vee \\gamma))$ \n\n$\\neg(\\neg \\alpha) \\equiv \\alpha$ \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg\\beta \\Rightarrow \\neg\\alpha)$ \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n$(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n$\\neg(\\alpha \\wedge \\beta) \\equiv (\\neg\\alpha \\vee \\neg \\beta)$ (De Morgan)\n\n$\\neg(\\alpha \\vee \\beta) \\equiv (\\neg\\alpha \\wedge \\neg \\beta)$ (De Morgan)\n\n$(\\alpha \\wedge (\\beta \\vee \\gamma)) \\equiv ((\\alpha \\wedge \\beta) \\vee ( \\alpha \\wedge \\gamma))$ \n\n$(\\alpha \\vee (\\beta \\wedge \\gamma)) \\equiv ((\\alpha \\vee \\beta) \\wedge ( \\alpha \\vee \\gamma))$ \n\n\nFor any sentences $P$ and $Q$, $P \\models Q$ if and only if $P \\Rightarrow Q$ is valid. \n\nInference rules: \n\n$\\frac{\\alpha \\Rightarrow \\beta, \\alpha}{\\beta}$ \n\n$\\frac{\\alpha \\wedge \\beta}{\\beta}$ \n\nAll logical equivalences can be used as inference rules. \n\nLogical systems is monotonicity, the set of entailed sentences can only increase as information is added to the knowledge base. \n\nIf $KB \\models \\alpha$ then $KB \\wedge \\beta \\models \\alpha$ \n\nResolution: $\\frac{(P_1 \\vee \\cdots \\vee P_k) \\wedge \\neg P_i}{P_1 \\vee \\cdots \\vee P_{i-1} \\vee P_{i+1} \\vee \\cdots \\vee P_k}$ \n\nThe resolution algorithm is complete.\nEvery definite clause can be written as an implication whose premise is a conjunction of positive literals whose conclusion is a positive literal. \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\nForward Chaining Algorithm：\n```\ndef FC(KB, q):\n    count = {number of clause c's premise}\n    inferred = {whether symbol s has been inferred}\n    queue =[initially symbols known to be true]\n    while queue:\n        p = queue.pop()\n        if p == q:\n            return True\n        if inferred[p] is False:\n            inferred[p] == True\n            for c in {c| where p is in c.Premise}:\n                count[c] -= 1\n                if count[c] == 0:\n                    queue.append(c.Conclusion) ### c is a definite clause $(\u0007lpha \\Rightarrow \\beta)$\n    return False\n```\nForward chaining is complete and sound. \n\nDeciding entailment with Horn clauses can be done in time that is linear in the size of knowledge base. \n\nBackward chaining is goal-directed reasoning.\n\n\n## Module 7 Lecture Notes\n\nConstruct CNF: \n\n1. Eliminate $\\Leftrightarrow$ by $(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n2. Eliminate $\\Rightarrow$ by $(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n3. Move $\\neg$ inwards (only before literals) by De Morgan and double-negation. \n\n4. Distribute $\\vee$ over $\\wedge$ wherever possible. \n\nResolution Algorithm: \n\nTo show $KB \\models \\alpha$, we can show that $KB \\wedge \\neg\\alpha$ is unsatisfiable. \n\n1. Convert $KB \\wedge \\neg\\alpha$ into CNF\n2. Repeat resolution for each pairs of disjunctions until one of two things happens:\na) There are no new clauses that can be added. In this case, the KB does not entail $\\alpha$\nb) Two clauses resolve to yield the empty clause (comes from contradiction), in which case the KB does entail $\\alpha$\nResolution is sound and complete. \n\n\n\n## Module 7 Definitions\n* **Soundness** - the inference algorithm should only derive entailed sentences\n* **Completeness** - An inference algorithm is complete if it can derive all sentences that are entailed.\n* **Validity** - A sentence is valid if it is true in all models. For example, $P \\vee \\neg P$ is valid.\n* **Satisfiability** - A sentence is satisfiable if it is true in, orsatisfied by some models (assignment).\n* **Cnf (conjunctive normal form)** - Every sentence of propositional logic is logically equivalent to a conjunction of clauses which are disjunctions of literals.\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at most one is positive\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": "51d6bc05-166a-4879-ab3f-c1386ca3bc14"
      },
      "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": 20,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n We can define AI from different perspectives. There are two dimensions: human vs. rational and thought vs. behavior. \n \nActing humanly: The Turing test approach (NLP, knowledge representation, automated reasoning, ML; Total Turing Test : CV, robotics) \n\nThinking humanly: The cognitive modeling approach (introspection, psychological experiments, brain imaging, cognitive science) \n\nThinking rationally: The logic approach (syllogisms, logic, probability)\n\nActing rationally: The rational agent approach (standard model (to achieve an objective), limited rationality) \n\nBeneficial machines where objective can not be specified (value alignment problem, provably beneficial)\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Weak AI：machines could act as if they were intelligent \n\nStrong AI: general AI which can solve an arbitrarily wide variety of tasks \n\nGood Old-Fashioned AI: logical agent for qualification problem \n\nNot all tasks can be achieved by the AI because of the informality of the behavior (eg. human's informal guidelines), machine's disability and mathematical limit (Godel Theorem).\n\n\n## AIMA Chapter 27.2 Can Machines Really Think?\n \nThe process of thinking is not important, the result matters.\n\n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n A rational agent is one that does the right thing. We need a criterion to measure the performance of the agent. \n \nFor each possible #percept sequence#, a rational agent should select an #action# that is expected to maximize its #performance measure#, given the #prior knowledge# the agent has.\nOmniscience is impossible in the reality. So the agent needs information gathering and learn from it. Rationality maximizes expected performance. Autonomy means the agent does not rely on the prior knowledge.\n\n\n## AIMA 2.3 The Nature of Environments\n PEAS (Performance, Environment, Actuators, Sensors) \n\nThe environment may be partially observable. or unobservable. \n\nThe environment can be multi-agent (competitive or cooperative). \n\nThe next state of the environment can be nondeterministic. \n\nThe behavior can be episodic or sequential.\nThe enviroment can be static, semidynamic (environment itself does not change, but the performance measurement changes) or dynamic. \n\nThe time can be discrete or continuous. \n\nThe prior knowledge can be known or unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture \n\nThe agent programs take the current percept as input from the sensors and return an action to the actuators. The agent = architecture + program.\n\nAgents need internal state, transition model and sensor model and choose action according to the utility to achieve the goal. \n\nLearning agents require the reward and penalty. \n\nThe transitions between states can be atomic, factored and structured.\n\n\n## Module 1 Lecture Notes\n Brain in the tank.\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - gathering information from an environment\n* **Utility** - performance measurement\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Objects of built-in types like (int, float, bool, str, tuple, unicode) are immutable and hashable.\n\n\n## Module 2 Definitions\n* **Mutability** - If an object is mutable, its state can be changed after declared.\n\n\n## WARNING: Your definition of 'completeness' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Goal formulation, Problem formulation, Search (for solution), Execution \n\nA search problem is made up of state space (a directed graph), initial state, goal states, action space, transition model, action cost function \n\nA sequence of actions forms a path, and a solution is a path from the initial state to a goal state.\n\n\n## AIMA Chapter 3.2 Example Problems\n The state space can be infinite. \n\n\n## AIMA Chapter 3.3 Search Algorithms\n The search algorithm superimposes a search tree over the state-space graph. \n\nThe state space describes the (possibly infinite) set of states in the world \n\nThe actions allow transitions from one state to another. \n\nThe search tree describes paths between states, reaching towards the goal. \n\nThe search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root. \n\n\n```\ndef Best_First_Search():\n    frontier = [initial_state]\n    reached = []\n    while frontier:\n        cur = frontier.pop()\n        if isGoal(cur): \n            return True \n        for s in cur.successors: \n            if s.state is not in reached or s.cost < reached[s.state]: ### cost = history_path + action cost\n              reached[s.state] = s \n              frontier.add(s) \n    return False \n```\n\nBest-first search: priority queue frontier \n\nIf the action costs are uniform, we can use BFS and DFS \n\nBFS: FIFO queue frontier \n\nDFS: LIFO stack frontier \n\nWe call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check. \n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n An uninformed search algorithm is given no clue about how close a state is to the goal. \n\nBFS is complete and cost-optimal for the problem where actions have identical cost. \n\nBoth time and space complexity are $O(b^d)$. \n\nDijkstra's algorithm/ uniform-cost search (Best_First_Search) ### uniform-cost is refered to uniform-depth (BFS) \n\nUniform-cost search is complete if all action costs are $\\ge \\epsilon > 0$ \n\nBoth time and space complexity are $O(b^{1 + \\frac{C^*}{\\epsilon}})$ \n\nDepth-first search is not cost-optimal; it returns the first solution it finds, even if it is not cheapest. \n\nFor finite state spaces that are trees DFS is efficient and complete. (For cyclic graph, DFS is not complete) \n\nBacktracking search uses less memory. Only one successor is generated at a time and undo the action after we have DFS it. \n\nTime complexity: $O(b^m)$ and space complexity: $O(bm)$ \n\nIterative Deepening search is complete and cost-optimal. (Depth-limited is not, but iterative deepening is based on depth-limited) \n\nBidirectional is complete and cost-optimal if both directions are breadth-first or uniform-cost.\n\n\n\n## Module 3 Lecture Notes\n Path: a sequence of actions leading from one state $s_j$ to another state $s_k$ \n\nSolution: a path from the initial state $s_i$ to a state sf that satisfies the goal test\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open-loop system** - system without percepts\n* **Close-loop system** - system monitors the percepts\n* **Completeness** - whether the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not.\n* **Optimality/admissibility** - whether the algorithm can find the solution with lowest cost\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nUninformed search can only access problem definition. \n\nInformed search has a heuristic function which estimates cost of the cheapest path from the state to the goal state. \n\nGreedy: worst case $O(|V|)$ and best case is DFS \n\nA* search is complete and cost-optimal if the heuristic is admissible. \n\nAdmissible heuristic: $h(n) \\le h^*(n) $ \n (where $h^*(n)$ is the real cost to the goal state) \n\nThe proof: \n\nAssume all action costs are $\\ge \\epsilon > 0$\nSuppose the optimal path has cost $C^*$, but A* returns $C>C^*$ \n\nThere must be some node $n$ which is on the real optimal path and is unexpanded. \n\n(If all the nodes on the optimal path had been expanded, then we would have returned that optimal solution)\n\n$f(n) > C > C^*$ (### otherwise $n$ would have been expanded ###) \n\n$f(n) = g(n) + h(n) \\le g(n) + h^*(n)$ (admissibility) \n\n$f(n) \\le C^*$ \n (contradiction) \n\nStronger property for graph search is consistency. (triangle inequality) \n \nWith a consistent heuristic, the first time A* reaches a state it will be on an optimal path. (optimally efficient) \n\nThe $g$ should be monotonic because the action cost is positive. \n\nA* expands all nodes $f(n) < C^*$, might expands some nodes $f(n) = C^*$, never expands nodes $f(n) > C^*$. \n\nWeighted A* (enforce the algorithm to be greedy) \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Misplaced tiles and Manhattan distance are fairly good heuristics. \n\nHeuristics can be generated from relaxed problems.\n\n\n## Module 4 Lecture Notes\n Another proof: \n\nClaim that $n$ which is an ancestor of optimal $A$ will be expanded before sub-optimal $B$ \n\n$f(n) \\le f(A)$ (admissibility) \n\n$f(A) \\le f(B)$ (B is sub-optimal) \n\n\n\n## Module 4 Definitions\n* **Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal: $h(n) \\le h^*(n)$\n* **Consistency** - $h(n) \\le c(n, a, n') + h(n')$\n* **Surely expanded nodes** - $f(n) < C^*\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Two-player, deterministic, turn-taking, perfect information, zero-sum game.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax. Two players MAX & MIN. \n\nAlpha–Beta Pruning \n\nAlpha: MAX's current lower bound on MAX's outcome \n\nBeta: MIN's current upper bound on MIN's outcome \n\nMAX will never allow a move that could lead to a worse score (for MAX) than $\\alpha$ \n\nMIN will never allow a move that could lead to a better score (for MAX) than $\\beta$ \n\nTherefore, stop evaluating a branch whenever: \n\nWhen evaluating a MAX node: a value $v \\ge \\beta$ (MIN will never select that MAX node) \n\nWhen evaluating a MIN node: a value $v \\le \\alpha$ (Max will never select that MIN node) \n\n```\ndef AlphaBeta(node, depth, alpha, beta, MAX):\n    if depth == 0 or node.isTerminal():\n        return node\n    if MAX:\n        value = -inf\n        for s in node.successors:\n            value = max(value, AlphaBeta(s, depth-1, alpha, beta, False))\n            if value >= beta:\n                break ### prune the branch\n            alpha = max(alpha, value)\n        return value\n    else:\n        value = inf\n        for s in node.successors:\n            value = min(value, AlphaBeta(s, depth-1, alpha, beta, True))\n            if value <= alpha:\n                break ### prune the branch\n            beta = min(beta, value)\n        return value\n### initial call\nAlphaBeta(origin, depth, -inf, inf, True)\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Beam search (Forward Pruning) \n\n\n## AIMA Chapter 5.5 Stochastic Games\n Expectimax search : calculate expectation at chance node\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n $P(s'|a) = \\sum_{s} P(s)P(s'|s,a)$ \n\nExpected utility of action $a$: $ EU(a) = \\sum_{s'}P(s'|a)U(s') $ \n\naction = $\\argmax_a EU(a)$ \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Rational preferences lead to utility.\n\n\n## AIMA Chapter 16.3 Utility Functions\n Human judgment is usually irrational.\n\n\n## Module 5 Lecture Notes\n \nUse Epectimax search to save time and space.\n\n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n\n\n## WARNING: Your definition of 'K-consistency' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP consists of $X$, $D$ and $C$. $X$ is set of variables, $D$ is set of domains for variables, $C$ is set of constraints. \n\nIn general, CSP is NP-complete problem. \n\nThe best-known category of continuous-domain CSPs is that of linear programming problems, which is also called COP (constrained optimization problem) \n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nLocal consistency & Constraint propagation \n\nNode consistency (unary constraints), Arc consistency tightens down the domains using the binary constraints. \n\nPath consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.) \n\n```\ndef AC3(X, D, ARC):\n    worklist = {(x,y) | arc(x,y) exists}\n    while worklist:\n        cur = worklist.pop()\n        if arc_reduce(x,y):\n            for arc in ARC:\n                if (arc[1] == cur[0]) and (arc[0] != cur[1]): ### (z , x) | z != y\n                    worklist.append(arc)\n\ndef arc_reduce(x,y):\n    if len(D(y)) == 1:\n        c = D(y)[0]\n        if c in D(x):\n            D(x).remove(c)\n            return True\n    return False\n```\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n When inference fails, we can make a tentative assignment and then keep inference. \n\nIf the inference turns out that it is a wrong assignment, then we can backtracking.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nWe can first make a random assignment. \n\nRandomly choose the min-conflicted variable and modift its value to satisfy the constraints. \n\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n According to structure of CSP, we can implement some tricks to simplify the problem. \n\n\n\n## Module 6 Lecture Notes\n Heuristic 1: Most constrained variable \n\nHeuristic 2: Most constraining variable \n\nHeuristic 3: Least constraining value \n\nHeuristic 4: Forward checking (Arc consistency & AC-3) \n\nAC-3's worst case complexity: $O(n^2d^3)$ (the number of arcs is $O(n^2)$ and checking an arc costs $O(d^2)$ (an arc may need to be checked d times)) \n\nFor planar constraint graphs, the number of arcs is $O(n)$\n\n\n## Module 6 Definitions\n* **K-consistency** - A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any the kth variable\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge base \n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n PEAS description: Performance measurement, Environment, Actuator, Sensor\n\n\n## AIMA Chapter 7.3 Logic\n A logic must also define the semantics. The semantics defines the truth of each sentence. \n\nEntailment: $\\alpha \\models \\beta$ iff in every model where $\\alpha$ is true, $\\beta$ is also true ($M(\\alpha) \\subset M(\\beta)$)\n\nIf an algorithm $i$ can derive $\\alpha$ from $KB$, we write $KB \\vdash_i \\alpha$\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. \n\nThe atomic sentences consist of a single proposition symbol. Each such symbol (e.g. $P$, $Q$) stands for a proposition that can be true or false. \n\nComplex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. \n\nnot : $\\neg$ (negation) \n\nand : $\\wedge$ ($\\wedge$ looks like \"A\" for \"And\") $P \\wedge Q$ is called a conjunction. \n\nor ： $\\vee$ $P \\vee Q$ is called a disjunction. \n\nimply : $\\Rightarrow$ \n\nif and only if: $\\Leftrightarrow$\n\n\n## AIMA 7.5 Propositional Theorem Proving\n logical equivalence: $\\alpha \\equiv \\beta$ iff $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$ \n\n$(\\alpha \\wedge \\beta) \\equiv (\\beta \\wedge \\alpha)$ \n\n$(\\alpha \\vee \\beta) \\equiv (\\beta \\vee \\alpha)$ \n\n$((\\alpha \\wedge \\beta) \\wedge \\gamma) \\equiv (\\alpha \\wedge (\\beta \\wedge \\gamma))$ \n\n$((\\alpha \\vee \\beta) \\vee \\gamma) \\equiv (\\alpha \\vee (\\beta \\vee \\gamma))$ \n\n$\\neg(\\neg \\alpha) \\equiv \\alpha$ \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg\\beta \\Rightarrow \\neg\\alpha)$ \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n$(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n$\\neg(\\alpha \\wedge \\beta) \\equiv (\\neg\\alpha \\vee \\neg \\beta)$ (De Morgan)\n\n$\\neg(\\alpha \\vee \\beta) \\equiv (\\neg\\alpha \\wedge \\neg \\beta)$ (De Morgan)\n\n$(\\alpha \\wedge (\\beta \\vee \\gamma)) \\equiv ((\\alpha \\wedge \\beta) \\vee ( \\alpha \\wedge \\gamma))$ \n\n$(\\alpha \\vee (\\beta \\wedge \\gamma)) \\equiv ((\\alpha \\vee \\beta) \\wedge ( \\alpha \\vee \\gamma))$ \n\n\nFor any sentences $P$ and $Q$, $P \\models Q$ if and only if $P \\Rightarrow Q$ is valid. \n\nInference rules: \n\n$\\frac{\\alpha \\Rightarrow \\beta, \\alpha}{\\beta}$ \n\n$\\frac{\\alpha \\wedge \\beta}{\\beta}$ \n\nAll logical equivalences can be used as inference rules. \n\nLogical systems is monotonicity, the set of entailed sentences can only increase as information is added to the knowledge base. \n\nIf $KB \\models \\alpha$ then $KB \\wedge \\beta \\models \\alpha$ \n\nResolution: $\\frac{(P_1 \\vee \\cdots \\vee P_k) \\wedge \\neg P_i}{P_1 \\vee \\cdots \\vee P_{i-1} \\vee P_{i+1} \\vee \\cdots \\vee P_k}$ \n\nThe resolution algorithm is complete.\nEvery definite clause can be written as an implication whose premise is a conjunction of positive literals whose conclusion is a positive literal. \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\nForward Chaining Algorithm：\n```\ndef FC(KB, q):\n    count = {number of clause c's premise}\n    inferred = {whether symbol s has been inferred}\n    queue =[initially symbols known to be true]\n    while queue:\n        p = queue.pop()\n        if p == q:\n            return True\n        if inferred[p] is False:\n            inferred[p] == True\n            for c in {c| where p is in c.Premise}:\n                count[c] -= 1\n                if count[c] == 0:\n                    queue.append(c.Conclusion) ### c is a definite clause $(\u0007lpha \\Rightarrow \\beta)$\n    return False\n```\nForward chaining is complete and sound. \n\nDeciding entailment with Horn clauses can be done in time that is linear in the size of knowledge base. \n\nBackward chaining is goal-directed reasoning.\n\n\n## Module 7 Lecture Notes\n\nConstruct CNF: \n\n1. Eliminate $\\Leftrightarrow$ by $(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n2. Eliminate $\\Rightarrow$ by $(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n3. Move $\\neg$ inwards (only before literals) by De Morgan and double-negation. \n\n4. Distribute $\\vee$ over $\\wedge$ wherever possible. \n\nResolution Algorithm: \n\nTo show $KB \\models \\alpha$, we can show that $KB \\wedge \\neg\\alpha$ is unsatisfiable. \n\n1. Convert $KB \\wedge \\neg\\alpha$ into CNF\n2. Repeat resolution for each pairs of disjunctions until one of two things happens:\na) There are no new clauses that can be added. In this case, the KB does not entail $\\alpha$\nb) Two clauses resolve to yield the empty clause (comes from contradiction), in which case the KB does entail $\\alpha$\nResolution is sound and complete. \n\n\n\n## Module 7 Definitions\n* **Soundness** - the inference algorithm should only derive entailed sentences\n* **Completeness** - An inference algorithm is complete if it can derive all sentences that are entailed.\n* **Validity** - A sentence is valid if it is true in all models. For example, $P \\vee \\neg P$ is valid.\n* **Satisfiability** - A sentence is satisfiable if it is true in, orsatisfied by some models (assignment).\n* **Cnf (conjunctive normal form)** - Every sentence of propositional logic is logically equivalent to a conjunction of clauses which are disjunctions of literals.\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at most one is positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}