{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "486490ea-9407-4981-c580-81f990fc4380"
      },
      "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": 73,
      "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": "b3a70e8f-230d-4fce-b82f-cfbd52a9e5f6"
      },
      "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": 74,
      "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": 75,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. \\\n",
        "An agent's choice of actions at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on \n",
        "anything it hasn't perceived.  \"\"\"\n",
        "chapter2_2 = \"\"\" We evaluate an agent's behavior by its consequences. The notion of desirability is captured by a performance measure that \n",
        "evaluates any given sequence of environment states. As a genral rule, it's better to design performance measures accordingto what one actually wants to be achieved in the \n",
        "environment rather than according to how one thinks the agent should behave. \n",
        "The same agent would be irrational under different circumstances. \n",
        "\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"Task environment: 1) Fully obsevable vs partially observable vs unobservable(no sensor)\n",
        "2) single-agent vs multiagent: whether B's behavior is best described as maximizing a performance measure whose value depends on agent A's behavior.\n",
        "Can be competitive or cooperative. e.g. communication often emerges as a rational behavior in multiagent environments; in some competitive environments, \n",
        "randomized behavior is rational because it avoids the pitfalls of predictability. \n",
        "3) deterministic vs nondeterministic: stochastic is synonym for nondeterministic, except that stochastic model deals with probabilites, while in nondeterminisitc model \n",
        "the possibilities are listed without being quantifies.\n",
        "4) episodic vs sequential : in episodic TE, the next episode does not depend on the actions taken in previous episodes; in seq envir, the current \n",
        "decision could affect all future decisions. \n",
        "5) static vs dynamic: the envir can change or not while an agent is deliberating. If the envir itself does not change with the passage of time but \n",
        "the agent's performance score does, then smidynamic.\n",
        "6) discrete vs continuous 7) known vs unknown: refers not to envir itself but to agent's (or designer's) state of knowledge about the environment. (new video game) \n",
        "The hardest: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" agent function vs agent program: agent program taks the current percept as input, the agent function may depend on the entire percept histroy.\n",
        "Four kinds of agent programs: see definitions. \n",
        "model-based reflex agent: the transition model (of the world) and sensor model allow an agent to keep track of the state of the world.\n",
        "In two kings of cases, utility wins goal: 1) Tradeoff: when there are conflicting goals 2)likelihood: when there are several goals, none of which be achieved with certainty\n",
        "All agents can improve their performance through learning.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"content agent's sensor are perceiving\",\n",
        "\"agent function\" : \"maps any given percept sequence to an action mathematically\",\n",
        "\"agent program\" : \"implementation of  the agent function running within some physical system\",\n",
        "\"agent architecture\" : \"agent = architecture(computing device with physical sensors and acuators) + program\",\n",
        "\"rational agent\": \"for each percept seq, it should select an action that is expected to maximize its performance measure\",\n",
        "\"Autonomy\" : \"a rational agent should learn what it can do to compensate for partial or incorrect prior knowledge\",\n",
        "\"Task environment\" : \"PEAS\",\n",
        "\"simple reflex agent (used in fully observable)\" : \"select actions based on the current percept, ignoring the rest of history\",\n",
        "\"model-based reflex agent\" : \"the agent maintain some internal state that depends on the percept history\",\n",
        "\"goal-based agents\" : \"act to achieve their goals. Search and planning\",\n",
        "\"utility-based agents\" : \"try to maximize their own expected happiness\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 76,
      "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": "55182633-1595-4c98-ecbe-77be099d0306"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 77,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. An agent's choice of actions at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on \nanything it hasn't perceived.  \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n We evaluate an agent's behavior by its consequences. The notion of desirability is captured by a performance measure that \nevaluates any given sequence of environment states. As a genral rule, it's better to design performance measures accordingto what one actually wants to be achieved in the \nenvironment rather than according to how one thinks the agent should behave. \nThe same agent would be irrational under different circumstances. \n\n\n\n## AIMA 2.3 The Nature of Environments\nTask environment: 1) Fully obsevable vs partially observable vs unobservable(no sensor)\n2) single-agent vs multiagent: whether B's behavior is best described as maximizing a performance measure whose value depends on agent A's behavior.\nCan be competitive or cooperative. e.g. communication often emerges as a rational behavior in multiagent environments; in some competitive environments, \nrandomized behavior is rational because it avoids the pitfalls of predictability. \n3) deterministic vs nondeterministic: stochastic is synonym for nondeterministic, except that stochastic model deals with probabilites, while in nondeterminisitc model \nthe possibilities are listed without being quantifies.\n4) episodic vs sequential : in episodic TE, the next episode does not depend on the actions taken in previous episodes; in seq envir, the current \ndecision could affect all future decisions. \n5) static vs dynamic: the envir can change or not while an agent is deliberating. If the envir itself does not change with the passage of time but \nthe agent's performance score does, then smidynamic.\n6) discrete vs continuous 7) known vs unknown: refers not to envir itself but to agent's (or designer's) state of knowledge about the environment. (new video game) \nThe hardest: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n agent function vs agent program: agent program taks the current percept as input, the agent function may depend on the entire percept histroy.\nFour kinds of agent programs: see definitions. \nmodel-based reflex agent: the transition model (of the world) and sensor model allow an agent to keep track of the state of the world.\nIn two kings of cases, utility wins goal: 1) Tradeoff: when there are conflicting goals 2)likelihood: when there are several goals, none of which be achieved with certainty\nAll agents can improve their performance through learning.\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content agent's sensor are perceiving\n* **Agent function** - maps any given percept sequence to an action mathematically\n* **Agent program** - implementation of  the agent function running within some physical system\n* **Agent architecture** - agent = architecture(computing device with physical sensors and acuators) + program\n* **Rational agent** - for each percept seq, it should select an action that is expected to maximize its performance measure\n* **Autonomy** - a rational agent should learn what it can do to compensate for partial or incorrect prior knowledge\n* **Task environment** - PEAS\n* **Simple reflex agent (used in fully observable)** - select actions based on the current percept, ignoring the rest of history\n* **Model-based reflex agent** - the agent maintain some internal state that depends on the percept history\n* **Goal-based agents** - act to achieve their goals. Search and planning\n* **Utility-based agents** - try to maximize their own expected happiness\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 78,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "51661ca7-d7a6-40e7-f414-cddd345b9058"
      },
      "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": 79,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" \n",
        "```\n",
        "funtion best-first-search(problem, f) returns a solution node or failure\n",
        "  node := NODE(state=problem.initial)\n",
        "  frontier := a priority queue ordered by f, with node as an elemnt\n",
        "  reached := a lookup table, problem.initial: node\n",
        "  while not is-empty(frontier) do\n",
        "    node := pop(frontier)\n",
        "    if problem.is-goal(node.state) then return node\n",
        "    for each child in expand(problem, node) do\n",
        "      s := child.state\n",
        "      if s is not in reached or child.path-cost < reached[s].path-cost then\n",
        "        reached[s] := child\n",
        "        add child to frontier\n",
        "  return failure\n",
        "\n",
        "function expand(problem, node) yields nodes\n",
        "  s := node.state\n",
        "  for each action in problem.actions(s) do\n",
        "    s' := problem.result(s,a)\n",
        "    cost := node.path-cost + problem.action-cost(s, action, s')\n",
        "    yield NODE(state=s', parent=node, action=action, path-cost=cost)\n",
        "```\n",
        "Redundant path: 1)we can remember all previously reached states 2) we call a search algorithm a graph search if it checks for redundant paths \n",
        "and a tree-like search if it does not check 3) only check cycles\n",
        "```\n",
        "function uniform-cost-search/Dijkstra(problem) returns a solution node or failure\n",
        "  return best-first-search(problem, path-cost)\n",
        "```\n",
        " \"\"\"\n",
        "\n",
        " \n",
        "chapter3_4 = \"\"\" \n",
        "```\n",
        "function iterative-deepening search(problem) returns a solution of failure\n",
        "  for depth=0 to inf do\n",
        "    result := depth-limited-search(problem, depth)\n",
        "    if result != cutoff then return result\n",
        "\n",
        "function depth-limited-search(problem,l) returns a node or failure or cutoff\n",
        "  frontier := a LIFO queue with NODE(problem.initial) as an element\n",
        "  result := failure\n",
        "  while not is-empty(frontier) do\n",
        "    node := pop(frontier)\n",
        "    if problem.is-goal(node.state) then return node\n",
        "    if depth(node) > l then\n",
        "      result := cutoff\n",
        "    else if not is-cycle(node) do \n",
        "      for each child in expand(problem, node) do\n",
        "        add child to frontier\n",
        "  return result\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",  \n",
        "\"atomic representation\" : \"state considered as whole, with no internal structure\",\n",
        "\"informed\" : \"the agent can estimate how far it is from goal\",\n",
        "\"Search Problem\" : \"a set of possible states, initial state, goal states, action, transition model, action cost function\",\n",
        "\"expand\" : \"generating child nodes for a node\",\n",
        "\"frontier\" : \"unexpanded nodes\",\n",
        "\"best-first search\" : \"we choose a node n with minimum value of some evaluation function f(n)\",\n",
        "\"bidirectional search\" : \"simultaneously seacnes forward from the initial state and backwards from the goal state(s)\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 80,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5cdab23d-66a2-46f5-dce0-f9d902924042"
      },
      "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": 81,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n \n```\nfuntion best-first-search(problem, f) returns a solution node or failure\n  node := NODE(state=problem.initial)\n  frontier := a priority queue ordered by f, with node as an elemnt\n  reached := a lookup table, problem.initial: node\n  while not is-empty(frontier) do\n    node := pop(frontier)\n    if problem.is-goal(node.state) then return node\n    for each child in expand(problem, node) do\n      s := child.state\n      if s is not in reached or child.path-cost < reached[s].path-cost then\n        reached[s] := child\n        add child to frontier\n  return failure\n\nfunction expand(problem, node) yields nodes\n  s := node.state\n  for each action in problem.actions(s) do\n    s' := problem.result(s,a)\n    cost := node.path-cost + problem.action-cost(s, action, s')\n    yield NODE(state=s', parent=node, action=action, path-cost=cost)\n```\nRedundant path: 1)we can remember all previously reached states 2) we call a search algorithm a graph search if it checks for redundant paths \nand a tree-like search if it does not check 3) only check cycles\n```\nfunction uniform-cost-search/Dijkstra(problem) returns a solution node or failure\n  return best-first-search(problem, path-cost)\n```\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n```\nfunction iterative-deepening search(problem) returns a solution of failure\n  for depth=0 to inf do\n    result := depth-limited-search(problem, depth)\n    if result != cutoff then return result\n\nfunction depth-limited-search(problem,l) returns a node or failure or cutoff\n  frontier := a LIFO queue with NODE(problem.initial) as an element\n  result := failure\n  while not is-empty(frontier) do\n    node := pop(frontier)\n    if problem.is-goal(node.state) then return node\n    if depth(node) > l then\n      result := cutoff\n    else if not is-cycle(node) do \n      for each child in expand(problem, node) do\n        add child to frontier\n  return result\n```\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Atomic representation** - state considered as whole, with no internal structure\n* **Informed** - the agent can estimate how far it is from goal\n* **Search problem** - a set of possible states, initial state, goal states, action, transition model, action cost function\n* **Expand** - generating child nodes for a node\n* **Frontier** - unexpanded nodes\n* **Best-first search** - we choose a node n with minimum value of some evaluation function f(n)\n* **Bidirectional search** - simultaneously seacnes forward from the initial state and backwards from the goal state(s)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Greedy best-first search: not optimal, not complete (can get stuck in loops). \\\n",
        "A* is complete.With a admissible heuristic, A* is optimal. A* is efficient beacuse it prunes away search tree nodes that are not necessary for finding an optimal solution. \n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"The heuristic accuracy influences performance. \n",
        "effective branching factor b*: if the total number of nodes generated by A* for a problem is N and the solution depth is d, then b* is the \n",
        "branching factor that a uniform tree of the depth d would have to have in order to contain N+1 nodes. Thus N+1 = 1+b*+(b*)^2 +...+(b*)^d. \n",
        "A well-design heuristic would have a value of b* close to 1. From the definition of two heuristics (both admissible), if for any node n, h2(n) >= h1(n), we say h2 dominates h1. \n",
        "Generating heuristic from relaxed problems: a problem with fewer restrictions on the actions is called a relaxed problem. \n",
        "The cost of an optimal solution to a relaxed problem is an admissible an admissible heuristic for the original problem.(also consistent)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"h(n)\" : \"estimated cost of the cheapest path from the state at node n to a goal state\",\n",
        "\"greedy best-first search\" : \"expands first the node with the lowest h(n) value\" ,\n",
        "\"A* search\" : \"a best-first search uses the evaluation function f(n) = g(n)+h(n)\",  \n",
        "\"admissible heuristic\" : \"never overestimate the cost to reach a goal\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 82,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 477
        },
        "cellView": "form",
        "outputId": "c7cd44a9-d13e-4a9f-f01c-a4a8b4b5348a"
      },
      "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": 83,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy best-first search: not optimal, not complete (can get stuck in loops). A* is complete.With a admissible heuristic, A* is optimal. A* is efficient beacuse it prunes away search tree nodes that are not necessary for finding an optimal solution. \n\n\n## AIMA Chapter 3.6 Heuristic Functions\nThe heuristic accuracy influences performance. \neffective branching factor b*: if the total number of nodes generated by A* for a problem is N and the solution depth is d, then b* is the \nbranching factor that a uniform tree of the depth d would have to have in order to contain N+1 nodes. Thus N+1 = 1+b*+(b*)^2 +...+(b*)^d. \nA well-design heuristic would have a value of b* close to 1. From the definition of two heuristics (both admissible), if for any node n, h2(n) >= h1(n), we say h2 dominates h1. \nGenerating heuristic from relaxed problems: a problem with fewer restrictions on the actions is called a relaxed problem. \nThe cost of an optimal solution to a relaxed problem is an admissible an admissible heuristic for the original problem.(also consistent)\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **H(n)** - estimated cost of the cheapest path from the state at node n to a goal state\n* **Greedy best-first search** - expands first the node with the lowest h(n) value\n* **A* search** - a best-first search uses the evaluation function f(n) = g(n)+h(n)\n* **Admissible heuristic** - never overestimate the cost to reach a goal\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "```\n",
        "function MINIMAX-SEARCH(game, state) returns an action\n",
        "  player := game.TO-MOVE(state)\n",
        "  value, move := MAX-VALUE(gmae, state)\n",
        "  return move\n",
        "\n",
        "function MAX-VALUE(game, state) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n",
        "  v := -inf\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2, a2 := MIN-VALUE(game, game.RESULT(state, a))\n",
        "    if v2 > v then\n",
        "      v, move := v2, a\n",
        "  return v, move\n",
        "\n",
        "function MIN-VALUE(game, state) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n",
        "  v := inf\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2, a2 := MAX-VALUE(game, game.RESULT(state, a))\n",
        "    if v2 < v then\n",
        "      v, move := v2, a\n",
        "  return v, move\n",
        "```\n",
        "If b is legal moves at each point, m is the maximum depth of tree, time complexity: O(b^m), space O(bm) (or O(m)). \n",
        "For multiplayer games,the backed-up value of a node n is the utility vector of the successor state with the highest value for the player choosing at n. \n",
        "alpha-beta pruning: alpha = the value of the best (highest value) choice we have found so far at the choice point along the path for max. a = at least. \n",
        "beta = the value of the best (lowest value) choice we have found so far at any choice point along the path for min. b = at most. \n",
        "The effectiveness of alpha-beta pruning is highly dependent on the order in which the states are examined. If this could be done perfectly, alpha-beta would need\n",
        "to examine only O(b^{m/2}) instead of O(b^m), wich means the effective branching factor becomes sqrt(b). Trying first the moves that were found \n",
        "to be best in the past: killer move heuristic. Also use transposition table that caches the heuristic value of states. Minimax won't work for games \n",
        "like chess and Go, because there are too many states to explore in the time available. Type A Strategy considers all possible moves to a certain depth, then \n",
        "use a heuristic evaluation function to estimate the utility of states at that depth. wide but shallow. Type B Strategy ignores moves that look bad, go \n",
        "as far as possible. deep but narrow.\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic Games tree must include chance nodes in adddition to max and min nodes. \n",
        "Expectiminimax value for games with chance nodes: terminal nodes and max and min nodes work exactly the same way as before. For chance nodes we compute \n",
        "the expected value. \n",
        "The program behaved totally differently if we make a change to some of the evaluation values, even if the preference order remains the same. The evaluation function \n",
        "must return values that are a positive linear ransformation of the probability of winning ( or of the expeceted utility). Expectiminimax take O(b^mn^m), where n is the \n",
        "number of distinct rolls.\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = r\"\"\" The agent's preferences are captured by a utility function U(s) which assigned a single number to express the desirability of a state. \n",
        "The expected utility of an action given the evidence: $EU(a) = \\sum_{s^\\prime} P(Result(a)=s^\\prime)U(s^\\prime)$, \n",
        "$P(Result(a)=s^\\prime) = \\sum_s P(s)P(s^\\prime|s,a)$. Maximum expected utility: $action = argmax_a EU(a)$. \n",
        "If an agent acts so as to maximize a utility function (internal) that correctly reflects the performance measure(external), then the agent \n",
        "will achieve the highest possible performance score. The performance measure gives a score for a history - a sequence of states. Thus it is applied retrospectively after an agent completes a sequence of actions. \n",
        "The utility functio applies to the very next state, so it can be used to guide actions step by step.\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" existence of a utility function that describes an agent's preference behavior does not necessayrily mean that the agent is explicity\n",
        "maximizing that utility function in its own deliberations \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"ply\" : \"one move by one player\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 84,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "070b009d-6f5f-4ad9-e196-2b78caac4c94"
      },
      "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": 85,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n```\nfunction MINIMAX-SEARCH(game, state) returns an action\n  player := game.TO-MOVE(state)\n  value, move := MAX-VALUE(gmae, state)\n  return move\n\nfunction MAX-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v := -inf\n  for each a in game.ACTIONS(state) do\n    v2, a2 := MIN-VALUE(game, game.RESULT(state, a))\n    if v2 > v then\n      v, move := v2, a\n  return v, move\n\nfunction MIN-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v := inf\n  for each a in game.ACTIONS(state) do\n    v2, a2 := MAX-VALUE(game, game.RESULT(state, a))\n    if v2 < v then\n      v, move := v2, a\n  return v, move\n```\nIf b is legal moves at each point, m is the maximum depth of tree, time complexity: O(b^m), space O(bm) (or O(m)). \nFor multiplayer games,the backed-up value of a node n is the utility vector of the successor state with the highest value for the player choosing at n. \nalpha-beta pruning: alpha = the value of the best (highest value) choice we have found so far at the choice point along the path for max. a = at least. \nbeta = the value of the best (lowest value) choice we have found so far at any choice point along the path for min. b = at most. \nThe effectiveness of alpha-beta pruning is highly dependent on the order in which the states are examined. If this could be done perfectly, alpha-beta would need\nto examine only O(b^{m/2}) instead of O(b^m), wich means the effective branching factor becomes sqrt(b). Trying first the moves that were found \nto be best in the past: killer move heuristic. Also use transposition table that caches the heuristic value of states. Minimax won't work for games \nlike chess and Go, because there are too many states to explore in the time available. Type A Strategy considers all possible moves to a certain depth, then \nuse a heuristic evaluation function to estimate the utility of states at that depth. wide but shallow. Type B Strategy ignores moves that look bad, go \nas far as possible. deep but narrow.\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic Games tree must include chance nodes in adddition to max and min nodes. \nExpectiminimax value for games with chance nodes: terminal nodes and max and min nodes work exactly the same way as before. For chance nodes we compute \nthe expected value. \nThe program behaved totally differently if we make a change to some of the evaluation values, even if the preference order remains the same. The evaluation function \nmust return values that are a positive linear ransformation of the probability of winning ( or of the expeceted utility). Expectiminimax take O(b^mn^m), where n is the \nnumber of distinct rolls.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n The agent's preferences are captured by a utility function U(s) which assigned a single number to express the desirability of a state. \nThe expected utility of an action given the evidence: $EU(a) = \\sum_{s^\\prime} P(Result(a)=s^\\prime)U(s^\\prime)$, \n$P(Result(a)=s^\\prime) = \\sum_s P(s)P(s^\\prime|s,a)$. Maximum expected utility: $action = argmax_a EU(a)$. \nIf an agent acts so as to maximize a utility function (internal) that correctly reflects the performance measure(external), then the agent \nwill achieve the highest possible performance score. The performance measure gives a score for a history - a sequence of states. Thus it is applied retrospectively after an agent completes a sequence of actions. \nThe utility functio applies to the very next state, so it can be used to guide actions step by step.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n existence of a utility function that describes an agent's preference behavior does not necessayrily mean that the agent is explicity\nmaximizing that utility function in its own deliberations \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Ply** - one move by one player\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 = \"\"\"In search algorithm, each state is atomic and indivisible(a black box with no internal structure).\\\n",
        "In constraint satisfaction problem, we use a factored representation for each state: a set of variables, each of which has\\\n",
        "a value. A CSP has 3 components, X is a set of variables,D is a set of domains,one for each variable,C is a set of constraints.\\\n",
        "Each constaints Cj consists of a pair <scope, rel>, e.g. <(X1,X2), {(3,1),(3,2),(2,1)}> or <(X1,X2),X1>X2>.\\\n",
        "Variations of CSP:\n",
        "1)domains: a. discrete, finite (8-queens); b. infinite (eg set of integers), we must use implicit constraints like T1+d1<=T2 \n",
        "rather than explicit tuples of values. linear constraints on integer variables are solvable while nonlinear constraints\n",
        " on integer variable is undecidable. c. continuous domains: linear programming.\n",
        " 2)contraints: number of variables - a.unary, binary, tenary b.global(involving an arbitrary number of variables, eg Alldiff).\n",
        " every finite-domain constraints can be reduced to a set of binary constraints, using dual graph approach for instance.\n",
        " Preference constraints - can often be encoded as costs on individual variable assignments. Also called constrained optimazation \n",
        " problem.\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\"A CSP can make progress / rule out values by two way: search(assignment) and inference(constaint propagation).Constraint propagation is a specific type of inference, whose main idea is using the constraints to reduce the \n",
        "number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on. The process\n",
        " of enforcing local consistency in each part of the constraint graph causes inconsistent values to be eliminated throughout the graph.\n",
        "```\n",
        "function AC-3(csp) returns false if an inconsistency is found and true otherwise\n",
        "  queue := a queue of arcs, initially all the arcs in csp\n",
        "  while queue is not empty do\n",
        "    (Xi, Xj) := POP(queue)\n",
        "    if REVISE(csp, Xi, Xj) then\n",
        "      if size of Di = 0 then return false\n",
        "      for each Xk in Xi.NEIGHBORS - {Xj} do\n",
        "        add(Xk, Xi) to queue\n",
        "  return true\n",
        "\n",
        "function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi\n",
        "  revised := false\n",
        "  for each x in Di do\n",
        "    if no value y in Dj allows (x,y) to satisfu the constraint between Xi and Xj then\n",
        "      delete x from Di\n",
        "      revised := true\n",
        "  return revised\n",
        "```\n",
        "Time complexity: n variables, domain size d, c constraints, O(cd^3).\n",
        "How to solve a strong n-consistent CSP: first choose a consistent value for X1, then for X2, then for X3,...For each variable Xi, we \n",
        "need to only search through the d values in the domain to find a value consistent with X1,...X_{i-1}. Total run time O(n^2d).\n",
        "A simple consistency procedure for a higher-order constraint is sometimes more effective than applying arc consistency to an equivalent set of binary constraints. \n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "```\n",
        "function backtracking-search(csp) returns a solution or failure\n",
        "  return backtrack(csp,{})\n",
        "\n",
        "function backtrack(csp, assignment) returns a solution or failure\n",
        "  if assignment is complete then return assignment\n",
        "  var := select-unassigned-variable(csp, assignment)\n",
        "  for each value in order-domain-values(csp, var, assignment) do\n",
        "    if value is consistent with assignment then\n",
        "      add {var = value} to assignment\n",
        "      inferences := inference(csp, var, assignment)\n",
        "      if inferences != failure then \n",
        "        add inferences to csp\n",
        "        result := backtrack(csp, assignment)\n",
        "        if result != failure then return result\n",
        "        remove inferences from csp\n",
        "      remove {var=value} from assignment\n",
        "  return failure\n",
        "```\n",
        "Improve above by domain-independent heuristics:\n",
        "minimum-remaining-values(more powerful): most constrained variable / fail-first; \n",
        "degree heuristic(tie breaker): reduce the branching factore on future choices by selecting variables that is involved in the largest number of constraints on other unassigned variables; \n",
        "least-constraining-value: value that rules out the fewest choices for the neighboring variables.\n",
        "Interleaving search and inference: 1) simple inference: forward checking: Whenever X is assigned, for each unassigned variable Y that is \n",
        "connected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for X. This method doesn't look ahead far enough. \\\\\n",
        "2) Maintaining Arc Consistency: after Xi is assigned, the inference procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs(Xj, Xi) \n",
        "for all Xj that are unassigned variables that are neighbors of Xi. From there, AC-3 does constaint propagration in teh usual way, but if any variable'domain reduced to empty set, \n",
        "the call to AC-3 fails and then we do backtrack.\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Independence can be ascertained by finding connnected components of the constrained graph. Suppose each CSPi has c variables, \n",
        "there're n/c subproblems. Total work is O(d^c n/c) linear in n. Without decomposition, O(d^n). \n",
        "Any tree with n nodes has n-1 edges, so we can make this graph directed arc-consistent in O(n) steps, taotl runtime O(nd^2). \n",
        "Reduce a constraint graph to a tree: 1) removing nodes (cutset conditioning) 2)collapsing nodes together(tree decomposition). The aim of choosing a tree\n",
        " decomposition is to make the subproblems as small as possible. O(nd^{w+1}), w = tree width. tree decompostion ia always faster than cutset conditioning.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP\" : \"A problem is solved when each variable has a value that satisfies all the constraints on the variable\",\n",
        "\"Consistent/legal assignment\" : \"An assignment that doesn't violate any constraints\",\n",
        "\"Complete assignment\" : \"every variable is assigned a value\",\n",
        "\"Solution\" : \"a consistent, complete assignment\",\n",
        "\"Partial assignment\" : \"leaves some variables unassigned\",\n",
        "\"Partial solution\" : \"a partial assignment that is consistent\",\n",
        "\"binary CSP\" : \"with only unary and binary constraints\",\n",
        "\"Node consistency\" : \"a single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints\",\n",
        "\"Xi Arc consistency wrt Xj\" : \"for all val in Di, exists val in Dj that satisfies binary constraints on (Xi,Xj)\",\n",
        "\"AC graph\" : \"every variable is AC with every other variable\",\n",
        "\"{Xi,Xj} Path consistency wrt Xm\" : \"for every consistent assignment {Xi=a,Xj=b}, exists an assignment to Xm that satisfies the constraints on {Xi, Xm} and {Xm, Xj}\",\n",
        "\"K-consistency\" : \"for any k-1 vars, with any consistent assignment to them, a consistent val can always be assigned to any kth\",\n",
        "\"Srong k-consistent\": \"it's k-consistent, k-1 consisitent,...1-consistent\",\n",
        "\"Global constraint\" : \"one involving arbitrary number of variables(but not necessarily all variables)\",\n",
        "\"Alldiff\" : \"if m varables are involved, and n possible distinct values altogether, m > n, then the constraint can't be satisfied\",\n",
        "\"Atmost\" : \"checking the sum of minimum values of the current domains, for large set, use bounds propagation/bounds-consistent\",\n",
        "\"Conflict set\" : \"if every possible val for Xj fails, backjump to the most recent Xi, conf(Xi) := conf(Xi) + conf(Xj) - {Xi}\",\n",
        "\"Constraint learning\" : \"finding a minimum set from the conflct set that causes the problem, the set along with values called no-good\",\n",
        "\"Tree CSP\": \"any two varibles are connnected by only one path, can be solved in linear in number of variables\",\n",
        "\"directional arc consistency\" : \"given an ordering of X1...Xn, iff every Xi is AC with each Xj for j > i\",\n",
        "\"cycle cutset\" : \"choose a subset S of the CSP's varibles such that the constraint graph becomes a tree after removel of S\",\n",
        "\"tree width\" : \"one less than the size of the largest node\"\n",
        "}\n"
      ],
      "execution_count": 86,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Xd4qOBM_TECU"
      },
      "source": [
        ""
      ],
      "execution_count": 86,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "cc947a7b-f2ad-4114-ff4c-280443824cc3"
      },
      "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": 87,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nIn search algorithm, each state is atomic and indivisible(a black box with no internal structure).In constraint satisfaction problem, we use a factored representation for each state: a set of variables, each of which hasa value. A CSP has 3 components, X is a set of variables,D is a set of domains,one for each variable,C is a set of constraints.Each constaints Cj consists of a pair <scope, rel>, e.g. <(X1,X2), {(3,1),(3,2),(2,1)}> or <(X1,X2),X1>X2>.Variations of CSP:\n1)domains: a. discrete, finite (8-queens); b. infinite (eg set of integers), we must use implicit constraints like T1+d1<=T2 \nrather than explicit tuples of values. linear constraints on integer variables are solvable while nonlinear constraints\n on integer variable is undecidable. c. continuous domains: linear programming.\n 2)contraints: number of variables - a.unary, binary, tenary b.global(involving an arbitrary number of variables, eg Alldiff).\n every finite-domain constraints can be reduced to a set of binary constraints, using dual graph approach for instance.\n Preference constraints - can often be encoded as costs on individual variable assignments. Also called constrained optimazation \n problem.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nA CSP can make progress / rule out values by two way: search(assignment) and inference(constaint propagation).Constraint propagation is a specific type of inference, whose main idea is using the constraints to reduce the \nnumber of legal values for a variable, which in turn can reduce the legal values for another variable, and so on. The process\n of enforcing local consistency in each part of the constraint graph causes inconsistent values to be eliminated throughout the graph.\n```\nfunction AC-3(csp) returns false if an inconsistency is found and true otherwise\n  queue := a queue of arcs, initially all the arcs in csp\n  while queue is not empty do\n    (Xi, Xj) := POP(queue)\n    if REVISE(csp, Xi, Xj) then\n      if size of Di = 0 then return false\n      for each Xk in Xi.NEIGHBORS - {Xj} do\n        add(Xk, Xi) to queue\n  return true\n\nfunction REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi\n  revised := false\n  for each x in Di do\n    if no value y in Dj allows (x,y) to satisfu the constraint between Xi and Xj then\n      delete x from Di\n      revised := true\n  return revised\n```\nTime complexity: n variables, domain size d, c constraints, O(cd^3).\nHow to solve a strong n-consistent CSP: first choose a consistent value for X1, then for X2, then for X3,...For each variable Xi, we \nneed to only search through the d values in the domain to find a value consistent with X1,...X_{i-1}. Total run time O(n^2d).\nA simple consistency procedure for a higher-order constraint is sometimes more effective than applying arc consistency to an equivalent set of binary constraints. \n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n```\nfunction backtracking-search(csp) returns a solution or failure\n  return backtrack(csp,{})\n\nfunction backtrack(csp, assignment) returns a solution or failure\n  if assignment is complete then return assignment\n  var := select-unassigned-variable(csp, assignment)\n  for each value in order-domain-values(csp, var, assignment) do\n    if value is consistent with assignment then\n      add {var = value} to assignment\n      inferences := inference(csp, var, assignment)\n      if inferences != failure then \n        add inferences to csp\n        result := backtrack(csp, assignment)\n        if result != failure then return result\n        remove inferences from csp\n      remove {var=value} from assignment\n  return failure\n```\nImprove above by domain-independent heuristics:\nminimum-remaining-values(more powerful): most constrained variable / fail-first; \ndegree heuristic(tie breaker): reduce the branching factore on future choices by selecting variables that is involved in the largest number of constraints on other unassigned variables; \nleast-constraining-value: value that rules out the fewest choices for the neighboring variables.\nInterleaving search and inference: 1) simple inference: forward checking: Whenever X is assigned, for each unassigned variable Y that is \nconnected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for X. This method doesn't look ahead far enough. \\\n2) Maintaining Arc Consistency: after Xi is assigned, the inference procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs(Xj, Xi) \nfor all Xj that are unassigned variables that are neighbors of Xi. From there, AC-3 does constaint propagration in teh usual way, but if any variable'domain reduced to empty set, \nthe call to AC-3 fails and then we do backtrack.\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Independence can be ascertained by finding connnected components of the constrained graph. Suppose each CSPi has c variables, \nthere're n/c subproblems. Total work is O(d^c n/c) linear in n. Without decomposition, O(d^n). \nAny tree with n nodes has n-1 edges, so we can make this graph directed arc-consistent in O(n) steps, taotl runtime O(nd^2). \nReduce a constraint graph to a tree: 1) removing nodes (cutset conditioning) 2)collapsing nodes together(tree decomposition). The aim of choosing a tree\n decomposition is to make the subproblems as small as possible. O(nd^{w+1}), w = tree width. tree decompostion ia always faster than cutset conditioning.\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Csp** - A problem is solved when each variable has a value that satisfies all the constraints on the variable\n* **Consistent/legal assignment** - An assignment that doesn't violate any constraints\n* **Complete assignment** - every variable is assigned a value\n* **Solution** - a consistent, complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - a partial assignment that is consistent\n* **Binary csp** - with only unary and binary constraints\n* **Node consistency** - a single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints\n* **Xi arc consistency wrt xj** - for all val in Di, exists val in Dj that satisfies binary constraints on (Xi,Xj)\n* **Ac graph** - every variable is AC with every other variable\n* **{xi,xj} path consistency wrt xm** - for every consistent assignment {Xi=a,Xj=b}, exists an assignment to Xm that satisfies the constraints on {Xi, Xm} and {Xm, Xj}\n* **K-consistency** - for any k-1 vars, with any consistent assignment to them, a consistent val can always be assigned to any kth\n* **Srong k-consistent** - it's k-consistent, k-1 consisitent,...1-consistent\n* **Global constraint** - one involving arbitrary number of variables(but not necessarily all variables)\n* **Alldiff** - if m varables are involved, and n possible distinct values altogether, m > n, then the constraint can't be satisfied\n* **Atmost** - checking the sum of minimum values of the current domains, for large set, use bounds propagation/bounds-consistent\n* **Conflict set** - if every possible val for Xj fails, backjump to the most recent Xi, conf(Xi) := conf(Xi) + conf(Xj) - {Xi}\n* **Constraint learning** - finding a minimum set from the conflct set that causes the problem, the set along with values called no-good\n* **Tree csp** - any two varibles are connnected by only one path, can be solved in linear in number of variables\n* **Directional arc consistency** - given an ordering of X1...Xn, iff every Xi is AC with each Xj for j > i\n* **Cycle cutset** - choose a subset S of the CSP's varibles such that the constraint graph becomes a tree after removel of S\n* **Tree width** - one less than the size of the largest node\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 = \"\"\"Agent program is called: 1) tells the KB what it perceives 2) asks the KB what action it should perform 3)tells the KB which action was chosen and returns \\\n",
        "the action so that is can be execured.\"\"\"\n",
        "chapter7_2 = \"\"\"\"\"\"\n",
        "chapter7_3 = r\"\"\" In standard logics, every sentence must be either true or false in each possible world.\\\n",
        "If a sentence a is true in model m, we say m satisfies a or m is a model of a. M(a) = set of all models of a.\\\n",
        "Model checking inference: enumerates all possible models to check $M(KB) \\subseteq M(\\alpha)$.\\\n",
        "If an inference algorithm i can derive $\\alpha$ from KB, $KB \\vdash_i \\alpha$.\\\n",
        "Sound/truth-preserving: an inference algo derives only entailes sentences.\\\n",
        "Completeness: it can derive any sentence that is entailed.\\\n",
        "Grouding: how do we know that KB is true in the real world(sensing a percept + learning a general rule).\"\"\"\n",
        "chapter7_4 = \"\"\"From truth table, the truth value of any sentence s can be computed wrt any model m by a simple recursive evaluation.\n",
        "```\n",
        "function TT-ENTAILS?(KB, a) returns true or false\n",
        "  inputs: KB, a(the query, a sentence in PL)\n",
        "  symbols := a list of the proposition symbols in KB and a\n",
        "  return TT-CHECK-ALL(KB, a, symbols, {})\n",
        "\n",
        "  function TT-CHECK-ALL(KB, a, symbols, model) returns true or false\n",
        "    if EMPTY?(symbols) then\n",
        "      if PL-TRUE?(KB, model) then return PL-TRUE?(a,model)\n",
        "      else return true\n",
        "    else\n",
        "      P := FIRST(symbols)\n",
        "      rest := REST(symbols)\n",
        "      return (TT-CHECK-ALL(KB, a, rest, model+{P=true})\n",
        "              and\n",
        "              TT-CHECK-ALL(KB, a, rest, model+{P=false}))\n",
        "```\n",
        "Time complexity: O(2^n), Space: O(n) (depth-first).This problem is co-NP-complete, so every known algo has a worst case complexity that is exponential in the size of the input.\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\"Define a proof problem using search: initial state - the initial KB; actions/result - all inference rules applied to all the top-half-form sentences/add bottom-half-form sentence to KB;\\\n",
        "goal - a state contains the sentence we want to prove.\\\n",
        "Resolution + Complete search algorithm = Complete Inference Algorithm.\\\n",
        "Full resolution:1) Only one pair of complementary literals at a time 2) factoring: result contains only one copy of each literal.\\\n",
        "Resolution inference works because: 1)every sentence can be converted into a CNF 2）how: \n",
        "```\n",
        "function PL-RESOLUTION(KB,a) returns true or false\n",
        "  inputs: KB, a(a sentence)\n",
        "  clauses := the set of clauses in CNF of KB && neg a\n",
        "  new := {}\n",
        "  while true do\n",
        "    for each pair of clauses Ci, Cj in clauses do\n",
        "      resolvents := PL-RESOLVE(Ci,Cj)\n",
        "      if resolvents contains the empty clause then return true\n",
        "      new.add(resolvents)\n",
        "    if new in clauses then return false\n",
        "    clauses.add(new)\n",
        "```\n",
        "Every difinite clause can be written as an implication whose premise(body) is conjuction of positive literals and whose conclusion(head) is a single positive literal.\\\n",
        "Forward chaining takes O(KB) time, while backward chaining takes even less.\n",
        "```\n",
        "function PL-FC-ENTAILS?(KB, q) returns true or flase\n",
        "  input: KB, q(a proposition symbol)\n",
        "  count := a table, where count[c] is initially the number of symbols in clause c's premise\n",
        "  inferred := a table, where inferred[s] is initially flase for all symbols\n",
        "  queue := a queue of symbols, initially sumbols known to be true in KB\n",
        "  while queue is not empty do\n",
        "    p := POP(queue)\n",
        "    if p = q then return true\n",
        "    if inferred[p] = false then\n",
        "       inferred[p] := true\n",
        "       for each clause c in KB where p is in c.PREMISE do\n",
        "         count[c]--\n",
        "         if count[c] = 0 then add c.CONCLUSION to queue\n",
        "  return false\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"KB\": \"a set of sentences(assertion about the world in knowledge representation language)\",\n",
        "\"axiom\":\"a sentence being given without being derived from other sentences\",\n",
        "\"declarative approach\":\"starting from empty KB, designer tells sentences one by one until the agent knows how to operate\",\n",
        "\"procedural approach\":\"encodes desired behaviors directly\",\n",
        "\"model\" : \"mathematical abstractions of possible world, which has a fixed truth value for every relevent sentence\",\n",
        "\"entailment\" : r\"$\\alpha \\models \\beta \\text{ iff } M(\\alpha) \\subseteq M(\\beta)$\",\n",
        "\"Syntax\" : \"defins the allowable sentences\",\n",
        "\"atomic sentence\" : \"consists of a single proposition symbol\",\n",
        "\"Symbol\" : \"Ture,False,P,Q,R stands for a proposition that can be true or false\",\n",
        "\"Complex sentences\" : \"constructed from simpler sentences using () and logical connectives\",\n",
        "\"Semantic\" : \"defines the rules for determining the truth of a sentence wrt a particular model\",\n",
        "\"logical equivalence\" : \"two sentences are LE if they're T in the same set of models, one can be entailed from the other\", \n",
        "\"theorem proving\" : \"apply rules of inference to the sentences in KB to construct a proof\\\n",
        "of the desired sentence without consulting models\",\n",
        "\"Validity\" : \"A sentence is true for all models\",\n",
        "\"Satisfiable\" : \"satisfied by some model\",\n",
        "\"deduction theorem\" : \"For any a and b, a entails b iff a implies b is valid \",\n",
        "\"Proof by contradiction\": \"KB entails a iff KB and neg a is unsatisfiable\",\n",
        "\"Monotonicity\" : \"if KB entails a, then KB and b entails a(new assertion can't invalidate any conlusion already inferred)\",\n",
        "\"Resolution\" : \"takes two clauses and produces a new clause containing all literals except two complementary literals\",\n",
        "\"factoring\" : \"removal of multiple copies of literals\",\n",
        "\"CNF\" : \"Conjuctive normal form\",\n",
        "\"ground resolution theorem\" : \"If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause\",\n",
        "\"definite clauses\" : \"exaclyt one literal is positive\",\n",
        "\"horn clauses\" : \"at most one is positive\",\n",
        "\"goal clauses\" : \"no positive literal\",\n",
        "\"fact\" : \"a sentence consisting of a single positive literal\",\n",
        "\"literal\" : r\"Symbol or $\\neg$Symbol\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 88,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "d90e51e2-b123-4c12-980b-f028e0b5942c"
      },
      "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": 89,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nAgent program is called: 1) tells the KB what it perceives 2) asks the KB what action it should perform 3)tells the KB which action was chosen and returns the action so that is can be execured.\n\n## AIMA Chapter 7.2 The Wumpus World\n\n\n## AIMA Chapter 7.3 Logic\n In standard logics, every sentence must be either true or false in each possible world.If a sentence a is true in model m, we say m satisfies a or m is a model of a. M(a) = set of all models of a.Model checking inference: enumerates all possible models to check $M(KB) \\subseteq M(\\alpha)$.If an inference algorithm i can derive $\\alpha$ from KB, $KB \\vdash_i \\alpha$.Sound/truth-preserving: an inference algo derives only entailes sentences.Completeness: it can derive any sentence that is entailed.Grouding: how do we know that KB is true in the real world(sensing a percept + learning a general rule).\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nFrom truth table, the truth value of any sentence s can be computed wrt any model m by a simple recursive evaluation.\n```\nfunction TT-ENTAILS?(KB, a) returns true or false\n  inputs: KB, a(the query, a sentence in PL)\n  symbols := a list of the proposition symbols in KB and a\n  return TT-CHECK-ALL(KB, a, symbols, {})\n\n  function TT-CHECK-ALL(KB, a, symbols, model) returns true or false\n    if EMPTY?(symbols) then\n      if PL-TRUE?(KB, model) then return PL-TRUE?(a,model)\n      else return true\n    else\n      P := FIRST(symbols)\n      rest := REST(symbols)\n      return (TT-CHECK-ALL(KB, a, rest, model+{P=true})\n              and\n              TT-CHECK-ALL(KB, a, rest, model+{P=false}))\n```\nTime complexity: O(2^n), Space: O(n) (depth-first).This problem is co-NP-complete, so every known algo has a worst case complexity that is exponential in the size of the input.\n \n\n## AIMA 7.5 Propositional Theorem Proving\nDefine a proof problem using search: initial state - the initial KB; actions/result - all inference rules applied to all the top-half-form sentences/add bottom-half-form sentence to KB;goal - a state contains the sentence we want to prove.Resolution + Complete search algorithm = Complete Inference Algorithm.Full resolution:1) Only one pair of complementary literals at a time 2) factoring: result contains only one copy of each literal.Resolution inference works because: 1)every sentence can be converted into a CNF 2）how: \n```\nfunction PL-RESOLUTION(KB,a) returns true or false\n  inputs: KB, a(a sentence)\n  clauses := the set of clauses in CNF of KB && neg a\n  new := {}\n  while true do\n    for each pair of clauses Ci, Cj in clauses do\n      resolvents := PL-RESOLVE(Ci,Cj)\n      if resolvents contains the empty clause then return true\n      new.add(resolvents)\n    if new in clauses then return false\n    clauses.add(new)\n```\nEvery difinite clause can be written as an implication whose premise(body) is conjuction of positive literals and whose conclusion(head) is a single positive literal.Forward chaining takes O(KB) time, while backward chaining takes even less.\n```\nfunction PL-FC-ENTAILS?(KB, q) returns true or flase\n  input: KB, q(a proposition symbol)\n  count := a table, where count[c] is initially the number of symbols in clause c's premise\n  inferred := a table, where inferred[s] is initially flase for all symbols\n  queue := a queue of symbols, initially sumbols known to be true in KB\n  while queue is not empty do\n    p := POP(queue)\n    if p = q then return true\n    if inferred[p] = false then\n       inferred[p] := true\n       for each clause c in KB where p is in c.PREMISE do\n         count[c]--\n         if count[c] = 0 then add c.CONCLUSION to queue\n  return false\n```\n\n\n## Module 7 Lecture Notes\n\n\n## Module 7 Definitions\n* **Kb** - a set of sentences(assertion about the world in knowledge representation language)\n* **Axiom** - a sentence being given without being derived from other sentences\n* **Declarative approach** - starting from empty KB, designer tells sentences one by one until the agent knows how to operate\n* **Procedural approach** - encodes desired behaviors directly\n* **Model** - mathematical abstractions of possible world, which has a fixed truth value for every relevent sentence\n* **Entailment** - $\\alpha \\models \\beta \\text{ iff } M(\\alpha) \\subseteq M(\\beta)$\n* **Syntax** - defins the allowable sentences\n* **Atomic sentence** - consists of a single proposition symbol\n* **Symbol** - Ture,False,P,Q,R stands for a proposition that can be true or false\n* **Complex sentences** - constructed from simpler sentences using () and logical connectives\n* **Semantic** - defines the rules for determining the truth of a sentence wrt a particular model\n* **Logical equivalence** - two sentences are LE if they're T in the same set of models, one can be entailed from the other\n* **Theorem proving** - apply rules of inference to the sentences in KB to construct a proofof the desired sentence without consulting models\n* **Validity** - A sentence is true for all models\n* **Satisfiable** - satisfied by some model\n* **Deduction theorem** - For any a and b, a entails b iff a implies b is valid \n* **Proof by contradiction** - KB entails a iff KB and neg a is unsatisfiable\n* **Monotonicity** - if KB entails a, then KB and b entails a(new assertion can't invalidate any conlusion already inferred)\n* **Resolution** - takes two clauses and produces a new clause containing all literals except two complementary literals\n* **Factoring** - removal of multiple copies of literals\n* **Cnf** - Conjuctive normal form\n* **Ground resolution theorem** - If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause\n* **Definite clauses** - exaclyt one literal is positive\n* **Horn clauses** - at most one is positive\n* **Goal clauses** - no positive literal\n* **Fact** - a sentence consisting of a single positive literal\n* **Literal** - Symbol or $\\neg$Symbol\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": "3e754e06-1dc9-4584-f66f-b17c806f11e5"
      },
      "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": 90,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. An agent's choice of actions at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on \nanything it hasn't perceived.  \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n We evaluate an agent's behavior by its consequences. The notion of desirability is captured by a performance measure that \nevaluates any given sequence of environment states. As a genral rule, it's better to design performance measures accordingto what one actually wants to be achieved in the \nenvironment rather than according to how one thinks the agent should behave. \nThe same agent would be irrational under different circumstances. \n\n\n\n## AIMA 2.3 The Nature of Environments\nTask environment: 1) Fully obsevable vs partially observable vs unobservable(no sensor)\n2) single-agent vs multiagent: whether B's behavior is best described as maximizing a performance measure whose value depends on agent A's behavior.\nCan be competitive or cooperative. e.g. communication often emerges as a rational behavior in multiagent environments; in some competitive environments, \nrandomized behavior is rational because it avoids the pitfalls of predictability. \n3) deterministic vs nondeterministic: stochastic is synonym for nondeterministic, except that stochastic model deals with probabilites, while in nondeterminisitc model \nthe possibilities are listed without being quantifies.\n4) episodic vs sequential : in episodic TE, the next episode does not depend on the actions taken in previous episodes; in seq envir, the current \ndecision could affect all future decisions. \n5) static vs dynamic: the envir can change or not while an agent is deliberating. If the envir itself does not change with the passage of time but \nthe agent's performance score does, then smidynamic.\n6) discrete vs continuous 7) known vs unknown: refers not to envir itself but to agent's (or designer's) state of knowledge about the environment. (new video game) \nThe hardest: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n agent function vs agent program: agent program taks the current percept as input, the agent function may depend on the entire percept histroy.\nFour kinds of agent programs: see definitions. \nmodel-based reflex agent: the transition model (of the world) and sensor model allow an agent to keep track of the state of the world.\nIn two kings of cases, utility wins goal: 1) Tradeoff: when there are conflicting goals 2)likelihood: when there are several goals, none of which be achieved with certainty\nAll agents can improve their performance through learning.\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content agent's sensor are perceiving\n* **Agent function** - maps any given percept sequence to an action mathematically\n* **Agent program** - implementation of  the agent function running within some physical system\n* **Agent architecture** - agent = architecture(computing device with physical sensors and acuators) + program\n* **Rational agent** - for each percept seq, it should select an action that is expected to maximize its performance measure\n* **Autonomy** - a rational agent should learn what it can do to compensate for partial or incorrect prior knowledge\n* **Task environment** - PEAS\n* **Simple reflex agent (used in fully observable)** - select actions based on the current percept, ignoring the rest of history\n* **Model-based reflex agent** - the agent maintain some internal state that depends on the percept history\n* **Goal-based agents** - act to achieve their goals. Search and planning\n* **Utility-based agents** - try to maximize their own expected happiness\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n \n```\nfuntion best-first-search(problem, f) returns a solution node or failure\n  node := NODE(state=problem.initial)\n  frontier := a priority queue ordered by f, with node as an elemnt\n  reached := a lookup table, problem.initial: node\n  while not is-empty(frontier) do\n    node := pop(frontier)\n    if problem.is-goal(node.state) then return node\n    for each child in expand(problem, node) do\n      s := child.state\n      if s is not in reached or child.path-cost < reached[s].path-cost then\n        reached[s] := child\n        add child to frontier\n  return failure\n\nfunction expand(problem, node) yields nodes\n  s := node.state\n  for each action in problem.actions(s) do\n    s' := problem.result(s,a)\n    cost := node.path-cost + problem.action-cost(s, action, s')\n    yield NODE(state=s', parent=node, action=action, path-cost=cost)\n```\nRedundant path: 1)we can remember all previously reached states 2) we call a search algorithm a graph search if it checks for redundant paths \nand a tree-like search if it does not check 3) only check cycles\n```\nfunction uniform-cost-search/Dijkstra(problem) returns a solution node or failure\n  return best-first-search(problem, path-cost)\n```\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n```\nfunction iterative-deepening search(problem) returns a solution of failure\n  for depth=0 to inf do\n    result := depth-limited-search(problem, depth)\n    if result != cutoff then return result\n\nfunction depth-limited-search(problem,l) returns a node or failure or cutoff\n  frontier := a LIFO queue with NODE(problem.initial) as an element\n  result := failure\n  while not is-empty(frontier) do\n    node := pop(frontier)\n    if problem.is-goal(node.state) then return node\n    if depth(node) > l then\n      result := cutoff\n    else if not is-cycle(node) do \n      for each child in expand(problem, node) do\n        add child to frontier\n  return result\n```\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Atomic representation** - state considered as whole, with no internal structure\n* **Informed** - the agent can estimate how far it is from goal\n* **Search problem** - a set of possible states, initial state, goal states, action, transition model, action cost function\n* **Expand** - generating child nodes for a node\n* **Frontier** - unexpanded nodes\n* **Best-first search** - we choose a node n with minimum value of some evaluation function f(n)\n* **Bidirectional search** - simultaneously seacnes forward from the initial state and backwards from the goal state(s)\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy best-first search: not optimal, not complete (can get stuck in loops). A* is complete.With a admissible heuristic, A* is optimal. A* is efficient beacuse it prunes away search tree nodes that are not necessary for finding an optimal solution. \n\n\n## AIMA Chapter 3.6 Heuristic Functions\nThe heuristic accuracy influences performance. \neffective branching factor b*: if the total number of nodes generated by A* for a problem is N and the solution depth is d, then b* is the \nbranching factor that a uniform tree of the depth d would have to have in order to contain N+1 nodes. Thus N+1 = 1+b*+(b*)^2 +...+(b*)^d. \nA well-design heuristic would have a value of b* close to 1. From the definition of two heuristics (both admissible), if for any node n, h2(n) >= h1(n), we say h2 dominates h1. \nGenerating heuristic from relaxed problems: a problem with fewer restrictions on the actions is called a relaxed problem. \nThe cost of an optimal solution to a relaxed problem is an admissible an admissible heuristic for the original problem.(also consistent)\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **H(n)** - estimated cost of the cheapest path from the state at node n to a goal state\n* **Greedy best-first search** - expands first the node with the lowest h(n) value\n* **A* search** - a best-first search uses the evaluation function f(n) = g(n)+h(n)\n* **Admissible heuristic** - never overestimate the cost to reach a goal\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n```\nfunction MINIMAX-SEARCH(game, state) returns an action\n  player := game.TO-MOVE(state)\n  value, move := MAX-VALUE(gmae, state)\n  return move\n\nfunction MAX-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v := -inf\n  for each a in game.ACTIONS(state) do\n    v2, a2 := MIN-VALUE(game, game.RESULT(state, a))\n    if v2 > v then\n      v, move := v2, a\n  return v, move\n\nfunction MIN-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state,player), null\n  v := inf\n  for each a in game.ACTIONS(state) do\n    v2, a2 := MAX-VALUE(game, game.RESULT(state, a))\n    if v2 < v then\n      v, move := v2, a\n  return v, move\n```\nIf b is legal moves at each point, m is the maximum depth of tree, time complexity: O(b^m), space O(bm) (or O(m)). \nFor multiplayer games,the backed-up value of a node n is the utility vector of the successor state with the highest value for the player choosing at n. \nalpha-beta pruning: alpha = the value of the best (highest value) choice we have found so far at the choice point along the path for max. a = at least. \nbeta = the value of the best (lowest value) choice we have found so far at any choice point along the path for min. b = at most. \nThe effectiveness of alpha-beta pruning is highly dependent on the order in which the states are examined. If this could be done perfectly, alpha-beta would need\nto examine only O(b^{m/2}) instead of O(b^m), wich means the effective branching factor becomes sqrt(b). Trying first the moves that were found \nto be best in the past: killer move heuristic. Also use transposition table that caches the heuristic value of states. Minimax won't work for games \nlike chess and Go, because there are too many states to explore in the time available. Type A Strategy considers all possible moves to a certain depth, then \nuse a heuristic evaluation function to estimate the utility of states at that depth. wide but shallow. Type B Strategy ignores moves that look bad, go \nas far as possible. deep but narrow.\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic Games tree must include chance nodes in adddition to max and min nodes. \nExpectiminimax value for games with chance nodes: terminal nodes and max and min nodes work exactly the same way as before. For chance nodes we compute \nthe expected value. \nThe program behaved totally differently if we make a change to some of the evaluation values, even if the preference order remains the same. The evaluation function \nmust return values that are a positive linear ransformation of the probability of winning ( or of the expeceted utility). Expectiminimax take O(b^mn^m), where n is the \nnumber of distinct rolls.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n The agent's preferences are captured by a utility function U(s) which assigned a single number to express the desirability of a state. \nThe expected utility of an action given the evidence: $EU(a) = \\sum_{s^\\prime} P(Result(a)=s^\\prime)U(s^\\prime)$, \n$P(Result(a)=s^\\prime) = \\sum_s P(s)P(s^\\prime|s,a)$. Maximum expected utility: $action = argmax_a EU(a)$. \nIf an agent acts so as to maximize a utility function (internal) that correctly reflects the performance measure(external), then the agent \nwill achieve the highest possible performance score. The performance measure gives a score for a history - a sequence of states. Thus it is applied retrospectively after an agent completes a sequence of actions. \nThe utility functio applies to the very next state, so it can be used to guide actions step by step.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n existence of a utility function that describes an agent's preference behavior does not necessayrily mean that the agent is explicity\nmaximizing that utility function in its own deliberations \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Ply** - one move by one player\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nIn search algorithm, each state is atomic and indivisible(a black box with no internal structure).In constraint satisfaction problem, we use a factored representation for each state: a set of variables, each of which hasa value. A CSP has 3 components, X is a set of variables,D is a set of domains,one for each variable,C is a set of constraints.Each constaints Cj consists of a pair <scope, rel>, e.g. <(X1,X2), {(3,1),(3,2),(2,1)}> or <(X1,X2),X1>X2>.Variations of CSP:\n1)domains: a. discrete, finite (8-queens); b. infinite (eg set of integers), we must use implicit constraints like T1+d1<=T2 \nrather than explicit tuples of values. linear constraints on integer variables are solvable while nonlinear constraints\n on integer variable is undecidable. c. continuous domains: linear programming.\n 2)contraints: number of variables - a.unary, binary, tenary b.global(involving an arbitrary number of variables, eg Alldiff).\n every finite-domain constraints can be reduced to a set of binary constraints, using dual graph approach for instance.\n Preference constraints - can often be encoded as costs on individual variable assignments. Also called constrained optimazation \n problem.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nA CSP can make progress / rule out values by two way: search(assignment) and inference(constaint propagation).Constraint propagation is a specific type of inference, whose main idea is using the constraints to reduce the \nnumber of legal values for a variable, which in turn can reduce the legal values for another variable, and so on. The process\n of enforcing local consistency in each part of the constraint graph causes inconsistent values to be eliminated throughout the graph.\n```\nfunction AC-3(csp) returns false if an inconsistency is found and true otherwise\n  queue := a queue of arcs, initially all the arcs in csp\n  while queue is not empty do\n    (Xi, Xj) := POP(queue)\n    if REVISE(csp, Xi, Xj) then\n      if size of Di = 0 then return false\n      for each Xk in Xi.NEIGHBORS - {Xj} do\n        add(Xk, Xi) to queue\n  return true\n\nfunction REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi\n  revised := false\n  for each x in Di do\n    if no value y in Dj allows (x,y) to satisfu the constraint between Xi and Xj then\n      delete x from Di\n      revised := true\n  return revised\n```\nTime complexity: n variables, domain size d, c constraints, O(cd^3).\nHow to solve a strong n-consistent CSP: first choose a consistent value for X1, then for X2, then for X3,...For each variable Xi, we \nneed to only search through the d values in the domain to find a value consistent with X1,...X_{i-1}. Total run time O(n^2d).\nA simple consistency procedure for a higher-order constraint is sometimes more effective than applying arc consistency to an equivalent set of binary constraints. \n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n```\nfunction backtracking-search(csp) returns a solution or failure\n  return backtrack(csp,{})\n\nfunction backtrack(csp, assignment) returns a solution or failure\n  if assignment is complete then return assignment\n  var := select-unassigned-variable(csp, assignment)\n  for each value in order-domain-values(csp, var, assignment) do\n    if value is consistent with assignment then\n      add {var = value} to assignment\n      inferences := inference(csp, var, assignment)\n      if inferences != failure then \n        add inferences to csp\n        result := backtrack(csp, assignment)\n        if result != failure then return result\n        remove inferences from csp\n      remove {var=value} from assignment\n  return failure\n```\nImprove above by domain-independent heuristics:\nminimum-remaining-values(more powerful): most constrained variable / fail-first; \ndegree heuristic(tie breaker): reduce the branching factore on future choices by selecting variables that is involved in the largest number of constraints on other unassigned variables; \nleast-constraining-value: value that rules out the fewest choices for the neighboring variables.\nInterleaving search and inference: 1) simple inference: forward checking: Whenever X is assigned, for each unassigned variable Y that is \nconnected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for X. This method doesn't look ahead far enough. \\\n2) Maintaining Arc Consistency: after Xi is assigned, the inference procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs(Xj, Xi) \nfor all Xj that are unassigned variables that are neighbors of Xi. From there, AC-3 does constaint propagration in teh usual way, but if any variable'domain reduced to empty set, \nthe call to AC-3 fails and then we do backtrack.\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Independence can be ascertained by finding connnected components of the constrained graph. Suppose each CSPi has c variables, \nthere're n/c subproblems. Total work is O(d^c n/c) linear in n. Without decomposition, O(d^n). \nAny tree with n nodes has n-1 edges, so we can make this graph directed arc-consistent in O(n) steps, taotl runtime O(nd^2). \nReduce a constraint graph to a tree: 1) removing nodes (cutset conditioning) 2)collapsing nodes together(tree decomposition). The aim of choosing a tree\n decomposition is to make the subproblems as small as possible. O(nd^{w+1}), w = tree width. tree decompostion ia always faster than cutset conditioning.\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Csp** - A problem is solved when each variable has a value that satisfies all the constraints on the variable\n* **Consistent/legal assignment** - An assignment that doesn't violate any constraints\n* **Complete assignment** - every variable is assigned a value\n* **Solution** - a consistent, complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - a partial assignment that is consistent\n* **Binary csp** - with only unary and binary constraints\n* **Node consistency** - a single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints\n* **Xi arc consistency wrt xj** - for all val in Di, exists val in Dj that satisfies binary constraints on (Xi,Xj)\n* **Ac graph** - every variable is AC with every other variable\n* **{xi,xj} path consistency wrt xm** - for every consistent assignment {Xi=a,Xj=b}, exists an assignment to Xm that satisfies the constraints on {Xi, Xm} and {Xm, Xj}\n* **K-consistency** - for any k-1 vars, with any consistent assignment to them, a consistent val can always be assigned to any kth\n* **Srong k-consistent** - it's k-consistent, k-1 consisitent,...1-consistent\n* **Global constraint** - one involving arbitrary number of variables(but not necessarily all variables)\n* **Alldiff** - if m varables are involved, and n possible distinct values altogether, m > n, then the constraint can't be satisfied\n* **Atmost** - checking the sum of minimum values of the current domains, for large set, use bounds propagation/bounds-consistent\n* **Conflict set** - if every possible val for Xj fails, backjump to the most recent Xi, conf(Xi) := conf(Xi) + conf(Xj) - {Xi}\n* **Constraint learning** - finding a minimum set from the conflct set that causes the problem, the set along with values called no-good\n* **Tree csp** - any two varibles are connnected by only one path, can be solved in linear in number of variables\n* **Directional arc consistency** - given an ordering of X1...Xn, iff every Xi is AC with each Xj for j > i\n* **Cycle cutset** - choose a subset S of the CSP's varibles such that the constraint graph becomes a tree after removel of S\n* **Tree width** - one less than the size of the largest node\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nAgent program is called: 1) tells the KB what it perceives 2) asks the KB what action it should perform 3)tells the KB which action was chosen and returns the action so that is can be execured.\n\n## AIMA Chapter 7.2 The Wumpus World\n\n\n## AIMA Chapter 7.3 Logic\n In standard logics, every sentence must be either true or false in each possible world.If a sentence a is true in model m, we say m satisfies a or m is a model of a. M(a) = set of all models of a.Model checking inference: enumerates all possible models to check $M(KB) \\subseteq M(\\alpha)$.If an inference algorithm i can derive $\\alpha$ from KB, $KB \\vdash_i \\alpha$.Sound/truth-preserving: an inference algo derives only entailes sentences.Completeness: it can derive any sentence that is entailed.Grouding: how do we know that KB is true in the real world(sensing a percept + learning a general rule).\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nFrom truth table, the truth value of any sentence s can be computed wrt any model m by a simple recursive evaluation.\n```\nfunction TT-ENTAILS?(KB, a) returns true or false\n  inputs: KB, a(the query, a sentence in PL)\n  symbols := a list of the proposition symbols in KB and a\n  return TT-CHECK-ALL(KB, a, symbols, {})\n\n  function TT-CHECK-ALL(KB, a, symbols, model) returns true or false\n    if EMPTY?(symbols) then\n      if PL-TRUE?(KB, model) then return PL-TRUE?(a,model)\n      else return true\n    else\n      P := FIRST(symbols)\n      rest := REST(symbols)\n      return (TT-CHECK-ALL(KB, a, rest, model+{P=true})\n              and\n              TT-CHECK-ALL(KB, a, rest, model+{P=false}))\n```\nTime complexity: O(2^n), Space: O(n) (depth-first).This problem is co-NP-complete, so every known algo has a worst case complexity that is exponential in the size of the input.\n \n\n## AIMA 7.5 Propositional Theorem Proving\nDefine a proof problem using search: initial state - the initial KB; actions/result - all inference rules applied to all the top-half-form sentences/add bottom-half-form sentence to KB;goal - a state contains the sentence we want to prove.Resolution + Complete search algorithm = Complete Inference Algorithm.Full resolution:1) Only one pair of complementary literals at a time 2) factoring: result contains only one copy of each literal.Resolution inference works because: 1)every sentence can be converted into a CNF 2）how: \n```\nfunction PL-RESOLUTION(KB,a) returns true or false\n  inputs: KB, a(a sentence)\n  clauses := the set of clauses in CNF of KB && neg a\n  new := {}\n  while true do\n    for each pair of clauses Ci, Cj in clauses do\n      resolvents := PL-RESOLVE(Ci,Cj)\n      if resolvents contains the empty clause then return true\n      new.add(resolvents)\n    if new in clauses then return false\n    clauses.add(new)\n```\nEvery difinite clause can be written as an implication whose premise(body) is conjuction of positive literals and whose conclusion(head) is a single positive literal.Forward chaining takes O(KB) time, while backward chaining takes even less.\n```\nfunction PL-FC-ENTAILS?(KB, q) returns true or flase\n  input: KB, q(a proposition symbol)\n  count := a table, where count[c] is initially the number of symbols in clause c's premise\n  inferred := a table, where inferred[s] is initially flase for all symbols\n  queue := a queue of symbols, initially sumbols known to be true in KB\n  while queue is not empty do\n    p := POP(queue)\n    if p = q then return true\n    if inferred[p] = false then\n       inferred[p] := true\n       for each clause c in KB where p is in c.PREMISE do\n         count[c]--\n         if count[c] = 0 then add c.CONCLUSION to queue\n  return false\n```\n\n\n## Module 7 Lecture Notes\n\n\n## Module 7 Definitions\n* **Kb** - a set of sentences(assertion about the world in knowledge representation language)\n* **Axiom** - a sentence being given without being derived from other sentences\n* **Declarative approach** - starting from empty KB, designer tells sentences one by one until the agent knows how to operate\n* **Procedural approach** - encodes desired behaviors directly\n* **Model** - mathematical abstractions of possible world, which has a fixed truth value for every relevent sentence\n* **Entailment** - $\\alpha \\models \\beta \\text{ iff } M(\\alpha) \\subseteq M(\\beta)$\n* **Syntax** - defins the allowable sentences\n* **Atomic sentence** - consists of a single proposition symbol\n* **Symbol** - Ture,False,P,Q,R stands for a proposition that can be true or false\n* **Complex sentences** - constructed from simpler sentences using () and logical connectives\n* **Semantic** - defines the rules for determining the truth of a sentence wrt a particular model\n* **Logical equivalence** - two sentences are LE if they're T in the same set of models, one can be entailed from the other\n* **Theorem proving** - apply rules of inference to the sentences in KB to construct a proofof the desired sentence without consulting models\n* **Validity** - A sentence is true for all models\n* **Satisfiable** - satisfied by some model\n* **Deduction theorem** - For any a and b, a entails b iff a implies b is valid \n* **Proof by contradiction** - KB entails a iff KB and neg a is unsatisfiable\n* **Monotonicity** - if KB entails a, then KB and b entails a(new assertion can't invalidate any conlusion already inferred)\n* **Resolution** - takes two clauses and produces a new clause containing all literals except two complementary literals\n* **Factoring** - removal of multiple copies of literals\n* **Cnf** - Conjuctive normal form\n* **Ground resolution theorem** - If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause\n* **Definite clauses** - exaclyt one literal is positive\n* **Horn clauses** - at most one is positive\n* **Goal clauses** - no positive literal\n* **Fact** - a sentence consisting of a single positive literal\n* **Literal** - Symbol or $\\neg$Symbol\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}