{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "FINAL_Template_for_CIS521_midterm_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "04ad85a9-6b69-4719-d50b-68f01c76468d"
      },
      "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": 39,
      "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": "b0a14d4e-3ecb-42c1-f96e-a9cb0ed1795e"
      },
      "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": 40,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 41,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "The field of artificial intelligence is\n",
        "concerned with not just understanding but also building intelligent entities—machines that\n",
        "can compute how to act effectively and safely in a wide variety of novel situations.\\n\\n\n",
        "Turing test: proposed by Alan Turing (1950)\\n\n",
        "The computer would need the following capabilities:\\n\n",
        "natural language processing to communicate successfully in a human language;\\n\n",
        "knowledge representation to store what it knows or hears;\\n\n",
        "automated reasoning to answer questions and to draw new conclusions;\\n\n",
        "All the skills needed for the Turing test also allow an agent to act rationally. Knowledge\n",
        "representation and reasoning enable agents to reach good decisions.\\n\\n\n",
        "machine learning to adapt to new circumstances and to detect and extrapolate patterns.\\n\n",
        "These laws of thought were supposed to govern the operation of the mind; their study\n",
        "initiated the field called logic.\\n\\n\n",
        "The problem of achieving agreement between our true preferences and the objective we put\n",
        "into the machine is called the value alignment problem: the values or objectives put into\n",
        "the machine must be aligned with those of the human.\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"weak AI—the idea that\n",
        "machines could act as if they were intelligent\\n\n",
        "strong AI—the assertion that machines\n",
        "that do so are actually consciously thinking\\n\n",
        "“human-level AI” or “general AI”—programs that can solve an arbitrarily wide variety of tasks, including novel ones, and\n",
        "do so as well as a human\\n\\n\n",
        "The embodied cognition approach claims that it makes no sense to consider the brain\n",
        "separately: cognition takes place within a body, which is embedded in an environment\\\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"Chinese room argument\\\n",
        "The process of thinking is not important, the result matters.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" The concept to develop a small set of design principles for building successful agents—systems that can reasonably be called intelligent\\n\n",
        "An agent is anything that can be viewed as perceiving its environment through sensors and\n",
        "acting upon that environment through actuators\\n\\n\n",
        "Mathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept\n",
        "sequence to an action\\n\n",
        "Internally, the agent function for an artificial agent will be\n",
        "implemented by an agent program \"\"\"\n",
        "chapter2_2 = \"\"\" consequentialism: we evaluate an agent’s behavior by\n",
        "its consequences\\n\\n\n",
        "This notion of desirability is captured by a performance measure\n",
        "that evaluates any given sequence of environment states or each possible percept sequence, a rational agent should select an action that is expected to\n",
        "maximize its performance measure, given the evidence provided by the percept sequence and\n",
        "whatever built-in knowledge the agent has.\\n\\n\n",
        "For each possible percept sequence, a rational agent should select an action that is expected to\n",
        "maximize its performance measure, given the evidence provided by the percept sequence and\n",
        "whatever built-in knowledge the agent has.\\n\\n\n",
        "Doing actions in order to modify future percepts—\n",
        "sometimes called information gathering\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" task environments: the “problems” to which rational agents are the solutions.\\n\n",
        "If an agent’s sensors give it access\n",
        "to the complete state of the environment at each point in time, then we say that the task\n",
        "environment is fully observable. If the agent has no sensors at all\n",
        "then the environment is unobservable.\\n\\n\n",
        "If the next state of the environment is completely\n",
        "determined by the current state and the action executed by the agent(s), then we say the\n",
        "environment is deterministic; otherwise, it is nondeterministic.\\n\n",
        "stochastic: we say that a model of the environment\n",
        "is stochastic if it explicitly deals with probabilities\\n\\n\n",
        "Episodic: each step an input and output; Sequential: all inputs has influence upon future decision\\n\n",
        "In a known environment, the outcomes for all actions are given  \"\"\"\n",
        "chapter2_4 = \"\"\" The job of AI is to design an agent program that implements the agent function—the\n",
        "mapping from percepts to actions. We assume this program will run on some sort of\n",
        "computing device with physical sensors and actuators—we call this the agent architecture\\n\\n\n",
        "The simplest kind of agent is the simple reflex agent. These agents select actions on the\n",
        "basis of the current percept, ignoring the rest of the percept history\\n\\n\n",
        "Escape from infinite loops is possible if the agent can randomize its actions\\n\\n\n",
        "the transition model and sensor model allow an agent to keep track of the state of\n",
        "the world—to the extent possible given the limitations of the agent’s sensors. An agent that\n",
        "uses such models is called a model-based agent.\\n\\n\n",
        "Goal-based agents\\n\n",
        "Utility-based agent\\n\n",
        "Learning agents\\n\\n\n",
        "A factored representation splits up each state into a fixed set of variables or attributes,\n",
        "each of which can have a value\\n\n",
        "A structured representation\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"PEAS (Performance, Environment, Actuators, Sensors) \\n\n",
        "n cases where the performance measure is unknown or hard to specify correctly, there\n",
        "is a significant risk of the agent optimizing the wrong objective. In such cases the agent\n",
        "design should reflect uncertainty about the true objective\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"agent\" : \"anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\",\n",
        "\"rationality\" : \"doing the right thing, formal definition of intelligence\",\n",
        "\"rational agent\": \"acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\",\n",
        "\"standard model\": \"general paradigm of AI, the right thing is defined by the objective that we provide to the agent\",\n",
        "\"limited rationality\": \"acting appropriately when there is not enough time to do all the computations\",\n",
        "\"Homo sapiens\": \"man the wise\",\n",
        "\"percept sequence\": \"complete history of everything the agent has ever perceived\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 42,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "5a260fd5-9891-4d09-cd4d-f03b928804a0"
      },
      "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": 43,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nThe field of artificial intelligence is\nconcerned with not just understanding but also building intelligent entities—machines that\ncan compute how to act effectively and safely in a wide variety of novel situations.\n\n\nTuring test: proposed by Alan Turing (1950)\n\nThe computer would need the following capabilities:\n\nnatural language processing to communicate successfully in a human language;\n\nknowledge representation to store what it knows or hears;\n\nautomated reasoning to answer questions and to draw new conclusions;\n\nAll the skills needed for the Turing test also allow an agent to act rationally. Knowledge\nrepresentation and reasoning enable agents to reach good decisions.\n\n\nmachine learning to adapt to new circumstances and to detect and extrapolate patterns.\n\nThese laws of thought were supposed to govern the operation of the mind; their study\ninitiated the field called logic.\n\n\nThe problem of achieving agreement between our true preferences and the objective we put\ninto the machine is called the value alignment problem: the values or objectives put into\nthe machine must be aligned with those of the human.\n \n\n## AIMA Chapter 27.1 The Limits of AI\nweak AI—the idea that\nmachines could act as if they were intelligent\n\nstrong AI—the assertion that machines\nthat do so are actually consciously thinking\n\n“human-level AI” or “general AI”—programs that can solve an arbitrarily wide variety of tasks, including novel ones, and\ndo so as well as a human\n\n\nThe embodied cognition approach claims that it makes no sense to consider the brain\nseparately: cognition takes place within a body, which is embedded in an environment\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nChinese room argumentThe process of thinking is not important, the result matters.\n\n## AIMA 2.1 Agents and Environments\n The concept to develop a small set of design principles for building successful agents—systems that can reasonably be called intelligent\n\nAn agent is anything that can be viewed as perceiving its environment through sensors and\nacting upon that environment through actuators\n\n\nMathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept\nsequence to an action\n\nInternally, the agent function for an artificial agent will be\nimplemented by an agent program \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n consequentialism: we evaluate an agent’s behavior by\nits consequences\n\n\nThis notion of desirability is captured by a performance measure\nthat evaluates any given sequence of environment states or each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has.\n\n\nFor each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has.\n\n\nDoing actions in order to modify future percepts—\nsometimes called information gathering\n \n\n## AIMA 2.3 The Nature of Environments\n task environments: the “problems” to which rational agents are the solutions.\n\nIf an agent’s sensors give it access\nto the complete state of the environment at each point in time, then we say that the task\nenvironment is fully observable. If the agent has no sensors at all\nthen the environment is unobservable.\n\n\nIf the next state of the environment is completely\ndetermined by the current state and the action executed by the agent(s), then we say the\nenvironment is deterministic; otherwise, it is nondeterministic.\n\nstochastic: we say that a model of the environment\nis stochastic if it explicitly deals with probabilities\n\n\nEpisodic: each step an input and output; Sequential: all inputs has influence upon future decision\n\nIn a known environment, the outcomes for all actions are given  \n\n## AIMA 2.4 The Structure of Agents\n The job of AI is to design an agent program that implements the agent function—the\nmapping from percepts to actions. We assume this program will run on some sort of\ncomputing device with physical sensors and actuators—we call this the agent architecture\n\n\nThe simplest kind of agent is the simple reflex agent. These agents select actions on the\nbasis of the current percept, ignoring the rest of the percept history\n\n\nEscape from infinite loops is possible if the agent can randomize its actions\n\n\nthe transition model and sensor model allow an agent to keep track of the state of\nthe world—to the extent possible given the limitations of the agent’s sensors. An agent that\nuses such models is called a model-based agent.\n\n\nGoal-based agents\n\nUtility-based agent\n\nLearning agents\n\n\nA factored representation splits up each state into a fixed set of variables or attributes,\neach of which can have a value\n\nA structured representation\n\n \n\n## Module 1 Lecture Notes\nPEAS (Performance, Environment, Actuators, Sensors) \n\nn cases where the performance measure is unknown or hard to specify correctly, there\nis a significant risk of the agent optimizing the wrong objective. In such cases the agent\ndesign should reflect uncertainty about the true objective\n\n## Module 1 Definitions\n* **Agent** - anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\n* **Rationality** - doing the right thing, formal definition of intelligence\n* **Rational agent** - acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n* **Standard model** - general paradigm of AI, the right thing is defined by the objective that we provide to the agent\n* **Limited rationality** - acting appropriately when there is not enough time to do all the computations\n* **Homo sapiens** - man the wise\n* **Percept sequence** - complete history of everything the agent has ever perceived\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Objects of built-in types like (int, float, bool, str, tuple, unicode) are immutable and hashable\\n\\n\n",
        "Strong Typing: Every object has a fixed type, interpreter doesn’t allow things incompatible with\n",
        "that type\\n\n",
        "Dynamic typing: Variables come into existence when first assigned \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"can change or not. str, tuple is imutable (the item within is not influenced)\",\n",
        "\"mutable\" : \"its state can be changed after declared.\",\n",
        "\"hashable\" : \"immutable, like tuple, string\",\n",
        "\"dict+dict\": \"not supported\",\n",
        "\"set.remove\": \"key exist needed\",\n",
        "\"Tuple\":\" A simple immutable ordered sequence of items\",\n",
        "\"Strings\": \"Immutable\",\n",
        "\"List\": \"Mutable ordered sequence of items of mixed types\",\n",
        "\"Dictionaries\": \"are unordered & work by hashing, so keys must be immutable\"\n",
        "\n",
        "}"
      ],
      "execution_count": 44,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 388
        },
        "outputId": "033acc12-6f25-471a-bb1d-119be026cd66"
      },
      "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": 45,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Objects of built-in types like (int, float, bool, str, tuple, unicode) are immutable and hashable\n\n\nStrong Typing: Every object has a fixed type, interpreter doesn’t allow things incompatible with\nthat type\n\nDynamic typing: Variables come into existence when first assigned \n\n## Module 2 Definitions\n* **Mutability** - can change or not. str, tuple is imutable (the item within is not influenced)\n* **Mutable** - its state can be changed after declared.\n* **Hashable** - immutable, like tuple, string\n* **Dict+dict** - not supported\n* **Set.remove** - key exist needed\n* **Tuple** -  A simple immutable ordered sequence of items\n* **Strings** - Immutable\n* **List** - Mutable ordered sequence of items of mixed types\n* **Dictionaries** - are unordered & work by hashing, so keys must be immutable\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 = \"\"\" We distinguish between informed algorithms, in which the agent can estimate how\n",
        "far it is from the goal, and uninformed algorithms, where no such estimate is available\\n\n",
        "Goal formulation, Problem formulation, Search (for solution), Execution \\n\n",
        "A search problem: state space, initial state, goal states, action space, transition model, action cost function \\n\n",
        "A sequence of actions forms a path, and a solution is a path from the initial state to a goal state.\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" The state space can be infinite.\\n\n",
        "A standardized problem is intended to illustrate or exercise various problem\u0002solving methods. \\n\n",
        "A real-world problem is one whose solutions people actually use, and whose\n",
        "formulation is idiosyncratic, not standardized \"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\"\n",
        "The search algorithm superimposes a search tree over the state-space graph\\n\n",
        "The state space describes the set of states in the world \\n\n",
        "The actions allow transitions from one state to another. \\n\n",
        "The search tree describes paths between states, reaching towards the goal. \\n\\n\n",
        "A priority queue first pops the node with the minimum cost according to some\n",
        "evaluation function, It is used in best-first search.\\n\n",
        "A FIFO queue or first-in-first-out queue first pops the node that was added to the queue\n",
        "first; we shall see it is used in breadth-first search\\n\n",
        "A LIFO queue or last-in-first-out queue(stack) pops first the most recently added node; we shall see it is used in depth-first search\\n\\n\n",
        "Best-first search: priority queue frontier, each time choose the node with the best evaluation function\n",
        "If the action costs are uniform, we can use BFS and DFS \\n\n",
        "We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check.\n",
        "\"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\"\n",
        "An uninformed search algorithm is given no clue about how close a state is to the goal. \\n\\n\n",
        "BFS:\\n\n",
        "complete, cost-optimal for the problem where actions have identical cost. \\n\n",
        "Both time complexity: $O(b^d)$ space complexity: $O(b^d)$. \\n\n",
        "Dijkstra's algorithm: uniform-cost search (Best First Search) uniform-cost is refered to uniform-depth (BFS) \\n\\n\n",
        "Uniform-cost search:\\n\n",
        "complete if all action costs are $\\\\ge \\\\epsilon > 0$ \\n\n",
        "Both time and space complexity are $O(b^{1 + \\\\frac{C^*}{\\\\epsilon}})$, or $O(b^{d+1})$ when all costs are equal \\n\\n\n",
        "Depth-first search:\\n\n",
        "not cost-optimal\\n\n",
        "For finite state spaces that are trees DFS is efficient and complete. (For cyclic graph, DFS is not complete) \\n\\n\n",
        "Depth-limited search:\\n\n",
        "Time complexity: $O(b^l)$, space complexity: $O(bl)$ \\n\\n\n",
        "Backtracking search:\\n\n",
        "uses less memory. Only one successor is generated at a time and undo the action after we have DFS it. \\n\n",
        "Time complexity: $O(b^m)$, space complexity: $O(bm)$ \\n\\n\n",
        "Iterative Deepening search:\\n\n",
        "complete and cost-optimal. (Depth-limited is not, but iterative deepening is based on depth-limited) \\n\n",
        "Time complexity: $O(b^d)$, space complexity: $O(b^m)$ \\n\\n\n",
        "Bidirectional search:\\n\n",
        "complete and cost-optimal if both directions are breadth-first or uniform-cost.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"A problem-solving agent must plan\n",
        "ahead.\\n\n",
        "The computational process that it\n",
        "undertakes is called search.\\n\n",
        "It will consider a sequence of actions\n",
        "that form a path to a goal state.\\n\n",
        "Such a sequence is called a solution.\\n\n",
        "Path: a sequence of actions leading from one state $s_j$ to another state $s_k$ \\n\n",
        "Solution: a path from the initial state $s_i$ to a state sf that satisfies the goal test\\n\\n\n",
        "In a fully observable, deterministic, known environment, the solution to any problem is a fixed set of actions\\n\\n\n",
        "Tree search uses less space than graph search \"\"\"\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",
        "'Dijkstra’s algorithm': 'a Uniform-cost Search without a goal.', \n",
        "\"open-loop system\" : \"system without percepts\",\n",
        "\"close-loop system\" : \"system monitors the percepts\",\n",
        "\"completeness\" : \"whether the algorithm guaranteed to find a solution when there is one, and to correctly report failure\",\n",
        "\"COST OPTIMALITY\": \"Does it find a solution with the lowest path cost of all solutions\",\n",
        "\"optimality/admissibility\" : \"whether the algorithm can find the solution with lowest cost\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e4c6fe1a-f08b-4132-d43a-0b3d1d732d63"
      },
      "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": 47,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n We distinguish between informed algorithms, in which the agent can estimate how\nfar it is from the goal, and uninformed algorithms, where no such estimate is available\n\nGoal formulation, Problem formulation, Search (for solution), Execution \n\nA search problem: state space, initial state, goal states, action space, transition model, action cost function \n\nA sequence of actions forms a path, and a solution is a path from the initial state to a goal state.\n \n\n## AIMA Chapter 3.2 Example Problems\n The state space can be infinite.\n\nA standardized problem is intended to illustrate or exercise various problem\u0002solving methods. \n\nA real-world problem is one whose solutions people actually use, and whose\nformulation is idiosyncratic, not standardized \n\n## AIMA Chapter 3.3 Search Algorithms\n\nThe search algorithm superimposes a search tree over the state-space graph\n\nThe state space describes the set of states in the world \n\nThe actions allow transitions from one state to another. \n\nThe search tree describes paths between states, reaching towards the goal. \n\n\nA priority queue first pops the node with the minimum cost according to some\nevaluation function, It is used in best-first search.\n\nA FIFO queue or first-in-first-out queue first pops the node that was added to the queue\nfirst; we shall see it is used in breadth-first search\n\nA LIFO queue or last-in-first-out queue(stack) pops first the most recently added node; we shall see it is used in depth-first search\n\n\nBest-first search: priority queue frontier, each time choose the node with the best evaluation function\nIf the action costs are uniform, we can use BFS and DFS \n\nWe call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nAn uninformed search algorithm is given no clue about how close a state is to the goal. \n\n\nBFS:\n\ncomplete, cost-optimal for the problem where actions have identical cost. \n\nBoth time complexity: $O(b^d)$ space complexity: $O(b^d)$. \n\nDijkstra's algorithm: uniform-cost search (Best First Search) uniform-cost is refered to uniform-depth (BFS) \n\n\nUniform-cost search:\n\ncomplete if all action costs are $\\ge \\epsilon > 0$ \n\nBoth time and space complexity are $O(b^{1 + \\frac{C^*}{\\epsilon}})$, or $O(b^{d+1})$ when all costs are equal \n\n\nDepth-first search:\n\nnot cost-optimal\n\nFor finite state spaces that are trees DFS is efficient and complete. (For cyclic graph, DFS is not complete) \n\n\nDepth-limited search:\n\nTime complexity: $O(b^l)$, space complexity: $O(bl)$ \n\n\nBacktracking search:\n\nuses less memory. Only one successor is generated at a time and undo the action after we have DFS it. \n\nTime complexity: $O(b^m)$, space complexity: $O(bm)$ \n\n\nIterative Deepening search:\n\ncomplete and cost-optimal. (Depth-limited is not, but iterative deepening is based on depth-limited) \n\nTime complexity: $O(b^d)$, space complexity: $O(b^m)$ \n\n\nBidirectional search:\n\ncomplete and cost-optimal if both directions are breadth-first or uniform-cost.\n\n\n## Module 3 Lecture Notes\nA problem-solving agent must plan\nahead.\n\nThe computational process that it\nundertakes is called search.\n\nIt will consider a sequence of actions\nthat form a path to a goal state.\n\nSuch a sequence is called a solution.\n\nPath: a sequence of actions leading from one state $s_j$ to another state $s_k$ \n\nSolution: a path from the initial state $s_i$ to a state sf that satisfies the goal test\n\n\nIn a fully observable, deterministic, known environment, the solution to any problem is a fixed set of actions\n\n\nTree search uses less space than graph search \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Dijkstra’s algorithm** - a Uniform-cost Search without a goal.\n* **Open-loop system** - system without percepts\n* **Close-loop system** - system monitors the percepts\n* **Completeness** - whether the algorithm guaranteed to find a solution when there is one, and to correctly report failure\n* **Cost optimality** - Does it find a solution with the lowest path cost of all solutions\n* **Optimality/admissibility** - whether the algorithm can find the solution with lowest cost\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "heuristic function: \\n\n",
        "h(n) =  estimated cost of the cheapest path from the state at node n to a goal state\\n\\n\n",
        "Greedy best-first search:\\n\n",
        "a form of best-first search that expands first the node with the\n",
        "lowest $h(n)$ value\\n\n",
        "Time complexity and space complexity, worst case $O(b^m)$\\n\n",
        "Time complexity and space complexity, optimal case $O(bm)$\\n\\n\n",
        "A* search:\\n\n",
        "complete and cost-optimal if the heuristic is admissible. \\n\n",
        "Time complexity and space complexity, worst case $O(|E|) = O(b^d),O(|V|) = O(b^d)$\\n\n",
        "Admissible heuristic: $h(n) \\le h^*(n) $ \\n (where $h^*(n)$ is the real cost to the goal state) \\n\\n\n",
        "Stronger property for graph search is consistency. (triangle inequality) \\n\n",
        "With a consistent heuristic, the first time A* reaches a state it will be on an optimal path. (optimally efficient) \\n\n",
        "The $g$ should be monotonic because the action cost is positive. \\n\n",
        "A* expands all nodes $f(n) < C^*$, might expands some nodes $f(n) = C^*$, never expands nodes $f(n) > C^*$. \\n\n",
        "Weighted A* (enforce the algorithm to be greedy) \\n\\n\n",
        "We can explore fewer\n",
        "nodes (taking less time and space) if we are willing to accept solutions that are suboptimal,\n",
        "but are “good enough”—what we call satisficing solutions. If we allow A* search to use an\n",
        "inadmissible heuristic\\n\\n\n",
        "Beam search limits the size of the frontier.\\n\\n\n",
        "terative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth\u0002first\\n\\n\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "One way to characterize the quality of a heuristic is the effective branching factor \\n\n",
        "number of nodes: N, solution depth: d,  effective branching factor: $b^*$\\n\n",
        "$N+1 = 1+(b^*)^2 + ...+(b^*)^d$\\n\\n\n",
        "A problem with fewer restrictions on the actions is\n",
        "called a relaxed problem. The state-space graph of the relaxed problem is a supergraph of\n",
        "the original state space because the removal of restrictions creates added edges in the graph.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"Before an agent can start searching, a well-defined problem must be formulated.\\n\\n\n",
        "A problem consists of five parts: the initial state, a set of actions, a transition model\n",
        "describing the results of those actions, a set of goal states, and an action cost function.\\n\\n\n",
        "The environment of the problem is represented by a state space graph. A path through\n",
        "the state space (a sequence of actions) from the initial state to a goal state is a solution.\\n\\n\n",
        "Search algorithms are judged on the basis of completeness, cost optimality, time\n",
        "complexity, and space complexity.\\n\\n\n",
        "Uninformed search methods have access only to the problem definition. Algorithms\n",
        "build a search tree in an attempt to find a solution. Algorithms differ based on which\n",
        "node they expand first:\\n\n",
        "– BEST-FIRST SEARCH selects nodes for expansion using to an evaluation function.\\n\n",
        "– BREADTH-FIRST SEARCH expands the shallowest nodes first; it is complete,\\n\n",
        "optimal for unit action costs, but has exponential space complexity.\n",
        "– UNIFORM-COST SEARCH expands the node with lowest path cost, and is\n",
        "optimal for general action costs.\\n\n",
        "– DEPTH-FIRST SEARCH expands the deepest unexpanded node first. It is neither\n",
        "complete nor optimal, but has linear space complexity. Depth-limited search adds a\n",
        "depth bound.\\n\n",
        "– ITERATIVE DEEPENING SEARCH calls depth-first search with increasing depth\n",
        "limits until a goal is found. It is complete when full cycle checking is done, optimal for\n",
        "unit action costs, has time complexity comparable to breadth-first search, and has linear\n",
        "space complexity.\n",
        "g(n),\\n\n",
        "– BIDIRECTIONAL SEARCH expands two frontiers, one around the initial state and\n",
        "one around the goal, stopping when the two frontiers meet.\n",
        "Informed search methods have access to a heuristic function that estimates the\n",
        "cost of a solution from They may have access to additional information such as\n",
        "pattern databases with solution costs.\\n\n",
        "– GREEDY BEST-FIRST SEARCH expands nodes with minimal It is not optimal\n",
        "but is often efficient.\\n\n",
        "– A* SEARCH expands nodes with minimal A* is complete and\n",
        "optimal, provided that is admissible. The space complexity of A* is still an issue for\n",
        "many problems.\\n\n",
        "– BIDIRECTIONAL A* SEARCH is sometimes more efficient than A* itself.\\n\n",
        "– IDA* (iterative deepening A* search) is an iterative deepening version of A*, and\n",
        "thus adresses the space complexity issue.\\n\n",
        "– RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are\n",
        "robust, optimal search algorithms that use limited amounts of memory; given enough\n",
        "time, they can solve problems for which A* runs out of memory.\\n\n",
        "– BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and\n",
        "suboptimal, but it often finds reasonably good solutions and runs faster than complete\n",
        "searches.\\n\n",
        "– WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but\n",
        "sacrificing optimality.\\n\\n\n",
        "The performance of heuristic search algorithms depends on the quality of the heuristic\n",
        "function. One can sometimes construct good heuristics by relaxing the problem\n",
        "definition, by storing precomputed solution costs for subproblems in a pattern database,\n",
        "by defining landmarks, or by learning from experience with the problem class. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"branching factor\" : \"the number of successors generated by a given node.\",  \n",
        "\"dominate\": \"A heuristic function h dominates h' if both are admissible and for every node n, h(n) is greater than h'(n).\",\n",
        "\"admissibility\" : \"an admissible heuristic is one that never overestimates the cost to reach a goal: $h(n) \\le h^*(n)$\", \n",
        "\"consistency\" :  \"$h(n) \\le c(n, a, n') + h(n')$\",\n",
        "\"surely expanded nodes\" : \"$f(n) < C^*\" ,\n",
        "\"IDA*\": \"iterative deeping A*\",\n",
        "\"RBFS\": \"recursive best-first search\",\n",
        "\"SMA*\": \"simplified memory-bounded A*\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 48,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "d53754db-4c59-4f6e-c2c2-810eee8d530d"
      },
      "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": 49,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nheuristic function: \n\nh(n) =  estimated cost of the cheapest path from the state at node n to a goal state\n\n\nGreedy best-first search:\n\na form of best-first search that expands first the node with the\nlowest $h(n)$ value\n\nTime complexity and space complexity, worst case $O(b^m)$\n\nTime complexity and space complexity, optimal case $O(bm)$\n\n\nA* search:\n\ncomplete and cost-optimal if the heuristic is admissible. \n\nTime complexity and space complexity, worst case $O(|E|) = O(b^d),O(|V|) = O(b^d)$\n\nAdmissible heuristic: $h(n) \\le h^*(n) $ \n (where $h^*(n)$ is the real cost to the goal state) \n\n\nStronger property for graph search is consistency. (triangle inequality) \n\nWith a consistent heuristic, the first time A* reaches a state it will be on an optimal path. (optimally efficient) \n\nThe $g$ should be monotonic because the action cost is positive. \n\nA* expands all nodes $f(n) < C^*$, might expands some nodes $f(n) = C^*$, never expands nodes $f(n) > C^*$. \n\nWeighted A* (enforce the algorithm to be greedy) \n\n\nWe can explore fewer\nnodes (taking less time and space) if we are willing to accept solutions that are suboptimal,\nbut are “good enough”—what we call satisficing solutions. If we allow A* search to use an\ninadmissible heuristic\n\n\nBeam search limits the size of the frontier.\n\n\nterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth\u0002first\n\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \nOne way to characterize the quality of a heuristic is the effective branching factor \n\nnumber of nodes: N, solution depth: d,  effective branching factor: $b^*$\n\n$N+1 = 1+(b^*)^2 + ...+(b^*)^d$\n\n\nA problem with fewer restrictions on the actions is\ncalled a relaxed problem. The state-space graph of the relaxed problem is a supergraph of\nthe original state space because the removal of restrictions creates added edges in the graph.\n\n\n## Module 4 Lecture Notes\nBefore an agent can start searching, a well-defined problem must be formulated.\n\n\nA problem consists of five parts: the initial state, a set of actions, a transition model\ndescribing the results of those actions, a set of goal states, and an action cost function.\n\n\nThe environment of the problem is represented by a state space graph. A path through\nthe state space (a sequence of actions) from the initial state to a goal state is a solution.\n\n\nSearch algorithms are judged on the basis of completeness, cost optimality, time\ncomplexity, and space complexity.\n\n\nUninformed search methods have access only to the problem definition. Algorithms\nbuild a search tree in an attempt to find a solution. Algorithms differ based on which\nnode they expand first:\n\n– BEST-FIRST SEARCH selects nodes for expansion using to an evaluation function.\n\n– BREADTH-FIRST SEARCH expands the shallowest nodes first; it is complete,\n\noptimal for unit action costs, but has exponential space complexity.\n– UNIFORM-COST SEARCH expands the node with lowest path cost, and is\noptimal for general action costs.\n\n– DEPTH-FIRST SEARCH expands the deepest unexpanded node first. It is neither\ncomplete nor optimal, but has linear space complexity. Depth-limited search adds a\ndepth bound.\n\n– ITERATIVE DEEPENING SEARCH calls depth-first search with increasing depth\nlimits until a goal is found. It is complete when full cycle checking is done, optimal for\nunit action costs, has time complexity comparable to breadth-first search, and has linear\nspace complexity.\ng(n),\n\n– BIDIRECTIONAL SEARCH expands two frontiers, one around the initial state and\none around the goal, stopping when the two frontiers meet.\nInformed search methods have access to a heuristic function that estimates the\ncost of a solution from They may have access to additional information such as\npattern databases with solution costs.\n\n– GREEDY BEST-FIRST SEARCH expands nodes with minimal It is not optimal\nbut is often efficient.\n\n– A* SEARCH expands nodes with minimal A* is complete and\noptimal, provided that is admissible. The space complexity of A* is still an issue for\nmany problems.\n\n– BIDIRECTIONAL A* SEARCH is sometimes more efficient than A* itself.\n\n– IDA* (iterative deepening A* search) is an iterative deepening version of A*, and\nthus adresses the space complexity issue.\n\n– RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are\nrobust, optimal search algorithms that use limited amounts of memory; given enough\ntime, they can solve problems for which A* runs out of memory.\n\n– BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and\nsuboptimal, but it often finds reasonably good solutions and runs faster than complete\nsearches.\n\n– WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but\nsacrificing optimality.\n\n\nThe performance of heuristic search algorithms depends on the quality of the heuristic\nfunction. One can sometimes construct good heuristics by relaxing the problem\ndefinition, by storing precomputed solution costs for subproblems in a pattern database,\nby defining landmarks, or by learning from experience with the problem class. \n\n## Module 4 Definitions\n* **Branching factor** - the number of successors generated by a given node.\n* **Dominate** - A heuristic function h dominates h' if both are admissible and for every node n, h(n) is greater than h'(n).\n* **Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal: $h(n) \\le h^*(n)$\n* **Consistency** - $h(n) \\le c(n, a, n') + h(n')$\n* **Surely expanded nodes** - $f(n) < C^*\n* **Ida*** - iterative deeping A*\n* **Rbfs** - recursive best-first search\n* **Sma*** - simplified memory-bounded A*\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "The games most commonly studied within AI (such as chess and Go) are what game\n",
        "theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.\n",
        "“Perfect information” is a synonym for “fully observable,” and “zero-sum” means that what\n",
        "is good for one player is just as bad for the other: there is no “win-win” outcome. For games\n",
        "we often use the term move as a synonym for “action” and position as a synonym for\n",
        "“state.”\\n\n",
        "utility funtion: defines the final numeric value to player when the game ends in terminal state\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Alpha: MAX's current lower bound on MAX's outcome \\n\n",
        "Beta: MIN's current upper bound on MIN's outcome \\n\n",
        "When evaluating a MAX node: a value $v \\\\ge \\\\beta$ (MIN will never select that MAX node) \\n\n",
        "When evaluating a MIN node: a value $v \\\\le \\\\alpha$ (Max will never select that MIN node) \\n\n",
        "```\n",
        "def AlphaBeta(node, depth, alpha, beta, MAX):\n",
        "    if depth == 0 or node.isTerminal():\n",
        "        return node\n",
        "    if MAX:\n",
        "        value = -inf\n",
        "        for s in node.successors:\n",
        "            value = max(value, AlphaBeta(s, depth-1, alpha, beta, False))\n",
        "            if value >= beta:\n",
        "                break ### prune the branch\n",
        "            alpha = max(alpha, value)\n",
        "        return value\n",
        "    else:\n",
        "        value = inf\n",
        "        for s in node.successors:\n",
        "            value = min(value, AlphaBeta(s, depth-1, alpha, beta, True))\n",
        "            if value <= alpha:\n",
        "                break ### prune the branch\n",
        "            beta = min(beta, value)\n",
        "        return value\n",
        "\n",
        "initial call\n",
        "AlphaBeta(origin, depth, -inf, inf, True)\n",
        "```\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"Alpha–beta pruning prunes branches of the tree that can have no effect on the final\n",
        "evaluation, but forward pruning prunes moves that appear to be poor moves, but might\n",
        "possibly be good ones\\n\n",
        "One approach to forward pruning is beam search\\n\n",
        "on each ply, consider only\n",
        "a “beam” of the best moves (according to the evaluation function) rather than considering n\n",
        "all possible moves. Unfortunately, this approach is rather dangerous because there is no\n",
        "guarantee that the best move will not be pruned away.\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "Expectimax search:\\n\n",
        "use expectation as the evalution funtion\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" $P(s'|a) = \\\\sum_{s} P(s)P(s'|s,a)$ \\n\n",
        "Expected utility of action $a$: $ EU(a) = \\\\sum_{s'}P(s'|a)U(s') $ \\n\n",
        "action = $\\\\argmax_a EU(a)$ \\n\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or\n",
        "else rate them as equally preferable\\n\n",
        "TRANSITIVITY: Given any three lotteries, if an agent prefers to and prefers to ,\n",
        "then the agent must prefer to .\\n\n",
        "CONTINUITY: If some lottery is between and in preference, then there is some\n",
        "probability for which the rational agent will be indifferent between getting for sure\n",
        "and the lottery that yields with probability and with probability .\\n\n",
        "SUBSTITUTABILITY: If an agent is indifferent between two lotteries and , then the\n",
        "agent is indifferent between two more complex lotteries that are the same except that \n",
        "is substituted for in one of them. This holds regardless of the probabilities and the\n",
        "other outcome(s) in the lotteries\\n\n",
        "MONOTONICITY: Suppose two lotteries have the same two possible outcomes, and \n",
        ". If an agent prefers to , then the agent must prefer the lottery that has a higher\n",
        "probability for (and vice versa)\\n\n",
        "DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the\n",
        "laws of probability.\n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "Human judgment is usually irrational.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Heuristic alpha-beta search replaces the utility function with an evaluation function estimates the value of non-terminal nodes, the terminal test is replaced with a cutoff test decides when to cut off the search\\\\\n",
        "The horizon effect is when an agent try to erroneously delay the inevitable\\n\n",
        "Beam-search: most used forward pruning\\n\n",
        "forward pruning is a type B strategy\\n\n",
        "An evalution function returns an estimate of the expected utility of some state s, for player p. For terminal states, the evaluation function is exactly equal to the utility.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"fully observable\",\n",
        "\"utility function U(s)\": \"gives the payoff for each player in terminal state\",\n",
        "\"minimax search\":\"solves perfect information, zero-sum games, same order as depth-first search, time complexity O(b^m)\",\n",
        "\"Alpha-beta pruning\": \"time complexity O(b^m/2)\",\n",
        "\"Type A Strategy\": \"explores a wide but shallow portion of the tree\",\n",
        "\"Type B Strategy\": \"explores a deep but narrow portion of the tree\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 50,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4512321d-9a53-47c5-dfe8-bdbf828e1f66"
      },
      "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": 51,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nThe games most commonly studied within AI (such as chess and Go) are what game\ntheorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.\n“Perfect information” is a synonym for “fully observable,” and “zero-sum” means that what\nis good for one player is just as bad for the other: there is no “win-win” outcome. For games\nwe often use the term move as a synonym for “action” and position as a synonym for\n“state.”\n\nutility funtion: defines the final numeric value to player when the game ends in terminal state\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nAlpha: MAX's current lower bound on MAX's outcome \n\nBeta: MIN's current upper bound on MIN's outcome \n\nWhen evaluating a MAX node: a value $v \\ge \\beta$ (MIN will never select that MAX node) \n\nWhen evaluating a MIN node: a value $v \\le \\alpha$ (Max will never select that MIN node) \n\n```\ndef AlphaBeta(node, depth, alpha, beta, MAX):\n    if depth == 0 or node.isTerminal():\n        return node\n    if MAX:\n        value = -inf\n        for s in node.successors:\n            value = max(value, AlphaBeta(s, depth-1, alpha, beta, False))\n            if value >= beta:\n                break ### prune the branch\n            alpha = max(alpha, value)\n        return value\n    else:\n        value = inf\n        for s in node.successors:\n            value = min(value, AlphaBeta(s, depth-1, alpha, beta, True))\n            if value <= alpha:\n                break ### prune the branch\n            beta = min(beta, value)\n        return value\n\ninitial call\nAlphaBeta(origin, depth, -inf, inf, True)\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nAlpha–beta pruning prunes branches of the tree that can have no effect on the final\nevaluation, but forward pruning prunes moves that appear to be poor moves, but might\npossibly be good ones\n\nOne approach to forward pruning is beam search\n\non each ply, consider only\na “beam” of the best moves (according to the evaluation function) rather than considering n\nall possible moves. Unfortunately, this approach is rather dangerous because there is no\nguarantee that the best move will not be pruned away.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \nExpectimax search:\n\nuse expectation as the evalution funtion\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n $P(s'|a) = \\sum_{s} P(s)P(s'|s,a)$ \n\nExpected utility of action $a$: $ EU(a) = \\sum_{s'}P(s'|a)U(s') $ \n\naction = $\\argmax_a EU(a)$ \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nORDERABILITY: Given any two lotteries, a rational agent must either prefer one or\nelse rate them as equally preferable\n\nTRANSITIVITY: Given any three lotteries, if an agent prefers to and prefers to ,\nthen the agent must prefer to .\n\nCONTINUITY: If some lottery is between and in preference, then there is some\nprobability for which the rational agent will be indifferent between getting for sure\nand the lottery that yields with probability and with probability .\n\nSUBSTITUTABILITY: If an agent is indifferent between two lotteries and , then the\nagent is indifferent between two more complex lotteries that are the same except that \nis substituted for in one of them. This holds regardless of the probabilities and the\nother outcome(s) in the lotteries\n\nMONOTONICITY: Suppose two lotteries have the same two possible outcomes, and \n. If an agent prefers to , then the agent must prefer the lottery that has a higher\nprobability for (and vice versa)\n\nDECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the\nlaws of probability.\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nHuman judgment is usually irrational.\n\n\n## Module 5 Lecture Notes\n\nHeuristic alpha-beta search replaces the utility function with an evaluation function estimates the value of non-terminal nodes, the terminal test is replaced with a cutoff test decides when to cut off the search\\\nThe horizon effect is when an agent try to erroneously delay the inevitable\n\nBeam-search: most used forward pruning\n\nforward pruning is a type B strategy\n\nAn evalution function returns an estimate of the expected utility of some state s, for player p. For terminal states, the evaluation function is exactly equal to the utility.\n\n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Utility function u(s)** - gives the payoff for each player in terminal state\n* **Minimax search** - solves perfect information, zero-sum games, same order as depth-first search, time complexity O(b^m)\n* **Alpha-beta pruning** - time complexity O(b^m/2)\n* **Type a strategy** - explores a wide but shallow portion of the tree\n* **Type b strategy** - explores a deep but narrow portion of the tree\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",
        "CSP consists of $X$, $D$ and $C$. $X$ is set of variables, $D$ is set of domains for variables, $C$ is set of constraints. \\n\n",
        "A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a\n",
        "consistent, complete assignment. A partial assignment is one that leaves some variables\n",
        "unassigned, and a partial solution is a partial assignment that is consistent. Solving a CSP is\n",
        "an NP-complete problem \\n\n",
        "The best-known category of continuous-domain CSPs is that of linear programming problems, which is also called COP (constrained optimization problem)\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"constraint propagation: using the constraints to reduce the number of legal values for a\n",
        "variable, which in turn can reduce the legal values for another variable, and so on\\n\n",
        "key idea: enforcing local consistency\\n\\n\n",
        "A single variable (corresponding to a node in the CSP graph) is node-consistent if all the\n",
        "values in the variable’s domain satisfy the variable’s unary constraints\\n\n",
        "A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s\n",
        "binary constraints\\n\n",
        "Path consistency tightens the binary constraints by using implicit constraints\n",
        "that are inferred by looking at triples of variables\\n\n",
        "Stronger forms of propagation can be defined with the notion of -consistency. A CSP is -\n",
        "consistent if, for any set of variables and for any consistent assignment to those\n",
        "variables, a consistent value can always be assigned to any th variable\\n\\n\n",
        "\n",
        "AC3: solving arc arc-consistency\\n\\n\n",
        "```\n",
        "def AC3(X, D, ARC):\n",
        "    worklist = {(x,y) | arc(x,y) exists}\n",
        "    while worklist:\n",
        "        cur = worklist.pop()\n",
        "        if arc_reduce(x,y):\n",
        "            for arc in ARC:\n",
        "                if (arc[1] == cur[0]) and (arc[0] != cur[1]): ### (z , x) | z != y\n",
        "                    worklist.append(arc)\n",
        "\n",
        "def arc_reduce(x,y):\n",
        "    if len(D(y)) == 1:\n",
        "        c = D(y)[0]\n",
        "        if c in D(x):\n",
        "            D(x).remove(c)\n",
        "            return True\n",
        "    return False\n",
        "```\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Backtrack searching repeatedly chooses an\n",
        "unassigned variable, and then tries all values in the domain of that variable in turn, trying to\n",
        "extend each one into a solution via a recursive call. If the call succeeds, the solution is\n",
        "returned, and if it fails, the assignment is restored to the previous state, and we try the next\n",
        "value. If no value works then we return failure\\n\\n\n",
        "MAC (Maintaining Arc Consistency) recursively propogrates constraints, whereas forward checking does not. \n",
        "If we assign X, forward checking makes all the arcs incident on X consistent. \n",
        "MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...).\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",
        "chapter6_4 = \"\"\"\n",
        "min-conflicts heuristic:\\n\n",
        "Randomly choose the min-conflicted variable and modift its value to satisfy the constraints. \\n\\n\n",
        "Another technique called constraint weighting aims to concentrate the search on the\n",
        "important constraints. Each constraint is given a numeric weight, initially all 1. At each step\n",
        "of the search, the algorithm chooses a variable/value pair to change that will result in the\n",
        "lowest total weight of all violated constraints.\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "independent subproblems:\\n\n",
        "Independence can be ascertained simply by finding connected components of the\n",
        "constraint graph\\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "Constraint satisfaction problems (CSPs) represent a state with a set of variable/value\n",
        "pairs and represent the conditions for a solution by a set of constraints on the variables.\\n\\n\n",
        "CSPs can rule out variable assignments using seach or inference\\n\\n\n",
        "Backtracking search, a form of depth-first search, is commonly used for solving CSPs.\n",
        "Inference can be interwoven with search.\\n\\n\n",
        "The minimum-remaining-values and degree heuristics are domain-independent\n",
        "methods for deciding which variable to choose next in a backtracking search. The least\u0002constraining-value heuristic helps in deciding which value to try first for a given\n",
        "variable. Backtracking occurs when no legal assignment can be found for a variable.\n",
        "Conflict-directed backjumping backtracks directly to the source of the problem.\n",
        "Constraint learning records the conflicts as they are encountered during search in order\n",
        "to avoid the same conflict later in the search.\\n\\n\n",
        "Local search using the min-conflicts heuristic has also been applied to constraint\n",
        "satisfaction problems with great success.\\n\\n\n",
        "The complexity of solving a CSP is strongly related to the structure of its constraint\n",
        "graph. Tree-structured problems can be solved in linear time. Cutset conditioning can\n",
        "reduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\n",
        "memory) if a small cutset can be found. Tree decomposition techniques transform the\n",
        "CSP into a tree of subproblems and are efficient if the tree width of the constraint graph\n",
        "is small; however they need memory exponential in the tree width of the constraint\n",
        "graph. Combining cutset conditioning with tree decomposition can allow a better\n",
        "tradeoff of memory versus time\\n\\n\n",
        "Heuristic 1: Most constrained variable \\n\n",
        "Heuristic 2: Most constraining variable \\n\n",
        "Heuristic 3: Least constraining value \\n\n",
        "Heuristic 4: Forward checking (Arc consistency & AC-3) \\n\n",
        "AC-3's worst case complexity: $O(n^2d^3)$ (the number of arcs is $O(n^2)$ and checking an arc costs $O(d^2)$ (an arc may need to be checked d times)) \\\\\n",
        "For planar constraint graphs, the number of arcs is $O(n)$, time complexity: $O(nd^3)$\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {   \n",
        "\"MAC\": \"Maintaining Arc Consistency, MAC recursively propogrates constraints, whereas forward checking does not\",\n",
        "\"MAC vs AC3\": \"MAC is a way of interleaving search and inference. AC-3 is pure inference\",\n",
        "\"CSPs\": \"CSPs represent the conditions for a solution with a set of constraints on the variables\",\n",
        "\"CSPs note-2\": \"In search problems, states are black boxes. In CSPs, the agent can see inside the states and move\",\n",
        "\"MRV heuristic\": \"Minimum Remaining Value, chooses the variable with the fewest 'legal' values\",\n",
        "\"degree heuristic\": \"chooses the variable with the largest number of constraints\",\n",
        "\"least constraining value heuristic\": \"chooses the value that rules out the fewest values for neighboring variables\",\n",
        "\"Constraint learning\": \"records the conflicts as they are encountered in the search in order to avoid the same conflict later\",\n",
        "\"Cutset conditioning\": \"reduce a general CSP (exponential) to a tree structured one(linear), space efficient\",\n",
        "\"Tree decomposition techniques\": \"transform the CSP into a tree of subproblems\",\n",
        "\"Tree decomposition techniques efficiency\": \"efficient if the tree width of the constraint graph is small, time efficient\",\n",
        "}\n"
      ],
      "execution_count": 52,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "85ec1dbe-a402-4366-ee77-aa7a0e1ff7f2"
      },
      "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": 53,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP consists of $X$, $D$ and $C$. $X$ is set of variables, $D$ is set of domains for variables, $C$ is set of constraints. \n\nA complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a\nconsistent, complete assignment. A partial assignment is one that leaves some variables\nunassigned, and a partial solution is a partial assignment that is consistent. Solving a CSP is\nan NP-complete problem \n\nThe best-known category of continuous-domain CSPs is that of linear programming problems, which is also called COP (constrained optimization problem)\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nconstraint propagation: using the constraints to reduce the number of legal values for a\nvariable, which in turn can reduce the legal values for another variable, and so on\n\nkey idea: enforcing local consistency\n\n\nA single variable (corresponding to a node in the CSP graph) is node-consistent if all the\nvalues in the variable’s domain satisfy the variable’s unary constraints\n\nA variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s\nbinary constraints\n\nPath consistency tightens the binary constraints by using implicit constraints\nthat are inferred by looking at triples of variables\n\nStronger forms of propagation can be defined with the notion of -consistency. A CSP is -\nconsistent if, for any set of variables and for any consistent assignment to those\nvariables, a consistent value can always be assigned to any th variable\n\n\n\nAC3: solving arc arc-consistency\n\n\n```\ndef AC3(X, D, ARC):\n    worklist = {(x,y) | arc(x,y) exists}\n    while worklist:\n        cur = worklist.pop()\n        if arc_reduce(x,y):\n            for arc in ARC:\n                if (arc[1] == cur[0]) and (arc[0] != cur[1]): ### (z , x) | z != y\n                    worklist.append(arc)\n\ndef arc_reduce(x,y):\n    if len(D(y)) == 1:\n        c = D(y)[0]\n        if c in D(x):\n            D(x).remove(c)\n            return True\n    return False\n```\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nBacktrack searching repeatedly chooses an\nunassigned variable, and then tries all values in the domain of that variable in turn, trying to\nextend each one into a solution via a recursive call. If the call succeeds, the solution is\nreturned, and if it fails, the assignment is restored to the previous state, and we try the next\nvalue. If no value works then we return failure\n\n\nMAC (Maintaining Arc Consistency) recursively propogrates constraints, whereas forward checking does not. \nIf we assign X, forward checking makes all the arcs incident on X consistent. \nMAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...).\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\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nmin-conflicts heuristic:\n\nRandomly choose the min-conflicted variable and modift its value to satisfy the constraints. \n\n\nAnother technique called constraint weighting aims to concentrate the search on the\nimportant constraints. Each constraint is given a numeric weight, initially all 1. At each step\nof the search, the algorithm chooses a variable/value pair to change that will result in the\nlowest total weight of all violated constraints.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nindependent subproblems:\n\nIndependence can be ascertained simply by finding connected components of the\nconstraint graph\n\n\n \n\n## Module 6 Lecture Notes\n \nConstraint satisfaction problems (CSPs) represent a state with a set of variable/value\npairs and represent the conditions for a solution by a set of constraints on the variables.\n\n\nCSPs can rule out variable assignments using seach or inference\n\n\nBacktracking search, a form of depth-first search, is commonly used for solving CSPs.\nInference can be interwoven with search.\n\n\nThe minimum-remaining-values and degree heuristics are domain-independent\nmethods for deciding which variable to choose next in a backtracking search. The least\u0002constraining-value heuristic helps in deciding which value to try first for a given\nvariable. Backtracking occurs when no legal assignment can be found for a variable.\nConflict-directed backjumping backtracks directly to the source of the problem.\nConstraint learning records the conflicts as they are encountered during search in order\nto avoid the same conflict later in the search.\n\n\nLocal search using the min-conflicts heuristic has also been applied to constraint\nsatisfaction problems with great success.\n\n\nThe complexity of solving a CSP is strongly related to the structure of its constraint\ngraph. Tree-structured problems can be solved in linear time. Cutset conditioning can\nreduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\nmemory) if a small cutset can be found. Tree decomposition techniques transform the\nCSP into a tree of subproblems and are efficient if the tree width of the constraint graph\nis small; however they need memory exponential in the tree width of the constraint\ngraph. Combining cutset conditioning with tree decomposition can allow a better\ntradeoff of memory versus time\n\n\nHeuristic 1: Most constrained variable \n\nHeuristic 2: Most constraining variable \n\nHeuristic 3: Least constraining value \n\nHeuristic 4: Forward checking (Arc consistency & AC-3) \n\nAC-3's worst case complexity: $O(n^2d^3)$ (the number of arcs is $O(n^2)$ and checking an arc costs $O(d^2)$ (an arc may need to be checked d times)) \\\nFor planar constraint graphs, the number of arcs is $O(n)$, time complexity: $O(nd^3)$\n \n\n## Module 6 Definitions\n* **Mac** - Maintaining Arc Consistency, MAC recursively propogrates constraints, whereas forward checking does not\n* **Mac vs ac3** - MAC is a way of interleaving search and inference. AC-3 is pure inference\n* **Csps** - CSPs represent the conditions for a solution with a set of constraints on the variables\n* **Csps note-2** - In search problems, states are black boxes. In CSPs, the agent can see inside the states and move\n* **Mrv heuristic** - Minimum Remaining Value, chooses the variable with the fewest 'legal' values\n* **Degree heuristic** - chooses the variable with the largest number of constraints\n* **Least constraining value heuristic** - chooses the value that rules out the fewest values for neighboring variables\n* **Constraint learning** - records the conflicts as they are encountered in the search in order to avoid the same conflict later\n* **Cutset conditioning** - reduce a general CSP (exponential) to a tree structured one(linear), space efficient\n* **Tree decomposition techniques** - transform the CSP into a tree of subproblems\n* **Tree decomposition techniques efficiency** - efficient if the tree width of the constraint graph is small, time efficient\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 base is a set of sentences \\n\n",
        "Each sentence is expressed in a language called a knowledge representation language and\n",
        "represents some assertion about the world. When the sentence is taken as being given\n",
        "without being derived from other sentences, we call it an axiom.\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" PEAS: Performance measurement, Environment, Actuator, Sensor\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" A logic must also define the semantics, or meaning, of sentences. The semantics defines the\n",
        "truth of each sentence with respect to each possible world\\n\n",
        "Entailment: one scentence is fully logical from one another scentence\\n\n",
        "$\\\\alpha \\\\models \\\\beta$ if in every model where $\\\\alpha$ is true, $\\\\beta$ is also true ($M(\\\\alpha) \\\\subset M(\\\\beta)$)\\n\n",
        "If an algorithm $i$ can derive $\\\\alpha$ from $KB$, we write $KB \\\\vdash_i \\\\alpha$\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" The syntax of propositional logic defines the allowable sentences. \\n\n",
        "The atomic sentences consist of a single proposition symbol. Each such symbol (e.g. $P$, $Q$) stands for a proposition that can be true or false. \\n\n",
        "Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. \\n\n",
        "not : $\\\\neg$ (negation) \\n\n",
        "and : $\\\\wedge$ ($\\\\wedge$ looks like \"A\" for \"And\") $P \\\\wedge Q$ is called a conjunction. \\n\n",
        "or ： $\\\\vee$ $P \\\\vee Q$ is called a disjunction. \\n\n",
        "imply : $\\\\Rightarrow$ \\n\n",
        "if and only if: $\\\\Leftrightarrow$\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" logical equivalence: $\\\\alpha \\\\equiv \\\\beta$ iff $\\\\alpha \\\\models \\\\beta$ and $\\\\beta \\\\models \\\\alpha$ \\n\n",
        "$(\\\\alpha \\\\wedge \\\\beta) \\\\equiv (\\\\beta \\\\wedge \\\\alpha)$ \\n\n",
        "$(\\\\alpha \\\\vee \\\\beta) \\\\equiv (\\\\beta \\\\vee \\\\alpha)$ \\n\n",
        "$((\\\\alpha \\\\wedge \\\\beta) \\\\wedge \\\\gamma) \\\\equiv (\\\\alpha \\\\wedge (\\\\beta \\\\wedge \\\\gamma))$ \\n\n",
        "$((\\\\alpha \\\\vee \\\\beta) \\\\vee \\\\gamma) \\\\equiv (\\\\alpha \\\\vee (\\\\beta \\\\vee \\\\gamma))$ \\n\n",
        "$\\\\neg(\\\\neg \\\\alpha) \\equiv \\\\alpha$ \\n\n",
        "$(\\\\alpha \\\\Rightarrow \\\\beta) \\\\equiv (\\\\neg\\\\beta \\\\Rightarrow \\\\neg\\\\alpha)$ \\n\n",
        "$(\\\\alpha \\\\Rightarrow \\\\beta) \\\\equiv (\\\\neg \\\\alpha \\\\vee \\\\beta)$ \\n\n",
        "$(\\\\alpha \\\\Leftrightarrow \\\\beta) \\\\equiv ((\\\\alpha \\\\Rightarrow \\\\beta) \\\\wedge (\\\\beta \\\\Leftrightarrow \\\\alpha))$ \\n\n",
        "$\\\\neg(\\\\alpha \\\\wedge \\\\beta) \\\\equiv (\\\\neg\\\\alpha \\\\vee \\\\neg \\\\beta)$ (De Morgan)\\n\n",
        "$\\\\neg(\\\\alpha \\\\vee \\\\beta) \\\\equiv (\\\\neg\\\\alpha \\\\wedge \\\\neg \\\\beta)$ (De Morgan)\\n\n",
        "$(\\\\alpha \\\\wedge (\\\\beta \\\\vee \\\\gamma)) \\\\equiv ((\\\\alpha \\\\wedge \\\\beta) \\\\vee ( \\\\alpha \\\\wedge \\\\gamma))$ \\n\n",
        "$(\\\\alpha \\\\vee (\\\\beta \\\\wedge \\\\gamma)) \\\\equiv ((\\\\alpha \\\\vee \\\\beta) \\\\wedge ( \\\\alpha \\\\vee \\\\gamma))$ \\n\n",
        "INITIAL STATE: the initial knowledge base.\\n\n",
        "ACTIONS: the set of actions consists of all the inference rules applied to all the\n",
        "sentences that match the top half of the inference rule.\\n\n",
        "RESULT: the result of an action is to add the sentence in the bottom half of the\n",
        "inference rule.\\n\n",
        "GOAL: the goal is a state that contains the sentence we are trying to prove.\\n\n",
        "\n",
        "\n",
        "For any sentences $P$ and $Q$, $P \\\\models Q$ if and only if $P \\\\Rightarrow Q$ is valid. \\n\n",
        "Inference rules: \\n\n",
        "$\\\\frac{\\\\alpha \\\\Rightarrow \\\\beta, \\\\alpha}{\\\\beta}$ \\n\n",
        "$\\\\frac{\\\\alpha \\\\wedge \\\\beta}{\\\\beta}$ \\n\n",
        "All logical equivalences can be used as inference rules. \\n\n",
        "Logical systems is monotonicity, the set of entailed sentences can only increase as information is added to the knowledge base. \\n\n",
        "If $KB \\\\models \\\\alpha$ then $KB \\\\wedge \\\\beta \\\\models \\\\alpha$ \\n\n",
        "Resolution: $\\\\frac{(P_1 \\\\vee \\\\cdots \\\\vee P_k) \\\\wedge \\\\neg P_i}{P_1 \\\\vee \\\\cdots \\\\vee P_{i-1} \\\\vee P_{i+1} \\\\vee \\\\cdots \\\\vee P_k}$ \\n\n",
        "The resolution algorithm is complete.\\n\n",
        "Forward Chaining Algorithm：\\n\n",
        "Forward chaining is a method of reasoning in artificial intelligence in which inference rules are applied to existing data \n",
        "to extract additional data until an endpoint (goal) is achieved.\n",
        "In this type of chaining, the inference engine starts by evaluating existing facts, derivations, and \n",
        "conditions before deducing new information. An endpoint (goal) is achieved through the manipulation of knowledge that exists in the knowledge base.\\n\n",
        "Forward chaining is complete and sound. \\n\n",
        "Deciding entailment with Horn clauses can be done in time that is linear in the size of knowledge base. \\n\n",
        "Backward chaining is goal-directed reasoning.\n",
        "\"\"\"\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Construct CNF: \\n\n",
        "1. Eliminate $\\\\Leftrightarrow$ by $(\\\\alpha \\\\Leftrightarrow \\\\beta) \\\\equiv ((\\\\alpha \\\\Rightarrow \\\\beta) \\\\wedge (\\\\beta \\\\Leftrightarrow \\\\alpha))$ \\n\n",
        "2. Eliminate $\\\\Rightarrow$ by $(\\\\alpha \\\\Rightarrow \\\\beta) \\\\equiv (\\\\neg \\\\alpha \\\\vee \\\\beta)$ \\n\n",
        "3. Move $\\\\neg$ inwards (only before literals) by De Morgan and double-negation. \\n\n",
        "4. Distribute $\\\\vee$ over $\\wedge$ wherever possible. \\n\n",
        "Resolution Algorithm: \\n\n",
        "To show $KB \\\\models \\\\alpha$, we can show that $KB \\\\wedge \\\\neg\\\\alpha$ is unsatisfiable. \\n\n",
        "1. Convert $KB \\\\wedge \\\\neg\\\\alpha$ into CNF\n",
        "2. Repeat resolution for each pairs of disjunctions until one of two things happens:\n",
        "a) There are no new clauses that can be added. In this case, the KB does not entail $\\\\alpha$\n",
        "b) Two clauses resolve to yield the empty clause (comes from contradiction), in which case the KB does entail $\\\\alpha$\n",
        "Resolution is sound and complete. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Soundness\" : \"the inference algorithm should only derive entailed sentences\", \n",
        "\"Completeness\" : \"An inference algorithm is complete if it can derive all sentences that are entailed.\",\n",
        "\"Validity\" : \"A sentence is valid if it is true in all models. For example, $P \\\\vee \\\\neg P$ is valid.\",\n",
        "\"Satisfiability\" : \"A sentence is satisfiable if it is true in, orsatisfied by some models (assignment).\",\n",
        "\"CNF (Conjunctive Normal Form)\" : \"Every sentence of propositional logic is logically equivalent to a conjunction of clauses which are disjunctions of literals.\",\n",
        "\"Definite clause\" : \"disjunction of literals where exactly one is positive\",\n",
        "\"Horn clause\" : \"disjunction of literals where at most one is positive\",\n",
        "}"
      ],
      "execution_count": 54,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d52a71ba-4249-43cb-c26f-e8774c3d32ce"
      },
      "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": 55,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nA knowledge base is a set of sentences \n\nEach sentence is expressed in a language called a knowledge representation language and\nrepresents some assertion about the world. When the sentence is taken as being given\nwithout being derived from other sentences, we call it an axiom.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n PEAS: Performance measurement, Environment, Actuator, Sensor\n\n\n## AIMA Chapter 7.3 Logic\n A logic must also define the semantics, or meaning, of sentences. The semantics defines the\ntruth of each sentence with respect to each possible world\n\nEntailment: one scentence is fully logical from one another scentence\n\n$\\alpha \\models \\beta$ if in every model where $\\alpha$ is true, $\\beta$ is also true ($M(\\alpha) \\subset M(\\beta)$)\n\nIf an algorithm $i$ can derive $\\alpha$ from $KB$, we write $KB \\vdash_i \\alpha$\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. \n\nThe atomic sentences consist of a single proposition symbol. Each such symbol (e.g. $P$, $Q$) stands for a proposition that can be true or false. \n\nComplex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. \n\nnot : $\\neg$ (negation) \n\nand : $\\wedge$ ($\\wedge$ looks like \"A\" for \"And\") $P \\wedge Q$ is called a conjunction. \n\nor ： $\\vee$ $P \\vee Q$ is called a disjunction. \n\nimply : $\\Rightarrow$ \n\nif and only if: $\\Leftrightarrow$\n\n\n## AIMA 7.5 Propositional Theorem Proving\n logical equivalence: $\\alpha \\equiv \\beta$ iff $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$ \n\n$(\\alpha \\wedge \\beta) \\equiv (\\beta \\wedge \\alpha)$ \n\n$(\\alpha \\vee \\beta) \\equiv (\\beta \\vee \\alpha)$ \n\n$((\\alpha \\wedge \\beta) \\wedge \\gamma) \\equiv (\\alpha \\wedge (\\beta \\wedge \\gamma))$ \n\n$((\\alpha \\vee \\beta) \\vee \\gamma) \\equiv (\\alpha \\vee (\\beta \\vee \\gamma))$ \n\n$\\neg(\\neg \\alpha) \\equiv \\alpha$ \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg\\beta \\Rightarrow \\neg\\alpha)$ \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n$(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n$\\neg(\\alpha \\wedge \\beta) \\equiv (\\neg\\alpha \\vee \\neg \\beta)$ (De Morgan)\n\n$\\neg(\\alpha \\vee \\beta) \\equiv (\\neg\\alpha \\wedge \\neg \\beta)$ (De Morgan)\n\n$(\\alpha \\wedge (\\beta \\vee \\gamma)) \\equiv ((\\alpha \\wedge \\beta) \\vee ( \\alpha \\wedge \\gamma))$ \n\n$(\\alpha \\vee (\\beta \\wedge \\gamma)) \\equiv ((\\alpha \\vee \\beta) \\wedge ( \\alpha \\vee \\gamma))$ \n\nINITIAL STATE: the initial knowledge base.\n\nACTIONS: the set of actions consists of all the inference rules applied to all the\nsentences that match the top half of the inference rule.\n\nRESULT: the result of an action is to add the sentence in the bottom half of the\ninference rule.\n\nGOAL: the goal is a state that contains the sentence we are trying to prove.\n\n\n\nFor any sentences $P$ and $Q$, $P \\models Q$ if and only if $P \\Rightarrow Q$ is valid. \n\nInference rules: \n\n$\\frac{\\alpha \\Rightarrow \\beta, \\alpha}{\\beta}$ \n\n$\\frac{\\alpha \\wedge \\beta}{\\beta}$ \n\nAll logical equivalences can be used as inference rules. \n\nLogical systems is monotonicity, the set of entailed sentences can only increase as information is added to the knowledge base. \n\nIf $KB \\models \\alpha$ then $KB \\wedge \\beta \\models \\alpha$ \n\nResolution: $\\frac{(P_1 \\vee \\cdots \\vee P_k) \\wedge \\neg P_i}{P_1 \\vee \\cdots \\vee P_{i-1} \\vee P_{i+1} \\vee \\cdots \\vee P_k}$ \n\nThe resolution algorithm is complete.\n\nForward Chaining Algorithm：\n\nForward chaining is a method of reasoning in artificial intelligence in which inference rules are applied to existing data \nto extract additional data until an endpoint (goal) is achieved.\nIn this type of chaining, the inference engine starts by evaluating existing facts, derivations, and \nconditions before deducing new information. An endpoint (goal) is achieved through the manipulation of knowledge that exists in the knowledge base.\n\nForward chaining is complete and sound. \n\nDeciding entailment with Horn clauses can be done in time that is linear in the size of knowledge base. \n\nBackward chaining is goal-directed reasoning.\n\n\n## Module 7 Lecture Notes\n\nConstruct CNF: \n\n1. Eliminate $\\Leftrightarrow$ by $(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n2. Eliminate $\\Rightarrow$ by $(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n3. Move $\\neg$ inwards (only before literals) by De Morgan and double-negation. \n\n4. Distribute $\\vee$ over $\\wedge$ wherever possible. \n\nResolution Algorithm: \n\nTo show $KB \\models \\alpha$, we can show that $KB \\wedge \\neg\\alpha$ is unsatisfiable. \n\n1. Convert $KB \\wedge \\neg\\alpha$ into CNF\n2. Repeat resolution for each pairs of disjunctions until one of two things happens:\na) There are no new clauses that can be added. In this case, the KB does not entail $\\alpha$\nb) Two clauses resolve to yield the empty clause (comes from contradiction), in which case the KB does entail $\\alpha$\nResolution is sound and complete. \n\n\n\n## Module 7 Definitions\n* **Soundness** - the inference algorithm should only derive entailed sentences\n* **Completeness** - An inference algorithm is complete if it can derive all sentences that are entailed.\n* **Validity** - A sentence is valid if it is true in all models. For example, $P \\vee \\neg P$ is valid.\n* **Satisfiability** - A sentence is satisfiable if it is true in, orsatisfied by some models (assignment).\n* **Cnf (conjunctive normal form)** - Every sentence of propositional logic is logically equivalent to a conjunction of clauses which are disjunctions of literals.\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at most one is positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "0df2d724-b3d7-4d2b-ae77-d8fb3807336d"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 56,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nThe field of artificial intelligence is\nconcerned with not just understanding but also building intelligent entities—machines that\ncan compute how to act effectively and safely in a wide variety of novel situations.\n\n\nTuring test: proposed by Alan Turing (1950)\n\nThe computer would need the following capabilities:\n\nnatural language processing to communicate successfully in a human language;\n\nknowledge representation to store what it knows or hears;\n\nautomated reasoning to answer questions and to draw new conclusions;\n\nAll the skills needed for the Turing test also allow an agent to act rationally. Knowledge\nrepresentation and reasoning enable agents to reach good decisions.\n\n\nmachine learning to adapt to new circumstances and to detect and extrapolate patterns.\n\nThese laws of thought were supposed to govern the operation of the mind; their study\ninitiated the field called logic.\n\n\nThe problem of achieving agreement between our true preferences and the objective we put\ninto the machine is called the value alignment problem: the values or objectives put into\nthe machine must be aligned with those of the human.\n \n\n## AIMA Chapter 27.1 The Limits of AI\nweak AI—the idea that\nmachines could act as if they were intelligent\n\nstrong AI—the assertion that machines\nthat do so are actually consciously thinking\n\n“human-level AI” or “general AI”—programs that can solve an arbitrarily wide variety of tasks, including novel ones, and\ndo so as well as a human\n\n\nThe embodied cognition approach claims that it makes no sense to consider the brain\nseparately: cognition takes place within a body, which is embedded in an environment\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nChinese room argumentThe process of thinking is not important, the result matters.\n\n## AIMA 2.1 Agents and Environments\n The concept to develop a small set of design principles for building successful agents—systems that can reasonably be called intelligent\n\nAn agent is anything that can be viewed as perceiving its environment through sensors and\nacting upon that environment through actuators\n\n\nMathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept\nsequence to an action\n\nInternally, the agent function for an artificial agent will be\nimplemented by an agent program \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n consequentialism: we evaluate an agent’s behavior by\nits consequences\n\n\nThis notion of desirability is captured by a performance measure\nthat evaluates any given sequence of environment states or each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has.\n\n\nFor each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has.\n\n\nDoing actions in order to modify future percepts—\nsometimes called information gathering\n \n\n## AIMA 2.3 The Nature of Environments\n task environments: the “problems” to which rational agents are the solutions.\n\nIf an agent’s sensors give it access\nto the complete state of the environment at each point in time, then we say that the task\nenvironment is fully observable. If the agent has no sensors at all\nthen the environment is unobservable.\n\n\nIf the next state of the environment is completely\ndetermined by the current state and the action executed by the agent(s), then we say the\nenvironment is deterministic; otherwise, it is nondeterministic.\n\nstochastic: we say that a model of the environment\nis stochastic if it explicitly deals with probabilities\n\n\nEpisodic: each step an input and output; Sequential: all inputs has influence upon future decision\n\nIn a known environment, the outcomes for all actions are given  \n\n## AIMA 2.4 The Structure of Agents\n The job of AI is to design an agent program that implements the agent function—the\nmapping from percepts to actions. We assume this program will run on some sort of\ncomputing device with physical sensors and actuators—we call this the agent architecture\n\n\nThe simplest kind of agent is the simple reflex agent. These agents select actions on the\nbasis of the current percept, ignoring the rest of the percept history\n\n\nEscape from infinite loops is possible if the agent can randomize its actions\n\n\nthe transition model and sensor model allow an agent to keep track of the state of\nthe world—to the extent possible given the limitations of the agent’s sensors. An agent that\nuses such models is called a model-based agent.\n\n\nGoal-based agents\n\nUtility-based agent\n\nLearning agents\n\n\nA factored representation splits up each state into a fixed set of variables or attributes,\neach of which can have a value\n\nA structured representation\n\n \n\n## Module 1 Lecture Notes\nPEAS (Performance, Environment, Actuators, Sensors) \n\nn cases where the performance measure is unknown or hard to specify correctly, there\nis a significant risk of the agent optimizing the wrong objective. In such cases the agent\ndesign should reflect uncertainty about the true objective\n\n## Module 1 Definitions\n* **Agent** - anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\n* **Rationality** - doing the right thing, formal definition of intelligence\n* **Rational agent** - acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n* **Standard model** - general paradigm of AI, the right thing is defined by the objective that we provide to the agent\n* **Limited rationality** - acting appropriately when there is not enough time to do all the computations\n* **Homo sapiens** - man the wise\n* **Percept sequence** - complete history of everything the agent has ever perceived\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Objects of built-in types like (int, float, bool, str, tuple, unicode) are immutable and hashable\n\n\nStrong Typing: Every object has a fixed type, interpreter doesn’t allow things incompatible with\nthat type\n\nDynamic typing: Variables come into existence when first assigned \n\n## Module 2 Definitions\n* **Mutability** - can change or not. str, tuple is imutable (the item within is not influenced)\n* **Mutable** - its state can be changed after declared.\n* **Hashable** - immutable, like tuple, string\n* **Dict+dict** - not supported\n* **Set.remove** - key exist needed\n* **Tuple** -  A simple immutable ordered sequence of items\n* **Strings** - Immutable\n* **List** - Mutable ordered sequence of items of mixed types\n* **Dictionaries** - are unordered & work by hashing, so keys must be immutable\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n We distinguish between informed algorithms, in which the agent can estimate how\nfar it is from the goal, and uninformed algorithms, where no such estimate is available\n\nGoal formulation, Problem formulation, Search (for solution), Execution \n\nA search problem: state space, initial state, goal states, action space, transition model, action cost function \n\nA sequence of actions forms a path, and a solution is a path from the initial state to a goal state.\n \n\n## AIMA Chapter 3.2 Example Problems\n The state space can be infinite.\n\nA standardized problem is intended to illustrate or exercise various problem\u0002solving methods. \n\nA real-world problem is one whose solutions people actually use, and whose\nformulation is idiosyncratic, not standardized \n\n## AIMA Chapter 3.3 Search Algorithms\n\nThe search algorithm superimposes a search tree over the state-space graph\n\nThe state space describes the set of states in the world \n\nThe actions allow transitions from one state to another. \n\nThe search tree describes paths between states, reaching towards the goal. \n\n\nA priority queue first pops the node with the minimum cost according to some\nevaluation function, It is used in best-first search.\n\nA FIFO queue or first-in-first-out queue first pops the node that was added to the queue\nfirst; we shall see it is used in breadth-first search\n\nA LIFO queue or last-in-first-out queue(stack) pops first the most recently added node; we shall see it is used in depth-first search\n\n\nBest-first search: priority queue frontier, each time choose the node with the best evaluation function\nIf the action costs are uniform, we can use BFS and DFS \n\nWe call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nAn uninformed search algorithm is given no clue about how close a state is to the goal. \n\n\nBFS:\n\ncomplete, cost-optimal for the problem where actions have identical cost. \n\nBoth time complexity: $O(b^d)$ space complexity: $O(b^d)$. \n\nDijkstra's algorithm: uniform-cost search (Best First Search) uniform-cost is refered to uniform-depth (BFS) \n\n\nUniform-cost search:\n\ncomplete if all action costs are $\\ge \\epsilon > 0$ \n\nBoth time and space complexity are $O(b^{1 + \\frac{C^*}{\\epsilon}})$, or $O(b^{d+1})$ when all costs are equal \n\n\nDepth-first search:\n\nnot cost-optimal\n\nFor finite state spaces that are trees DFS is efficient and complete. (For cyclic graph, DFS is not complete) \n\n\nDepth-limited search:\n\nTime complexity: $O(b^l)$, space complexity: $O(bl)$ \n\n\nBacktracking search:\n\nuses less memory. Only one successor is generated at a time and undo the action after we have DFS it. \n\nTime complexity: $O(b^m)$, space complexity: $O(bm)$ \n\n\nIterative Deepening search:\n\ncomplete and cost-optimal. (Depth-limited is not, but iterative deepening is based on depth-limited) \n\nTime complexity: $O(b^d)$, space complexity: $O(b^m)$ \n\n\nBidirectional search:\n\ncomplete and cost-optimal if both directions are breadth-first or uniform-cost.\n\n\n## Module 3 Lecture Notes\nA problem-solving agent must plan\nahead.\n\nThe computational process that it\nundertakes is called search.\n\nIt will consider a sequence of actions\nthat form a path to a goal state.\n\nSuch a sequence is called a solution.\n\nPath: a sequence of actions leading from one state $s_j$ to another state $s_k$ \n\nSolution: a path from the initial state $s_i$ to a state sf that satisfies the goal test\n\n\nIn a fully observable, deterministic, known environment, the solution to any problem is a fixed set of actions\n\n\nTree search uses less space than graph search \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Dijkstra’s algorithm** - a Uniform-cost Search without a goal.\n* **Open-loop system** - system without percepts\n* **Close-loop system** - system monitors the percepts\n* **Completeness** - whether the algorithm guaranteed to find a solution when there is one, and to correctly report failure\n* **Cost optimality** - Does it find a solution with the lowest path cost of all solutions\n* **Optimality/admissibility** - whether the algorithm can find the solution with lowest cost\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nheuristic function: \n\nh(n) =  estimated cost of the cheapest path from the state at node n to a goal state\n\n\nGreedy best-first search:\n\na form of best-first search that expands first the node with the\nlowest $h(n)$ value\n\nTime complexity and space complexity, worst case $O(b^m)$\n\nTime complexity and space complexity, optimal case $O(bm)$\n\n\nA* search:\n\ncomplete and cost-optimal if the heuristic is admissible. \n\nTime complexity and space complexity, worst case $O(|E|) = O(b^d),O(|V|) = O(b^d)$\n\nAdmissible heuristic: $h(n) \\le h^*(n) $ \n (where $h^*(n)$ is the real cost to the goal state) \n\n\nStronger property for graph search is consistency. (triangle inequality) \n\nWith a consistent heuristic, the first time A* reaches a state it will be on an optimal path. (optimally efficient) \n\nThe $g$ should be monotonic because the action cost is positive. \n\nA* expands all nodes $f(n) < C^*$, might expands some nodes $f(n) = C^*$, never expands nodes $f(n) > C^*$. \n\nWeighted A* (enforce the algorithm to be greedy) \n\n\nWe can explore fewer\nnodes (taking less time and space) if we are willing to accept solutions that are suboptimal,\nbut are “good enough”—what we call satisficing solutions. If we allow A* search to use an\ninadmissible heuristic\n\n\nBeam search limits the size of the frontier.\n\n\nterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth\u0002first\n\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \nOne way to characterize the quality of a heuristic is the effective branching factor \n\nnumber of nodes: N, solution depth: d,  effective branching factor: $b^*$\n\n$N+1 = 1+(b^*)^2 + ...+(b^*)^d$\n\n\nA problem with fewer restrictions on the actions is\ncalled a relaxed problem. The state-space graph of the relaxed problem is a supergraph of\nthe original state space because the removal of restrictions creates added edges in the graph.\n\n\n## Module 4 Lecture Notes\nBefore an agent can start searching, a well-defined problem must be formulated.\n\n\nA problem consists of five parts: the initial state, a set of actions, a transition model\ndescribing the results of those actions, a set of goal states, and an action cost function.\n\n\nThe environment of the problem is represented by a state space graph. A path through\nthe state space (a sequence of actions) from the initial state to a goal state is a solution.\n\n\nSearch algorithms are judged on the basis of completeness, cost optimality, time\ncomplexity, and space complexity.\n\n\nUninformed search methods have access only to the problem definition. Algorithms\nbuild a search tree in an attempt to find a solution. Algorithms differ based on which\nnode they expand first:\n\n– BEST-FIRST SEARCH selects nodes for expansion using to an evaluation function.\n\n– BREADTH-FIRST SEARCH expands the shallowest nodes first; it is complete,\n\noptimal for unit action costs, but has exponential space complexity.\n– UNIFORM-COST SEARCH expands the node with lowest path cost, and is\noptimal for general action costs.\n\n– DEPTH-FIRST SEARCH expands the deepest unexpanded node first. It is neither\ncomplete nor optimal, but has linear space complexity. Depth-limited search adds a\ndepth bound.\n\n– ITERATIVE DEEPENING SEARCH calls depth-first search with increasing depth\nlimits until a goal is found. It is complete when full cycle checking is done, optimal for\nunit action costs, has time complexity comparable to breadth-first search, and has linear\nspace complexity.\ng(n),\n\n– BIDIRECTIONAL SEARCH expands two frontiers, one around the initial state and\none around the goal, stopping when the two frontiers meet.\nInformed search methods have access to a heuristic function that estimates the\ncost of a solution from They may have access to additional information such as\npattern databases with solution costs.\n\n– GREEDY BEST-FIRST SEARCH expands nodes with minimal It is not optimal\nbut is often efficient.\n\n– A* SEARCH expands nodes with minimal A* is complete and\noptimal, provided that is admissible. The space complexity of A* is still an issue for\nmany problems.\n\n– BIDIRECTIONAL A* SEARCH is sometimes more efficient than A* itself.\n\n– IDA* (iterative deepening A* search) is an iterative deepening version of A*, and\nthus adresses the space complexity issue.\n\n– RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are\nrobust, optimal search algorithms that use limited amounts of memory; given enough\ntime, they can solve problems for which A* runs out of memory.\n\n– BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and\nsuboptimal, but it often finds reasonably good solutions and runs faster than complete\nsearches.\n\n– WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but\nsacrificing optimality.\n\n\nThe performance of heuristic search algorithms depends on the quality of the heuristic\nfunction. One can sometimes construct good heuristics by relaxing the problem\ndefinition, by storing precomputed solution costs for subproblems in a pattern database,\nby defining landmarks, or by learning from experience with the problem class. \n\n## Module 4 Definitions\n* **Branching factor** - the number of successors generated by a given node.\n* **Dominate** - A heuristic function h dominates h' if both are admissible and for every node n, h(n) is greater than h'(n).\n* **Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal: $h(n) \\le h^*(n)$\n* **Consistency** - $h(n) \\le c(n, a, n') + h(n')$\n* **Surely expanded nodes** - $f(n) < C^*\n* **Ida*** - iterative deeping A*\n* **Rbfs** - recursive best-first search\n* **Sma*** - simplified memory-bounded A*\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nThe games most commonly studied within AI (such as chess and Go) are what game\ntheorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.\n“Perfect information” is a synonym for “fully observable,” and “zero-sum” means that what\nis good for one player is just as bad for the other: there is no “win-win” outcome. For games\nwe often use the term move as a synonym for “action” and position as a synonym for\n“state.”\n\nutility funtion: defines the final numeric value to player when the game ends in terminal state\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nAlpha: MAX's current lower bound on MAX's outcome \n\nBeta: MIN's current upper bound on MIN's outcome \n\nWhen evaluating a MAX node: a value $v \\ge \\beta$ (MIN will never select that MAX node) \n\nWhen evaluating a MIN node: a value $v \\le \\alpha$ (Max will never select that MIN node) \n\n```\ndef AlphaBeta(node, depth, alpha, beta, MAX):\n    if depth == 0 or node.isTerminal():\n        return node\n    if MAX:\n        value = -inf\n        for s in node.successors:\n            value = max(value, AlphaBeta(s, depth-1, alpha, beta, False))\n            if value >= beta:\n                break ### prune the branch\n            alpha = max(alpha, value)\n        return value\n    else:\n        value = inf\n        for s in node.successors:\n            value = min(value, AlphaBeta(s, depth-1, alpha, beta, True))\n            if value <= alpha:\n                break ### prune the branch\n            beta = min(beta, value)\n        return value\n\ninitial call\nAlphaBeta(origin, depth, -inf, inf, True)\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nAlpha–beta pruning prunes branches of the tree that can have no effect on the final\nevaluation, but forward pruning prunes moves that appear to be poor moves, but might\npossibly be good ones\n\nOne approach to forward pruning is beam search\n\non each ply, consider only\na “beam” of the best moves (according to the evaluation function) rather than considering n\nall possible moves. Unfortunately, this approach is rather dangerous because there is no\nguarantee that the best move will not be pruned away.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \nExpectimax search:\n\nuse expectation as the evalution funtion\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n $P(s'|a) = \\sum_{s} P(s)P(s'|s,a)$ \n\nExpected utility of action $a$: $ EU(a) = \\sum_{s'}P(s'|a)U(s') $ \n\naction = $\\argmax_a EU(a)$ \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nORDERABILITY: Given any two lotteries, a rational agent must either prefer one or\nelse rate them as equally preferable\n\nTRANSITIVITY: Given any three lotteries, if an agent prefers to and prefers to ,\nthen the agent must prefer to .\n\nCONTINUITY: If some lottery is between and in preference, then there is some\nprobability for which the rational agent will be indifferent between getting for sure\nand the lottery that yields with probability and with probability .\n\nSUBSTITUTABILITY: If an agent is indifferent between two lotteries and , then the\nagent is indifferent between two more complex lotteries that are the same except that \nis substituted for in one of them. This holds regardless of the probabilities and the\nother outcome(s) in the lotteries\n\nMONOTONICITY: Suppose two lotteries have the same two possible outcomes, and \n. If an agent prefers to , then the agent must prefer the lottery that has a higher\nprobability for (and vice versa)\n\nDECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the\nlaws of probability.\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nHuman judgment is usually irrational.\n\n\n## Module 5 Lecture Notes\n\nHeuristic alpha-beta search replaces the utility function with an evaluation function estimates the value of non-terminal nodes, the terminal test is replaced with a cutoff test decides when to cut off the search\\\nThe horizon effect is when an agent try to erroneously delay the inevitable\n\nBeam-search: most used forward pruning\n\nforward pruning is a type B strategy\n\nAn evalution function returns an estimate of the expected utility of some state s, for player p. For terminal states, the evaluation function is exactly equal to the utility.\n\n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Utility function u(s)** - gives the payoff for each player in terminal state\n* **Minimax search** - solves perfect information, zero-sum games, same order as depth-first search, time complexity O(b^m)\n* **Alpha-beta pruning** - time complexity O(b^m/2)\n* **Type a strategy** - explores a wide but shallow portion of the tree\n* **Type b strategy** - explores a deep but narrow portion of the tree\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP consists of $X$, $D$ and $C$. $X$ is set of variables, $D$ is set of domains for variables, $C$ is set of constraints. \n\nA complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a\nconsistent, complete assignment. A partial assignment is one that leaves some variables\nunassigned, and a partial solution is a partial assignment that is consistent. Solving a CSP is\nan NP-complete problem \n\nThe best-known category of continuous-domain CSPs is that of linear programming problems, which is also called COP (constrained optimization problem)\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nconstraint propagation: using the constraints to reduce the number of legal values for a\nvariable, which in turn can reduce the legal values for another variable, and so on\n\nkey idea: enforcing local consistency\n\n\nA single variable (corresponding to a node in the CSP graph) is node-consistent if all the\nvalues in the variable’s domain satisfy the variable’s unary constraints\n\nA variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s\nbinary constraints\n\nPath consistency tightens the binary constraints by using implicit constraints\nthat are inferred by looking at triples of variables\n\nStronger forms of propagation can be defined with the notion of -consistency. A CSP is -\nconsistent if, for any set of variables and for any consistent assignment to those\nvariables, a consistent value can always be assigned to any th variable\n\n\n\nAC3: solving arc arc-consistency\n\n\n```\ndef AC3(X, D, ARC):\n    worklist = {(x,y) | arc(x,y) exists}\n    while worklist:\n        cur = worklist.pop()\n        if arc_reduce(x,y):\n            for arc in ARC:\n                if (arc[1] == cur[0]) and (arc[0] != cur[1]): ### (z , x) | z != y\n                    worklist.append(arc)\n\ndef arc_reduce(x,y):\n    if len(D(y)) == 1:\n        c = D(y)[0]\n        if c in D(x):\n            D(x).remove(c)\n            return True\n    return False\n```\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nBacktrack searching repeatedly chooses an\nunassigned variable, and then tries all values in the domain of that variable in turn, trying to\nextend each one into a solution via a recursive call. If the call succeeds, the solution is\nreturned, and if it fails, the assignment is restored to the previous state, and we try the next\nvalue. If no value works then we return failure\n\n\nMAC (Maintaining Arc Consistency) recursively propogrates constraints, whereas forward checking does not. \nIf we assign X, forward checking makes all the arcs incident on X consistent. \nMAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...).\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\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nmin-conflicts heuristic:\n\nRandomly choose the min-conflicted variable and modift its value to satisfy the constraints. \n\n\nAnother technique called constraint weighting aims to concentrate the search on the\nimportant constraints. Each constraint is given a numeric weight, initially all 1. At each step\nof the search, the algorithm chooses a variable/value pair to change that will result in the\nlowest total weight of all violated constraints.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nindependent subproblems:\n\nIndependence can be ascertained simply by finding connected components of the\nconstraint graph\n\n\n \n\n## Module 6 Lecture Notes\n \nConstraint satisfaction problems (CSPs) represent a state with a set of variable/value\npairs and represent the conditions for a solution by a set of constraints on the variables.\n\n\nCSPs can rule out variable assignments using seach or inference\n\n\nBacktracking search, a form of depth-first search, is commonly used for solving CSPs.\nInference can be interwoven with search.\n\n\nThe minimum-remaining-values and degree heuristics are domain-independent\nmethods for deciding which variable to choose next in a backtracking search. The least\u0002constraining-value heuristic helps in deciding which value to try first for a given\nvariable. Backtracking occurs when no legal assignment can be found for a variable.\nConflict-directed backjumping backtracks directly to the source of the problem.\nConstraint learning records the conflicts as they are encountered during search in order\nto avoid the same conflict later in the search.\n\n\nLocal search using the min-conflicts heuristic has also been applied to constraint\nsatisfaction problems with great success.\n\n\nThe complexity of solving a CSP is strongly related to the structure of its constraint\ngraph. Tree-structured problems can be solved in linear time. Cutset conditioning can\nreduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\nmemory) if a small cutset can be found. Tree decomposition techniques transform the\nCSP into a tree of subproblems and are efficient if the tree width of the constraint graph\nis small; however they need memory exponential in the tree width of the constraint\ngraph. Combining cutset conditioning with tree decomposition can allow a better\ntradeoff of memory versus time\n\n\nHeuristic 1: Most constrained variable \n\nHeuristic 2: Most constraining variable \n\nHeuristic 3: Least constraining value \n\nHeuristic 4: Forward checking (Arc consistency & AC-3) \n\nAC-3's worst case complexity: $O(n^2d^3)$ (the number of arcs is $O(n^2)$ and checking an arc costs $O(d^2)$ (an arc may need to be checked d times)) \\\nFor planar constraint graphs, the number of arcs is $O(n)$, time complexity: $O(nd^3)$\n \n\n## Module 6 Definitions\n* **Mac** - Maintaining Arc Consistency, MAC recursively propogrates constraints, whereas forward checking does not\n* **Mac vs ac3** - MAC is a way of interleaving search and inference. AC-3 is pure inference\n* **Csps** - CSPs represent the conditions for a solution with a set of constraints on the variables\n* **Csps note-2** - In search problems, states are black boxes. In CSPs, the agent can see inside the states and move\n* **Mrv heuristic** - Minimum Remaining Value, chooses the variable with the fewest 'legal' values\n* **Degree heuristic** - chooses the variable with the largest number of constraints\n* **Least constraining value heuristic** - chooses the value that rules out the fewest values for neighboring variables\n* **Constraint learning** - records the conflicts as they are encountered in the search in order to avoid the same conflict later\n* **Cutset conditioning** - reduce a general CSP (exponential) to a tree structured one(linear), space efficient\n* **Tree decomposition techniques** - transform the CSP into a tree of subproblems\n* **Tree decomposition techniques efficiency** - efficient if the tree width of the constraint graph is small, time efficient\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nA knowledge base is a set of sentences \n\nEach sentence is expressed in a language called a knowledge representation language and\nrepresents some assertion about the world. When the sentence is taken as being given\nwithout being derived from other sentences, we call it an axiom.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n PEAS: Performance measurement, Environment, Actuator, Sensor\n\n\n## AIMA Chapter 7.3 Logic\n A logic must also define the semantics, or meaning, of sentences. The semantics defines the\ntruth of each sentence with respect to each possible world\n\nEntailment: one scentence is fully logical from one another scentence\n\n$\\alpha \\models \\beta$ if in every model where $\\alpha$ is true, $\\beta$ is also true ($M(\\alpha) \\subset M(\\beta)$)\n\nIf an algorithm $i$ can derive $\\alpha$ from $KB$, we write $KB \\vdash_i \\alpha$\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines the allowable sentences. \n\nThe atomic sentences consist of a single proposition symbol. Each such symbol (e.g. $P$, $Q$) stands for a proposition that can be true or false. \n\nComplex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. \n\nnot : $\\neg$ (negation) \n\nand : $\\wedge$ ($\\wedge$ looks like \"A\" for \"And\") $P \\wedge Q$ is called a conjunction. \n\nor ： $\\vee$ $P \\vee Q$ is called a disjunction. \n\nimply : $\\Rightarrow$ \n\nif and only if: $\\Leftrightarrow$\n\n\n## AIMA 7.5 Propositional Theorem Proving\n logical equivalence: $\\alpha \\equiv \\beta$ iff $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$ \n\n$(\\alpha \\wedge \\beta) \\equiv (\\beta \\wedge \\alpha)$ \n\n$(\\alpha \\vee \\beta) \\equiv (\\beta \\vee \\alpha)$ \n\n$((\\alpha \\wedge \\beta) \\wedge \\gamma) \\equiv (\\alpha \\wedge (\\beta \\wedge \\gamma))$ \n\n$((\\alpha \\vee \\beta) \\vee \\gamma) \\equiv (\\alpha \\vee (\\beta \\vee \\gamma))$ \n\n$\\neg(\\neg \\alpha) \\equiv \\alpha$ \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg\\beta \\Rightarrow \\neg\\alpha)$ \n\n$(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n$(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n$\\neg(\\alpha \\wedge \\beta) \\equiv (\\neg\\alpha \\vee \\neg \\beta)$ (De Morgan)\n\n$\\neg(\\alpha \\vee \\beta) \\equiv (\\neg\\alpha \\wedge \\neg \\beta)$ (De Morgan)\n\n$(\\alpha \\wedge (\\beta \\vee \\gamma)) \\equiv ((\\alpha \\wedge \\beta) \\vee ( \\alpha \\wedge \\gamma))$ \n\n$(\\alpha \\vee (\\beta \\wedge \\gamma)) \\equiv ((\\alpha \\vee \\beta) \\wedge ( \\alpha \\vee \\gamma))$ \n\nINITIAL STATE: the initial knowledge base.\n\nACTIONS: the set of actions consists of all the inference rules applied to all the\nsentences that match the top half of the inference rule.\n\nRESULT: the result of an action is to add the sentence in the bottom half of the\ninference rule.\n\nGOAL: the goal is a state that contains the sentence we are trying to prove.\n\n\n\nFor any sentences $P$ and $Q$, $P \\models Q$ if and only if $P \\Rightarrow Q$ is valid. \n\nInference rules: \n\n$\\frac{\\alpha \\Rightarrow \\beta, \\alpha}{\\beta}$ \n\n$\\frac{\\alpha \\wedge \\beta}{\\beta}$ \n\nAll logical equivalences can be used as inference rules. \n\nLogical systems is monotonicity, the set of entailed sentences can only increase as information is added to the knowledge base. \n\nIf $KB \\models \\alpha$ then $KB \\wedge \\beta \\models \\alpha$ \n\nResolution: $\\frac{(P_1 \\vee \\cdots \\vee P_k) \\wedge \\neg P_i}{P_1 \\vee \\cdots \\vee P_{i-1} \\vee P_{i+1} \\vee \\cdots \\vee P_k}$ \n\nThe resolution algorithm is complete.\n\nForward Chaining Algorithm：\n\nForward chaining is a method of reasoning in artificial intelligence in which inference rules are applied to existing data \nto extract additional data until an endpoint (goal) is achieved.\nIn this type of chaining, the inference engine starts by evaluating existing facts, derivations, and \nconditions before deducing new information. An endpoint (goal) is achieved through the manipulation of knowledge that exists in the knowledge base.\n\nForward chaining is complete and sound. \n\nDeciding entailment with Horn clauses can be done in time that is linear in the size of knowledge base. \n\nBackward chaining is goal-directed reasoning.\n\n\n## Module 7 Lecture Notes\n\nConstruct CNF: \n\n1. Eliminate $\\Leftrightarrow$ by $(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n2. Eliminate $\\Rightarrow$ by $(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n3. Move $\\neg$ inwards (only before literals) by De Morgan and double-negation. \n\n4. Distribute $\\vee$ over $\\wedge$ wherever possible. \n\nResolution Algorithm: \n\nTo show $KB \\models \\alpha$, we can show that $KB \\wedge \\neg\\alpha$ is unsatisfiable. \n\n1. Convert $KB \\wedge \\neg\\alpha$ into CNF\n2. Repeat resolution for each pairs of disjunctions until one of two things happens:\na) There are no new clauses that can be added. In this case, the KB does not entail $\\alpha$\nb) Two clauses resolve to yield the empty clause (comes from contradiction), in which case the KB does entail $\\alpha$\nResolution is sound and complete. \n\n\n\n## Module 7 Definitions\n* **Soundness** - the inference algorithm should only derive entailed sentences\n* **Completeness** - An inference algorithm is complete if it can derive all sentences that are entailed.\n* **Validity** - A sentence is valid if it is true in all models. For example, $P \\vee \\neg P$ is valid.\n* **Satisfiability** - A sentence is satisfiable if it is true in, orsatisfied by some models (assignment).\n* **Cnf (conjunctive normal form)** - Every sentence of propositional logic is logically equivalent to a conjunction of clauses which are disjunctions of literals.\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at most one is positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}