{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes yuxinji.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": "80fa8253-8d8b-4797-af76-2f4520151dc2"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "661acfdf-d765-42c4-d2cc-29e6d60476b2"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"Six disciplines compose most of AI:\n",
        "1. natural language processing to communicate successfully in a human language;\n",
        "2. knowledge representation to store what it knows or hears; \n",
        "3. automated reasoning to answer questions and to draw new conclusions; \n",
        "4. machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n",
        "5. computer vision and speech recognition to perceive the world; \n",
        "6. robotics to manipulate objects and move about.\n",
        "\n",
        "Two advantages of rational-agent approach:\n",
        "1. More general than the “laws of thought” approach (correct inference is just one of the possible mechanisms for achieving rationality)\n",
        "2. More amenable to scientific development (mathematically well-defined and completely general)\n",
        "\n",
        "AI focused on the study and construction of agents that do the right thing – objective that we provide to the agent, also called standard model.\\\n",
        "As it becomes more difficult to specify the objective completely and correctly, standard model is not the right model in the long run.\n",
        "\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Informality - Turing: “argument from informality of behavior” – \\\n",
        "human behavior is too complex to be captured by and formal set of rules.\n",
        "Key proponent: Hubert Dreyfus, critiques of AI (Good Old-Fashioned AI, GOFAI)\n",
        "Embodied cognition: study the system as a whole, cognition takes place within a body, \\\n",
        "which is embedded in an environment. Robotics, vision and other sensors become central, not peripheral \n",
        "\n",
        "Disability - claim “a machine can never do X”.\n",
        "Turing: examples of X “be kind, resourceful, beautiful,…\"\n",
        "\n",
        "Mathematical objection - Turing and Godel proved that certain mathematical questions are \\\n",
        "in principle unanswerable by particular formal systems. E.g. Godel’s incompleteness theorem\n",
        "\n",
        "Measuring AI - Turing Test\n",
        "whether a machine can pass a behavioral test – chat with an interrogator for 5 min, passes the test if it fools the interrogator 30% of the time\n",
        "Key point: idea of measuring intelligence by performance on some kind of open-ended behavioral task\n",
        "Focus of research within AI community: improve basic science and technology to provide useful tools, not to fool judges\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" John Searle: computers generate no understanding, just like the Chinese room \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" In general, an agent’s choice of action at any given instant can depend on its built-in\\\n",
        "knowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived. \n",
        "\"\"\"\n",
        "\n",
        "chapter2_2 = \"\"\" Rationality is not perfection, where rationality maximizes expected performance\\\n",
        "and perfection maximizes actual performance. \"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\" Task environment consists of PEAS: Performance, Environment, Actuators, Sensors.\n",
        "\n",
        "Properties of task environments:\n",
        "Fully observable vs. partially observable vs unobservable,\n",
        "Single-agent vs. (competitive/cooperative) multiagent,\n",
        "Deterministic vs. nondeterministic,\n",
        "Episodic vs. sequential,\n",
        "Static vs. dynamic,\n",
        "Discrete vs. continuous,\n",
        "Known vs. unknown\n",
        " \"\"\"\n",
        "\n",
        "chapter2_4 = \"\"\" Agent = architecture + program\n",
        "\n",
        "4 basic kinds of agent programs:\n",
        "- Simple reflex agents: select actions on the basis of the current percept\n",
        "- Model-based reflex agents: use transition model(“how the world works”) and sensor model\\\n",
        "(how the state of the world is reflected in the agent’s percepts) to keep track of the state of the world (internal state)\n",
        "- Goal-based agents: keep track of a set of goals it is trying to achieve. E.g. search and planning\n",
        "- Utility-based agents: a rational utility-based agent chooses the action that maximizes the expected utility of the action outcomes\n",
        "\n",
        "All agents can improve their performance through learning.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \"\"\"\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(through sensors) and act(through actuators) in an environment\",\n",
        "\"rational agent\" : \"select action that maximizes performance measure given percept sequence and built-in knowledge\",\n",
        "\"limited rationality\": \"do the most appropriate thing under limited computational availability\",\n",
        "\"value alignment problem\": \"human and machine should share the same values or objectives\",\n",
        "\"weak AI\": \"machine pretends to think\",\n",
        "\"strong AI\": \"machine can consiously think\",\n",
        "\"consciousness\":\"aware of the environment, of self, of subjective experience of living\",\n",
        "\"qualia\": \"internal, subjective sense, experience\",\n",
        "\"percept\" : \"what an agent’s sensors are perceiving\",\n",
        "\"percept sequence\" : \"complete history of what an agent has perceived\",\n",
        "\"agent function\": \"abstract mathematical description, maps given percept sequence to action\",\n",
        "\"agent program\": \"concrete implementation of agent function, running within physical system\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "cellView": "form",
        "outputId": "c2938571-87cc-482a-fcea-f77527355ce7"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nSix disciplines compose most of AI:\n1. natural language processing to communicate successfully in a human language;\n2. knowledge representation to store what it knows or hears; \n3. automated reasoning to answer questions and to draw new conclusions; \n4. machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n5. computer vision and speech recognition to perceive the world; \n6. robotics to manipulate objects and move about.\n\nTwo advantages of rational-agent approach:\n1. More general than the “laws of thought” approach (correct inference is just one of the possible mechanisms for achieving rationality)\n2. More amenable to scientific development (mathematically well-defined and completely general)\n\nAI focused on the study and construction of agents that do the right thing – objective that we provide to the agent, also called standard model.As it becomes more difficult to specify the objective completely and correctly, standard model is not the right model in the long run.\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Informality - Turing: “argument from informality of behavior” – human behavior is too complex to be captured by and formal set of rules.\nKey proponent: Hubert Dreyfus, critiques of AI (Good Old-Fashioned AI, GOFAI)\nEmbodied cognition: study the system as a whole, cognition takes place within a body, which is embedded in an environment. Robotics, vision and other sensors become central, not peripheral \n\nDisability - claim “a machine can never do X”.\nTuring: examples of X “be kind, resourceful, beautiful,…\"\n\nMathematical objection - Turing and Godel proved that certain mathematical questions are in principle unanswerable by particular formal systems. E.g. Godel’s incompleteness theorem\n\nMeasuring AI - Turing Test\nwhether a machine can pass a behavioral test – chat with an interrogator for 5 min, passes the test if it fools the interrogator 30% of the time\nKey point: idea of measuring intelligence by performance on some kind of open-ended behavioral task\nFocus of research within AI community: improve basic science and technology to provide useful tools, not to fool judges\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n John Searle: computers generate no understanding, just like the Chinese room \n\n## AIMA 2.1 Agents and Environments\n In general, an agent’s choice of action at any given instant can depend on its built-inknowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived. \n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rationality is not perfection, where rationality maximizes expected performanceand perfection maximizes actual performance. \n\n## AIMA 2.3 The Nature of Environments\n Task environment consists of PEAS: Performance, Environment, Actuators, Sensors.\n\nProperties of task environments:\nFully observable vs. partially observable vs unobservable,\nSingle-agent vs. (competitive/cooperative) multiagent,\nDeterministic vs. nondeterministic,\nEpisodic vs. sequential,\nStatic vs. dynamic,\nDiscrete vs. continuous,\nKnown vs. unknown\n \n\n## AIMA 2.4 The Structure of Agents\n Agent = architecture + program\n\n4 basic kinds of agent programs:\n- Simple reflex agents: select actions on the basis of the current percept\n- Model-based reflex agents: use transition model(“how the world works”) and sensor model(how the state of the world is reflected in the agent’s percepts) to keep track of the state of the world (internal state)\n- Goal-based agents: keep track of a set of goals it is trying to achieve. E.g. search and planning\n- Utility-based agents: a rational utility-based agent chooses the action that maximizes the expected utility of the action outcomes\n\nAll agents can improve their performance through learning.\n\n\n## Module 1 Lecture Notes\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive(through sensors) and act(through actuators) in an environment\n* **Rational agent** - select action that maximizes performance measure given percept sequence and built-in knowledge\n* **Limited rationality** - do the most appropriate thing under limited computational availability\n* **Value alignment problem** - human and machine should share the same values or objectives\n* **Weak ai** - machine pretends to think\n* **Strong ai** - machine can consiously think\n* **Consciousness** - aware of the environment, of self, of subjective experience of living\n* **Qualia** - internal, subjective sense, experience\n* **Percept** - what an agent’s sensors are perceiving\n* **Percept sequence** - complete history of what an agent has perceived\n* **Agent function** - abstract mathematical description, maps given percept sequence to action\n* **Agent program** - concrete implementation of agent function, running within physical system\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "All data  treated as objects.\n",
        "\n",
        "Strong Typing: Every object has a fixed type, interpreter doesn’t allow things incompatible with that type(eg. “foo”+2)\n",
        "\n",
        "Examples of Types: int, float, str, tuple, dict, list, bool, None, generator, function\n",
        "\n",
        "Dynamic typing: variables come into existence when first assigned, type is automatically determined. If assign agian, type is updated.\n",
        "\n",
        "String:\n",
        "- Immutable\n",
        "- concatenate use \"+\"\n",
        "- r means raw: no need to escape special characters. eg r'\\n' will print out \\n. Without r, will print out nothing.\n",
        "- use of %: print(\"%s can speak %d languages\" % (\"C3PO\",  6000000)) will print \"C3PO can speak 6000000 languages\".\n",
        "- s.split(\" \"): split s on space; \"_\".join(words): join a list to form a string with underscore\n",
        "\n",
        "List:\n",
        "- Mutable\n",
        "- y = x[:] to get a shallow copy of x\n",
        "- .index(): index of first occurrence; .count(): number of occurrences; .remove(): remove first occurrence;\\\n",
        ".reverse(): reverse in place; .sort(): sort in place; sorted(list): return a copy sorted\n",
        "\n",
        "\n",
        "Tuple:\n",
        "- Immutable ordered sequence of items, items can be of mixed types, including collection types\n",
        "\n",
        "Dictionary:\n",
        "- unordered, keys must be immutable, constant average time add, lookup, update\n",
        "- .keys(); .values(); .items()\n",
        "- defaultdict(str) automatically initializes nonexistent dictionary values to \"\", (int) initializes to 0, etc.\n",
        "- Counter() also initializes nonexistent dictionary, value to 0\n",
        "\n",
        "Function:\n",
        "- can return muptiple values, return type: tuple\n",
        "- if default values are specified in def, the arguments are optional when calling the function,\\\n",
        "non-default argument should always precede default arguments; otherwise, it reports SyntaxError\n",
        "- myfun(1,2,3) OK; myfun(c=3, b=1, a=2) OK; myfun(1, c=3, b=2) OK; myfun(a=1, b=3, 2) SyntaxError\n",
        "- *args: accept a variable number of non-keyword arguments to your function\n",
        "- **kwargs: keyword arguments, kwargs is a dict of the keyword args passed to the fn\n",
        "\n",
        "Class:\n",
        "- constructors:__init__, \n",
        "- subclass: the ancestor’s __init__ method is executed in addition to new commands\n",
        "class subClass(parentClass):must be done explicitly init: parentClass.__init__(self, x, y)\n",
        "- magic methods: __len__: define len(obj). __copy__: define copy. __cmp__: define ==. __add__:  Define + .\\\n",
        "__neg__: define unary  negation\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"duck typing\" : \"determine if methods are present\",\n",
        "\"list comprehensions\": \"[expression for name in list if filter]\",\n",
        "\"iterable\": \"has __iter__ method, returns an iterator obj\",\n",
        "\"iterator\": \"object with a __next()__ method, throws StopIteration when done, memory efficient\",\n",
        "\"generator\": \"generators are iterators, next method runs until a yield statement, stops and returns\"\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 928
        },
        "outputId": "c1360bfa-7f2e-4ba8-89c6-12e7ab4086f8"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nAll data  treated as objects.\n\nStrong Typing: Every object has a fixed type, interpreter doesn’t allow things incompatible with that type(eg. “foo”+2)\n\nExamples of Types: int, float, str, tuple, dict, list, bool, None, generator, function\n\nDynamic typing: variables come into existence when first assigned, type is automatically determined. If assign agian, type is updated.\n\nString:\n- Immutable\n- concatenate use \"+\"\n- r means raw: no need to escape special characters. eg r'\n' will print out \n. Without r, will print out nothing.\n- use of %: print(\"%s can speak %d languages\" % (\"C3PO\",  6000000)) will print \"C3PO can speak 6000000 languages\".\n- s.split(\" \"): split s on space; \"_\".join(words): join a list to form a string with underscore\n\nList:\n- Mutable\n- y = x[:] to get a shallow copy of x\n- .index(): index of first occurrence; .count(): number of occurrences; .remove(): remove first occurrence;.reverse(): reverse in place; .sort(): sort in place; sorted(list): return a copy sorted\n\n\nTuple:\n- Immutable ordered sequence of items, items can be of mixed types, including collection types\n\nDictionary:\n- unordered, keys must be immutable, constant average time add, lookup, update\n- .keys(); .values(); .items()\n- defaultdict(str) automatically initializes nonexistent dictionary values to \"\", (int) initializes to 0, etc.\n- Counter() also initializes nonexistent dictionary, value to 0\n\nFunction:\n- can return muptiple values, return type: tuple\n- if default values are specified in def, the arguments are optional when calling the function,non-default argument should always precede default arguments; otherwise, it reports SyntaxError\n- myfun(1,2,3) OK; myfun(c=3, b=1, a=2) OK; myfun(1, c=3, b=2) OK; myfun(a=1, b=3, 2) SyntaxError\n- *args: accept a variable number of non-keyword arguments to your function\n- **kwargs: keyword arguments, kwargs is a dict of the keyword args passed to the fn\n\nClass:\n- constructors:__init__, \n- subclass: the ancestor’s __init__ method is executed in addition to new commands\nclass subClass(parentClass):must be done explicitly init: parentClass.__init__(self, x, y)\n- magic methods: __len__: define len(obj). __copy__: define copy. __cmp__: define ==. __add__:  Define + .__neg__: define unary  negation\n\n\n## Module 2 Definitions\n* **Duck typing** - determine if methods are present\n* **List comprehensions** - [expression for name in list if filter]\n* **Iterable** - has __iter__ method, returns an iterator obj\n* **Iterator** - object with a __next()__ method, throws StopIteration when done, memory efficient\n* **Generator** - generators are iterators, next method runs until a yield statement, stops and returns\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \n",
        "To fully define a search problem:\n",
        "- State space: set of possible states that the environment can be in\n",
        "- Initial state: agent starts in\n",
        "- Goal states: one or more or a property that applies to many states\n",
        "- Actions: available to the agent\n",
        "- Transition model: describes what each action does. E.g. RESULT(s,a) returns the state from doing action a in state s.\n",
        "- Action cost function\n",
        " \"\"\"\n",
        "\n",
        "chapter3_2 = \"\"\" \n",
        "Route-finding problems are defined in terms of specified locations and transitions along edges between them.\n",
        "\n",
        "Touring problems describe a set of locations that must be visited, rather than a single goal\n",
        "destination. The traveling salesperson problem (TSP) is a touring problem in which every\n",
        "city on a map must be visited.\n",
        "\n",
        "A VLSI layout problem requires positioning millions of components and connections on a\n",
        "chip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize\n",
        "manufacturing yield.\n",
        "\"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\" \n",
        "Frontier separates two regions of the state-space graph: an interior region where every state has been expanded, \\\n",
        "and an exterior region of states that have not yet been reached.\n",
        "\n",
        "Evaluate an algorithm’s performance: complete, optimal, time and space complexity\n",
        "\n",
        "Best-first search: \n",
        "- choose node n with minimum value of some evaluation function f(n).\n",
        "- Uses priority queue – first pops the node with minimum cost.\n",
        "- graph-search \n",
        "\n",
        "Breadth-first-search: \n",
        "- Uses FIFO queue – first pops the node that was added to the queue first\n",
        "\n",
        "Depth-first-search:\n",
        "- Uses LIFO queue(stack) – first pops the most recently added node\n",
        "- Tree-like search\n",
        "\"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\" \n",
        "__Breadth-first-search__: \n",
        "- expands the shallowest nodes first\n",
        "- complete\n",
        "- cost-optimal for unit action costs (where all actions have same cost)\n",
        "- Both time and space complexity are O(b^d), b: # of successors of each state, d: depth\n",
        "- large memory requirement: exponential\n",
        "\n",
        "__Dijkstra’s algorithm / Uniform-cost search__：\n",
        "- Actions have different costs, use best-first search, evaluation function is the path cost, optimal for general action costs\n",
        "- complete\n",
        "- cost optimal\n",
        "- worst case time and space complexity, O(b^(1+floor(C*/e))), C*: cost of the optimal solution, e: lower bound on the cost of each action,\\\n",
        "can be much higher than b^d\n",
        "\n",
        "__Depth-first-search__:\n",
        "- expands the deepest unexpanded node first\n",
        "- incomplete\n",
        "- not cost-optimal\n",
        "- linear space complexity, O(bm), m: maximum depth of the tree; b: branching factor\n",
        "- __Depth-limited search__ adds a depth bound L, incomplete when a poor choice of L fails to reach the solution\n",
        "\n",
        "__Iterative deepening search__:\n",
        "- calls depth-first search with increasing depth limits until a goal is found\n",
        "- complete when full cycle checking is done\n",
        "- optimal for unit action costs\n",
        "- time complexity comparable to breadth-first search, linear space complexity\n",
        "\n",
        "__Bidirectional search__:\n",
        "- expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet\n",
        "- complete and optimal\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "\"path\": \"a sequence of actions\",\n",
        "\"solution\": \"a path from the initial state to a goal state\", \n",
        "\"optimal solution\": \"a solution with the lowest path cost\",\n",
        "\"model\": \"formulation or the problem, abstract mathematical description\",\n",
        "\"complete\": \"algorithm finds a solution iff there is one, must reach every state systematically\",\n",
        "\"cost optimal\": \"algorithm finds a solution with the lowest path cost of all solutions\", \n",
        "\"d, depth\": \"depth or number of actions in an optimal solution\",\n",
        "\"m\": \"maximum number of actions in any path\",\n",
        "\"b, branching factor\": \"branching factor or number of successors of a node that need to be considered\",\n",
        "\"graph search\": \"checks for redundant paths, more memory for storing reached states and redundant paths, faster\", \n",
        "\"tree-like search\": \"does not check for redundant paths, less memory but slower\",\n",
        "\"uninformed search\": \"only knows problem definition, doesn't know how close a state is to the goal\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4c275a85-120b-41d8-c983-e1a172307aed"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nTo fully define a search problem:\n- State space: set of possible states that the environment can be in\n- Initial state: agent starts in\n- Goal states: one or more or a property that applies to many states\n- Actions: available to the agent\n- Transition model: describes what each action does. E.g. RESULT(s,a) returns the state from doing action a in state s.\n- Action cost function\n \n\n## AIMA Chapter 3.2 Example Problems\n \nRoute-finding problems are defined in terms of specified locations and transitions along edges between them.\n\nTouring problems describe a set of locations that must be visited, rather than a single goal\ndestination. The traveling salesperson problem (TSP) is a touring problem in which every\ncity on a map must be visited.\n\nA VLSI layout problem requires positioning millions of components and connections on a\nchip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize\nmanufacturing yield.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \nFrontier separates two regions of the state-space graph: an interior region where every state has been expanded, and an exterior region of states that have not yet been reached.\n\nEvaluate an algorithm’s performance: complete, optimal, time and space complexity\n\nBest-first search: \n- choose node n with minimum value of some evaluation function f(n).\n- Uses priority queue – first pops the node with minimum cost.\n- graph-search \n\nBreadth-first-search: \n- Uses FIFO queue – first pops the node that was added to the queue first\n\nDepth-first-search:\n- Uses LIFO queue(stack) – first pops the most recently added node\n- Tree-like search\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n__Breadth-first-search__: \n- expands the shallowest nodes first\n- complete\n- cost-optimal for unit action costs (where all actions have same cost)\n- Both time and space complexity are O(b^d), b: # of successors of each state, d: depth\n- large memory requirement: exponential\n\n__Dijkstra’s algorithm / Uniform-cost search__：\n- Actions have different costs, use best-first search, evaluation function is the path cost, optimal for general action costs\n- complete\n- cost optimal\n- worst case time and space complexity, O(b^(1+floor(C*/e))), C*: cost of the optimal solution, e: lower bound on the cost of each action,can be much higher than b^d\n\n__Depth-first-search__:\n- expands the deepest unexpanded node first\n- incomplete\n- not cost-optimal\n- linear space complexity, O(bm), m: maximum depth of the tree; b: branching factor\n- __Depth-limited search__ adds a depth bound L, incomplete when a poor choice of L fails to reach the solution\n\n__Iterative deepening search__:\n- calls depth-first search with increasing depth limits until a goal is found\n- complete when full cycle checking is done\n- optimal for unit action costs\n- time complexity comparable to breadth-first search, linear space complexity\n\n__Bidirectional search__:\n- expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet\n- complete and optimal\n\n\n## Module 3 Lecture Notes\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** - a sequence of actions\n* **Solution** - a path from the initial state to a goal state\n* **Optimal solution** - a solution with the lowest path cost\n* **Model** - formulation or the problem, abstract mathematical description\n* **Complete** - algorithm finds a solution iff there is one, must reach every state systematically\n* **Cost optimal** - algorithm finds a solution with the lowest path cost of all solutions\n* **D, depth** - depth or number of actions in an optimal solution\n* **M** - maximum number of actions in any path\n* **B, branching factor** - branching factor or number of successors of a node that need to be considered\n* **Graph search** - checks for redundant paths, more memory for storing reached states and redundant paths, faster\n* **Tree-like search** - does not check for redundant paths, less memory but slower\n* **Uninformed search** - only knows problem definition, doesn't know how close a state is to the goal\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "__Greedy Best-First Search__:\n",
        "- expands nodes with minimal h(n) value, f(n)=h(n)\n",
        "- not optimal, but often efficient\n",
        "- complete in finite state spaces, but not in infinite ones\n",
        "- worst-case time and space complexity is O(|V|). A good heuristic function can reduce complexity to linear O(bm)\n",
        "\n",
        "__A* search__ – most common informed search algorithm:\n",
        "- expands nodes with minimal f(n)=g(n)+h(n), where g(n) is the path cost from the initial state to node n\n",
        "- complete\n",
        "- optimal if h(n) is admissible\n",
        "- efficient bc it prunes away nodes that are not necessary for finding an optimal solution\n",
        "- main issue: memory(frontier and reached), the number of nodes expanded can be exponential in the length of the solution\n",
        "\n",
        "Every consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A* is cost-optimal.\n",
        "\n",
        "__Beam search__ limits the size of the frontier. The easiest approach is to keep only the nodes \\\n",
        "with the best k-scores, discarding any other expanded nodes. Incomplete and suboptimal, but less memory, and fast.\n",
        "\n",
        "__Iterative-deepening A* search__ (IDA*) addresses the space complexity issue, not keeping all reached states in\n",
        "memory, at a cost of visiting some states multiple times. Cutoff is the f-cost (g+h); at each iteration, the cutoff value is the\n",
        "smallest f-cost of any node that exceeded the cutoff on the previous iteration.\n",
        "\n",
        "__Recursive best-first search__ (RBFS) uses linear space. RBFS resembles a recursive depthfirst\n",
        "search, uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor\n",
        "of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path.\n",
        "RBFS and __SMA*__ (simplified memory-bounded A*) are robust, optimal search algorithms that use limited amounts of memory; \n",
        "given enough time, they can solve problems for which A* runs out of memory.\n",
        "\n",
        "__Wighted A* search__ focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\n",
        "\"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\"\n",
        "A well-designed heuristic would have b* close to 1.\n",
        "\n",
        "\n",
        "State-space graph of the relaxed problem is a supergraph of the original state space. \n",
        "Any optimal solution in the original problem is, also a solution in the relaxed problem; \n",
        "but the relaxed problem may have better solutions if the added edges provide shortcuts. \n",
        "Hence, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n",
        "\n",
        "The performance of heuristic search algorithms depends on the quality of the heuristic function. \n",
        "Construct good heuristics:\n",
        "- relaxing the problem definition\n",
        "- storing precomputed solution costs for subproblems in a pattern database\n",
        "- defining landmarks\n",
        "- learning from experience with the problem class\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"has access to the problem definition and heuristic function h(n)\",    \n",
        "\"heuristic function\": \"estimates the cost of the shortest path from the current node n to a goal node\", \n",
        "\"admissible heuristics\": \"optimistic, never overestimates the cost\",\n",
        "\"consistent heuristics\": \"h(n) <= c(n, a, n’) + h(n’), triangle inequality\",\n",
        "\"weighted A* search\": \"weigh h(n) more, f(n)=g(n)+h(n)*W, with W>1\",\n",
        "\"bounded suboptimal search\": \"solution guaranteed to be within a constant factor W of the optimal cost. e.g. weighted A*\",\n",
        "\"bounded-cost search\": \"cost of solution less than some constant C\",\n",
        "\"unbounded-cost search\": \"accept a solution as long as we can find it quickly, e.g. speedy search\",\n",
        "\"effective branching factor b*\": \"N+1 = 1 + b* + (b*)^2 + … + (b*)^d\",\n",
        "\"Manhattan distance\" : \"sum of the absolute differences\",\n",
        "\"effective depth\": \"A* pruning reduces the effective depth by a constant compared to the true depth\",\n",
        "\"heuristic dominate\": \"h2 dominates h1 if h2(n) >= h1(n). A* using will h2 never expand more nodes than using h1\",\n",
        "\"relaxed problem\": \"fewer restrictions on actions\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "47855237-27fd-4900-8156-002be010d0f1"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n__Greedy Best-First Search__:\n- expands nodes with minimal h(n) value, f(n)=h(n)\n- not optimal, but often efficient\n- complete in finite state spaces, but not in infinite ones\n- worst-case time and space complexity is O(|V|). A good heuristic function can reduce complexity to linear O(bm)\n\n__A* search__ – most common informed search algorithm:\n- expands nodes with minimal f(n)=g(n)+h(n), where g(n) is the path cost from the initial state to node n\n- complete\n- optimal if h(n) is admissible\n- efficient bc it prunes away nodes that are not necessary for finding an optimal solution\n- main issue: memory(frontier and reached), the number of nodes expanded can be exponential in the length of the solution\n\nEvery consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A* is cost-optimal.\n\n__Beam search__ limits the size of the frontier. The easiest approach is to keep only the nodes with the best k-scores, discarding any other expanded nodes. Incomplete and suboptimal, but less memory, and fast.\n\n__Iterative-deepening A* search__ (IDA*) addresses the space complexity issue, not keeping all reached states in\nmemory, at a cost of visiting some states multiple times. Cutoff is the f-cost (g+h); at each iteration, the cutoff value is the\nsmallest f-cost of any node that exceeded the cutoff on the previous iteration.\n\n__Recursive best-first search__ (RBFS) uses linear space. RBFS resembles a recursive depthfirst\nsearch, uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor\nof the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path.\nRBFS and __SMA*__ (simplified memory-bounded A*) are robust, optimal search algorithms that use limited amounts of memory; \ngiven enough time, they can solve problems for which A* runs out of memory.\n\n__Wighted A* search__ focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nA well-designed heuristic would have b* close to 1.\n\n\nState-space graph of the relaxed problem is a supergraph of the original state space. \nAny optimal solution in the original problem is, also a solution in the relaxed problem; \nbut the relaxed problem may have better solutions if the added edges provide shortcuts. \nHence, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\nThe performance of heuristic search algorithms depends on the quality of the heuristic function. \nConstruct good heuristics:\n- relaxing the problem definition\n- storing precomputed solution costs for subproblems in a pattern database\n- defining landmarks\n- learning from experience with the problem class\n\n\n## Module 4 Lecture Notes\n \n\n## Module 4 Definitions\n* **Informed search** - has access to the problem definition and heuristic function h(n)\n* **Heuristic function** - estimates the cost of the shortest path from the current node n to a goal node\n* **Admissible heuristics** - optimistic, never overestimates the cost\n* **Consistent heuristics** - h(n) <= c(n, a, n’) + h(n’), triangle inequality\n* **Weighted a* search** - weigh h(n) more, f(n)=g(n)+h(n)*W, with W>1\n* **Bounded suboptimal search** - solution guaranteed to be within a constant factor W of the optimal cost. e.g. weighted A*\n* **Bounded-cost search** - cost of solution less than some constant C\n* **Unbounded-cost search** - accept a solution as long as we can find it quickly, e.g. speedy search\n* **Effective branching factor b*** - N+1 = 1 + b* + (b*)^2 + … + (b*)^d\n* **Manhattan distance** - sum of the absolute differences\n* **Effective depth** - A* pruning reduces the effective depth by a constant compared to the true depth\n* **Heuristic dominate** - h2 dominates h1 if h2(n) >= h1(n). A* using will h2 never expand more nodes than using h1\n* **Relaxed problem** - fewer restrictions on actions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "Games differ from search problems: Games have multiple agents\n",
        "\n",
        "Two players: MAX & MIN, MAX moves first\n",
        "\n",
        "To define a game as a search problem:\n",
        "- initial state S0\n",
        "- To-Move(s): the player whose turn it is to move in state s\n",
        "- Actions(s): set of legal moves that a player can make\n",
        "- Result(s,a): Transitional model, state resulting from taking action in state s.\n",
        "-\tIs-Terminal(s): terminal test, terminal states\n",
        "- Utility(s,p): utility functions\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" \n",
        "In a game tree, the optimal strategy can be determined by working out the __Minimax value__ of each state of the tree.\n",
        "\n",
        "The minimax value is the utility (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game. \n",
        "The minimax value of a terminal state is just its utility.\n",
        "In a non-terminal state, MAX prefers to move to a state of maximum value when it is MAX’s turn to move, and MIN prefers a state of minimum value.\n",
        "In minimax search, the value of a node is the optimal value of its children. For the MAX player, that's the highest value. For MIN, that's the lowest value. This is because minimax assumes both players play optimally.\n",
        "\n",
        "__Minimax search algorithm__ solves perfect information, zero-sum games. The minimax algorithm uses a depth-first approach.\n",
        "It is a recursive algorithm that proceeds all the way down to the leaves of the tree and then backs up the minimax values through the tree as the recursion unwinds.\n",
        "- time-complexity: O(bm)\n",
        "- space complexity: O(bm) generates all actions at once/ O(m) generates actions one at a time\n",
        "\n",
        "__Alpha-Beta pruning__:\n",
        "The effectiveness of Alpha-Beta pruning depends on the order in which successor nodes are examined.\n",
        "Alpha-beta with __perfect move ordering__: O(b^(m/2)) instead of O(b^m), effective branching factor becomes sqrt(b) instead of b.\n",
        "Alpha-beta with __random move ordering__: O(b^(3m/4)), for moderate b.\n",
        "Dynamic move-ordering schemes: trying first the moves that were found to be best in the past (precious move/ iterative deepening).\n",
        "\n",
        "__Type A strategy__ considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation\\ \n",
        "function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree.\n",
        "__Type B strategy__ ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter5_3 = \"\"\" \n",
        "Evaluation function should be strongly correlated with the actual chances of winning, \n",
        "but it need not be linearly correlated: if state is twice as likely to win as state we don’t require that EVAL(S) be twice EVAL(S'); \n",
        "all we require is that EVAL(S) > EVAL(S'). \n",
        "\n",
        "Many game-playing programs use __table lookup__ rather than search for the opening and ending of games.\n",
        "\"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\" \n",
        "Chance nodes + MAX and MIN nodes \n",
        "\n",
        "__expectiminimax__: generalization of minimax, Terminal nodes and MAX and MIN nodes work exactly the same way as before \n",
        "(with the caveat that the legal moves for MAX and MIN will depend on the outcome of the chance event in the previous chance node). \n",
        "For chance nodes we compute the expected value, which is the sum of the value over all outcomes, weighted by the probability of each chance action.\n",
        "\n",
        "Problem: An order-preserving transformation on leaf evaluation values could change the best move. \n",
        "To avoid this problem, the evaluation function must return values that are a positive linear transformation of the probability of winning \n",
        "(or of the expected utility, for games that have outcomes other than win/lose).\n",
        "\n",
        "When the move is deterministic, Expectiminimax will also choose the optimal movement (no chance to take a random movement), just like minimax. \n",
        "Minimax: O(b^m), Expectiminimax: O(b^m n^m), n: number of distinct rolls of dice.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "The expected utility of an action is the average utility value of outcomes weighed by the probability of that outcome occurring.\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "Six constraints of reasonable preference relation(axioms of utility theory):\n",
        "- ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. The agent cannot avoid deciding.\n",
        "- TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C.\n",
        "- CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure\n",
        "and the lottery that yields A with probability p and C with probability (1-p).\n",
        "- SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B\n",
        "is substituted for A in one of them\n",
        "- MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A, then the agent must prefer the lottery that has a higher\n",
        "probability for A.\n",
        "- DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "EMV: expected monetary value\n",
        "\n",
        "insurance premium = difference between the EMV of a lottery and its certainty equivalent\n",
        "\n",
        "risk-averse: prefer a sure thing with a payoff that is less than the expected monetary value of a gamble\n",
        "\n",
        "ambiguity aversion: Most people elect the known probability rather than the unknown unknowns\n",
        "\n",
        "framing effect: wording of a decision problem can have a big impact on the agent’s choices\n",
        "\n",
        "anchoring effect: People feel more comfortable making relative utility judgments rather than absolute ones\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\": \"fully observable\",\n",
        "\"move\": \"action\",\n",
        "\"position\": \"state\",\n",
        "\"Alpha\": \"highest value along the path for MAX\",\n",
        "\"Beta\": \"lowest value along the path for MIN\",\n",
        "\"killer moves\": \"Best moves\",\n",
        "\"killer move heuristic\": \" try best moves first\",\n",
        "\"heuristic evaluation function\": \"eval(s,p) estimate of the expected utility of state s of player p, equal to utility at terminal\",\n",
        "\"quiescent\": \"positions where there is no pending move that would influence the evaluation\",\n",
        "\"quiescence search\": \"consider only certain types of moves that will quickly resolve the uncertainties\",\n",
        "\"horizon effect\": \"when facing unavoidable serious damage, temporarily avoid loss by delaying\",\n",
        "\"Forward pruning\": \"prunes moves that appear to be poor moves, saves computational time but could be an error, type B strategy\",\n",
        "\"policy\": \"a mapping from every possible state to the best move in that state\",\n",
        "\"value function / ordinal utility function\": \"in deterministic environment, agent needs preference ranking on states, not numbers\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "fdab4e37-26db-47ab-89f7-b1e0162a80e2"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nGames differ from search problems: Games have multiple agents\n\nTwo players: MAX & MIN, MAX moves first\n\nTo define a game as a search problem:\n- initial state S0\n- To-Move(s): the player whose turn it is to move in state s\n- Actions(s): set of legal moves that a player can make\n- Result(s,a): Transitional model, state resulting from taking action in state s.\n-\tIs-Terminal(s): terminal test, terminal states\n- Utility(s,p): utility functions\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nIn a game tree, the optimal strategy can be determined by working out the __Minimax value__ of each state of the tree.\n\nThe minimax value is the utility (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game. \nThe minimax value of a terminal state is just its utility.\nIn a non-terminal state, MAX prefers to move to a state of maximum value when it is MAX’s turn to move, and MIN prefers a state of minimum value.\nIn minimax search, the value of a node is the optimal value of its children. For the MAX player, that's the highest value. For MIN, that's the lowest value. This is because minimax assumes both players play optimally.\n\n__Minimax search algorithm__ solves perfect information, zero-sum games. The minimax algorithm uses a depth-first approach.\nIt is a recursive algorithm that proceeds all the way down to the leaves of the tree and then backs up the minimax values through the tree as the recursion unwinds.\n- time-complexity: O(bm)\n- space complexity: O(bm) generates all actions at once/ O(m) generates actions one at a time\n\n__Alpha-Beta pruning__:\nThe effectiveness of Alpha-Beta pruning depends on the order in which successor nodes are examined.\nAlpha-beta with __perfect move ordering__: O(b^(m/2)) instead of O(b^m), effective branching factor becomes sqrt(b) instead of b.\nAlpha-beta with __random move ordering__: O(b^(3m/4)), for moderate b.\nDynamic move-ordering schemes: trying first the moves that were found to be best in the past (precious move/ iterative deepening).\n\n__Type A strategy__ considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation\\ \nfunction to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree.\n__Type B strategy__ ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nEvaluation function should be strongly correlated with the actual chances of winning, \nbut it need not be linearly correlated: if state is twice as likely to win as state we don’t require that EVAL(S) be twice EVAL(S'); \nall we require is that EVAL(S) > EVAL(S'). \n\nMany game-playing programs use __table lookup__ rather than search for the opening and ending of games.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nChance nodes + MAX and MIN nodes \n\n__expectiminimax__: generalization of minimax, Terminal nodes and MAX and MIN nodes work exactly the same way as before \n(with the caveat that the legal moves for MAX and MIN will depend on the outcome of the chance event in the previous chance node). \nFor chance nodes we compute the expected value, which is the sum of the value over all outcomes, weighted by the probability of each chance action.\n\nProblem: An order-preserving transformation on leaf evaluation values could change the best move. \nTo avoid this problem, the evaluation function must return values that are a positive linear transformation of the probability of winning \n(or of the expected utility, for games that have outcomes other than win/lose).\n\nWhen the move is deterministic, Expectiminimax will also choose the optimal movement (no chance to take a random movement), just like minimax. \nMinimax: O(b^m), Expectiminimax: O(b^m n^m), n: number of distinct rolls of dice.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe expected utility of an action is the average utility value of outcomes weighed by the probability of that outcome occurring.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nSix constraints of reasonable preference relation(axioms of utility theory):\n- ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. The agent cannot avoid deciding.\n- TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C.\n- CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure\nand the lottery that yields A with probability p and C with probability (1-p).\n- SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B\nis substituted for A in one of them\n- MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A, then the agent must prefer the lottery that has a higher\nprobability for A.\n- DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nEMV: expected monetary value\n\ninsurance premium = difference between the EMV of a lottery and its certainty equivalent\n\nrisk-averse: prefer a sure thing with a payoff that is less than the expected monetary value of a gamble\n\nambiguity aversion: Most people elect the known probability rather than the unknown unknowns\n\nframing effect: wording of a decision problem can have a big impact on the agent’s choices\n\nanchoring effect: People feel more comfortable making relative utility judgments rather than absolute ones\n\n\n\n\n## Module 5 Lecture Notes\n \n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Move** - action\n* **Position** - state\n* **Alpha** - highest value along the path for MAX\n* **Beta** - lowest value along the path for MIN\n* **Killer moves** - Best moves\n* **Killer move heuristic** -  try best moves first\n* **Heuristic evaluation function** - eval(s,p) estimate of the expected utility of state s of player p, equal to utility at terminal\n* **Quiescent** - positions where there is no pending move that would influence the evaluation\n* **Quiescence search** - consider only certain types of moves that will quickly resolve the uncertainties\n* **Horizon effect** - when facing unavoidable serious damage, temporarily avoid loss by delaying\n* **Forward pruning** - prunes moves that appear to be poor moves, saves computational time but could be an error, type B strategy\n* **Policy** - a mapping from every possible state to the best move in that state\n* **Value function / ordinal utility function** - in deterministic environment, agent needs preference ranking on states, not numbers\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "CSPs deal with assignments of values to variables. \n",
        "\n",
        "An assignment that does not violate any constraints is called a __consistent__ or legal assignment.\n",
        "\n",
        "Solution to a CSP is a consistent, complete assignment.\n",
        "\n",
        "CSP differ from search problems that:\n",
        "In search problems, states are black boxes with a transition model to move between boxes. \n",
        "In CSPs, the agent can see inside the states and move between states accordingly.\n",
        "\"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\" \n",
        "__AC-3__: algorithm for enforcing arc consistency:\n",
        "- maintains a queue of arcs, initially, the queue contains all the arcs\n",
        "- pops off an arbitrary arc from the queue, (X1, X2), makes X1 arc-consistent with respect to X2\n",
        "- Domian D unchanged: next arc; D changes: add all arcs of neighbors of X1, (Xn, X1)\n",
        "- Assume a CSP with n variables, each with domain size at most d,  with c binary constraints (arcs). worst case time: __O(cd^3)__\n",
        "\n",
        "constraint satisfaction is NP-complete in general, and any algorithm for establishing n-consistency must take \n",
        "time exponential in n in the worst case. Worse, n-consistency also requires space that is exponential in n.\n",
        "\n",
        "CSPs can rule out variable assignments using __search__ or __inference__.\n",
        "Inference techniques use constraints to rule out variable assignment.\n",
        "The key idea behind inference in CSPs is enforcing k-consistency. \n",
        "\"\"\"\n",
        "\n",
        "chapter6_3 = \"\"\" \n",
        "minimum-remaining-values (MRV) heuristic: choosing the variable with the fewest “legal” values\n",
        "The minimum-remaining-values and degree heuristics are domain-independent\n",
        "methods for deciding which variable to choose next in a backtracking search. \n",
        "\n",
        "The least-constraining-value heuristic helps in deciding which value to try first for a given\n",
        "variable.\n",
        "\n",
        "Backtracking occurs when no legal assignment can be found for a variable.\n",
        "\n",
        "Conflict-directed backjumping backtracks directly to the source of the problem.\n",
        "\n",
        "Constraint learning records the conflicts as they are encountered during search in order to avoid the same conflict later in the search.\n",
        "\n",
        "__forward checking__: Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each\n",
        "unassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for X.\n",
        "\n",
        "__MAC(Maintaining Arc Consistency)__: Both search and inference. After a variable Xi is assigned a value, the INFERENCE procedure calls AC-3, but instead\n",
        "of a queue of all arcs in the CSP, we start with only the arcs (Xj, Xi) for all Xj that are\n",
        "__unassigned variables__ that are neighbors of Xi. From there, AC-3 does constraint\n",
        "propagation in the usual way, and if any variable has its domain reduced to the empty set,\n",
        "the call to AC-3 fails and we know to __backtrack__ immediately.\n",
        "\n",
        "Difference between MAC and AC-3:\n",
        "MAC is a way of interleaving search and inference. AC-3 is pure inference. \n",
        "MAC runs while assigning variables in backtracking search. \n",
        "Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3.\n",
        "\n",
        "Difference between MAC and forward checking:\n",
        "MAC recursively propagates constraints, whereas forward checking does not. \n",
        "\n",
        "BACKTRACKING-SEARCH: back up to the preceding variable and try a different value for it.\n",
        "\n",
        "Backjumping method backtracks to the most recent assignment in the conflict set.\n",
        "\"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\" \"\"\"\n",
        "\n",
        "chapter6_5 = \"\"\" \n",
        "Solving an arbitrary CSP takes exponential time in the number of variables.\n",
        "\n",
        "Solving a tree-structured CSP takes linear time in the number of variables. (tree: when any two variables are connected by only one path)\n",
        "\n",
        "__Cutset conditioning__ is used to reduce a general CSP to a tree structured one.\n",
        "__Tree decomposition__ techniques transform the CSP into a tree of subproblems.\n",
        "\n",
        "Cutset conditioning vs tree decomposition:\n",
        "Cutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width w.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "General idea:\n",
        "- Represent the __constraints__ that solutions must satisfy in a __uniform declarative language__\n",
        "- Find solutions by __GENERAL PURPOSE__ search algorithms with no changes from problem to problem\n",
        "- No hand-built transition functions\n",
        "- No hand-built heuristics\n",
        "- Just specify the problem in a formal declarative language, and a general-purpose algorithm does everything else\n",
        "\n",
        "Depth-first search for CSPs with single-variable assignments is called __backtracking search__.\n",
        "Backtracking search is the basic uninformed algorithm for CSPs.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"unary constraint\": \"restricts the value of one variable\",\n",
        "\"binary constraint\": \"restriction involves two variables\",\n",
        "\"binary CSP\": \"with only unary and binary constraints\",\n",
        "\"global constraint\": \"A constraint involving an arbitrary number of variables, don't nedd to be all variables\",\n",
        "\"Node consistency\": \"k-consistency for k=1\",\n",
        "\"Arc consistency\": \"k-consistency for k=2\",\n",
        "\"Path consistency\": \"k-consistency for k=3\",\n",
        "\"k-consistent\": \"for any set of k−1 variables, when they are consistently assigned, a consistent value can be assigned to kth variable\",\n",
        "\"strongly k-consistent\": \"CSP is k-consistent, k-1 consistent, ..., 1-consistent\",\n",
        "\"resource constraint\": \"atmost constraint, enforce by deleting the max value of any domain not consistent with the min of other domians\",\n",
        "\"bounds-consistent\": \"both lowerbound and upperbound of X have some Y satisfies the constraint between X and Y\",\n",
        "\"directional arc consistency(DAC)\": \"ordered variables X1...Xn, every Xi is arc-consistent with every Xj, where j>i\",\n",
        "\"cycle cutset\": \"subset S, removal of S makes constraint graph to a tree\",\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "fdb94a52-8db9-4c6e-a5dd-20089d01d1e4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSPs deal with assignments of values to variables. \n\nAn assignment that does not violate any constraints is called a __consistent__ or legal assignment.\n\nSolution to a CSP is a consistent, complete assignment.\n\nCSP differ from search problems that:\nIn search problems, states are black boxes with a transition model to move between boxes. \nIn CSPs, the agent can see inside the states and move between states accordingly.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n__AC-3__: algorithm for enforcing arc consistency:\n- maintains a queue of arcs, initially, the queue contains all the arcs\n- pops off an arbitrary arc from the queue, (X1, X2), makes X1 arc-consistent with respect to X2\n- Domian D unchanged: next arc; D changes: add all arcs of neighbors of X1, (Xn, X1)\n- Assume a CSP with n variables, each with domain size at most d,  with c binary constraints (arcs). worst case time: __O(cd^3)__\n\nconstraint satisfaction is NP-complete in general, and any algorithm for establishing n-consistency must take \ntime exponential in n in the worst case. Worse, n-consistency also requires space that is exponential in n.\n\nCSPs can rule out variable assignments using __search__ or __inference__.\nInference techniques use constraints to rule out variable assignment.\nThe key idea behind inference in CSPs is enforcing k-consistency. \n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nminimum-remaining-values (MRV) heuristic: choosing the variable with the fewest “legal” values\nThe minimum-remaining-values and degree heuristics are domain-independent\nmethods for deciding which variable to choose next in a backtracking search. \n\nThe least-constraining-value heuristic helps in deciding which value to try first for a given\nvariable.\n\nBacktracking occurs when no legal assignment can be found for a variable.\n\nConflict-directed backjumping backtracks directly to the source of the problem.\n\nConstraint learning records the conflicts as they are encountered during search in order to avoid the same conflict later in the search.\n\n__forward checking__: Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each\nunassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for X.\n\n__MAC(Maintaining Arc Consistency)__: Both search and inference. After a variable Xi is assigned a value, the INFERENCE procedure calls AC-3, but instead\nof a queue of all arcs in the CSP, we start with only the arcs (Xj, Xi) for all Xj that are\n__unassigned variables__ that are neighbors of Xi. From there, AC-3 does constraint\npropagation in the usual way, and if any variable has its domain reduced to the empty set,\nthe call to AC-3 fails and we know to __backtrack__ immediately.\n\nDifference between MAC and AC-3:\nMAC is a way of interleaving search and inference. AC-3 is pure inference. \nMAC runs while assigning variables in backtracking search. \nInstead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3.\n\nDifference between MAC and forward checking:\nMAC recursively propagates constraints, whereas forward checking does not. \n\nBACKTRACKING-SEARCH: back up to the preceding variable and try a different value for it.\n\nBackjumping method backtracks to the most recent assignment in the conflict set.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nSolving an arbitrary CSP takes exponential time in the number of variables.\n\nSolving a tree-structured CSP takes linear time in the number of variables. (tree: when any two variables are connected by only one path)\n\n__Cutset conditioning__ is used to reduce a general CSP to a tree structured one.\n__Tree decomposition__ techniques transform the CSP into a tree of subproblems.\n\nCutset conditioning vs tree decomposition:\nCutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width w.\n\n\n\n## Module 6 Lecture Notes\n \nGeneral idea:\n- Represent the __constraints__ that solutions must satisfy in a __uniform declarative language__\n- Find solutions by __GENERAL PURPOSE__ search algorithms with no changes from problem to problem\n- No hand-built transition functions\n- No hand-built heuristics\n- Just specify the problem in a formal declarative language, and a general-purpose algorithm does everything else\n\nDepth-first search for CSPs with single-variable assignments is called __backtracking search__.\nBacktracking search is the basic uninformed algorithm for CSPs.\n\n\n\n## Module 6 Definitions\n* **Unary constraint** - restricts the value of one variable\n* **Binary constraint** - restriction involves two variables\n* **Binary csp** - with only unary and binary constraints\n* **Global constraint** - A constraint involving an arbitrary number of variables, don't nedd to be all variables\n* **Node consistency** - k-consistency for k=1\n* **Arc consistency** - k-consistency for k=2\n* **Path consistency** - k-consistency for k=3\n* **K-consistent** - for any set of k−1 variables, when they are consistently assigned, a consistent value can be assigned to kth variable\n* **Strongly k-consistent** - CSP is k-consistent, k-1 consistent, ..., 1-consistent\n* **Resource constraint** - atmost constraint, enforce by deleting the max value of any domain not consistent with the min of other domians\n* **Bounds-consistent** - both lowerbound and upperbound of X have some Y satisfies the constraint between X and Y\n* **Directional arc consistency(dac)** - ordered variables X1...Xn, every Xi is arc-consistent with every Xj, where j>i\n* **Cycle cutset** - subset S, removal of S makes constraint graph to a tree\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "A knowledge-based agent can be built simply by TELLing it what it needs to know.\n",
        "\n",
        "__Models__ are mathematical abstractions that have a fixed set of truth values which are {true, false} for each sentence.\n",
        "- If sentence 𝛂 is true in model m then we say:\n",
        "- m satisfies 𝛂, or m is a model of 𝛂\n",
        "- We use the notation M(𝛂) to mean the set of all models of 𝛂\n",
        "\"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\" \"\"\"\n",
        "\n",
        "\n",
        "chapter7_3 = \"\"\" \"\"\"\n",
        "\n",
        "chapter7_4 = \"\"\" \n",
        "For complex sentences, we have five rules, which hold for any subsentences P andQ  (atomic or complex) in any model m:\n",
        "- ¬P is true iff P is false in m.\n",
        "- P ∧ Q is true iff both P and Q are true in m.\n",
        "- P ∨ Q is true iff either P or Q is true in m.\n",
        "- P => Q is true unless P is true and Q is false in m.\n",
        "- P <=> Q is true iff P and Q are both true or both false in m.\n",
        "\n",
        "\n",
        "Note for implication =>:\n",
        "-\tpropositional logic does not require any relation of causation or relevance between P and Q.\n",
        "-\tAny implication is true whenever its antecedent is false. For example, “5 is even implies Sam is smart” is true, regardless of whether Sam is smart.\n",
        "\n",
        "\n",
        "If KB and alpha contain n symbols in all, then there are 2^n models. \n",
        "Thus, the time complexity of the algorithm is O(2^n). The space complexity is only O(n) because the enumeration is depth-first.\n",
        "\n",
        "Every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter7_5 = \"\"\" \n",
        "Every sentence of propositional logic is logically equivalent to a conjunction of clauses.\n",
        "\n",
        "Conjunctive Normal Form: A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF.\n",
        "\n",
        "procedure for converting to CNF:\n",
        "1. Eliminate <=>, replacing α<=>β with (α ⇒ β) ∧ (β ⇒ α)\n",
        "2. Eliminate ⇒,  replacing α ⇒ β with (¬α ∨ β)\n",
        "3. CNF requires ¬ to appear only in literals, so we “move ¬ inwards”:\n",
        "¬(α ∧ β) ≡ (¬α ∨¬β)   (De Morgan),\n",
        "¬(α ∨ β) ≡ (¬α ∧ ¬β)   (De Morgan)\n",
        "4. Distribute ∨ over ∧ wherever possible.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "__Forward Chaining__ is a kind of data-driven reasoning. An agent can start with known\n",
        "data, adding premises as new percepts come in, and then incrementally apply the\n",
        "forward chaining algorithm to derive new conclusions. It doesn’t have to have a\n",
        "specific query in mind to do so.\n",
        "\n",
        "__Backward chaining__ works backwards from a query. If the query is known to be true,\n",
        "then no work is needed. Otherwise, the algorithm finds implications in the KB whose\n",
        "conclusions is the query. If all the premises of one of those can be proved to be true\n",
        "(via backward chaining), then the query is true.\n",
        "\n",
        "__Backward chaining__ is a form of goal-directed reasoning.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\": \"reason over an internal representation of knowledge and decide to take actcion\",\n",
        "\"KB\": \"knowledge base, set of sentences in knowledge representation language\",\n",
        "\"logic\": \"general class of representations for knowledge-based agents\",\n",
        "\"axiom\": \"sentence is given, without inference, i.e. not derived sentence\",\n",
        "\"syntax\": \"the structure of sentences\",\n",
        "\"semantics\": \"meaning, defines the truth of sentences\",\n",
        "\"entailment\": \"a sentence follows logically from another, a entails b iff in every model where a true, b s also true\",\n",
        "\"sound / truth-preserving\": \"an inference algo that derives only entailed sentences\",\n",
        "\"completeness\": \"an inference algo that can derive any sentence that is entailed\",\n",
        "\"grounding\": \"connection between logical reasoning processes and the real environment\", \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "87b382b5-6e40-45cc-db41-0db8a367e5a8"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nA knowledge-based agent can be built simply by TELLing it what it needs to know.\n\n__Models__ are mathematical abstractions that have a fixed set of truth values which are {true, false} for each sentence.\n- If sentence 𝛂 is true in model m then we say:\n- m satisfies 𝛂, or m is a model of 𝛂\n- We use the notation M(𝛂) to mean the set of all models of 𝛂\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \n\n## AIMA Chapter 7.3 Logic\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nFor complex sentences, we have five rules, which hold for any subsentences P andQ  (atomic or complex) in any model m:\n- ¬P is true iff P is false in m.\n- P ∧ Q is true iff both P and Q are true in m.\n- P ∨ Q is true iff either P or Q is true in m.\n- P => Q is true unless P is true and Q is false in m.\n- P <=> Q is true iff P and Q are both true or both false in m.\n\n\nNote for implication =>:\n-\tpropositional logic does not require any relation of causation or relevance between P and Q.\n-\tAny implication is true whenever its antecedent is false. For example, “5 is even implies Sam is smart” is true, regardless of whether Sam is smart.\n\n\nIf KB and alpha contain n symbols in all, then there are 2^n models. \nThus, the time complexity of the algorithm is O(2^n). The space complexity is only O(n) because the enumeration is depth-first.\n\nEvery known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input.\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses.\n\nConjunctive Normal Form: A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF.\n\nprocedure for converting to CNF:\n1. Eliminate <=>, replacing α<=>β with (α ⇒ β) ∧ (β ⇒ α)\n2. Eliminate ⇒,  replacing α ⇒ β with (¬α ∨ β)\n3. CNF requires ¬ to appear only in literals, so we “move ¬ inwards”:\n¬(α ∧ β) ≡ (¬α ∨¬β)   (De Morgan),\n¬(α ∨ β) ≡ (¬α ∧ ¬β)   (De Morgan)\n4. Distribute ∨ over ∧ wherever possible.\n\n\n## Module 7 Lecture Notes\n \n__Forward Chaining__ is a kind of data-driven reasoning. An agent can start with known\ndata, adding premises as new percepts come in, and then incrementally apply the\nforward chaining algorithm to derive new conclusions. It doesn’t have to have a\nspecific query in mind to do so.\n\n__Backward chaining__ works backwards from a query. If the query is known to be true,\nthen no work is needed. Otherwise, the algorithm finds implications in the KB whose\nconclusions is the query. If all the premises of one of those can be proved to be true\n(via backward chaining), then the query is true.\n\n__Backward chaining__ is a form of goal-directed reasoning.\n\n\n## Module 7 Definitions\n* **Knowledge-based agents** - reason over an internal representation of knowledge and decide to take actcion\n* **Kb** - knowledge base, set of sentences in knowledge representation language\n* **Logic** - general class of representations for knowledge-based agents\n* **Axiom** - sentence is given, without inference, i.e. not derived sentence\n* **Syntax** - the structure of sentences\n* **Semantics** - meaning, defines the truth of sentences\n* **Entailment** - a sentence follows logically from another, a entails b iff in every model where a true, b s also true\n* **Sound / truth-preserving** - an inference algo that derives only entailed sentences\n* **Completeness** - an inference algo that can derive any sentence that is entailed\n* **Grounding** - connection between logical reasoning processes and the real environment\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": 0
        },
        "id": "T3cm1WV542_a",
        "outputId": "bddc337f-e39c-410f-87b8-72a13704f81e"
      },
      "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",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nSix disciplines compose most of AI:\n1. natural language processing to communicate successfully in a human language;\n2. knowledge representation to store what it knows or hears; \n3. automated reasoning to answer questions and to draw new conclusions; \n4. machine learning to adapt to new circumstances and to detect and extrapolate patterns.\n5. computer vision and speech recognition to perceive the world; \n6. robotics to manipulate objects and move about.\n\nTwo advantages of rational-agent approach:\n1. More general than the “laws of thought” approach (correct inference is just one of the possible mechanisms for achieving rationality)\n2. More amenable to scientific development (mathematically well-defined and completely general)\n\nAI focused on the study and construction of agents that do the right thing – objective that we provide to the agent, also called standard model.As it becomes more difficult to specify the objective completely and correctly, standard model is not the right model in the long run.\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Informality - Turing: “argument from informality of behavior” – human behavior is too complex to be captured by and formal set of rules.\nKey proponent: Hubert Dreyfus, critiques of AI (Good Old-Fashioned AI, GOFAI)\nEmbodied cognition: study the system as a whole, cognition takes place within a body, which is embedded in an environment. Robotics, vision and other sensors become central, not peripheral \n\nDisability - claim “a machine can never do X”.\nTuring: examples of X “be kind, resourceful, beautiful,…\"\n\nMathematical objection - Turing and Godel proved that certain mathematical questions are in principle unanswerable by particular formal systems. E.g. Godel’s incompleteness theorem\n\nMeasuring AI - Turing Test\nwhether a machine can pass a behavioral test – chat with an interrogator for 5 min, passes the test if it fools the interrogator 30% of the time\nKey point: idea of measuring intelligence by performance on some kind of open-ended behavioral task\nFocus of research within AI community: improve basic science and technology to provide useful tools, not to fool judges\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n John Searle: computers generate no understanding, just like the Chinese room \n\n## AIMA 2.1 Agents and Environments\n In general, an agent’s choice of action at any given instant can depend on its built-inknowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived. \n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rationality is not perfection, where rationality maximizes expected performanceand perfection maximizes actual performance. \n\n## AIMA 2.3 The Nature of Environments\n Task environment consists of PEAS: Performance, Environment, Actuators, Sensors.\n\nProperties of task environments:\nFully observable vs. partially observable vs unobservable,\nSingle-agent vs. (competitive/cooperative) multiagent,\nDeterministic vs. nondeterministic,\nEpisodic vs. sequential,\nStatic vs. dynamic,\nDiscrete vs. continuous,\nKnown vs. unknown\n \n\n## AIMA 2.4 The Structure of Agents\n Agent = architecture + program\n\n4 basic kinds of agent programs:\n- Simple reflex agents: select actions on the basis of the current percept\n- Model-based reflex agents: use transition model(“how the world works”) and sensor model(how the state of the world is reflected in the agent’s percepts) to keep track of the state of the world (internal state)\n- Goal-based agents: keep track of a set of goals it is trying to achieve. E.g. search and planning\n- Utility-based agents: a rational utility-based agent chooses the action that maximizes the expected utility of the action outcomes\n\nAll agents can improve their performance through learning.\n\n\n## Module 1 Lecture Notes\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive(through sensors) and act(through actuators) in an environment\n* **Rational agent** - select action that maximizes performance measure given percept sequence and built-in knowledge\n* **Limited rationality** - do the most appropriate thing under limited computational availability\n* **Value alignment problem** - human and machine should share the same values or objectives\n* **Weak ai** - machine pretends to think\n* **Strong ai** - machine can consiously think\n* **Consciousness** - aware of the environment, of self, of subjective experience of living\n* **Qualia** - internal, subjective sense, experience\n* **Percept** - what an agent’s sensors are perceiving\n* **Percept sequence** - complete history of what an agent has perceived\n* **Agent function** - abstract mathematical description, maps given percept sequence to action\n* **Agent program** - concrete implementation of agent function, running within physical system\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\nAll data  treated as objects.\n\nStrong Typing: Every object has a fixed type, interpreter doesn’t allow things incompatible with that type(eg. “foo”+2)\n\nExamples of Types: int, float, str, tuple, dict, list, bool, None, generator, function\n\nDynamic typing: variables come into existence when first assigned, type is automatically determined. If assign agian, type is updated.\n\nString:\n- Immutable\n- concatenate use \"+\"\n- r means raw: no need to escape special characters. eg r'\n' will print out \n. Without r, will print out nothing.\n- use of %: print(\"%s can speak %d languages\" % (\"C3PO\",  6000000)) will print \"C3PO can speak 6000000 languages\".\n- s.split(\" \"): split s on space; \"_\".join(words): join a list to form a string with underscore\n\nList:\n- Mutable\n- y = x[:] to get a shallow copy of x\n- .index(): index of first occurrence; .count(): number of occurrences; .remove(): remove first occurrence;.reverse(): reverse in place; .sort(): sort in place; sorted(list): return a copy sorted\n\n\nTuple:\n- Immutable ordered sequence of items, items can be of mixed types, including collection types\n\nDictionary:\n- unordered, keys must be immutable, constant average time add, lookup, update\n- .keys(); .values(); .items()\n- defaultdict(str) automatically initializes nonexistent dictionary values to \"\", (int) initializes to 0, etc.\n- Counter() also initializes nonexistent dictionary, value to 0\n\nFunction:\n- can return muptiple values, return type: tuple\n- if default values are specified in def, the arguments are optional when calling the function,non-default argument should always precede default arguments; otherwise, it reports SyntaxError\n- myfun(1,2,3) OK; myfun(c=3, b=1, a=2) OK; myfun(1, c=3, b=2) OK; myfun(a=1, b=3, 2) SyntaxError\n- *args: accept a variable number of non-keyword arguments to your function\n- **kwargs: keyword arguments, kwargs is a dict of the keyword args passed to the fn\n\nClass:\n- constructors:__init__, \n- subclass: the ancestor’s __init__ method is executed in addition to new commands\nclass subClass(parentClass):must be done explicitly init: parentClass.__init__(self, x, y)\n- magic methods: __len__: define len(obj). __copy__: define copy. __cmp__: define ==. __add__:  Define + .__neg__: define unary  negation\n\n\n## Module 2 Definitions\n* **Duck typing** - determine if methods are present\n* **List comprehensions** - [expression for name in list if filter]\n* **Iterable** - has __iter__ method, returns an iterator obj\n* **Iterator** - object with a __next()__ method, throws StopIteration when done, memory efficient\n* **Generator** - generators are iterators, next method runs until a yield statement, stops and returns\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nTo fully define a search problem:\n- State space: set of possible states that the environment can be in\n- Initial state: agent starts in\n- Goal states: one or more or a property that applies to many states\n- Actions: available to the agent\n- Transition model: describes what each action does. E.g. RESULT(s,a) returns the state from doing action a in state s.\n- Action cost function\n \n\n## AIMA Chapter 3.2 Example Problems\n \nRoute-finding problems are defined in terms of specified locations and transitions along edges between them.\n\nTouring problems describe a set of locations that must be visited, rather than a single goal\ndestination. The traveling salesperson problem (TSP) is a touring problem in which every\ncity on a map must be visited.\n\nA VLSI layout problem requires positioning millions of components and connections on a\nchip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize\nmanufacturing yield.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \nFrontier separates two regions of the state-space graph: an interior region where every state has been expanded, and an exterior region of states that have not yet been reached.\n\nEvaluate an algorithm’s performance: complete, optimal, time and space complexity\n\nBest-first search: \n- choose node n with minimum value of some evaluation function f(n).\n- Uses priority queue – first pops the node with minimum cost.\n- graph-search \n\nBreadth-first-search: \n- Uses FIFO queue – first pops the node that was added to the queue first\n\nDepth-first-search:\n- Uses LIFO queue(stack) – first pops the most recently added node\n- Tree-like search\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n__Breadth-first-search__: \n- expands the shallowest nodes first\n- complete\n- cost-optimal for unit action costs (where all actions have same cost)\n- Both time and space complexity are O(b^d), b: # of successors of each state, d: depth\n- large memory requirement: exponential\n\n__Dijkstra’s algorithm / Uniform-cost search__：\n- Actions have different costs, use best-first search, evaluation function is the path cost, optimal for general action costs\n- complete\n- cost optimal\n- worst case time and space complexity, O(b^(1+floor(C*/e))), C*: cost of the optimal solution, e: lower bound on the cost of each action,can be much higher than b^d\n\n__Depth-first-search__:\n- expands the deepest unexpanded node first\n- incomplete\n- not cost-optimal\n- linear space complexity, O(bm), m: maximum depth of the tree; b: branching factor\n- __Depth-limited search__ adds a depth bound L, incomplete when a poor choice of L fails to reach the solution\n\n__Iterative deepening search__:\n- calls depth-first search with increasing depth limits until a goal is found\n- complete when full cycle checking is done\n- optimal for unit action costs\n- time complexity comparable to breadth-first search, linear space complexity\n\n__Bidirectional search__:\n- expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet\n- complete and optimal\n\n\n## Module 3 Lecture Notes\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** - a sequence of actions\n* **Solution** - a path from the initial state to a goal state\n* **Optimal solution** - a solution with the lowest path cost\n* **Model** - formulation or the problem, abstract mathematical description\n* **Complete** - algorithm finds a solution iff there is one, must reach every state systematically\n* **Cost optimal** - algorithm finds a solution with the lowest path cost of all solutions\n* **D, depth** - depth or number of actions in an optimal solution\n* **M** - maximum number of actions in any path\n* **B, branching factor** - branching factor or number of successors of a node that need to be considered\n* **Graph search** - checks for redundant paths, more memory for storing reached states and redundant paths, faster\n* **Tree-like search** - does not check for redundant paths, less memory but slower\n* **Uninformed search** - only knows problem definition, doesn't know how close a state is to the goal\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n__Greedy Best-First Search__:\n- expands nodes with minimal h(n) value, f(n)=h(n)\n- not optimal, but often efficient\n- complete in finite state spaces, but not in infinite ones\n- worst-case time and space complexity is O(|V|). A good heuristic function can reduce complexity to linear O(bm)\n\n__A* search__ – most common informed search algorithm:\n- expands nodes with minimal f(n)=g(n)+h(n), where g(n) is the path cost from the initial state to node n\n- complete\n- optimal if h(n) is admissible\n- efficient bc it prunes away nodes that are not necessary for finding an optimal solution\n- main issue: memory(frontier and reached), the number of nodes expanded can be exponential in the length of the solution\n\nEvery consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A* is cost-optimal.\n\n__Beam search__ limits the size of the frontier. The easiest approach is to keep only the nodes with the best k-scores, discarding any other expanded nodes. Incomplete and suboptimal, but less memory, and fast.\n\n__Iterative-deepening A* search__ (IDA*) addresses the space complexity issue, not keeping all reached states in\nmemory, at a cost of visiting some states multiple times. Cutoff is the f-cost (g+h); at each iteration, the cutoff value is the\nsmallest f-cost of any node that exceeded the cutoff on the previous iteration.\n\n__Recursive best-first search__ (RBFS) uses linear space. RBFS resembles a recursive depthfirst\nsearch, uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor\nof the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path.\nRBFS and __SMA*__ (simplified memory-bounded A*) are robust, optimal search algorithms that use limited amounts of memory; \ngiven enough time, they can solve problems for which A* runs out of memory.\n\n__Wighted A* search__ focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nA well-designed heuristic would have b* close to 1.\n\n\nState-space graph of the relaxed problem is a supergraph of the original state space. \nAny optimal solution in the original problem is, also a solution in the relaxed problem; \nbut the relaxed problem may have better solutions if the added edges provide shortcuts. \nHence, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\nThe performance of heuristic search algorithms depends on the quality of the heuristic function. \nConstruct good heuristics:\n- relaxing the problem definition\n- storing precomputed solution costs for subproblems in a pattern database\n- defining landmarks\n- learning from experience with the problem class\n\n\n## Module 4 Lecture Notes\n \n\n## Module 4 Definitions\n* **Informed search** - has access to the problem definition and heuristic function h(n)\n* **Heuristic function** - estimates the cost of the shortest path from the current node n to a goal node\n* **Admissible heuristics** - optimistic, never overestimates the cost\n* **Consistent heuristics** - h(n) <= c(n, a, n’) + h(n’), triangle inequality\n* **Weighted a* search** - weigh h(n) more, f(n)=g(n)+h(n)*W, with W>1\n* **Bounded suboptimal search** - solution guaranteed to be within a constant factor W of the optimal cost. e.g. weighted A*\n* **Bounded-cost search** - cost of solution less than some constant C\n* **Unbounded-cost search** - accept a solution as long as we can find it quickly, e.g. speedy search\n* **Effective branching factor b*** - N+1 = 1 + b* + (b*)^2 + … + (b*)^d\n* **Manhattan distance** - sum of the absolute differences\n* **Effective depth** - A* pruning reduces the effective depth by a constant compared to the true depth\n* **Heuristic dominate** - h2 dominates h1 if h2(n) >= h1(n). A* using will h2 never expand more nodes than using h1\n* **Relaxed problem** - fewer restrictions on actions\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nGames differ from search problems: Games have multiple agents\n\nTwo players: MAX & MIN, MAX moves first\n\nTo define a game as a search problem:\n- initial state S0\n- To-Move(s): the player whose turn it is to move in state s\n- Actions(s): set of legal moves that a player can make\n- Result(s,a): Transitional model, state resulting from taking action in state s.\n-\tIs-Terminal(s): terminal test, terminal states\n- Utility(s,p): utility functions\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nIn a game tree, the optimal strategy can be determined by working out the __Minimax value__ of each state of the tree.\n\nThe minimax value is the utility (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game. \nThe minimax value of a terminal state is just its utility.\nIn a non-terminal state, MAX prefers to move to a state of maximum value when it is MAX’s turn to move, and MIN prefers a state of minimum value.\nIn minimax search, the value of a node is the optimal value of its children. For the MAX player, that's the highest value. For MIN, that's the lowest value. This is because minimax assumes both players play optimally.\n\n__Minimax search algorithm__ solves perfect information, zero-sum games. The minimax algorithm uses a depth-first approach.\nIt is a recursive algorithm that proceeds all the way down to the leaves of the tree and then backs up the minimax values through the tree as the recursion unwinds.\n- time-complexity: O(bm)\n- space complexity: O(bm) generates all actions at once/ O(m) generates actions one at a time\n\n__Alpha-Beta pruning__:\nThe effectiveness of Alpha-Beta pruning depends on the order in which successor nodes are examined.\nAlpha-beta with __perfect move ordering__: O(b^(m/2)) instead of O(b^m), effective branching factor becomes sqrt(b) instead of b.\nAlpha-beta with __random move ordering__: O(b^(3m/4)), for moderate b.\nDynamic move-ordering schemes: trying first the moves that were found to be best in the past (precious move/ iterative deepening).\n\n__Type A strategy__ considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation\\ \nfunction to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree.\n__Type B strategy__ ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nEvaluation function should be strongly correlated with the actual chances of winning, \nbut it need not be linearly correlated: if state is twice as likely to win as state we don’t require that EVAL(S) be twice EVAL(S'); \nall we require is that EVAL(S) > EVAL(S'). \n\nMany game-playing programs use __table lookup__ rather than search for the opening and ending of games.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nChance nodes + MAX and MIN nodes \n\n__expectiminimax__: generalization of minimax, Terminal nodes and MAX and MIN nodes work exactly the same way as before \n(with the caveat that the legal moves for MAX and MIN will depend on the outcome of the chance event in the previous chance node). \nFor chance nodes we compute the expected value, which is the sum of the value over all outcomes, weighted by the probability of each chance action.\n\nProblem: An order-preserving transformation on leaf evaluation values could change the best move. \nTo avoid this problem, the evaluation function must return values that are a positive linear transformation of the probability of winning \n(or of the expected utility, for games that have outcomes other than win/lose).\n\nWhen the move is deterministic, Expectiminimax will also choose the optimal movement (no chance to take a random movement), just like minimax. \nMinimax: O(b^m), Expectiminimax: O(b^m n^m), n: number of distinct rolls of dice.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe expected utility of an action is the average utility value of outcomes weighed by the probability of that outcome occurring.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nSix constraints of reasonable preference relation(axioms of utility theory):\n- ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. The agent cannot avoid deciding.\n- TRANSITIVITY: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C.\n- CONTINUITY: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure\nand the lottery that yields A with probability p and C with probability (1-p).\n- SUBSTITUTABILITY: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B\nis substituted for A in one of them\n- MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A, then the agent must prefer the lottery that has a higher\nprobability for A.\n- DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability.\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nEMV: expected monetary value\n\ninsurance premium = difference between the EMV of a lottery and its certainty equivalent\n\nrisk-averse: prefer a sure thing with a payoff that is less than the expected monetary value of a gamble\n\nambiguity aversion: Most people elect the known probability rather than the unknown unknowns\n\nframing effect: wording of a decision problem can have a big impact on the agent’s choices\n\nanchoring effect: People feel more comfortable making relative utility judgments rather than absolute ones\n\n\n\n\n## Module 5 Lecture Notes\n \n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Move** - action\n* **Position** - state\n* **Alpha** - highest value along the path for MAX\n* **Beta** - lowest value along the path for MIN\n* **Killer moves** - Best moves\n* **Killer move heuristic** -  try best moves first\n* **Heuristic evaluation function** - eval(s,p) estimate of the expected utility of state s of player p, equal to utility at terminal\n* **Quiescent** - positions where there is no pending move that would influence the evaluation\n* **Quiescence search** - consider only certain types of moves that will quickly resolve the uncertainties\n* **Horizon effect** - when facing unavoidable serious damage, temporarily avoid loss by delaying\n* **Forward pruning** - prunes moves that appear to be poor moves, saves computational time but could be an error, type B strategy\n* **Policy** - a mapping from every possible state to the best move in that state\n* **Value function / ordinal utility function** - in deterministic environment, agent needs preference ranking on states, not numbers\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSPs deal with assignments of values to variables. \n\nAn assignment that does not violate any constraints is called a __consistent__ or legal assignment.\n\nSolution to a CSP is a consistent, complete assignment.\n\nCSP differ from search problems that:\nIn search problems, states are black boxes with a transition model to move between boxes. \nIn CSPs, the agent can see inside the states and move between states accordingly.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n__AC-3__: algorithm for enforcing arc consistency:\n- maintains a queue of arcs, initially, the queue contains all the arcs\n- pops off an arbitrary arc from the queue, (X1, X2), makes X1 arc-consistent with respect to X2\n- Domian D unchanged: next arc; D changes: add all arcs of neighbors of X1, (Xn, X1)\n- Assume a CSP with n variables, each with domain size at most d,  with c binary constraints (arcs). worst case time: __O(cd^3)__\n\nconstraint satisfaction is NP-complete in general, and any algorithm for establishing n-consistency must take \ntime exponential in n in the worst case. Worse, n-consistency also requires space that is exponential in n.\n\nCSPs can rule out variable assignments using __search__ or __inference__.\nInference techniques use constraints to rule out variable assignment.\nThe key idea behind inference in CSPs is enforcing k-consistency. \n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nminimum-remaining-values (MRV) heuristic: choosing the variable with the fewest “legal” values\nThe minimum-remaining-values and degree heuristics are domain-independent\nmethods for deciding which variable to choose next in a backtracking search. \n\nThe least-constraining-value heuristic helps in deciding which value to try first for a given\nvariable.\n\nBacktracking occurs when no legal assignment can be found for a variable.\n\nConflict-directed backjumping backtracks directly to the source of the problem.\n\nConstraint learning records the conflicts as they are encountered during search in order to avoid the same conflict later in the search.\n\n__forward checking__: Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each\nunassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for X.\n\n__MAC(Maintaining Arc Consistency)__: Both search and inference. After a variable Xi is assigned a value, the INFERENCE procedure calls AC-3, but instead\nof a queue of all arcs in the CSP, we start with only the arcs (Xj, Xi) for all Xj that are\n__unassigned variables__ that are neighbors of Xi. From there, AC-3 does constraint\npropagation in the usual way, and if any variable has its domain reduced to the empty set,\nthe call to AC-3 fails and we know to __backtrack__ immediately.\n\nDifference between MAC and AC-3:\nMAC is a way of interleaving search and inference. AC-3 is pure inference. \nMAC runs while assigning variables in backtracking search. \nInstead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3.\n\nDifference between MAC and forward checking:\nMAC recursively propagates constraints, whereas forward checking does not. \n\nBACKTRACKING-SEARCH: back up to the preceding variable and try a different value for it.\n\nBackjumping method backtracks to the most recent assignment in the conflict set.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nSolving an arbitrary CSP takes exponential time in the number of variables.\n\nSolving a tree-structured CSP takes linear time in the number of variables. (tree: when any two variables are connected by only one path)\n\n__Cutset conditioning__ is used to reduce a general CSP to a tree structured one.\n__Tree decomposition__ techniques transform the CSP into a tree of subproblems.\n\nCutset conditioning vs tree decomposition:\nCutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width w.\n\n\n\n## Module 6 Lecture Notes\n \nGeneral idea:\n- Represent the __constraints__ that solutions must satisfy in a __uniform declarative language__\n- Find solutions by __GENERAL PURPOSE__ search algorithms with no changes from problem to problem\n- No hand-built transition functions\n- No hand-built heuristics\n- Just specify the problem in a formal declarative language, and a general-purpose algorithm does everything else\n\nDepth-first search for CSPs with single-variable assignments is called __backtracking search__.\nBacktracking search is the basic uninformed algorithm for CSPs.\n\n\n\n## Module 6 Definitions\n* **Unary constraint** - restricts the value of one variable\n* **Binary constraint** - restriction involves two variables\n* **Binary csp** - with only unary and binary constraints\n* **Global constraint** - A constraint involving an arbitrary number of variables, don't nedd to be all variables\n* **Node consistency** - k-consistency for k=1\n* **Arc consistency** - k-consistency for k=2\n* **Path consistency** - k-consistency for k=3\n* **K-consistent** - for any set of k−1 variables, when they are consistently assigned, a consistent value can be assigned to kth variable\n* **Strongly k-consistent** - CSP is k-consistent, k-1 consistent, ..., 1-consistent\n* **Resource constraint** - atmost constraint, enforce by deleting the max value of any domain not consistent with the min of other domians\n* **Bounds-consistent** - both lowerbound and upperbound of X have some Y satisfies the constraint between X and Y\n* **Directional arc consistency(dac)** - ordered variables X1...Xn, every Xi is arc-consistent with every Xj, where j>i\n* **Cycle cutset** - subset S, removal of S makes constraint graph to a tree\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nA knowledge-based agent can be built simply by TELLing it what it needs to know.\n\n__Models__ are mathematical abstractions that have a fixed set of truth values which are {true, false} for each sentence.\n- If sentence 𝛂 is true in model m then we say:\n- m satisfies 𝛂, or m is a model of 𝛂\n- We use the notation M(𝛂) to mean the set of all models of 𝛂\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \n\n## AIMA Chapter 7.3 Logic\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nFor complex sentences, we have five rules, which hold for any subsentences P andQ  (atomic or complex) in any model m:\n- ¬P is true iff P is false in m.\n- P ∧ Q is true iff both P and Q are true in m.\n- P ∨ Q is true iff either P or Q is true in m.\n- P => Q is true unless P is true and Q is false in m.\n- P <=> Q is true iff P and Q are both true or both false in m.\n\n\nNote for implication =>:\n-\tpropositional logic does not require any relation of causation or relevance between P and Q.\n-\tAny implication is true whenever its antecedent is false. For example, “5 is even implies Sam is smart” is true, regardless of whether Sam is smart.\n\n\nIf KB and alpha contain n symbols in all, then there are 2^n models. \nThus, the time complexity of the algorithm is O(2^n). The space complexity is only O(n) because the enumeration is depth-first.\n\nEvery known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input.\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses.\n\nConjunctive Normal Form: A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF.\n\nprocedure for converting to CNF:\n1. Eliminate <=>, replacing α<=>β with (α ⇒ β) ∧ (β ⇒ α)\n2. Eliminate ⇒,  replacing α ⇒ β with (¬α ∨ β)\n3. CNF requires ¬ to appear only in literals, so we “move ¬ inwards”:\n¬(α ∧ β) ≡ (¬α ∨¬β)   (De Morgan),\n¬(α ∨ β) ≡ (¬α ∧ ¬β)   (De Morgan)\n4. Distribute ∨ over ∧ wherever possible.\n\n\n## Module 7 Lecture Notes\n \n__Forward Chaining__ is a kind of data-driven reasoning. An agent can start with known\ndata, adding premises as new percepts come in, and then incrementally apply the\nforward chaining algorithm to derive new conclusions. It doesn’t have to have a\nspecific query in mind to do so.\n\n__Backward chaining__ works backwards from a query. If the query is known to be true,\nthen no work is needed. Otherwise, the algorithm finds implications in the KB whose\nconclusions is the query. If all the premises of one of those can be proved to be true\n(via backward chaining), then the query is true.\n\n__Backward chaining__ is a form of goal-directed reasoning.\n\n\n## Module 7 Definitions\n* **Knowledge-based agents** - reason over an internal representation of knowledge and decide to take actcion\n* **Kb** - knowledge base, set of sentences in knowledge representation language\n* **Logic** - general class of representations for knowledge-based agents\n* **Axiom** - sentence is given, without inference, i.e. not derived sentence\n* **Syntax** - the structure of sentences\n* **Semantics** - meaning, defines the truth of sentences\n* **Entailment** - a sentence follows logically from another, a entails b iff in every model where a true, b s also true\n* **Sound / truth-preserving** - an inference algo that derives only entailed sentences\n* **Completeness** - an inference algo that can derive any sentence that is entailed\n* **Grounding** - connection between logical reasoning processes and the real environment\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}