{
  "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/",
          "height": 0
        },
        "outputId": "818386e5-cb09-4489-e6bc-f73a7acddd1d"
      },
      "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": 32,
      "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/",
          "height": 0
        },
        "outputId": "5f790167-eec9-4312-a4c6-a46aa5e0e7b0"
      },
      "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": 33,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 34,
      "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",
        "4 combinations of AI: human vs. rational; thought vs. behavior\n",
        "  -\tHuman: involving observations/hypotheses abt actual human behavior and thought processes\n",
        "    -\tTuring test: (Alan Turing 1950) designed as a thought experiment where a human would not be able to tell if computer generated responses were from a human or a computer and contain the following capabilities:\n",
        "      -\tNatural language processing: to communicate in a human language\n",
        "      -\tKnowledge representation: to store what it knows and hears\n",
        "      -\tAutomated reasoning: to answer questions and draw conclusions\n",
        "      -\tMachine learning: to adapt to new circumstances and detect patterns\n",
        "    -\tTotal Turing test: require intereaction with objects and people where the robot needs:\n",
        "      -\tComputer vision and speech recognition: to perceive the world\n",
        "      -\tRobotics: to manipulate objects and move around\n",
        "  -\tRationalist: comb of math and engineering and connects to STAT, control theory, and econ\n",
        "  -\t3 different approaches to AI\n",
        "    -\tCognitive modeling approach: we can learn about human thought in 3 ways: Introspection, psychological experiments, brain imaging\n",
        "      -Cognitive science: brings tgt computer models in AI and experimental techniques from psychology to construct precise and testable theories of the human mind\n",
        "    -\tLaws of thought approach; Logic: the laws of thought governed the operation of the mind\n",
        "      -\tProbability fills the gaps where there are areas where the rules are unknown\n",
        "    -\tRational agent approach (general the most popular bc it is more general than the laws of thought approach, more friendly to scientific development)\n",
        "      -\tAgent: something that acts\n",
        "      -\tRational agent: an agent that acts to achieve best (expected) outcome – not always guaranteed to find optimal solutions\n",
        "  - Value alignment problem: real world conflict between our true preferences and the objective we put into the machine \n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "  -\tWeak AI: machines could act as if they were intelligent\n",
        "  -\tStrong AI: machines actually consciously thinking  “human-level AI”\n",
        "  -\tQualification problem: difficult to capture every appropriate behavior in a set of logical rules\n",
        "  -\tEmbodied cognition approach: claims that cognition need to be examined with/in an environment (including the rest of its body)\n",
        "  -\tAreas where AI did not have complete answers\n",
        "    -\tArgument from disability: “machine can never do X”\n",
        "    -\tMathematical objection: certain math questions are unanswerable by formal systems\n",
        "\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "  -\tChinese room (John Searle 1990): human who only understands English is in a room that contains a rule book written in English. Paper slips with indecipherable symbols are slipped under the doors, and the human uses the book to decipher the symbols and write back. However, since neither the human or the Chinese room has an understanding of Chinese, it is like a computer also has no understanding\n",
        "    -\tBiological naturalism: mental states are high level emergent features that are caused by low-level physical processes in neurons\n",
        "      -\tSearle is a supporter\n",
        "  -\tConsciousness: awareness to the outside world, self, and subjective experience of living\n",
        "  -\tQualia: the technical term for the intrinsic nature of experiences\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "  -\tAgent: anything that can be viewed as perceiving its environment through sensors and acting through actuators\n",
        "  -\tPercept: the content an agent’s sensors are perceiving\n",
        "  -\tPercept sequence: complete history of everything that was perceived\n",
        "  -\tAgent function: describes an agent’s behavior (maps a percept to an action)\n",
        "  -\tAgent program: the thing that implements the agent function\n",
        "\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "  -\tConsequentialism: evaluate an agent’s behavior by its consequences\n",
        "  -\tPerformance measure: evaluates any given sequence of environment states (captures the notion of desirability)\n",
        "  -\tRationality (depends on 4 things) – rational agent: select action that expects to maximize performance measure given percept sequence and built in knowledge\n",
        "    -\tPerformance measure that defines success\n",
        "    -\tAgent’s prior knowledge of environment\n",
        "    -\tActions that agent can perform\n",
        "    -\tAgent’s percept sequence to date\n",
        "  -\tPiori: “geography” of an environment\n",
        "  -\tOmniscience: agent that knows the outcome of its actions (impossible in reality)\n",
        "  -\tPerfection vs. Rationality: perfection = actual while rationality = expected\n",
        "  -\tInformation gathering: doing actions to modify future percepts\n",
        "    -\tExploration: information gathering in an initially unknown environment\n",
        "  -\tAutonomy: extent that an agent relies on prior knowledge rather than percepts and learning processes\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "  -\tTask environment: the “problem” where the rational agents are “solutions”\n",
        "  -\tPEAS: \n",
        "    -\tPerformance measure: what would we want the agent to strive for\n",
        "    -\tEnvironment\n",
        "    -\tActuators: control of things that can change the environment\n",
        "    -\tSensors: things to help learn about the environment\n",
        "  -\tSoftware agent == software robot == softbot\n",
        "  -\tFully observable vs. partially observable:\n",
        "    - Fully observable: agent’s sensors give it access to all relevant & complete environment state\n",
        "    -\tPartially observable: there are noisy/inaccurate sensors or there are missing parts from the sensor data\n",
        "      -\tVacuum with a local dirt sensor\n",
        "      -\tAutomated taxi that can’t see what other drivers are thinking\n",
        "    - Unobservable: no sensors\n",
        "  -\tSingle vs. multi agent:\n",
        "    - Single-agent\n",
        "    - Multi-agent\n",
        "      -\tCompetitive multiagent: chess\n",
        "      -\tPartially cooperative multiagent: taxi-driving environment\n",
        "  -\tDeterministic vs. Nondeterministic:\n",
        "    - Deterministic: next state is completely determined by the surrent state and action executed by agent\n",
        "    - Nondeterministic: anything otherwise\n",
        "      -\tA partially observable environment could “appear”: nondeterministic\n",
        "    - Stochastic: synonym for nondeterministic but more explicitly deals with probabilities (using percentages) while nondeterministic just means without being quantified\n",
        "  -\tEpisodic vs. sequential\n",
        "    - Episodic: agent experience is divided into atomic episodes of one percept and one action\n",
        "    - Sequential: current decision could affect all future decisions \n",
        "  -\tStatic vs. dynamic:\n",
        "    - Static: environment does not change as time passes\n",
        "    - Dynamic: environment can change while agent is deliberating\n",
        "  -\tDiscrete vs. Continuous: (applies to state of environment, way time is handled, and percepts and actions of agent)\n",
        "    - Discrete: finite number of distinct states\n",
        "    - Continuous: infinite and never ending smooth states over time\n",
        "  -\tKnown vs. unknown:\n",
        "    - Known: agents state of knowledge where all the outcomes are given\n",
        "      -\tKnown environments can be partially observable (cards where you can’t see the unturned cards)\n",
        "    - Unknown: agent need to learn how the environment works to make good decisions\n",
        "      -\tUnknown environment can be fully observable (video game where the screen shows entire game state but u don’t know what the buttons do until you try them\n",
        "  -\tHardest case: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown\n",
        "  -\tEnvironment class: environments are often carried out from an environment drawn from an environment class\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "  -\tAgent = architecture + program\n",
        "    - Agent program: implements agent function\n",
        "    - Agent architecture: the computing device that runs the agent program\n",
        "  -\t4 types of agents\n",
        "    - Simple reflex agents: agents that select actions on the bases of current percept (ignoring percept history)\n",
        "      -\tCondition-action rule: if-then rule\n",
        "      -\tInfinite loops are often unavoidable but can be prevented if agent randomizes its actions\n",
        "    - Model-based reflex agents: agent needs to maintain some sort of internal state that depends on percept history and reflects some unobserved aspects of the current state\n",
        "      -\tTransition model: knowledge about what happens if an action is taken “how the world works”\n",
        "      -\tSensor model: information about how the state of the world is reflected in agent’s percepts\n",
        "      -\tModel-based agent: an agent that uses transition and sensor models\n",
        "    - Goal-based agents: agents needs some goal information that describes desirable situations\n",
        "      -\tSubfields of AI devoted to finding action sequences that achieve agent’s goals\n",
        "        -\tSearch\n",
        "        -\tplanning\n",
        "    - Utility-based agents: what state is most useful for the agent\n",
        "      -\tUtility function: internalization of the performance measure\n",
        "      -\tExpected utility: the expected utility agents get from an action\n",
        "      -\tModel free agent: learn what action is best in a situation without learing how the action changes the environment\n",
        "  -\tLearning agents\n",
        "    - Learning element: responsible for making improvements where it uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to do better\n",
        "    - Performance element: responsible for selecting external actions\n",
        "      -\tPerformance standard that provides feedback on agent quality\n",
        "        -\tReward\n",
        "        -\tPenalty\n",
        "    - Problem generator: responsible for suggesting actions that lead to informative experiences\n",
        "  -\tAtomic vs. Factored vs. Structured representation\n",
        "    - Atomic representation: each stat of the world is indivisible\n",
        "    - Factored representation: splits up each state into a fixed set of variables or attributes which can have a value\n",
        "    - Structured representation: objects and their various relationships can be described explicitly\n",
        "    - Axises for representation:\n",
        "      -\tExpressiveness: expressive language is more concise\n",
        "      -\tLocalist representation: one to one mapping between concepts and memory locations\n",
        "      -\tDistributed representation: representation of a concept is spread over many memory locations and each is employed as a representation of multiple different concepts\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 35,
      "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": 3101
        },
        "cellView": "form",
        "outputId": "6005474b-5de0-4cbe-9ff9-49f7ba16d0e4"
      },
      "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": 36,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \n4 combinations of AI: human vs. rational; thought vs. behavior\n  -\tHuman: involving observations/hypotheses abt actual human behavior and thought processes\n    -\tTuring test: (Alan Turing 1950) designed as a thought experiment where a human would not be able to tell if computer generated responses were from a human or a computer and contain the following capabilities:\n      -\tNatural language processing: to communicate in a human language\n      -\tKnowledge representation: to store what it knows and hears\n      -\tAutomated reasoning: to answer questions and draw conclusions\n      -\tMachine learning: to adapt to new circumstances and detect patterns\n    -\tTotal Turing test: require intereaction with objects and people where the robot needs:\n      -\tComputer vision and speech recognition: to perceive the world\n      -\tRobotics: to manipulate objects and move around\n  -\tRationalist: comb of math and engineering and connects to STAT, control theory, and econ\n  -\t3 different approaches to AI\n    -\tCognitive modeling approach: we can learn about human thought in 3 ways: Introspection, psychological experiments, brain imaging\n      -Cognitive science: brings tgt computer models in AI and experimental techniques from psychology to construct precise and testable theories of the human mind\n    -\tLaws of thought approach; Logic: the laws of thought governed the operation of the mind\n      -\tProbability fills the gaps where there are areas where the rules are unknown\n    -\tRational agent approach (general the most popular bc it is more general than the laws of thought approach, more friendly to scientific development)\n      -\tAgent: something that acts\n      -\tRational agent: an agent that acts to achieve best (expected) outcome – not always guaranteed to find optimal solutions\n  - Value alignment problem: real world conflict between our true preferences and the objective we put into the machine \n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n  -\tWeak AI: machines could act as if they were intelligent\n  -\tStrong AI: machines actually consciously thinking  “human-level AI”\n  -\tQualification problem: difficult to capture every appropriate behavior in a set of logical rules\n  -\tEmbodied cognition approach: claims that cognition need to be examined with/in an environment (including the rest of its body)\n  -\tAreas where AI did not have complete answers\n    -\tArgument from disability: “machine can never do X”\n    -\tMathematical objection: certain math questions are unanswerable by formal systems\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n  -\tChinese room (John Searle 1990): human who only understands English is in a room that contains a rule book written in English. Paper slips with indecipherable symbols are slipped under the doors, and the human uses the book to decipher the symbols and write back. However, since neither the human or the Chinese room has an understanding of Chinese, it is like a computer also has no understanding\n    -\tBiological naturalism: mental states are high level emergent features that are caused by low-level physical processes in neurons\n      -\tSearle is a supporter\n  -\tConsciousness: awareness to the outside world, self, and subjective experience of living\n  -\tQualia: the technical term for the intrinsic nature of experiences\n\n\n## AIMA 2.1 Agents and Environments\n\n  -\tAgent: anything that can be viewed as perceiving its environment through sensors and acting through actuators\n  -\tPercept: the content an agent’s sensors are perceiving\n  -\tPercept sequence: complete history of everything that was perceived\n  -\tAgent function: describes an agent’s behavior (maps a percept to an action)\n  -\tAgent program: the thing that implements the agent function\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n  -\tConsequentialism: evaluate an agent’s behavior by its consequences\n  -\tPerformance measure: evaluates any given sequence of environment states (captures the notion of desirability)\n  -\tRationality (depends on 4 things) – rational agent: select action that expects to maximize performance measure given percept sequence and built in knowledge\n    -\tPerformance measure that defines success\n    -\tAgent’s prior knowledge of environment\n    -\tActions that agent can perform\n    -\tAgent’s percept sequence to date\n  -\tPiori: “geography” of an environment\n  -\tOmniscience: agent that knows the outcome of its actions (impossible in reality)\n  -\tPerfection vs. Rationality: perfection = actual while rationality = expected\n  -\tInformation gathering: doing actions to modify future percepts\n    -\tExploration: information gathering in an initially unknown environment\n  -\tAutonomy: extent that an agent relies on prior knowledge rather than percepts and learning processes\n\n\n## AIMA 2.3 The Nature of Environments\n\n  -\tTask environment: the “problem” where the rational agents are “solutions”\n  -\tPEAS: \n    -\tPerformance measure: what would we want the agent to strive for\n    -\tEnvironment\n    -\tActuators: control of things that can change the environment\n    -\tSensors: things to help learn about the environment\n  -\tSoftware agent == software robot == softbot\n  -\tFully observable vs. partially observable:\n    - Fully observable: agent’s sensors give it access to all relevant & complete environment state\n    -\tPartially observable: there are noisy/inaccurate sensors or there are missing parts from the sensor data\n      -\tVacuum with a local dirt sensor\n      -\tAutomated taxi that can’t see what other drivers are thinking\n    - Unobservable: no sensors\n  -\tSingle vs. multi agent:\n    - Single-agent\n    - Multi-agent\n      -\tCompetitive multiagent: chess\n      -\tPartially cooperative multiagent: taxi-driving environment\n  -\tDeterministic vs. Nondeterministic:\n    - Deterministic: next state is completely determined by the surrent state and action executed by agent\n    - Nondeterministic: anything otherwise\n      -\tA partially observable environment could “appear”: nondeterministic\n    - Stochastic: synonym for nondeterministic but more explicitly deals with probabilities (using percentages) while nondeterministic just means without being quantified\n  -\tEpisodic vs. sequential\n    - Episodic: agent experience is divided into atomic episodes of one percept and one action\n    - Sequential: current decision could affect all future decisions \n  -\tStatic vs. dynamic:\n    - Static: environment does not change as time passes\n    - Dynamic: environment can change while agent is deliberating\n  -\tDiscrete vs. Continuous: (applies to state of environment, way time is handled, and percepts and actions of agent)\n    - Discrete: finite number of distinct states\n    - Continuous: infinite and never ending smooth states over time\n  -\tKnown vs. unknown:\n    - Known: agents state of knowledge where all the outcomes are given\n      -\tKnown environments can be partially observable (cards where you can’t see the unturned cards)\n    - Unknown: agent need to learn how the environment works to make good decisions\n      -\tUnknown environment can be fully observable (video game where the screen shows entire game state but u don’t know what the buttons do until you try them\n  -\tHardest case: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown\n  -\tEnvironment class: environments are often carried out from an environment drawn from an environment class\n\n\n## AIMA 2.4 The Structure of Agents\n\n  -\tAgent = architecture + program\n    - Agent program: implements agent function\n    - Agent architecture: the computing device that runs the agent program\n  -\t4 types of agents\n    - Simple reflex agents: agents that select actions on the bases of current percept (ignoring percept history)\n      -\tCondition-action rule: if-then rule\n      -\tInfinite loops are often unavoidable but can be prevented if agent randomizes its actions\n    - Model-based reflex agents: agent needs to maintain some sort of internal state that depends on percept history and reflects some unobserved aspects of the current state\n      -\tTransition model: knowledge about what happens if an action is taken “how the world works”\n      -\tSensor model: information about how the state of the world is reflected in agent’s percepts\n      -\tModel-based agent: an agent that uses transition and sensor models\n    - Goal-based agents: agents needs some goal information that describes desirable situations\n      -\tSubfields of AI devoted to finding action sequences that achieve agent’s goals\n        -\tSearch\n        -\tplanning\n    - Utility-based agents: what state is most useful for the agent\n      -\tUtility function: internalization of the performance measure\n      -\tExpected utility: the expected utility agents get from an action\n      -\tModel free agent: learn what action is best in a situation without learing how the action changes the environment\n  -\tLearning agents\n    - Learning element: responsible for making improvements where it uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to do better\n    - Performance element: responsible for selecting external actions\n      -\tPerformance standard that provides feedback on agent quality\n        -\tReward\n        -\tPenalty\n    - Problem generator: responsible for suggesting actions that lead to informative experiences\n  -\tAtomic vs. Factored vs. Structured representation\n    - Atomic representation: each stat of the world is indivisible\n    - Factored representation: splits up each state into a fixed set of variables or attributes which can have a value\n    - Structured representation: objects and their various relationships can be described explicitly\n    - Axises for representation:\n      -\tExpressiveness: expressive language is more concise\n      -\tLocalist representation: one to one mapping between concepts and memory locations\n      -\tDistributed representation: representation of a concept is spread over many memory locations and each is employed as a representation of multiple different concepts\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "  - Python uses dynamic scope: see most current variable value\n",
        "  - References and Mutability\n",
        "    - strings are immutable\n",
        "    - == checks if variable point to objects of same value\n",
        "    - is checks if variables point to same object\n",
        "    - lists are mutable\n",
        "    - use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value\n",
        "  - Sequence Types\n",
        "    - tuple: immutable, ordered seq of items; mixed type (include collection types)\n",
        "      - tu = (23, 'ab', 4.6, (2,3), 'def')\n",
        "    - string: immutable (unicode and use 2byte char -- python 1 uses 8-bit char)\n",
        "      - operations\n",
        "        - s.split(\" \") -> ['Pretend', 'this', 'sentence']\n",
        "        - \"_\".join(words) -> 'Pretend_this_sentence'\n",
        "        - s.caplitaize()\n",
        "        - s.upper()\n",
        "        - \"hi--\".strip('--')\n",
        "    - list: mutable, ordered seq of item; mixed type\n",
        "      - li = ['abc', 34, 4.34]\n",
        "      - operations: \n",
        "        - li.append()\n",
        "        - li.insert(2,\"\")\n",
        "        - li.index(1st occur)\n",
        "        - li.count()\n",
        "        - li.remove(1st occur)\n",
        "        - li.reverse() - reverse in place(modify)\n",
        "        - li.sort() or li.sort(some_function)\n",
        "        - sorted(li) - return a copy sorted\n",
        "  - Slicing\n",
        "    - t[1:4] #slicing ends before last index ('ab', 4.6, (2,3))\n",
        "    - t[1:-1] #using negative index ('ab', 4.6, (2,3))\n",
        "    - t[1:-1:2] # selection of every nth item. ('ab', (2,3))\n",
        "    - t[:2] # copy from beginning of sequence (23, 'ab')\n",
        "    - t[2:] # copy to the very end of the sequence (4.6, (2,3), 'def')\n",
        "  - Dict: unordered, work by hashing, so keys are immutable\n",
        "    - operations\n",
        "      - d[key] - return value\n",
        "      - d[value] - KeyError\n",
        "      - d[key] = xxx - replaces value\n",
        "      - d.keys(), d.values(), d.items() - list of item tuple\n",
        "  - Functions\n",
        "    - can return multiple values as tuple, java (have to design object to return multiple values)\n",
        "    - python: no function overloading like java bc function specified by only name\n",
        "      - 2 functions can't have same name even if diff number, order, or arguments\n",
        "      - operator overloading can happening using special methods in class\n",
        "    - first-class object: functions can be...\n",
        "      - pass functions as arguments other functions\n",
        "      - return functions as values from other furnctions\n",
        "      - assign functions to variables/store in data structure\n",
        "    - List comprehension\n",
        "      - squares = [x*x for x in range(0,4)] = [0, 1, 4, 9]\n",
        "      - iterate thru list of tuples = [n*3 for (x, n) in list]\n",
        "      - list of values from 1 to 100 = [x for x in range(1, 101)]\n",
        "      - filter list = [x*2 for x in list if x >4]\n",
        "    - Set comprehension\n",
        "      - d = {k: v for k, v, in list} - list of tuples\n",
        "      - s = {x for x in list}\n",
        "    - search in a directed graph\n",
        "      - d = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n",
        "        - [v for v in d.search(1, set())] --> [1, 2, 4, 3]\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"*args\" : \"accept a variable number of non-keyword arguments to the function\",\n",
        "\"*kwargs\" : \"accept a variable number of keyword arguments to the function\",\n",
        "\"higher order functions\" : \"take functions as input\",\n",
        "}"
      ],
      "execution_count": 37,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1408
        },
        "outputId": "f1d6450d-40f6-49f6-8fd7-2e960903363f"
      },
      "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": 38,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\n  - Python uses dynamic scope: see most current variable value\n  - References and Mutability\n    - strings are immutable\n    - == checks if variable point to objects of same value\n    - is checks if variables point to same object\n    - lists are mutable\n    - use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value\n  - Sequence Types\n    - tuple: immutable, ordered seq of items; mixed type (include collection types)\n      - tu = (23, 'ab', 4.6, (2,3), 'def')\n    - string: immutable (unicode and use 2byte char -- python 1 uses 8-bit char)\n      - operations\n        - s.split(\" \") -> ['Pretend', 'this', 'sentence']\n        - \"_\".join(words) -> 'Pretend_this_sentence'\n        - s.caplitaize()\n        - s.upper()\n        - \"hi--\".strip('--')\n    - list: mutable, ordered seq of item; mixed type\n      - li = ['abc', 34, 4.34]\n      - operations: \n        - li.append()\n        - li.insert(2,\"\")\n        - li.index(1st occur)\n        - li.count()\n        - li.remove(1st occur)\n        - li.reverse() - reverse in place(modify)\n        - li.sort() or li.sort(some_function)\n        - sorted(li) - return a copy sorted\n  - Slicing\n    - t[1:4] #slicing ends before last index ('ab', 4.6, (2,3))\n    - t[1:-1] #using negative index ('ab', 4.6, (2,3))\n    - t[1:-1:2] # selection of every nth item. ('ab', (2,3))\n    - t[:2] # copy from beginning of sequence (23, 'ab')\n    - t[2:] # copy to the very end of the sequence (4.6, (2,3), 'def')\n  - Dict: unordered, work by hashing, so keys are immutable\n    - operations\n      - d[key] - return value\n      - d[value] - KeyError\n      - d[key] = xxx - replaces value\n      - d.keys(), d.values(), d.items() - list of item tuple\n  - Functions\n    - can return multiple values as tuple, java (have to design object to return multiple values)\n    - python: no function overloading like java bc function specified by only name\n      - 2 functions can't have same name even if diff number, order, or arguments\n      - operator overloading can happening using special methods in class\n    - first-class object: functions can be...\n      - pass functions as arguments other functions\n      - return functions as values from other furnctions\n      - assign functions to variables/store in data structure\n    - List comprehension\n      - squares = [x*x for x in range(0,4)] = [0, 1, 4, 9]\n      - iterate thru list of tuples = [n*3 for (x, n) in list]\n      - list of values from 1 to 100 = [x for x in range(1, 101)]\n      - filter list = [x*2 for x in list if x >4]\n    - Set comprehension\n      - d = {k: v for k, v, in list} - list of tuples\n      - s = {x for x in list}\n    - search in a directed graph\n      - d = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n        - [v for v in d.search(1, set())] --> [1, 2, 4, 3]\n\n\n## Module 2 Definitions\n* ***args** - accept a variable number of non-keyword arguments to the function\n* ***kwargs** - accept a variable number of keyword arguments to the function\n* **Higher order functions** - take functions as input\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "  -\tProblem-solving agent: agent who take a sequence of actions in a path to a goal state\n",
        "    -\tSearch: the process the agent undertakes\n",
        "    -\tSearch problem: \n",
        "      -\tState space: a set of possible states that the environment can be in (can be infinite)\n",
        "        -\tGraph: state space where vertices = states and directed edges = actions\n",
        "      -\tInitial state\n",
        "      -\tGoal state: sometimes there is one, sometimes there are multiple, or infinite – can be defined by a property that applies to many states (i.e. no dirt in a vacuum cleaner world)\n",
        "      -\tActions: moves an agent can take – usually a finite set of actions(s)\n",
        "      -\tTransition model: describes what each action does; result(s,a) returns the state that results from doing action an in state s\n",
        "      -\tAction cost function: provides the numeric cost of apply action a in state s to reach state s’\n",
        "      -\tSolution: a path (sequence of actions) from the initial to goal state\n",
        "        -\tOptimal solution: lowest path cost among all solutions\n",
        "    -\tIf environment is unknown, agent must execute action at random\n",
        "  -\tRepresentations of states: \n",
        "    -\tProblem-solving agents use atomic representations: states of the world are whole (no internal structure is visible to the problem-solving algorithms)\n",
        "    -\tPlanning agents use factored/structured representations of states\n",
        "      -\tAbstraction: process of removing detail as possible form a representation while retaining validity and ensuring the abstract actions are easy to carry out\n",
        "        -\tLevel of abstraction depends of the detailed world states and detailed action sequences\n",
        "    -\tValid: if can elaborate any abstract solution into a solution in the detailed world\n",
        "    -\tUseful: if carrying out each of the actions in the solution is easier than the original problem (no further search of planning needed)\n",
        "  -\tInformed vs. uninformed algorithms:\n",
        "    -\tInformed: agent can estimate how far it is from goal\n",
        "    -\tUninformed: no estimate is available\n",
        "  -\t4 phase problem solving process:\n",
        "    -\tGoal formulation: limit objectives and actions to be considered\n",
        "    -\tProblem formulation: agent devises description of states and actions necessary to reach a goal\n",
        "    -\tSearch: agent simulates and searches sequence of actions that reaches the goal  solution\n",
        "    -\tExecution: agent will execute actions in the solution, one at a time\n",
        "  -\tOpen-loop vs. closed-loop system:\n",
        "    -\tOpen-loop system: ignoring percepts as it follows the solution path (ignoring percepts breaks the loop between agent and environment)\n",
        "    - Closed-loop system: safer when model is incorrect, or environment is nondeterministic – this monitors percepts\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "-\tStandardized vs. real-world problems:\n",
        "  -\tStandardized problem: illustrate various problem solving methods bc it can be given as a concise, exact description so researches can use it as a benchmark to compare the performance of algorithms\n",
        "    -\tGrid vs. vacuum world:\n",
        "      -\tGrid world: 2D rectangular array of square cells where the agent can move form cell to cell; cells can contain objects that the agent can pick up, push, or act upon, walls prevent agents from moving into that cell (pg157)\n",
        "  -\tSokoban puzzle: agent’s goal is to push boxes to designated storage locations\n",
        "  -\tSliding-tile puzzle: rush hour, 8, and 15 puzzle\n",
        "      -\tVacuum world: grid world problem with dirty cells (with n cells has n*2^n states)\n",
        "  -\tReal-world problem: (robot navigation) is idiosyncratic, not standardized because each robot has different sensors that produce different data\n",
        "    -\tRoute-finding problem\n",
        "      -\tRobot navigation: generalization of the route-finding problem – instead of following distinct routes, the robot can make its own path\n",
        "    -\tTouring problem: set of locations that must be visited\n",
        "      -\tTraveling salesperson problem (TSP): touring problem in which every city on a map must be visited\n",
        "    -\tVLSI layout problem: position millions of components and connections on a chip to minimize area, circuit delays, stray capacitances, and maximize manufacturing yield (split into two parts below)\n",
        "      -\tCell layout: primitive components of circuit are grouped into cells, each which performs some recognized function\n",
        "      -\tChanneling routing: finds specific route for each wire thorugh gaps between the cells\n",
        "    -\tAutomatic assembly sequencing of complex objects: algorithms find a feasible assembly sequence then work to optimize the process\n",
        "      -\tProtein design: the goal is to find a sequence of amino acids that will fold into 3-D protein with the right properties to cure some disease\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "  -\tSearch algorithm: input = search problem and output = solution, or indication of failure\n",
        "    -\tSearch tree: describes paths between different states; unique path back to the root\n",
        "      -\tNode: is a state in the state space\n",
        "      -\tExpand: considering the available actions for that state\n",
        "      -\tChild/successor node: generate a new node for each of the resulting states\n",
        "      -\tFrontier: the result of the latest node expansion\n",
        "          - Separates two regions of the state-space graph: \n",
        "            1) interior regions where every state has been expanded\n",
        "            2) exterior region of states that have not yet been reached\n",
        "    -\tQueue is the data structure that stores the frontier; possible operations include:\n",
        "      -\tIs-Empty(frontier): returns true only if there are no nodes in the frontier\n",
        "      -\tPop(frontier): removes the top node form the frontier and returns it\n",
        "      -\tTop(frontier): returns (but doesn’t remove) the top node of the frontier\n",
        "      -\tAdd(node, frontier): inserts node into proper place in the queue\n",
        "        -\tReached: any state that has had a node generated for it is reached\n",
        "        -\tRepeated state: caused by a cycle/loopy path – means the complete search is infinite\n",
        "    -\tCycle = special case of a redundant path\n",
        "      -\tA tree node: is represented by a data structure with 4 components\n",
        "        -\tNode.state: state the node corresponds to\n",
        "        -\tNode.parent: node in the tree that generated this node\n",
        "        -\tNode.action: action that was applied to the parent’s state to generate this node\n",
        "        -\tNode.path-cost: total cost of the path from initial state to this node\n",
        "  -\tProblem solving performance:\n",
        "    -\tCompleteness: is the algorithm guaranteed to find a solution or failure -- to be complete, the algorithm must by systematic\n",
        "    -\tCost optimality/admissibility: does it find a solution with the lowest path cost of all solutions\n",
        "    -\tComplexity:\n",
        "      -\tTime complexity: how long to find a solution\n",
        "      -\tSpace complexity: how much memory to perform search\n",
        "      -\tComplexity can be measured using\n",
        "        -\tDepth: number of actions in the optimal solution\n",
        "        -\tMaximum number of actions in any path\n",
        "        -\tBranching factor: number of successors of a node\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "  -\tExponential complexity search problems usually need informed search\n",
        "  -\tBreadth-first search: root node expanded first, then successors of the root node expanded, then their successors, etc. \n",
        "    -\tCan implement best first search where the evaluation function f(n) is the depth of the node – the number of actions it takes to reach the node\n",
        "    -\tSystematic, complete even on infinite state spaces, optimal for problems where all the actions have the same cost\n",
        "    -\tPossible efficiency improvements:\n",
        "      -\tEarly goal test: check node is a solution when generated\n",
        "      -\tLate goal test (best-first search): check if a solution after popped off the queue\n",
        "  -\tUniform-cost search (Dijkstra): spreads out in waves of uniform path-cost\n",
        "    -\tImplemented as a call to best-first search with path-cost as the evaluation function\n",
        "    -\tSystematic, complete, and cost-optimal, will not get stuck in a loop (infinite path)\n",
        "    -\twhen all action costs are equal,  and is like breadth-first search\n",
        "  -\tDepth-first search: expands the deepest node in the frontier first \n",
        "    -\tPreferred for problems where tree-like search is feasible bc has much smaller memory needs\n",
        "      -\tNo reached table\n",
        "      -\tFrontier very small (radius of sphere) vs. breadth-first search frontier (filled in sphere)\n",
        "    -\tImplemented as a call to best-first search where evaluation function f(n) is the negative of the depth, usually a tree-like search that does not keep a table of reached states\n",
        "    -\tSearch to the deepest level of the tree (where there are no successors), then search “backs up” to the next deepest node with unexpanded successors\n",
        "    -\tComplete (for finite state spaces); not cost-optimal (returns first solution it finds)\n",
        "      -\tIncomplete when:\n",
        "        -\tacyclic state spaces, end up expanding the same state many times via different paths but will eventually systematically explore the entire space\n",
        "        -\tcyclic state space, can get stuck in infinite loop\n",
        "        -\tinfinite state spaces – depth first search is not systematic (can get stuck going down infinite paths even if there are no cycles)\n",
        "  -\tBacktracking search (variant of depth-first search uses less memory): \n",
        "    -\tOne successor is generated at a time rather than all successors and each partially expanded node remembers which successor to generate next\n",
        "    -\tSuccessors are generated by modifying current state description instead of allocating memory for a new state\n",
        "      -\tResults in one state description\n",
        "    -\tCan maintain an efficient set data structure\n",
        "    -\tMust be able to undo each action when we backtrack\n",
        "    -\tGood for problems with large state descriptions (robotic assembly)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "Section 3_3\n",
        "  -\tGraph vs. tree search\n",
        "    -\tGraph search: checks for redundant paths, more memory, faster bc checks for redundant paths\n",
        "    -\tTree-like search: does not check for redundant paths, less memory and slower bc doesn’t check for redundant paths\n",
        "  -\t3 types of queues used in search algorithms:\n",
        "    -\tPropriety queue: pops the node with minimum cost (Best-first search)\n",
        "    -\tFIFO queue: pops the node that was added to the queue first (Breadth-first search)\n",
        "    -\tLIFO queue: pops the most recently added node (Depth-first search)\n",
        "\n",
        "  -\tBest-first search: choose node n, with minimum value of some evaluation function f(n)\n",
        "    - on each iteration, we choose a node on the frontier with minimum f(n) value\n",
        "    - return it is the state is a goal state, otherwise apply expand to generate child nodes\n",
        "    - each child node is added to frontier if not reached before or re-added if it is now being reached with path of lower path cost than any previous path\n",
        "    - finally algorithm returns either failure or a node that represents a path to the goal\n",
        "\n",
        "section 3_4\n",
        "  -\tDepth-limited search: prevents depth-first from going down an infinite path by using depth limit, l, and treat all nodes at depth l as if they had no successors\n",
        "    -\tIf we choose a bad l, it will fail to reach the solution so it is incomplete\n",
        "    -\tDiameter of the state space: a depth limit that leads to a more efficient depth-limited search, but most of the time, we will not know a good depth limit until we have solved the problem\n",
        "  -\tIterative deepening search:\n",
        "    -\tSolves problem of picking a good l value by trying all values until 1) a solution is found or 2) depth limited search returns the failure value instead of a cutoff value\n",
        "    -\tOptimal for when all actions have the same cost; complete on finite acyclic state spaces or finite state when we check nodes for cycles all the way up the path\n",
        "    -\tIterative deepening repeats all the previous level – saves memory at the cost of more time compared to breadth-first search that stores all the nodes in memory\n",
        "    -\tGenerally iterative deepening preferred when:\n",
        "      -\tthe search state space is larger than can fit in memory\n",
        "      -\tdepth of the solution unknown\n",
        "  -\tBidirectional search: simultaneously searches forward from initial state and backwards form the goal state because  is much less than \n",
        "    -\tSolution = when frontiers collide\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 39,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3162
        },
        "outputId": "a93fb835-dca1-4492-ffd1-774b5534fba2"
      },
      "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": 40,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n  -\tProblem-solving agent: agent who take a sequence of actions in a path to a goal state\n    -\tSearch: the process the agent undertakes\n    -\tSearch problem: \n      -\tState space: a set of possible states that the environment can be in (can be infinite)\n        -\tGraph: state space where vertices = states and directed edges = actions\n      -\tInitial state\n      -\tGoal state: sometimes there is one, sometimes there are multiple, or infinite – can be defined by a property that applies to many states (i.e. no dirt in a vacuum cleaner world)\n      -\tActions: moves an agent can take – usually a finite set of actions(s)\n      -\tTransition model: describes what each action does; result(s,a) returns the state that results from doing action an in state s\n      -\tAction cost function: provides the numeric cost of apply action a in state s to reach state s’\n      -\tSolution: a path (sequence of actions) from the initial to goal state\n        -\tOptimal solution: lowest path cost among all solutions\n    -\tIf environment is unknown, agent must execute action at random\n  -\tRepresentations of states: \n    -\tProblem-solving agents use atomic representations: states of the world are whole (no internal structure is visible to the problem-solving algorithms)\n    -\tPlanning agents use factored/structured representations of states\n      -\tAbstraction: process of removing detail as possible form a representation while retaining validity and ensuring the abstract actions are easy to carry out\n        -\tLevel of abstraction depends of the detailed world states and detailed action sequences\n    -\tValid: if can elaborate any abstract solution into a solution in the detailed world\n    -\tUseful: if carrying out each of the actions in the solution is easier than the original problem (no further search of planning needed)\n  -\tInformed vs. uninformed algorithms:\n    -\tInformed: agent can estimate how far it is from goal\n    -\tUninformed: no estimate is available\n  -\t4 phase problem solving process:\n    -\tGoal formulation: limit objectives and actions to be considered\n    -\tProblem formulation: agent devises description of states and actions necessary to reach a goal\n    -\tSearch: agent simulates and searches sequence of actions that reaches the goal  solution\n    -\tExecution: agent will execute actions in the solution, one at a time\n  -\tOpen-loop vs. closed-loop system:\n    -\tOpen-loop system: ignoring percepts as it follows the solution path (ignoring percepts breaks the loop between agent and environment)\n    - Closed-loop system: safer when model is incorrect, or environment is nondeterministic – this monitors percepts\n\n\n## AIMA Chapter 3.2 Example Problems\n\n-\tStandardized vs. real-world problems:\n  -\tStandardized problem: illustrate various problem solving methods bc it can be given as a concise, exact description so researches can use it as a benchmark to compare the performance of algorithms\n    -\tGrid vs. vacuum world:\n      -\tGrid world: 2D rectangular array of square cells where the agent can move form cell to cell; cells can contain objects that the agent can pick up, push, or act upon, walls prevent agents from moving into that cell (pg157)\n  -\tSokoban puzzle: agent’s goal is to push boxes to designated storage locations\n  -\tSliding-tile puzzle: rush hour, 8, and 15 puzzle\n      -\tVacuum world: grid world problem with dirty cells (with n cells has n*2^n states)\n  -\tReal-world problem: (robot navigation) is idiosyncratic, not standardized because each robot has different sensors that produce different data\n    -\tRoute-finding problem\n      -\tRobot navigation: generalization of the route-finding problem – instead of following distinct routes, the robot can make its own path\n    -\tTouring problem: set of locations that must be visited\n      -\tTraveling salesperson problem (TSP): touring problem in which every city on a map must be visited\n    -\tVLSI layout problem: position millions of components and connections on a chip to minimize area, circuit delays, stray capacitances, and maximize manufacturing yield (split into two parts below)\n      -\tCell layout: primitive components of circuit are grouped into cells, each which performs some recognized function\n      -\tChanneling routing: finds specific route for each wire thorugh gaps between the cells\n    -\tAutomatic assembly sequencing of complex objects: algorithms find a feasible assembly sequence then work to optimize the process\n      -\tProtein design: the goal is to find a sequence of amino acids that will fold into 3-D protein with the right properties to cure some disease\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n  -\tSearch algorithm: input = search problem and output = solution, or indication of failure\n    -\tSearch tree: describes paths between different states; unique path back to the root\n      -\tNode: is a state in the state space\n      -\tExpand: considering the available actions for that state\n      -\tChild/successor node: generate a new node for each of the resulting states\n      -\tFrontier: the result of the latest node expansion\n          - Separates two regions of the state-space graph: \n            1) interior regions where every state has been expanded\n            2) exterior region of states that have not yet been reached\n    -\tQueue is the data structure that stores the frontier; possible operations include:\n      -\tIs-Empty(frontier): returns true only if there are no nodes in the frontier\n      -\tPop(frontier): removes the top node form the frontier and returns it\n      -\tTop(frontier): returns (but doesn’t remove) the top node of the frontier\n      -\tAdd(node, frontier): inserts node into proper place in the queue\n        -\tReached: any state that has had a node generated for it is reached\n        -\tRepeated state: caused by a cycle/loopy path – means the complete search is infinite\n    -\tCycle = special case of a redundant path\n      -\tA tree node: is represented by a data structure with 4 components\n        -\tNode.state: state the node corresponds to\n        -\tNode.parent: node in the tree that generated this node\n        -\tNode.action: action that was applied to the parent’s state to generate this node\n        -\tNode.path-cost: total cost of the path from initial state to this node\n  -\tProblem solving performance:\n    -\tCompleteness: is the algorithm guaranteed to find a solution or failure -- to be complete, the algorithm must by systematic\n    -\tCost optimality/admissibility: does it find a solution with the lowest path cost of all solutions\n    -\tComplexity:\n      -\tTime complexity: how long to find a solution\n      -\tSpace complexity: how much memory to perform search\n      -\tComplexity can be measured using\n        -\tDepth: number of actions in the optimal solution\n        -\tMaximum number of actions in any path\n        -\tBranching factor: number of successors of a node\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n  -\tExponential complexity search problems usually need informed search\n  -\tBreadth-first search: root node expanded first, then successors of the root node expanded, then their successors, etc. \n    -\tCan implement best first search where the evaluation function f(n) is the depth of the node – the number of actions it takes to reach the node\n    -\tSystematic, complete even on infinite state spaces, optimal for problems where all the actions have the same cost\n    -\tPossible efficiency improvements:\n      -\tEarly goal test: check node is a solution when generated\n      -\tLate goal test (best-first search): check if a solution after popped off the queue\n  -\tUniform-cost search (Dijkstra): spreads out in waves of uniform path-cost\n    -\tImplemented as a call to best-first search with path-cost as the evaluation function\n    -\tSystematic, complete, and cost-optimal, will not get stuck in a loop (infinite path)\n    -\twhen all action costs are equal,  and is like breadth-first search\n  -\tDepth-first search: expands the deepest node in the frontier first \n    -\tPreferred for problems where tree-like search is feasible bc has much smaller memory needs\n      -\tNo reached table\n      -\tFrontier very small (radius of sphere) vs. breadth-first search frontier (filled in sphere)\n    -\tImplemented as a call to best-first search where evaluation function f(n) is the negative of the depth, usually a tree-like search that does not keep a table of reached states\n    -\tSearch to the deepest level of the tree (where there are no successors), then search “backs up” to the next deepest node with unexpanded successors\n    -\tComplete (for finite state spaces); not cost-optimal (returns first solution it finds)\n      -\tIncomplete when:\n        -\tacyclic state spaces, end up expanding the same state many times via different paths but will eventually systematically explore the entire space\n        -\tcyclic state space, can get stuck in infinite loop\n        -\tinfinite state spaces – depth first search is not systematic (can get stuck going down infinite paths even if there are no cycles)\n  -\tBacktracking search (variant of depth-first search uses less memory): \n    -\tOne successor is generated at a time rather than all successors and each partially expanded node remembers which successor to generate next\n    -\tSuccessors are generated by modifying current state description instead of allocating memory for a new state\n      -\tResults in one state description\n    -\tCan maintain an efficient set data structure\n    -\tMust be able to undo each action when we backtrack\n    -\tGood for problems with large state descriptions (robotic assembly)\n\n\n## Module 3 Lecture Notes\n\nSection 3_3\n  -\tGraph vs. tree search\n    -\tGraph search: checks for redundant paths, more memory, faster bc checks for redundant paths\n    -\tTree-like search: does not check for redundant paths, less memory and slower bc doesn’t check for redundant paths\n  -\t3 types of queues used in search algorithms:\n    -\tPropriety queue: pops the node with minimum cost (Best-first search)\n    -\tFIFO queue: pops the node that was added to the queue first (Breadth-first search)\n    -\tLIFO queue: pops the most recently added node (Depth-first search)\n\n  -\tBest-first search: choose node n, with minimum value of some evaluation function f(n)\n    - on each iteration, we choose a node on the frontier with minimum f(n) value\n    - return it is the state is a goal state, otherwise apply expand to generate child nodes\n    - each child node is added to frontier if not reached before or re-added if it is now being reached with path of lower path cost than any previous path\n    - finally algorithm returns either failure or a node that represents a path to the goal\n\nsection 3_4\n  -\tDepth-limited search: prevents depth-first from going down an infinite path by using depth limit, l, and treat all nodes at depth l as if they had no successors\n    -\tIf we choose a bad l, it will fail to reach the solution so it is incomplete\n    -\tDiameter of the state space: a depth limit that leads to a more efficient depth-limited search, but most of the time, we will not know a good depth limit until we have solved the problem\n  -\tIterative deepening search:\n    -\tSolves problem of picking a good l value by trying all values until 1) a solution is found or 2) depth limited search returns the failure value instead of a cutoff value\n    -\tOptimal for when all actions have the same cost; complete on finite acyclic state spaces or finite state when we check nodes for cycles all the way up the path\n    -\tIterative deepening repeats all the previous level – saves memory at the cost of more time compared to breadth-first search that stores all the nodes in memory\n    -\tGenerally iterative deepening preferred when:\n      -\tthe search state space is larger than can fit in memory\n      -\tdepth of the solution unknown\n  -\tBidirectional search: simultaneously searches forward from initial state and backwards form the goal state because  is much less than \n    -\tSolution = when frontiers collide\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\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",
        "  -\tInformed search: strategy that uses domain-specific hints; find solutions more efficiently than uninformed\n",
        "    -\tHeuristic function h(n) is the estimated cost of the cheapest path from node n to goal state\n",
        "  -\tGreedy best-first search: form of best-first search that expands the nodes with lowest h(n) value – node that appears the closest to the goal\n",
        "    -\tEvaluation function f(n) = h(n)\n",
        "    -\tComplete in finite state spaces, not in infinite ones\n",
        "  -\tA* search: best-first search that uses 1) path cost from initial state to node n and 2) estimated cost of the shortest path from n to a goal state\n",
        "    -\tcomplete and cost-optimal and optimally efficient depending on the heuristic\n",
        "      -\tadmissible heuristic: never overestimates the cost to reach a goal\n",
        "    -\tnon-cost-optimal: even if there is one cost-optimal path that h(n) is admissible for, solution won’t be found \n",
        "        -\tweighted A* search (detour index): apply heuristic value more heavily by multiplying a number (multiplied applied to straight-line distance to account for road curvature)\n",
        "      -\tconsistent vs. inconsistnet heuristic:\n",
        "        - consistent heuristic:  first time we reach a state it will be on an optimal path, never have to re-add to frontier and never change entry in reached\n",
        "        -\tinconsistent heuristic: end up with multiple paths reaching the same state, end up with multiple node for that state in the frontier – costs time and space\n",
        "        -\tevery consistent heuristic is admissible but not vice versa – A* is cost-optimal thus has consistent heuristic\n",
        "        -\tA* with consistent heuristic is optimally efficient\n",
        "    -\tEfficient bc prunes away search tree nodes that are not necessary\n",
        "  -\tSearch contours: visualize a search by drawing topographic map\n",
        "    -\tUniform-cost search: contours of g-cost that are circular around the state state and spread out equally in all directions\n",
        "    -\tA* search: g+h bands stretch to goal state and become more narrow focus around optimal path\n",
        "  -\tSuboptimal search algorithms\n",
        "    -\tBounded suboptimal search: look for a solution that is guaranteed to be in a constant factor W or the optimal cost\n",
        "    -\tBounded-cost search: looks for solutions whose cost is less than some constant C\n",
        "    -\tUnbounded-cost search: accept a solution of any cost (as long as can quickly find it)\n",
        "      -\tSpeedy search: greedy best-first search version that heuristic is estimated number of actions required to reach a goal, regardless of cost\n",
        "        - same cost actions = greedy best-first search\n",
        "        - diff costs, it finds solution quickly but with high cost\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "  -\tHeuristic functions\n",
        "    -\tCity block distance = Manhattan distance: sum of vertical and horizontal distances\n",
        "    -\tEffective branching factor (b*): characterize the quality of a heuristic\n",
        "      -\tN+1 = 1 + b* + (b*)^2 + …+(b*)^d\n",
        "      -\tEffective depth: can be reduced by a constant  A* pruning with a given heuristic so total cost is  instead of \n",
        "    -\tDominates: a heuristic function dominates another one if it will be more efficient in the search \n",
        "    -\tRelaxed problem: a problem with fewer restriction on action (state space graph of relaxed problem is a supergraph of original state space bc restriction removal creates more edges)\n",
        "      -\tMay provide better solution if added edges have shortcuts\n",
        "      -\tCost of optimal solution in a relaxed prob is admissible h for the original\n",
        "      -\tAbsolver: program that generates heuristics from problem definitions using the “relaxed” problem and other techniques\n",
        "    -\tSubproblem: admissible heuristics can be derived from solution cost of subproblem of larger problem\n",
        "    -\tPattern database: store exact solutions for all possible subproblems, and compute admissible heuristic by looking up the subproblem in the database\n",
        "    -\tDisjoint pattern database: break into two subproblems and add them up\n",
        "  -\tHeuristics with landmarks\n",
        "    -\tPrecomputation: precompute the optimal path costs—only need to be done once\n",
        "      -\tLandmark points: choose a few and precompute the path from vertex v to L\n",
        "        -\tBest to choose ones that are spread out and not too close around the perimeter of the graph (centroid)\n",
        "    -\tShortcuts: artificial edges in the graph that define a optimal multi-action path\n",
        "    -\tDifferential heuristic: landmark that is beyond the goal – goal is on the optimal path from n to landmark then subtract the last part of the path\n",
        "  -\tImproving search\n",
        "    -\tMetalevel state space: each state captures the internal state of a program that is searching in an ordinary state space – each state on path is object-level search tree\n",
        "    -\tObject-level state space: map of Romania\n",
        "    -\tMeta-level learning algorithm: can learn from missteps and avoid exploring unpromising subtrees\n",
        "      -\tLearning goal is to minimize the total cost of solving problem by using more computational expense and path cost\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "Additional textbook stuff\n",
        "  -\tPage 202: Memory-bounded search \n",
        "    -\tSolution is to keep reference counts of the number of times a state has been reached\n",
        "    -\tBeam search: limits frontier size\n",
        "    -\tIterative-deepening A* search\n",
        "    -\tRecursive best-first search\n",
        "      -\tBack-up value\n",
        "    -\tMemory related algorithms\n",
        "      -\tMemory bounded A* (MA*)\n",
        "      -\tSimplified memory bounded A* (SMA*)\n",
        "    -\tBidirectional heuristic search\n",
        "      -\tFront-to-end search\n",
        "      -\tFront-to-front search\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 41,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1567
        },
        "cellView": "form",
        "outputId": "33e862da-34d6-4f9b-b854-a88af812d378"
      },
      "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": 42,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n  -\tInformed search: strategy that uses domain-specific hints; find solutions more efficiently than uninformed\n    -\tHeuristic function h(n) is the estimated cost of the cheapest path from node n to goal state\n  -\tGreedy best-first search: form of best-first search that expands the nodes with lowest h(n) value – node that appears the closest to the goal\n    -\tEvaluation function f(n) = h(n)\n    -\tComplete in finite state spaces, not in infinite ones\n  -\tA* search: best-first search that uses 1) path cost from initial state to node n and 2) estimated cost of the shortest path from n to a goal state\n    -\tcomplete and cost-optimal and optimally efficient depending on the heuristic\n      -\tadmissible heuristic: never overestimates the cost to reach a goal\n    -\tnon-cost-optimal: even if there is one cost-optimal path that h(n) is admissible for, solution won’t be found \n        -\tweighted A* search (detour index): apply heuristic value more heavily by multiplying a number (multiplied applied to straight-line distance to account for road curvature)\n      -\tconsistent vs. inconsistnet heuristic:\n        - consistent heuristic:  first time we reach a state it will be on an optimal path, never have to re-add to frontier and never change entry in reached\n        -\tinconsistent heuristic: end up with multiple paths reaching the same state, end up with multiple node for that state in the frontier – costs time and space\n        -\tevery consistent heuristic is admissible but not vice versa – A* is cost-optimal thus has consistent heuristic\n        -\tA* with consistent heuristic is optimally efficient\n    -\tEfficient bc prunes away search tree nodes that are not necessary\n  -\tSearch contours: visualize a search by drawing topographic map\n    -\tUniform-cost search: contours of g-cost that are circular around the state state and spread out equally in all directions\n    -\tA* search: g+h bands stretch to goal state and become more narrow focus around optimal path\n  -\tSuboptimal search algorithms\n    -\tBounded suboptimal search: look for a solution that is guaranteed to be in a constant factor W or the optimal cost\n    -\tBounded-cost search: looks for solutions whose cost is less than some constant C\n    -\tUnbounded-cost search: accept a solution of any cost (as long as can quickly find it)\n      -\tSpeedy search: greedy best-first search version that heuristic is estimated number of actions required to reach a goal, regardless of cost\n        - same cost actions = greedy best-first search\n        - diff costs, it finds solution quickly but with high cost\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n  -\tHeuristic functions\n    -\tCity block distance = Manhattan distance: sum of vertical and horizontal distances\n    -\tEffective branching factor (b*): characterize the quality of a heuristic\n      -\tN+1 = 1 + b* + (b*)^2 + …+(b*)^d\n      -\tEffective depth: can be reduced by a constant  A* pruning with a given heuristic so total cost is  instead of \n    -\tDominates: a heuristic function dominates another one if it will be more efficient in the search \n    -\tRelaxed problem: a problem with fewer restriction on action (state space graph of relaxed problem is a supergraph of original state space bc restriction removal creates more edges)\n      -\tMay provide better solution if added edges have shortcuts\n      -\tCost of optimal solution in a relaxed prob is admissible h for the original\n      -\tAbsolver: program that generates heuristics from problem definitions using the “relaxed” problem and other techniques\n    -\tSubproblem: admissible heuristics can be derived from solution cost of subproblem of larger problem\n    -\tPattern database: store exact solutions for all possible subproblems, and compute admissible heuristic by looking up the subproblem in the database\n    -\tDisjoint pattern database: break into two subproblems and add them up\n  -\tHeuristics with landmarks\n    -\tPrecomputation: precompute the optimal path costs—only need to be done once\n      -\tLandmark points: choose a few and precompute the path from vertex v to L\n        -\tBest to choose ones that are spread out and not too close around the perimeter of the graph (centroid)\n    -\tShortcuts: artificial edges in the graph that define a optimal multi-action path\n    -\tDifferential heuristic: landmark that is beyond the goal – goal is on the optimal path from n to landmark then subtract the last part of the path\n  -\tImproving search\n    -\tMetalevel state space: each state captures the internal state of a program that is searching in an ordinary state space – each state on path is object-level search tree\n    -\tObject-level state space: map of Romania\n    -\tMeta-level learning algorithm: can learn from missteps and avoid exploring unpromising subtrees\n      -\tLearning goal is to minimize the total cost of solving problem by using more computational expense and path cost\n\n\n## Module 4 Lecture Notes\n\nAdditional textbook stuff\n  -\tPage 202: Memory-bounded search \n    -\tSolution is to keep reference counts of the number of times a state has been reached\n    -\tBeam search: limits frontier size\n    -\tIterative-deepening A* search\n    -\tRecursive best-first search\n      -\tBack-up value\n    -\tMemory related algorithms\n      -\tMemory bounded A* (MA*)\n      -\tSimplified memory bounded A* (SMA*)\n    -\tBidirectional heuristic search\n      -\tFront-to-end search\n      -\tFront-to-front search\n\n\n## Module 4 Definitions\n* **Concept** - definition\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",
        "  -\tMinimax search: for games with multiple outcome scores; recursive algorithm that searches all down, and then backs up minimax valuers through the tree; a type of depth-first search be \n",
        "    -\tPly: one player moves\n",
        "    -\tMinimax value: utility (max) of being in that state assuming both players play optimally from beginning to end\n",
        "    -\tMinimax decision: at root, action a1 will be the optimal choice with highest minimax value\n",
        "    -\tAlliances: multiplayer games usually have alliances (formal or informal) – alliances can be a natural consequence of optimal player strategies\n",
        "  -\tAlpha-beta pruning\n",
        "    -\tPruning: compute correct minimax even by cutting half the branches\n",
        "    -\tAlpha-beta pruning: technique we use to prune  best case; random move ordering roughly  for moderate b\n",
        "      -\tHighly dependent on the order nodes are examined – not prune any if worst successors generated first\n",
        "      -\tCan solve a tree twice as deep using alpha-beta pruning as minimax\n",
        "      -\tKiller moves: best moves\n",
        "      -\tCan also use combination with iterative deepening\n",
        "      -\tTranspositions: different permutation of move sequence that result same position\n",
        "        -\tTransposition table: record heuristic values\n",
        "    -\tType A vs. Type B strategy:\n",
        "      -\tType A: consider all moves to a certain depth (wide but shallow)\n",
        "      -\tType B: ignore bad looking moves, following promising paths all the way (deep by narrow) – world champion level play across some games (chess)\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "  -\tHeuristic Alpha-beta tree search\n",
        "    -\tUse heuristic evaluation function: returns estimate of expected utility of state for player (can treat nonterminal nodes as terminal) \n",
        "      -\tComputation can’t take too long \n",
        "      -\tShould be strongly correlated with actual wining chances\n",
        "      -\tCan cause algorithm to be unnecessarily certain about final outcomes\n",
        "      -\tFeatures: define categories of states that have the same values for all the features\n",
        "      -\tA good evaluation for states is expected value; usually weighted linear function\n",
        "        -\tMaterial value: assign a value for each piece in chess\n",
        "    -\tShould only be applied to quiescent positions where no pending move (capturing queen) that would drastically swing evaluation\n",
        "      -\tQuiescent search is sometimes restricted to consider only specific moves (like capture moves)\n",
        "    -\tHorizon effect: program is facing a move that can cause serious damage\n",
        "      -\tcan mitigate using singular extension: moves that are “clearly better” than all other moves even when search would be cut off normally\n",
        "    -\tUse cutoff test: returns true for terminal states, otherwise free to decide when to stop search (based on depth and any other property)\n",
        "      -\tModify alpha-beta search to call the evaluation function and see whether to cut off the search or not\n",
        "  -\tForward pruning: prunes poor moves, but might make mistake of pruning good ones\n",
        "    -\tBeam search: an approach to forward pruning where you consider only the “beam” of the n best moves (based on evaluation function) rather than all possible moves – this does not guarantee that the best move will not be pruned away\n",
        "    -\tProbabilistic cut: forward-pruning of alpha-beta search using stats from prior experiences to increase the chances of not prune best move \n",
        "    -\tLate move reduction: assumes that move ordering has been done well, so later moves are less likely to be good moves – so reduce depth to which we search these moves (saves time), if a reduced search returns a value above the current alpha, rerun search with full depth\n",
        "  -\tSearch vs. lookup: many game-playing programs use table lookup rather than searching for opening and ending of a game because it is faster?\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "  -\tMonte Carlo tree search: the value of a state is estimated as the avg utility over multiple simulations (playout/rollout) of complete games\n",
        "    -\tFor games with win/lose outcomes, “average utility” = “win percentage”\n",
        "    -\tPlayout policy: biases moves towards good ones providing useful information\n",
        "    -\tPure monte carlo search: perform N simulations starting from current state of game and track which moves from the current position has the highest win %\n",
        "    -\tSelection policy: focuses computational resources on tree’s important parts\n",
        "      -\tTwo factors that need to be balanced\n",
        "        -\tExploration of states that have had a few playouts\n",
        "        -\tExploitation of states that have done well in past playouts\n",
        "      -\tMonte carlo does the selection policy by maintaining a search tree and grows it on each iteration (steps are shown below)\n",
        "        -\tSelection: starting at tree root, choose a node, go to successor node, and keep repeat\n",
        "        -\tExpansion: grow search tree by generate new child of the node\n",
        "        -\tSimulation: perform playout form new generated child node\n",
        "        -\tBack-propagation: use simulation result to update all nodes up to root\n",
        "        -\t**we repeat 4 steps multiple times until time expires, then return move with highest playouts\n",
        "      -\tUpper confidence bound applies to trees (UCT): ranks each move based on upper CI formula, UCBI\n",
        "    -\tMonte carlo has an advantage over alpha-beta for games like GO where branching factor is very high (alpha beta can’t search deep enough) or when difficult to define a good evaluation function\n",
        "      -\tAlpha beta – choose a wrong node is done for\n",
        "      -\tMonte carlo --  takes an aggregate of many playouts, so not as vulnerable to single error\n",
        "    -\tMonte carlo has a disadvantage when it is likely that single move can change the course of a game (stochastic nature means it might fail to consider the move)\n",
        "  -\tEarly playout termination: for games that can last many moves\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "  -\tStochastic games: include a random element in games\n",
        "    -\tChance nodes: included in addition to max and min nodes\n",
        "      -\tExpected value = average over all possible outcomes of chance nodes\n",
        "      -\tExpectiminimax value: games with chance nodes (generalization of minimax for deterministic games)\n",
        "        -\tMin and max nodes are same\n",
        "  - Chance nodes – compute expected value (sum of value over all outcomes weighted by probability of each action)\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "  -\tProbability theory: what agent should believe based on evidence\n",
        "  -\tUtility theory: what agent wants\n",
        "    -\tUtility function: possessed by agent whose preferences between lotteries are consistent with set of axioms \n",
        "    -\tMultiattribute utility theory: deal with utilities that depend on several distinct attributes of states\n",
        "      -\tStochastic dominance is useful for making unambiguous decisions even without precise utility values for attributes\n",
        "  -\tDecision theory: put two together to describe what agent should do\n",
        "  -\tRational agent: use decision theory for system that make decisions by considering all possible actions and choosing one with best expected outcome\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" included above \"\"\"\n",
        "chapter16_3 = \"\"\" included above \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 43,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1996
        },
        "outputId": "7fcf6f1f-6b6d-4ce9-84f3-82f0d8c5dc8e"
      },
      "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": 44,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n  -\tMinimax search: for games with multiple outcome scores; recursive algorithm that searches all down, and then backs up minimax valuers through the tree; a type of depth-first search be \n    -\tPly: one player moves\n    -\tMinimax value: utility (max) of being in that state assuming both players play optimally from beginning to end\n    -\tMinimax decision: at root, action a1 will be the optimal choice with highest minimax value\n    -\tAlliances: multiplayer games usually have alliances (formal or informal) – alliances can be a natural consequence of optimal player strategies\n  -\tAlpha-beta pruning\n    -\tPruning: compute correct minimax even by cutting half the branches\n    -\tAlpha-beta pruning: technique we use to prune  best case; random move ordering roughly  for moderate b\n      -\tHighly dependent on the order nodes are examined – not prune any if worst successors generated first\n      -\tCan solve a tree twice as deep using alpha-beta pruning as minimax\n      -\tKiller moves: best moves\n      -\tCan also use combination with iterative deepening\n      -\tTranspositions: different permutation of move sequence that result same position\n        -\tTransposition table: record heuristic values\n    -\tType A vs. Type B strategy:\n      -\tType A: consider all moves to a certain depth (wide but shallow)\n      -\tType B: ignore bad looking moves, following promising paths all the way (deep by narrow) – world champion level play across some games (chess)\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n  -\tHeuristic Alpha-beta tree search\n    -\tUse heuristic evaluation function: returns estimate of expected utility of state for player (can treat nonterminal nodes as terminal) \n      -\tComputation can’t take too long \n      -\tShould be strongly correlated with actual wining chances\n      -\tCan cause algorithm to be unnecessarily certain about final outcomes\n      -\tFeatures: define categories of states that have the same values for all the features\n      -\tA good evaluation for states is expected value; usually weighted linear function\n        -\tMaterial value: assign a value for each piece in chess\n    -\tShould only be applied to quiescent positions where no pending move (capturing queen) that would drastically swing evaluation\n      -\tQuiescent search is sometimes restricted to consider only specific moves (like capture moves)\n    -\tHorizon effect: program is facing a move that can cause serious damage\n      -\tcan mitigate using singular extension: moves that are “clearly better” than all other moves even when search would be cut off normally\n    -\tUse cutoff test: returns true for terminal states, otherwise free to decide when to stop search (based on depth and any other property)\n      -\tModify alpha-beta search to call the evaluation function and see whether to cut off the search or not\n  -\tForward pruning: prunes poor moves, but might make mistake of pruning good ones\n    -\tBeam search: an approach to forward pruning where you consider only the “beam” of the n best moves (based on evaluation function) rather than all possible moves – this does not guarantee that the best move will not be pruned away\n    -\tProbabilistic cut: forward-pruning of alpha-beta search using stats from prior experiences to increase the chances of not prune best move \n    -\tLate move reduction: assumes that move ordering has been done well, so later moves are less likely to be good moves – so reduce depth to which we search these moves (saves time), if a reduced search returns a value above the current alpha, rerun search with full depth\n  -\tSearch vs. lookup: many game-playing programs use table lookup rather than searching for opening and ending of a game because it is faster?\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n  -\tMonte Carlo tree search: the value of a state is estimated as the avg utility over multiple simulations (playout/rollout) of complete games\n    -\tFor games with win/lose outcomes, “average utility” = “win percentage”\n    -\tPlayout policy: biases moves towards good ones providing useful information\n    -\tPure monte carlo search: perform N simulations starting from current state of game and track which moves from the current position has the highest win %\n    -\tSelection policy: focuses computational resources on tree’s important parts\n      -\tTwo factors that need to be balanced\n        -\tExploration of states that have had a few playouts\n        -\tExploitation of states that have done well in past playouts\n      -\tMonte carlo does the selection policy by maintaining a search tree and grows it on each iteration (steps are shown below)\n        -\tSelection: starting at tree root, choose a node, go to successor node, and keep repeat\n        -\tExpansion: grow search tree by generate new child of the node\n        -\tSimulation: perform playout form new generated child node\n        -\tBack-propagation: use simulation result to update all nodes up to root\n        -\t**we repeat 4 steps multiple times until time expires, then return move with highest playouts\n      -\tUpper confidence bound applies to trees (UCT): ranks each move based on upper CI formula, UCBI\n    -\tMonte carlo has an advantage over alpha-beta for games like GO where branching factor is very high (alpha beta can’t search deep enough) or when difficult to define a good evaluation function\n      -\tAlpha beta – choose a wrong node is done for\n      -\tMonte carlo --  takes an aggregate of many playouts, so not as vulnerable to single error\n    -\tMonte carlo has a disadvantage when it is likely that single move can change the course of a game (stochastic nature means it might fail to consider the move)\n  -\tEarly playout termination: for games that can last many moves\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n  -\tStochastic games: include a random element in games\n    -\tChance nodes: included in addition to max and min nodes\n      -\tExpected value = average over all possible outcomes of chance nodes\n      -\tExpectiminimax value: games with chance nodes (generalization of minimax for deterministic games)\n        -\tMin and max nodes are same\n  - Chance nodes – compute expected value (sum of value over all outcomes weighted by probability of each action)\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n  -\tProbability theory: what agent should believe based on evidence\n  -\tUtility theory: what agent wants\n    -\tUtility function: possessed by agent whose preferences between lotteries are consistent with set of axioms \n    -\tMultiattribute utility theory: deal with utilities that depend on several distinct attributes of states\n      -\tStochastic dominance is useful for making unambiguous decisions even without precise utility values for attributes\n  -\tDecision theory: put two together to describe what agent should do\n  -\tRational agent: use decision theory for system that make decisions by considering all possible actions and choosing one with best expected outcome\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n included above \n\n## AIMA Chapter 16.3 Utility Functions\n included above \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\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",
        "  -\tEasy to formulate problem into CSP, solvers are fast and efficient, can see why a assignment is not a solution\n",
        "  -\tCSP 3 components:\n",
        "    -\tX set of variables\n",
        "    -\tD set of domains, one for each variable\n",
        "    -\tC set of constraints specifying allowable combinations of values\n",
        "      -\tEach constraint = <scope, rel>\n",
        "        -\tRel = relation that defines the values that variables can take on\n",
        "  -\tAssignment of values to variables\n",
        "    -\tConsistent/legal assignment: assignment does not violate constraints\n",
        "    -\tComplete assignment: every variable assigned a value\n",
        "    -\tComplete, consistent assignment = solution\n",
        "    -\tPartial assignment: leaves some variable assigned\n",
        "    -\tPartial solution: consistent partial assignment\n",
        "  -\tConstraint graph: help to visualize CSP\n",
        "  - Constraints: represented in a constraint hypergraph that consists of nodes(circles) and hypernodes(squares) with n-ary constraints\n",
        "    -\tPrecedence constraint: task T1 must occur before task T2\n",
        "    -\tDisjunctive constraint: two actions must not overlap in time\n",
        "    -\tLinear constraints: each variable appears in linear form\n",
        "    -\tNonlinear constraints: no algorithm exists bc problem is undecidable\n",
        "    -\tUnary constraint: restricts value of a single variable (south Australians won’t tolerate green)\n",
        "    -\tBinary constraint: relates two variables (SA =!= NSW)\n",
        "      -\tBinary CSP: has only unary and binary constraints\n",
        "    -\tGlobal constraint: constraint with arbitrary number of variables, does not need to involve all variables in a problem (alldiff)\n",
        "      -\tCryptarithmetic puzzle: each letter in puzzle represent different digit\n",
        "      -\tSudoku: alldiff\n",
        "    -\tPreference constraint: indicate which solutions are preferred\n",
        "      -\tConstrained optimization problem (COP): CSP with preferences that can be solved with optimization search methods (path-based or local)\n",
        "        -\tLinear programs are one class\n",
        "      -\tResource constraint (almost constraint): no more than 10 personnel are assigned in total in a scheduling problem\n",
        "        -\tBounds propagation: domains represented by upper and lower bounds for resource limited problems (domains for number of passengers on flights F1 and F2\n",
        "  -\tCSP variables\n",
        "    -\tDiscrete, finite domains (map coloring and scheduling with time limits)\n",
        "    -\tDiscrete, infinite domain (no deadline on job-scheduling problem)\n",
        "    -\tContinuous domains: common in real world and in operations research (scheduling experiment son Hubble space telescope)\n",
        "      -\tLinear programming problems: constraints must be linear equalities or inequalities\n",
        "  -\tConvert n-ary CSP to binary\n",
        "    -\tUse dual graph transformation: create new graph one variable for each constraint in original, one binary constraint for each pair of constraints in original\n",
        "    -\tGlobal constraints are somtimes better than binary: easier, less error-prone, efficient can use speical-purpose inference algorithm\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "  -\tConstraint propagation: using constraints, reduce number of legal value sfor a variable – can reduce the legal values for another variable, etc.\n",
        "    -\tThis leaves fewer choices to consider when choosing next variable assignment\n",
        "    -\tA form of preprocessing that can sometimes solve the problem\n",
        "  -\tLocal consistency: treat each variable as a node in a graph and binary constraint = edge; enforcing local consistency in each part of the graph causes inconsistent values to be eliminated through graph\n",
        "    -\tTypes of local consistency\n",
        "      -\tNode consistent: all the values in the variable domain satisfy variable’s unary constraints\n",
        "        -\tIf not, you can eliminate unary constraints by reducing domain of variables with unary constraints or transform all n-ary constraints into binary\n",
        "      -\tArc consistent: every value in domain satisfies variable’s binary constraints\n",
        "        -\tAC-3: maintains a queue of arcs to consider; pops off arbitrary arc from queue and makes it Xi consistent wrt Xj; if it changes anything, it adds all the neighbors of Xi; continue and we will either get a failure or remove values until there are no more arcs in the queue\n",
        "    -\tThis is faster than the original CSP bc it is faster to search since variables have smaller domains\n",
        "    -\tComplexity:   and worst case  CSP with n variables, domain size at most d, and c binary constraints (arcs)\n",
        "    -\tSolves basic sudoku problems\n",
        "      -\tPath consistency: tighten binary constraints by implicit constraints that are inferred by looking at triples of variables\n",
        "      -\tK-consistency: a stronger form of propagation where consistent for any set of k-1 variables and for any consistent assignment to any kth variable\n",
        "        -\t1-consisitency: given {} we can make a set of 1 variable consistent\n",
        "        -\t2-consistency: arc consistency\n",
        "        -\t2-consistency: path consistency (in binary constraint graphs)\n",
        "      -\tStrongly k-consistent: k-consistent and (k-1) consistent and (k-2) consistent…to 1-consistent\n",
        "        -\tCSP with n nodes = strongly n-consistent (k=n)\n",
        "        -\tSolve from X1 (1-consistent) and then X2 (2-consistent) then X3 (3-consistent)\n",
        "      -\tBounds consistent: for every variable X and for both lower and upper bound values of X there is some Y that satisfies the constraint between X and Y for every variable Y\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "  -\tCan finish constraint propagation and still have variables with multiple possible values, then we must resort to searching for a solution\n",
        "  -\tCSPs are commutative: order of application of set of actions does not matter\n",
        "  -\tBacktracking search: keeps a single representation of a state (assignment) and alters the representation of that instead of creating a new one\n",
        "    -\tCan be improved using domain-independent heuristics taking advantage of the factored representations of CSPs\n",
        "    -\tVs. uninformed search algorithms in chapter 3 can only be improved by domain-specific heuristics\n",
        "  HOW TO IMPROVE BACKTRACKING page 383\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "  -\tChoose conflicted variable to change the value to something that brings closer to solution\n",
        "    -\tMini-conflicts heuristic: select a value that results in the minimum number of conflicts with other variables\n",
        "    -\tTabu search: keeps small list of recently visited states and forbids algorithm to go back to those states\n",
        "    -\tConstraint weighting: keep search on the important constraints – at each step of search, algorithm can choose a variable/value pair of which to change resulting in the lowest total weight of all violated constraints. Weights then r adjusted by incrementing weight of each constraint that is violated by current assignment\n",
        "      -\t2 benefits\n",
        "        -\tAdds topography to plateau\n",
        "        -\tMake sure you can improve on current state\n",
        "        -\tAdds learning bc difficult constraints are assigned higher weights\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "  -\tIndependent subproblems: subproblems are not dependent\n",
        "  -\tIndependence: can be confirmed by finding connected components of the constraint graph; each component corresponds to a subproblem CSP\n",
        "  -\tCompletely independent subproblems are rare\n",
        "    -\tA constraint graph: tree when any 2 variables are connected by one path\n",
        "  -\tDirectional arc consistency (DAC): every Xi is arc-consistent with each Xj for j>i\n",
        "    -\tA DAC we can just go down list of variables and choose remaining values because each edge from parent to child is arc-consistent already  this means we don’t have to backtrack and can linearly move through variables\n",
        "    -\tA tree with n nodes has n-1 edges so can make graph DAC in  steps which must compare up to d domain values for 2 variables gives total  time\n",
        "  -\tSolving a tree-structured CSP:\n",
        "    -\tTopological sort: pick variable at root and choose an ordering of variable that each variable is after its parent in the tree\n",
        "  -\tReducing constraint graph to a tree \n",
        "    -\tCutset conditioning\n",
        "      -\tAssign values to some variables so remaining variables form a tree\n",
        "      -\tDelete values from domains that are inconsistent\n",
        "      -\tCutset conditioning: General algorithm as follows for CSP\n",
        "        -\tChoose subset s of CSP’s variables such that constraint graph is a tree after s is removed – s is a cycle cutset\n",
        "        -\tFor each possible assignment to the variables in S that satisfy all constraints\n",
        "    -\tRemove any values that are inconsistent from domains\n",
        "    -\tReturn it together with s assignment if there is a still a possible solution\n",
        "      -\tRuntime is  \n",
        "  -\tTree decomposition: transform original graph into tree where each node in tree consist of set of variables that \n",
        "    -\tDecomposition must satisfy 3 requirements\n",
        "      -\tEvery variable in original problem appears in at least one of tree nodes\n",
        "      -\t2 variables are connected by constraint in the original problem, must appear together in at least 1 node\n",
        "      -\tIf variable appears in 2 nodes, must appear in every node along path connecting those node\n",
        "    -\tOnce have tree-structured graph apply tree-csp-solver to get solution in in  time – this is efficient as long as d is small\n",
        "      -\tN = number tree nodes\n",
        "      -\tD = size of largest domain\n",
        "  -\tValue symmetry: 3 colors to 3 regions\n",
        "  -\tSymmetry-breaking constraint: reduce search space by breaking symmetry in assignments and imposing an arbitrary ordering constraint\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "  - Waltz/Mackworth Constraint Propagation Algorithm:\n",
        "    1. assign every node in graph a set of all possible val\n",
        "    2. repeat until no change in set of values for any node\n",
        "      - for each node i\n",
        "        - for each neighbor j\n",
        "          - remove any value from i that is not arcconsistent with j\n",
        "  - AC-3 inefficiencies:\n",
        "    - At each iteration, we only need to examine those Xi where at least one neighbor of Xi has lost a value in the previous iteration\n",
        "    - If Xi loses value bc of arc inconsistencies w/Yj, we don’t need to check Yj on the next iteration\n",
        "    - Remove value on Xi can only make Yj arcinconsistent with respect to Xi itself\n",
        "      - only need to check that (j,i) is still arcconsistent\n",
        "  - Worst Case Complexity:\n",
        "    - All nodes can be connected to every other node, each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1) --> O(n^2)\n",
        "    - If there are d values, checking arc (i,j) takes O(d^2) time\n",
        "    - Each arc (i,j) can only be inserted into the queue dx\n",
        "    - Worst case complexity: O(n^2d^3 )\n",
        "      - (For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3 ))\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 45,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2881
        },
        "outputId": "e196f400-e8ac-47e2-ec19-3a6715583609"
      },
      "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": 46,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n  -\tEasy to formulate problem into CSP, solvers are fast and efficient, can see why a assignment is not a solution\n  -\tCSP 3 components:\n    -\tX set of variables\n    -\tD set of domains, one for each variable\n    -\tC set of constraints specifying allowable combinations of values\n      -\tEach constraint = <scope, rel>\n        -\tRel = relation that defines the values that variables can take on\n  -\tAssignment of values to variables\n    -\tConsistent/legal assignment: assignment does not violate constraints\n    -\tComplete assignment: every variable assigned a value\n    -\tComplete, consistent assignment = solution\n    -\tPartial assignment: leaves some variable assigned\n    -\tPartial solution: consistent partial assignment\n  -\tConstraint graph: help to visualize CSP\n  - Constraints: represented in a constraint hypergraph that consists of nodes(circles) and hypernodes(squares) with n-ary constraints\n    -\tPrecedence constraint: task T1 must occur before task T2\n    -\tDisjunctive constraint: two actions must not overlap in time\n    -\tLinear constraints: each variable appears in linear form\n    -\tNonlinear constraints: no algorithm exists bc problem is undecidable\n    -\tUnary constraint: restricts value of a single variable (south Australians won’t tolerate green)\n    -\tBinary constraint: relates two variables (SA =!= NSW)\n      -\tBinary CSP: has only unary and binary constraints\n    -\tGlobal constraint: constraint with arbitrary number of variables, does not need to involve all variables in a problem (alldiff)\n      -\tCryptarithmetic puzzle: each letter in puzzle represent different digit\n      -\tSudoku: alldiff\n    -\tPreference constraint: indicate which solutions are preferred\n      -\tConstrained optimization problem (COP): CSP with preferences that can be solved with optimization search methods (path-based or local)\n        -\tLinear programs are one class\n      -\tResource constraint (almost constraint): no more than 10 personnel are assigned in total in a scheduling problem\n        -\tBounds propagation: domains represented by upper and lower bounds for resource limited problems (domains for number of passengers on flights F1 and F2\n  -\tCSP variables\n    -\tDiscrete, finite domains (map coloring and scheduling with time limits)\n    -\tDiscrete, infinite domain (no deadline on job-scheduling problem)\n    -\tContinuous domains: common in real world and in operations research (scheduling experiment son Hubble space telescope)\n      -\tLinear programming problems: constraints must be linear equalities or inequalities\n  -\tConvert n-ary CSP to binary\n    -\tUse dual graph transformation: create new graph one variable for each constraint in original, one binary constraint for each pair of constraints in original\n    -\tGlobal constraints are somtimes better than binary: easier, less error-prone, efficient can use speical-purpose inference algorithm\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n  -\tConstraint propagation: using constraints, reduce number of legal value sfor a variable – can reduce the legal values for another variable, etc.\n    -\tThis leaves fewer choices to consider when choosing next variable assignment\n    -\tA form of preprocessing that can sometimes solve the problem\n  -\tLocal consistency: treat each variable as a node in a graph and binary constraint = edge; enforcing local consistency in each part of the graph causes inconsistent values to be eliminated through graph\n    -\tTypes of local consistency\n      -\tNode consistent: all the values in the variable domain satisfy variable’s unary constraints\n        -\tIf not, you can eliminate unary constraints by reducing domain of variables with unary constraints or transform all n-ary constraints into binary\n      -\tArc consistent: every value in domain satisfies variable’s binary constraints\n        -\tAC-3: maintains a queue of arcs to consider; pops off arbitrary arc from queue and makes it Xi consistent wrt Xj; if it changes anything, it adds all the neighbors of Xi; continue and we will either get a failure or remove values until there are no more arcs in the queue\n    -\tThis is faster than the original CSP bc it is faster to search since variables have smaller domains\n    -\tComplexity:   and worst case  CSP with n variables, domain size at most d, and c binary constraints (arcs)\n    -\tSolves basic sudoku problems\n      -\tPath consistency: tighten binary constraints by implicit constraints that are inferred by looking at triples of variables\n      -\tK-consistency: a stronger form of propagation where consistent for any set of k-1 variables and for any consistent assignment to any kth variable\n        -\t1-consisitency: given {} we can make a set of 1 variable consistent\n        -\t2-consistency: arc consistency\n        -\t2-consistency: path consistency (in binary constraint graphs)\n      -\tStrongly k-consistent: k-consistent and (k-1) consistent and (k-2) consistent…to 1-consistent\n        -\tCSP with n nodes = strongly n-consistent (k=n)\n        -\tSolve from X1 (1-consistent) and then X2 (2-consistent) then X3 (3-consistent)\n      -\tBounds consistent: for every variable X and for both lower and upper bound values of X there is some Y that satisfies the constraint between X and Y for every variable Y\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n  -\tCan finish constraint propagation and still have variables with multiple possible values, then we must resort to searching for a solution\n  -\tCSPs are commutative: order of application of set of actions does not matter\n  -\tBacktracking search: keeps a single representation of a state (assignment) and alters the representation of that instead of creating a new one\n    -\tCan be improved using domain-independent heuristics taking advantage of the factored representations of CSPs\n    -\tVs. uninformed search algorithms in chapter 3 can only be improved by domain-specific heuristics\n  HOW TO IMPROVE BACKTRACKING page 383\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n  -\tChoose conflicted variable to change the value to something that brings closer to solution\n    -\tMini-conflicts heuristic: select a value that results in the minimum number of conflicts with other variables\n    -\tTabu search: keeps small list of recently visited states and forbids algorithm to go back to those states\n    -\tConstraint weighting: keep search on the important constraints – at each step of search, algorithm can choose a variable/value pair of which to change resulting in the lowest total weight of all violated constraints. Weights then r adjusted by incrementing weight of each constraint that is violated by current assignment\n      -\t2 benefits\n        -\tAdds topography to plateau\n        -\tMake sure you can improve on current state\n        -\tAdds learning bc difficult constraints are assigned higher weights\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n  -\tIndependent subproblems: subproblems are not dependent\n  -\tIndependence: can be confirmed by finding connected components of the constraint graph; each component corresponds to a subproblem CSP\n  -\tCompletely independent subproblems are rare\n    -\tA constraint graph: tree when any 2 variables are connected by one path\n  -\tDirectional arc consistency (DAC): every Xi is arc-consistent with each Xj for j>i\n    -\tA DAC we can just go down list of variables and choose remaining values because each edge from parent to child is arc-consistent already  this means we don’t have to backtrack and can linearly move through variables\n    -\tA tree with n nodes has n-1 edges so can make graph DAC in  steps which must compare up to d domain values for 2 variables gives total  time\n  -\tSolving a tree-structured CSP:\n    -\tTopological sort: pick variable at root and choose an ordering of variable that each variable is after its parent in the tree\n  -\tReducing constraint graph to a tree \n    -\tCutset conditioning\n      -\tAssign values to some variables so remaining variables form a tree\n      -\tDelete values from domains that are inconsistent\n      -\tCutset conditioning: General algorithm as follows for CSP\n        -\tChoose subset s of CSP’s variables such that constraint graph is a tree after s is removed – s is a cycle cutset\n        -\tFor each possible assignment to the variables in S that satisfy all constraints\n    -\tRemove any values that are inconsistent from domains\n    -\tReturn it together with s assignment if there is a still a possible solution\n      -\tRuntime is  \n  -\tTree decomposition: transform original graph into tree where each node in tree consist of set of variables that \n    -\tDecomposition must satisfy 3 requirements\n      -\tEvery variable in original problem appears in at least one of tree nodes\n      -\t2 variables are connected by constraint in the original problem, must appear together in at least 1 node\n      -\tIf variable appears in 2 nodes, must appear in every node along path connecting those node\n    -\tOnce have tree-structured graph apply tree-csp-solver to get solution in in  time – this is efficient as long as d is small\n      -\tN = number tree nodes\n      -\tD = size of largest domain\n  -\tValue symmetry: 3 colors to 3 regions\n  -\tSymmetry-breaking constraint: reduce search space by breaking symmetry in assignments and imposing an arbitrary ordering constraint\n\n\n## Module 6 Lecture Notes\n\n  - Waltz/Mackworth Constraint Propagation Algorithm:\n    1. assign every node in graph a set of all possible val\n    2. repeat until no change in set of values for any node\n      - for each node i\n        - for each neighbor j\n          - remove any value from i that is not arcconsistent with j\n  - AC-3 inefficiencies:\n    - At each iteration, we only need to examine those Xi where at least one neighbor of Xi has lost a value in the previous iteration\n    - If Xi loses value bc of arc inconsistencies w/Yj, we don’t need to check Yj on the next iteration\n    - Remove value on Xi can only make Yj arcinconsistent with respect to Xi itself\n      - only need to check that (j,i) is still arcconsistent\n  - Worst Case Complexity:\n    - All nodes can be connected to every other node, each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1) --> O(n^2)\n    - If there are d values, checking arc (i,j) takes O(d^2) time\n    - Each arc (i,j) can only be inserted into the queue dx\n    - Worst case complexity: O(n^2d^3 )\n      - (For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3 ))\n\n\n## Module 6 Definitions\n* **Concept** - definition\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",
        "-\tIntelligent agents need knowledge about world to reach good decisions\n",
        "-\tKnowledge is contained in agents in the form of sentences in a knowledge representation language that are stored in a knowledge base\n",
        "-\tKnowledge-based agent: composed of knowledge base and inference mechanism\n",
        "  -\tOperates by storing sentences about world in knowledge base\n",
        "  -\tUsing inference mech to infer new sentences\n",
        "  -\tUse sentences to decide what action to take\n",
        "-\tRepresentation language: defined by syntax and semantics\n",
        "  -\tSyntax: specifies structure of sentences\n",
        "  -\tSemantics: defines truth of each sentence in each possible world/model\n",
        "-\tEntailment: a sentence alpha entails beta if beta is true in all worlds where alpha is true\n",
        "  -\tValidity of sentence alpha -> beta\n",
        "  -\tAnd satisfiability of alpha ^ not beta\n",
        "-\tInference: process of deriving new sentences from old ones\n",
        "  -\tSound inference algorithms: derive only entailed sentences\n",
        "  -\tComplete algorithms: derive all sentences that are entailed\n",
        "-\tPropositional logic: language with propositional symbols and logical connectives\n",
        "  -\tIt can handle propositions that are known true, known false, and unknown\n",
        "-\tSet of possible models with fixed propositional vocabulary is finite, so entailment can be checked by enumerating models\n",
        "  -\tEfficient model-checking inference algorithms include __ and often solve large problem quickly\n",
        "    -\tBacktracking\n",
        "    -\tLocal search methods\n",
        "-\tInference rules are patterns of sound inference used to find proofs\n",
        "  -\tResolution rule = complete inference algorithm for knowledge bases that are expressed in conjunctive normal form (CNF)\n",
        "  -\tNatural reasoning algorithms in Horn form for knowledge bases\n",
        "    -\tForward chaining: determine if proposition symbol, q—the query, is entailed by a knowledge base of definite clauses (begins from known facts in knowledge base)\n",
        "    -\tBackward chaining: works backwards from the query (if query q is true, no work is needed); otherwise find implications in knowledge base whose conclusion is q and the words back down the graph until it reaches set of known facts, A and B that is basis for proof\n",
        "- Goal-directed reasoning – useful to answer specific questions\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" included above \"\"\"\n",
        "chapter7_3 = \"\"\" included above \"\"\"\n",
        "chapter7_4 = \"\"\" included above \"\"\"\n",
        "chapter7_5 = \"\"\" included above \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "  - Proof by Resolution\n",
        "    - resolution: yields complete inference algorithm when coupled with any complete search algorithm\n",
        "  - Conjuctive Normal Form (CNF)\n",
        "    1. Eliminate ⇔ by replacing a ⇔ β with (a ⟹ β) ⋀ (β ⟹a)\n",
        "    2. Eliminate ⟹ by replacing a ⟹ β with ¬a ⋁ β\n",
        "    3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n",
        "    4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible. \n",
        "  - Resolution Algorithm: inference procedures use the principle of proof by contradiction (is complete)\n",
        "      - To show KB⊨a then we can show that KB ⋀ ¬a is unsatisfiable\n",
        "        1. Convert (KB ⋀ ¬a) into CNF\n",
        "        2. Apply the resolution rule to the resulting clauses\n",
        "        3. Resolve every pair that contains complementary literals to produce a new clause\n",
        "        4. If that new clause isn’t already present, then add it to the set\n",
        "        5. Continue the process until one of two things happens:\n",
        "          - There are no new clauses that can be added. In this case, the KB does not entail a\n",
        "          - Two clauses resolve to yield the empty clause, in which case the KB does entail a\n",
        "  - Definite clause: disjunction of literals where exactly 1 is positive\n",
        "  - Horn Clause: disjunction of literals where at most 1 is positive\n",
        "    - includes definite clauses\n",
        "    - and clauses with no positive literals\n",
        "  - Forward chaining and Backward chaining\n",
        "    - forward chaining: kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so\n",
        "    - backward chaining: works backwards from a query. If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
        "      - a form of goal-directed reasoning\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 47,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1580
        },
        "outputId": "ff4f6d27-0267-48fe-9700-946c93bb4373"
      },
      "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": 48,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n-\tIntelligent agents need knowledge about world to reach good decisions\n-\tKnowledge is contained in agents in the form of sentences in a knowledge representation language that are stored in a knowledge base\n-\tKnowledge-based agent: composed of knowledge base and inference mechanism\n  -\tOperates by storing sentences about world in knowledge base\n  -\tUsing inference mech to infer new sentences\n  -\tUse sentences to decide what action to take\n-\tRepresentation language: defined by syntax and semantics\n  -\tSyntax: specifies structure of sentences\n  -\tSemantics: defines truth of each sentence in each possible world/model\n-\tEntailment: a sentence alpha entails beta if beta is true in all worlds where alpha is true\n  -\tValidity of sentence alpha -> beta\n  -\tAnd satisfiability of alpha ^ not beta\n-\tInference: process of deriving new sentences from old ones\n  -\tSound inference algorithms: derive only entailed sentences\n  -\tComplete algorithms: derive all sentences that are entailed\n-\tPropositional logic: language with propositional symbols and logical connectives\n  -\tIt can handle propositions that are known true, known false, and unknown\n-\tSet of possible models with fixed propositional vocabulary is finite, so entailment can be checked by enumerating models\n  -\tEfficient model-checking inference algorithms include __ and often solve large problem quickly\n    -\tBacktracking\n    -\tLocal search methods\n-\tInference rules are patterns of sound inference used to find proofs\n  -\tResolution rule = complete inference algorithm for knowledge bases that are expressed in conjunctive normal form (CNF)\n  -\tNatural reasoning algorithms in Horn form for knowledge bases\n    -\tForward chaining: determine if proposition symbol, q—the query, is entailed by a knowledge base of definite clauses (begins from known facts in knowledge base)\n    -\tBackward chaining: works backwards from the query (if query q is true, no work is needed); otherwise find implications in knowledge base whose conclusion is q and the words back down the graph until it reaches set of known facts, A and B that is basis for proof\n- Goal-directed reasoning – useful to answer specific questions\n\n\n## AIMA Chapter 7.2 The Wumpus World\n included above \n\n## AIMA Chapter 7.3 Logic\n included above \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n included above \n\n## AIMA 7.5 Propositional Theorem Proving\n included above \n\n## Module 7 Lecture Notes\n\n  - Proof by Resolution\n    - resolution: yields complete inference algorithm when coupled with any complete search algorithm\n  - Conjuctive Normal Form (CNF)\n    1. Eliminate ⇔ by replacing a ⇔ β with (a ⟹ β) ⋀ (β ⟹a)\n    2. Eliminate ⟹ by replacing a ⟹ β with ¬a ⋁ β\n    3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n    4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible. \n  - Resolution Algorithm: inference procedures use the principle of proof by contradiction (is complete)\n      - To show KB⊨a then we can show that KB ⋀ ¬a is unsatisfiable\n        1. Convert (KB ⋀ ¬a) into CNF\n        2. Apply the resolution rule to the resulting clauses\n        3. Resolve every pair that contains complementary literals to produce a new clause\n        4. If that new clause isn’t already present, then add it to the set\n        5. Continue the process until one of two things happens:\n          - There are no new clauses that can be added. In this case, the KB does not entail a\n          - Two clauses resolve to yield the empty clause, in which case the KB does entail a\n  - Definite clause: disjunction of literals where exactly 1 is positive\n  - Horn Clause: disjunction of literals where at most 1 is positive\n    - includes definite clauses\n    - and clauses with no positive literals\n  - Forward chaining and Backward chaining\n    - forward chaining: kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so\n    - backward chaining: works backwards from a query. If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n      - a form of goal-directed reasoning\n\n\n## Module 7 Definitions\n* **Concept** - definition\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": "fc48aada-5289-49a9-8f8b-11cd440291a9"
      },
      "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": 54,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \n4 combinations of AI: human vs. rational; thought vs. behavior\n  -\tHuman: involving observations/hypotheses abt actual human behavior and thought processes\n    -\tTuring test: (Alan Turing 1950) designed as a thought experiment where a human would not be able to tell if computer generated responses were from a human or a computer and contain the following capabilities:\n      -\tNatural language processing: to communicate in a human language\n      -\tKnowledge representation: to store what it knows and hears\n      -\tAutomated reasoning: to answer questions and draw conclusions\n      -\tMachine learning: to adapt to new circumstances and detect patterns\n    -\tTotal Turing test: require intereaction with objects and people where the robot needs:\n      -\tComputer vision and speech recognition: to perceive the world\n      -\tRobotics: to manipulate objects and move around\n  -\tRationalist: comb of math and engineering and connects to STAT, control theory, and econ\n  -\t3 different approaches to AI\n    -\tCognitive modeling approach: we can learn about human thought in 3 ways: Introspection, psychological experiments, brain imaging\n      -Cognitive science: brings tgt computer models in AI and experimental techniques from psychology to construct precise and testable theories of the human mind\n    -\tLaws of thought approach; Logic: the laws of thought governed the operation of the mind\n      -\tProbability fills the gaps where there are areas where the rules are unknown\n    -\tRational agent approach (general the most popular bc it is more general than the laws of thought approach, more friendly to scientific development)\n      -\tAgent: something that acts\n      -\tRational agent: an agent that acts to achieve best (expected) outcome – not always guaranteed to find optimal solutions\n  - Value alignment problem: real world conflict between our true preferences and the objective we put into the machine \n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n  -\tWeak AI: machines could act as if they were intelligent\n  -\tStrong AI: machines actually consciously thinking  “human-level AI”\n  -\tQualification problem: difficult to capture every appropriate behavior in a set of logical rules\n  -\tEmbodied cognition approach: claims that cognition need to be examined with/in an environment (including the rest of its body)\n  -\tAreas where AI did not have complete answers\n    -\tArgument from disability: “machine can never do X”\n    -\tMathematical objection: certain math questions are unanswerable by formal systems\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n  -\tChinese room (John Searle 1990): human who only understands English is in a room that contains a rule book written in English. Paper slips with indecipherable symbols are slipped under the doors, and the human uses the book to decipher the symbols and write back. However, since neither the human or the Chinese room has an understanding of Chinese, it is like a computer also has no understanding\n    -\tBiological naturalism: mental states are high level emergent features that are caused by low-level physical processes in neurons\n      -\tSearle is a supporter\n  -\tConsciousness: awareness to the outside world, self, and subjective experience of living\n  -\tQualia: the technical term for the intrinsic nature of experiences\n\n\n## AIMA 2.1 Agents and Environments\n\n  -\tAgent: anything that can be viewed as perceiving its environment through sensors and acting through actuators\n  -\tPercept: the content an agent’s sensors are perceiving\n  -\tPercept sequence: complete history of everything that was perceived\n  -\tAgent function: describes an agent’s behavior (maps a percept to an action)\n  -\tAgent program: the thing that implements the agent function\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n  -\tConsequentialism: evaluate an agent’s behavior by its consequences\n  -\tPerformance measure: evaluates any given sequence of environment states (captures the notion of desirability)\n  -\tRationality (depends on 4 things) – rational agent: select action that expects to maximize performance measure given percept sequence and built in knowledge\n    -\tPerformance measure that defines success\n    -\tAgent’s prior knowledge of environment\n    -\tActions that agent can perform\n    -\tAgent’s percept sequence to date\n  -\tPiori: “geography” of an environment\n  -\tOmniscience: agent that knows the outcome of its actions (impossible in reality)\n  -\tPerfection vs. Rationality: perfection = actual while rationality = expected\n  -\tInformation gathering: doing actions to modify future percepts\n    -\tExploration: information gathering in an initially unknown environment\n  -\tAutonomy: extent that an agent relies on prior knowledge rather than percepts and learning processes\n\n\n## AIMA 2.3 The Nature of Environments\n\n  -\tTask environment: the “problem” where the rational agents are “solutions”\n  -\tPEAS: \n    -\tPerformance measure: what would we want the agent to strive for\n    -\tEnvironment\n    -\tActuators: control of things that can change the environment\n    -\tSensors: things to help learn about the environment\n  -\tSoftware agent == software robot == softbot\n  -\tFully observable vs. partially observable:\n    - Fully observable: agent’s sensors give it access to all relevant & complete environment state\n    -\tPartially observable: there are noisy/inaccurate sensors or there are missing parts from the sensor data\n      -\tVacuum with a local dirt sensor\n      -\tAutomated taxi that can’t see what other drivers are thinking\n    - Unobservable: no sensors\n  -\tSingle vs. multi agent:\n    - Single-agent\n    - Multi-agent\n      -\tCompetitive multiagent: chess\n      -\tPartially cooperative multiagent: taxi-driving environment\n  -\tDeterministic vs. Nondeterministic:\n    - Deterministic: next state is completely determined by the surrent state and action executed by agent\n    - Nondeterministic: anything otherwise\n      -\tA partially observable environment could “appear”: nondeterministic\n    - Stochastic: synonym for nondeterministic but more explicitly deals with probabilities (using percentages) while nondeterministic just means without being quantified\n  -\tEpisodic vs. sequential\n    - Episodic: agent experience is divided into atomic episodes of one percept and one action\n    - Sequential: current decision could affect all future decisions \n  -\tStatic vs. dynamic:\n    - Static: environment does not change as time passes\n    - Dynamic: environment can change while agent is deliberating\n  -\tDiscrete vs. Continuous: (applies to state of environment, way time is handled, and percepts and actions of agent)\n    - Discrete: finite number of distinct states\n    - Continuous: infinite and never ending smooth states over time\n  -\tKnown vs. unknown:\n    - Known: agents state of knowledge where all the outcomes are given\n      -\tKnown environments can be partially observable (cards where you can’t see the unturned cards)\n    - Unknown: agent need to learn how the environment works to make good decisions\n      -\tUnknown environment can be fully observable (video game where the screen shows entire game state but u don’t know what the buttons do until you try them\n  -\tHardest case: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown\n  -\tEnvironment class: environments are often carried out from an environment drawn from an environment class\n\n\n## AIMA 2.4 The Structure of Agents\n\n  -\tAgent = architecture + program\n    - Agent program: implements agent function\n    - Agent architecture: the computing device that runs the agent program\n  -\t4 types of agents\n    - Simple reflex agents: agents that select actions on the bases of current percept (ignoring percept history)\n      -\tCondition-action rule: if-then rule\n      -\tInfinite loops are often unavoidable but can be prevented if agent randomizes its actions\n    - Model-based reflex agents: agent needs to maintain some sort of internal state that depends on percept history and reflects some unobserved aspects of the current state\n      -\tTransition model: knowledge about what happens if an action is taken “how the world works”\n      -\tSensor model: information about how the state of the world is reflected in agent’s percepts\n      -\tModel-based agent: an agent that uses transition and sensor models\n    - Goal-based agents: agents needs some goal information that describes desirable situations\n      -\tSubfields of AI devoted to finding action sequences that achieve agent’s goals\n        -\tSearch\n        -\tplanning\n    - Utility-based agents: what state is most useful for the agent\n      -\tUtility function: internalization of the performance measure\n      -\tExpected utility: the expected utility agents get from an action\n      -\tModel free agent: learn what action is best in a situation without learing how the action changes the environment\n  -\tLearning agents\n    - Learning element: responsible for making improvements where it uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to do better\n    - Performance element: responsible for selecting external actions\n      -\tPerformance standard that provides feedback on agent quality\n        -\tReward\n        -\tPenalty\n    - Problem generator: responsible for suggesting actions that lead to informative experiences\n  -\tAtomic vs. Factored vs. Structured representation\n    - Atomic representation: each stat of the world is indivisible\n    - Factored representation: splits up each state into a fixed set of variables or attributes which can have a value\n    - Structured representation: objects and their various relationships can be described explicitly\n    - Axises for representation:\n      -\tExpressiveness: expressive language is more concise\n      -\tLocalist representation: one to one mapping between concepts and memory locations\n      -\tDistributed representation: representation of a concept is spread over many memory locations and each is employed as a representation of multiple different concepts\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\n  - Python uses dynamic scope: see most current variable value\n  - References and Mutability\n    - strings are immutable\n    - == checks if variable point to objects of same value\n    - is checks if variables point to same object\n    - lists are mutable\n    - use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value\n  - Sequence Types\n    - tuple: immutable, ordered seq of items; mixed type (include collection types)\n      - tu = (23, 'ab', 4.6, (2,3), 'def')\n    - string: immutable (unicode and use 2byte char -- python 1 uses 8-bit char)\n      - operations\n        - s.split(\" \") -> ['Pretend', 'this', 'sentence']\n        - \"_\".join(words) -> 'Pretend_this_sentence'\n        - s.caplitaize()\n        - s.upper()\n        - \"hi--\".strip('--')\n    - list: mutable, ordered seq of item; mixed type\n      - li = ['abc', 34, 4.34]\n      - operations: \n        - li.append()\n        - li.insert(2,\"\")\n        - li.index(1st occur)\n        - li.count()\n        - li.remove(1st occur)\n        - li.reverse() - reverse in place(modify)\n        - li.sort() or li.sort(some_function)\n        - sorted(li) - return a copy sorted\n  - Slicing\n    - t[1:4] #slicing ends before last index ('ab', 4.6, (2,3))\n    - t[1:-1] #using negative index ('ab', 4.6, (2,3))\n    - t[1:-1:2] # selection of every nth item. ('ab', (2,3))\n    - t[:2] # copy from beginning of sequence (23, 'ab')\n    - t[2:] # copy to the very end of the sequence (4.6, (2,3), 'def')\n  - Dict: unordered, work by hashing, so keys are immutable\n    - operations\n      - d[key] - return value\n      - d[value] - KeyError\n      - d[key] = xxx - replaces value\n      - d.keys(), d.values(), d.items() - list of item tuple\n  - Functions\n    - can return multiple values as tuple, java (have to design object to return multiple values)\n    - python: no function overloading like java bc function specified by only name\n      - 2 functions can't have same name even if diff number, order, or arguments\n      - operator overloading can happening using special methods in class\n    - first-class object: functions can be...\n      - pass functions as arguments other functions\n      - return functions as values from other furnctions\n      - assign functions to variables/store in data structure\n    - List comprehension\n      - squares = [x*x for x in range(0,4)] = [0, 1, 4, 9]\n      - iterate thru list of tuples = [n*3 for (x, n) in list]\n      - list of values from 1 to 100 = [x for x in range(1, 101)]\n      - filter list = [x*2 for x in list if x >4]\n    - Set comprehension\n      - d = {k: v for k, v, in list} - list of tuples\n      - s = {x for x in list}\n    - search in a directed graph\n      - d = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n        - [v for v in d.search(1, set())] --> [1, 2, 4, 3]\n\n\n## Module 2 Definitions\n* ***args** - accept a variable number of non-keyword arguments to the function\n* ***kwargs** - accept a variable number of keyword arguments to the function\n* **Higher order functions** - take functions as input\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n  -\tProblem-solving agent: agent who take a sequence of actions in a path to a goal state\n    -\tSearch: the process the agent undertakes\n    -\tSearch problem: \n      -\tState space: a set of possible states that the environment can be in (can be infinite)\n        -\tGraph: state space where vertices = states and directed edges = actions\n      -\tInitial state\n      -\tGoal state: sometimes there is one, sometimes there are multiple, or infinite – can be defined by a property that applies to many states (i.e. no dirt in a vacuum cleaner world)\n      -\tActions: moves an agent can take – usually a finite set of actions(s)\n      -\tTransition model: describes what each action does; result(s,a) returns the state that results from doing action an in state s\n      -\tAction cost function: provides the numeric cost of apply action a in state s to reach state s’\n      -\tSolution: a path (sequence of actions) from the initial to goal state\n        -\tOptimal solution: lowest path cost among all solutions\n    -\tIf environment is unknown, agent must execute action at random\n  -\tRepresentations of states: \n    -\tProblem-solving agents use atomic representations: states of the world are whole (no internal structure is visible to the problem-solving algorithms)\n    -\tPlanning agents use factored/structured representations of states\n      -\tAbstraction: process of removing detail as possible form a representation while retaining validity and ensuring the abstract actions are easy to carry out\n        -\tLevel of abstraction depends of the detailed world states and detailed action sequences\n    -\tValid: if can elaborate any abstract solution into a solution in the detailed world\n    -\tUseful: if carrying out each of the actions in the solution is easier than the original problem (no further search of planning needed)\n  -\tInformed vs. uninformed algorithms:\n    -\tInformed: agent can estimate how far it is from goal\n    -\tUninformed: no estimate is available\n  -\t4 phase problem solving process:\n    -\tGoal formulation: limit objectives and actions to be considered\n    -\tProblem formulation: agent devises description of states and actions necessary to reach a goal\n    -\tSearch: agent simulates and searches sequence of actions that reaches the goal  solution\n    -\tExecution: agent will execute actions in the solution, one at a time\n  -\tOpen-loop vs. closed-loop system:\n    -\tOpen-loop system: ignoring percepts as it follows the solution path (ignoring percepts breaks the loop between agent and environment)\n    - Closed-loop system: safer when model is incorrect, or environment is nondeterministic – this monitors percepts\n\n\n## AIMA Chapter 3.2 Example Problems\n\n-\tStandardized vs. real-world problems:\n  -\tStandardized problem: illustrate various problem solving methods bc it can be given as a concise, exact description so researches can use it as a benchmark to compare the performance of algorithms\n    -\tGrid vs. vacuum world:\n      -\tGrid world: 2D rectangular array of square cells where the agent can move form cell to cell; cells can contain objects that the agent can pick up, push, or act upon, walls prevent agents from moving into that cell (pg157)\n  -\tSokoban puzzle: agent’s goal is to push boxes to designated storage locations\n  -\tSliding-tile puzzle: rush hour, 8, and 15 puzzle\n      -\tVacuum world: grid world problem with dirty cells (with n cells has n*2^n states)\n  -\tReal-world problem: (robot navigation) is idiosyncratic, not standardized because each robot has different sensors that produce different data\n    -\tRoute-finding problem\n      -\tRobot navigation: generalization of the route-finding problem – instead of following distinct routes, the robot can make its own path\n    -\tTouring problem: set of locations that must be visited\n      -\tTraveling salesperson problem (TSP): touring problem in which every city on a map must be visited\n    -\tVLSI layout problem: position millions of components and connections on a chip to minimize area, circuit delays, stray capacitances, and maximize manufacturing yield (split into two parts below)\n      -\tCell layout: primitive components of circuit are grouped into cells, each which performs some recognized function\n      -\tChanneling routing: finds specific route for each wire thorugh gaps between the cells\n    -\tAutomatic assembly sequencing of complex objects: algorithms find a feasible assembly sequence then work to optimize the process\n      -\tProtein design: the goal is to find a sequence of amino acids that will fold into 3-D protein with the right properties to cure some disease\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n  -\tSearch algorithm: input = search problem and output = solution, or indication of failure\n    -\tSearch tree: describes paths between different states; unique path back to the root\n      -\tNode: is a state in the state space\n      -\tExpand: considering the available actions for that state\n      -\tChild/successor node: generate a new node for each of the resulting states\n      -\tFrontier: the result of the latest node expansion\n          - Separates two regions of the state-space graph: \n            1) interior regions where every state has been expanded\n            2) exterior region of states that have not yet been reached\n    -\tQueue is the data structure that stores the frontier; possible operations include:\n      -\tIs-Empty(frontier): returns true only if there are no nodes in the frontier\n      -\tPop(frontier): removes the top node form the frontier and returns it\n      -\tTop(frontier): returns (but doesn’t remove) the top node of the frontier\n      -\tAdd(node, frontier): inserts node into proper place in the queue\n        -\tReached: any state that has had a node generated for it is reached\n        -\tRepeated state: caused by a cycle/loopy path – means the complete search is infinite\n    -\tCycle = special case of a redundant path\n      -\tA tree node: is represented by a data structure with 4 components\n        -\tNode.state: state the node corresponds to\n        -\tNode.parent: node in the tree that generated this node\n        -\tNode.action: action that was applied to the parent’s state to generate this node\n        -\tNode.path-cost: total cost of the path from initial state to this node\n  -\tProblem solving performance:\n    -\tCompleteness: is the algorithm guaranteed to find a solution or failure -- to be complete, the algorithm must by systematic\n    -\tCost optimality/admissibility: does it find a solution with the lowest path cost of all solutions\n    -\tComplexity:\n      -\tTime complexity: how long to find a solution\n      -\tSpace complexity: how much memory to perform search\n      -\tComplexity can be measured using\n        -\tDepth: number of actions in the optimal solution\n        -\tMaximum number of actions in any path\n        -\tBranching factor: number of successors of a node\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n  -\tExponential complexity search problems usually need informed search\n  -\tBreadth-first search: root node expanded first, then successors of the root node expanded, then their successors, etc. \n    -\tCan implement best first search where the evaluation function f(n) is the depth of the node – the number of actions it takes to reach the node\n    -\tSystematic, complete even on infinite state spaces, optimal for problems where all the actions have the same cost\n    -\tPossible efficiency improvements:\n      -\tEarly goal test: check node is a solution when generated\n      -\tLate goal test (best-first search): check if a solution after popped off the queue\n  -\tUniform-cost search (Dijkstra): spreads out in waves of uniform path-cost\n    -\tImplemented as a call to best-first search with path-cost as the evaluation function\n    -\tSystematic, complete, and cost-optimal, will not get stuck in a loop (infinite path)\n    -\twhen all action costs are equal,  and is like breadth-first search\n  -\tDepth-first search: expands the deepest node in the frontier first \n    -\tPreferred for problems where tree-like search is feasible bc has much smaller memory needs\n      -\tNo reached table\n      -\tFrontier very small (radius of sphere) vs. breadth-first search frontier (filled in sphere)\n    -\tImplemented as a call to best-first search where evaluation function f(n) is the negative of the depth, usually a tree-like search that does not keep a table of reached states\n    -\tSearch to the deepest level of the tree (where there are no successors), then search “backs up” to the next deepest node with unexpanded successors\n    -\tComplete (for finite state spaces); not cost-optimal (returns first solution it finds)\n      -\tIncomplete when:\n        -\tacyclic state spaces, end up expanding the same state many times via different paths but will eventually systematically explore the entire space\n        -\tcyclic state space, can get stuck in infinite loop\n        -\tinfinite state spaces – depth first search is not systematic (can get stuck going down infinite paths even if there are no cycles)\n  -\tBacktracking search (variant of depth-first search uses less memory): \n    -\tOne successor is generated at a time rather than all successors and each partially expanded node remembers which successor to generate next\n    -\tSuccessors are generated by modifying current state description instead of allocating memory for a new state\n      -\tResults in one state description\n    -\tCan maintain an efficient set data structure\n    -\tMust be able to undo each action when we backtrack\n    -\tGood for problems with large state descriptions (robotic assembly)\n\n\n## Module 3 Lecture Notes\n\nSection 3_3\n  -\tGraph vs. tree search\n    -\tGraph search: checks for redundant paths, more memory, faster bc checks for redundant paths\n    -\tTree-like search: does not check for redundant paths, less memory and slower bc doesn’t check for redundant paths\n  -\t3 types of queues used in search algorithms:\n    -\tPropriety queue: pops the node with minimum cost (Best-first search)\n    -\tFIFO queue: pops the node that was added to the queue first (Breadth-first search)\n    -\tLIFO queue: pops the most recently added node (Depth-first search)\n\n  -\tBest-first search: choose node n, with minimum value of some evaluation function f(n)\n    - on each iteration, we choose a node on the frontier with minimum f(n) value\n    - return it is the state is a goal state, otherwise apply expand to generate child nodes\n    - each child node is added to frontier if not reached before or re-added if it is now being reached with path of lower path cost than any previous path\n    - finally algorithm returns either failure or a node that represents a path to the goal\n\nsection 3_4\n  -\tDepth-limited search: prevents depth-first from going down an infinite path by using depth limit, l, and treat all nodes at depth l as if they had no successors\n    -\tIf we choose a bad l, it will fail to reach the solution so it is incomplete\n    -\tDiameter of the state space: a depth limit that leads to a more efficient depth-limited search, but most of the time, we will not know a good depth limit until we have solved the problem\n  -\tIterative deepening search:\n    -\tSolves problem of picking a good l value by trying all values until 1) a solution is found or 2) depth limited search returns the failure value instead of a cutoff value\n    -\tOptimal for when all actions have the same cost; complete on finite acyclic state spaces or finite state when we check nodes for cycles all the way up the path\n    -\tIterative deepening repeats all the previous level – saves memory at the cost of more time compared to breadth-first search that stores all the nodes in memory\n    -\tGenerally iterative deepening preferred when:\n      -\tthe search state space is larger than can fit in memory\n      -\tdepth of the solution unknown\n  -\tBidirectional search: simultaneously searches forward from initial state and backwards form the goal state because  is much less than \n    -\tSolution = when frontiers collide\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n  -\tInformed search: strategy that uses domain-specific hints; find solutions more efficiently than uninformed\n    -\tHeuristic function h(n) is the estimated cost of the cheapest path from node n to goal state\n  -\tGreedy best-first search: form of best-first search that expands the nodes with lowest h(n) value – node that appears the closest to the goal\n    -\tEvaluation function f(n) = h(n)\n    -\tComplete in finite state spaces, not in infinite ones\n  -\tA* search: best-first search that uses 1) path cost from initial state to node n and 2) estimated cost of the shortest path from n to a goal state\n    -\tcomplete and cost-optimal and optimally efficient depending on the heuristic\n      -\tadmissible heuristic: never overestimates the cost to reach a goal\n    -\tnon-cost-optimal: even if there is one cost-optimal path that h(n) is admissible for, solution won’t be found \n        -\tweighted A* search (detour index): apply heuristic value more heavily by multiplying a number (multiplied applied to straight-line distance to account for road curvature)\n      -\tconsistent vs. inconsistnet heuristic:\n        - consistent heuristic:  first time we reach a state it will be on an optimal path, never have to re-add to frontier and never change entry in reached\n        -\tinconsistent heuristic: end up with multiple paths reaching the same state, end up with multiple node for that state in the frontier – costs time and space\n        -\tevery consistent heuristic is admissible but not vice versa – A* is cost-optimal thus has consistent heuristic\n        -\tA* with consistent heuristic is optimally efficient\n    -\tEfficient bc prunes away search tree nodes that are not necessary\n  -\tSearch contours: visualize a search by drawing topographic map\n    -\tUniform-cost search: contours of g-cost that are circular around the state state and spread out equally in all directions\n    -\tA* search: g+h bands stretch to goal state and become more narrow focus around optimal path\n  -\tSuboptimal search algorithms\n    -\tBounded suboptimal search: look for a solution that is guaranteed to be in a constant factor W or the optimal cost\n    -\tBounded-cost search: looks for solutions whose cost is less than some constant C\n    -\tUnbounded-cost search: accept a solution of any cost (as long as can quickly find it)\n      -\tSpeedy search: greedy best-first search version that heuristic is estimated number of actions required to reach a goal, regardless of cost\n        - same cost actions = greedy best-first search\n        - diff costs, it finds solution quickly but with high cost\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n  -\tHeuristic functions\n    -\tCity block distance = Manhattan distance: sum of vertical and horizontal distances\n    -\tEffective branching factor (b*): characterize the quality of a heuristic\n      -\tN+1 = 1 + b* + (b*)^2 + …+(b*)^d\n      -\tEffective depth: can be reduced by a constant  A* pruning with a given heuristic so total cost is  instead of \n    -\tDominates: a heuristic function dominates another one if it will be more efficient in the search \n    -\tRelaxed problem: a problem with fewer restriction on action (state space graph of relaxed problem is a supergraph of original state space bc restriction removal creates more edges)\n      -\tMay provide better solution if added edges have shortcuts\n      -\tCost of optimal solution in a relaxed prob is admissible h for the original\n      -\tAbsolver: program that generates heuristics from problem definitions using the “relaxed” problem and other techniques\n    -\tSubproblem: admissible heuristics can be derived from solution cost of subproblem of larger problem\n    -\tPattern database: store exact solutions for all possible subproblems, and compute admissible heuristic by looking up the subproblem in the database\n    -\tDisjoint pattern database: break into two subproblems and add them up\n  -\tHeuristics with landmarks\n    -\tPrecomputation: precompute the optimal path costs—only need to be done once\n      -\tLandmark points: choose a few and precompute the path from vertex v to L\n        -\tBest to choose ones that are spread out and not too close around the perimeter of the graph (centroid)\n    -\tShortcuts: artificial edges in the graph that define a optimal multi-action path\n    -\tDifferential heuristic: landmark that is beyond the goal – goal is on the optimal path from n to landmark then subtract the last part of the path\n  -\tImproving search\n    -\tMetalevel state space: each state captures the internal state of a program that is searching in an ordinary state space – each state on path is object-level search tree\n    -\tObject-level state space: map of Romania\n    -\tMeta-level learning algorithm: can learn from missteps and avoid exploring unpromising subtrees\n      -\tLearning goal is to minimize the total cost of solving problem by using more computational expense and path cost\n\n\n## Module 4 Lecture Notes\n\nAdditional textbook stuff\n  -\tPage 202: Memory-bounded search \n    -\tSolution is to keep reference counts of the number of times a state has been reached\n    -\tBeam search: limits frontier size\n    -\tIterative-deepening A* search\n    -\tRecursive best-first search\n      -\tBack-up value\n    -\tMemory related algorithms\n      -\tMemory bounded A* (MA*)\n      -\tSimplified memory bounded A* (SMA*)\n    -\tBidirectional heuristic search\n      -\tFront-to-end search\n      -\tFront-to-front search\n\n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n  -\tMinimax search: for games with multiple outcome scores; recursive algorithm that searches all down, and then backs up minimax valuers through the tree; a type of depth-first search be \n    -\tPly: one player moves\n    -\tMinimax value: utility (max) of being in that state assuming both players play optimally from beginning to end\n    -\tMinimax decision: at root, action a1 will be the optimal choice with highest minimax value\n    -\tAlliances: multiplayer games usually have alliances (formal or informal) – alliances can be a natural consequence of optimal player strategies\n  -\tAlpha-beta pruning\n    -\tPruning: compute correct minimax even by cutting half the branches\n    -\tAlpha-beta pruning: technique we use to prune  best case; random move ordering roughly  for moderate b\n      -\tHighly dependent on the order nodes are examined – not prune any if worst successors generated first\n      -\tCan solve a tree twice as deep using alpha-beta pruning as minimax\n      -\tKiller moves: best moves\n      -\tCan also use combination with iterative deepening\n      -\tTranspositions: different permutation of move sequence that result same position\n        -\tTransposition table: record heuristic values\n    -\tType A vs. Type B strategy:\n      -\tType A: consider all moves to a certain depth (wide but shallow)\n      -\tType B: ignore bad looking moves, following promising paths all the way (deep by narrow) – world champion level play across some games (chess)\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n  -\tHeuristic Alpha-beta tree search\n    -\tUse heuristic evaluation function: returns estimate of expected utility of state for player (can treat nonterminal nodes as terminal) \n      -\tComputation can’t take too long \n      -\tShould be strongly correlated with actual wining chances\n      -\tCan cause algorithm to be unnecessarily certain about final outcomes\n      -\tFeatures: define categories of states that have the same values for all the features\n      -\tA good evaluation for states is expected value; usually weighted linear function\n        -\tMaterial value: assign a value for each piece in chess\n    -\tShould only be applied to quiescent positions where no pending move (capturing queen) that would drastically swing evaluation\n      -\tQuiescent search is sometimes restricted to consider only specific moves (like capture moves)\n    -\tHorizon effect: program is facing a move that can cause serious damage\n      -\tcan mitigate using singular extension: moves that are “clearly better” than all other moves even when search would be cut off normally\n    -\tUse cutoff test: returns true for terminal states, otherwise free to decide when to stop search (based on depth and any other property)\n      -\tModify alpha-beta search to call the evaluation function and see whether to cut off the search or not\n  -\tForward pruning: prunes poor moves, but might make mistake of pruning good ones\n    -\tBeam search: an approach to forward pruning where you consider only the “beam” of the n best moves (based on evaluation function) rather than all possible moves – this does not guarantee that the best move will not be pruned away\n    -\tProbabilistic cut: forward-pruning of alpha-beta search using stats from prior experiences to increase the chances of not prune best move \n    -\tLate move reduction: assumes that move ordering has been done well, so later moves are less likely to be good moves – so reduce depth to which we search these moves (saves time), if a reduced search returns a value above the current alpha, rerun search with full depth\n  -\tSearch vs. lookup: many game-playing programs use table lookup rather than searching for opening and ending of a game because it is faster?\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n  -\tMonte Carlo tree search: the value of a state is estimated as the avg utility over multiple simulations (playout/rollout) of complete games\n    -\tFor games with win/lose outcomes, “average utility” = “win percentage”\n    -\tPlayout policy: biases moves towards good ones providing useful information\n    -\tPure monte carlo search: perform N simulations starting from current state of game and track which moves from the current position has the highest win %\n    -\tSelection policy: focuses computational resources on tree’s important parts\n      -\tTwo factors that need to be balanced\n        -\tExploration of states that have had a few playouts\n        -\tExploitation of states that have done well in past playouts\n      -\tMonte carlo does the selection policy by maintaining a search tree and grows it on each iteration (steps are shown below)\n        -\tSelection: starting at tree root, choose a node, go to successor node, and keep repeat\n        -\tExpansion: grow search tree by generate new child of the node\n        -\tSimulation: perform playout form new generated child node\n        -\tBack-propagation: use simulation result to update all nodes up to root\n        -\t**we repeat 4 steps multiple times until time expires, then return move with highest playouts\n      -\tUpper confidence bound applies to trees (UCT): ranks each move based on upper CI formula, UCBI\n    -\tMonte carlo has an advantage over alpha-beta for games like GO where branching factor is very high (alpha beta can’t search deep enough) or when difficult to define a good evaluation function\n      -\tAlpha beta – choose a wrong node is done for\n      -\tMonte carlo --  takes an aggregate of many playouts, so not as vulnerable to single error\n    -\tMonte carlo has a disadvantage when it is likely that single move can change the course of a game (stochastic nature means it might fail to consider the move)\n  -\tEarly playout termination: for games that can last many moves\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n  -\tStochastic games: include a random element in games\n    -\tChance nodes: included in addition to max and min nodes\n      -\tExpected value = average over all possible outcomes of chance nodes\n      -\tExpectiminimax value: games with chance nodes (generalization of minimax for deterministic games)\n        -\tMin and max nodes are same\n  - Chance nodes – compute expected value (sum of value over all outcomes weighted by probability of each action)\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n  -\tProbability theory: what agent should believe based on evidence\n  -\tUtility theory: what agent wants\n    -\tUtility function: possessed by agent whose preferences between lotteries are consistent with set of axioms \n    -\tMultiattribute utility theory: deal with utilities that depend on several distinct attributes of states\n      -\tStochastic dominance is useful for making unambiguous decisions even without precise utility values for attributes\n  -\tDecision theory: put two together to describe what agent should do\n  -\tRational agent: use decision theory for system that make decisions by considering all possible actions and choosing one with best expected outcome\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n included above \n\n## AIMA Chapter 16.3 Utility Functions\n included above \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n  -\tEasy to formulate problem into CSP, solvers are fast and efficient, can see why a assignment is not a solution\n  -\tCSP 3 components:\n    -\tX set of variables\n    -\tD set of domains, one for each variable\n    -\tC set of constraints specifying allowable combinations of values\n      -\tEach constraint = <scope, rel>\n        -\tRel = relation that defines the values that variables can take on\n  -\tAssignment of values to variables\n    -\tConsistent/legal assignment: assignment does not violate constraints\n    -\tComplete assignment: every variable assigned a value\n    -\tComplete, consistent assignment = solution\n    -\tPartial assignment: leaves some variable assigned\n    -\tPartial solution: consistent partial assignment\n  -\tConstraint graph: help to visualize CSP\n  - Constraints: represented in a constraint hypergraph that consists of nodes(circles) and hypernodes(squares) with n-ary constraints\n    -\tPrecedence constraint: task T1 must occur before task T2\n    -\tDisjunctive constraint: two actions must not overlap in time\n    -\tLinear constraints: each variable appears in linear form\n    -\tNonlinear constraints: no algorithm exists bc problem is undecidable\n    -\tUnary constraint: restricts value of a single variable (south Australians won’t tolerate green)\n    -\tBinary constraint: relates two variables (SA =!= NSW)\n      -\tBinary CSP: has only unary and binary constraints\n    -\tGlobal constraint: constraint with arbitrary number of variables, does not need to involve all variables in a problem (alldiff)\n      -\tCryptarithmetic puzzle: each letter in puzzle represent different digit\n      -\tSudoku: alldiff\n    -\tPreference constraint: indicate which solutions are preferred\n      -\tConstrained optimization problem (COP): CSP with preferences that can be solved with optimization search methods (path-based or local)\n        -\tLinear programs are one class\n      -\tResource constraint (almost constraint): no more than 10 personnel are assigned in total in a scheduling problem\n        -\tBounds propagation: domains represented by upper and lower bounds for resource limited problems (domains for number of passengers on flights F1 and F2\n  -\tCSP variables\n    -\tDiscrete, finite domains (map coloring and scheduling with time limits)\n    -\tDiscrete, infinite domain (no deadline on job-scheduling problem)\n    -\tContinuous domains: common in real world and in operations research (scheduling experiment son Hubble space telescope)\n      -\tLinear programming problems: constraints must be linear equalities or inequalities\n  -\tConvert n-ary CSP to binary\n    -\tUse dual graph transformation: create new graph one variable for each constraint in original, one binary constraint for each pair of constraints in original\n    -\tGlobal constraints are somtimes better than binary: easier, less error-prone, efficient can use speical-purpose inference algorithm\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n  -\tConstraint propagation: using constraints, reduce number of legal value sfor a variable – can reduce the legal values for another variable, etc.\n    -\tThis leaves fewer choices to consider when choosing next variable assignment\n    -\tA form of preprocessing that can sometimes solve the problem\n  -\tLocal consistency: treat each variable as a node in a graph and binary constraint = edge; enforcing local consistency in each part of the graph causes inconsistent values to be eliminated through graph\n    -\tTypes of local consistency\n      -\tNode consistent: all the values in the variable domain satisfy variable’s unary constraints\n        -\tIf not, you can eliminate unary constraints by reducing domain of variables with unary constraints or transform all n-ary constraints into binary\n      -\tArc consistent: every value in domain satisfies variable’s binary constraints\n        -\tAC-3: maintains a queue of arcs to consider; pops off arbitrary arc from queue and makes it Xi consistent wrt Xj; if it changes anything, it adds all the neighbors of Xi; continue and we will either get a failure or remove values until there are no more arcs in the queue\n    -\tThis is faster than the original CSP bc it is faster to search since variables have smaller domains\n    -\tComplexity:   and worst case  CSP with n variables, domain size at most d, and c binary constraints (arcs)\n    -\tSolves basic sudoku problems\n      -\tPath consistency: tighten binary constraints by implicit constraints that are inferred by looking at triples of variables\n      -\tK-consistency: a stronger form of propagation where consistent for any set of k-1 variables and for any consistent assignment to any kth variable\n        -\t1-consisitency: given {} we can make a set of 1 variable consistent\n        -\t2-consistency: arc consistency\n        -\t2-consistency: path consistency (in binary constraint graphs)\n      -\tStrongly k-consistent: k-consistent and (k-1) consistent and (k-2) consistent…to 1-consistent\n        -\tCSP with n nodes = strongly n-consistent (k=n)\n        -\tSolve from X1 (1-consistent) and then X2 (2-consistent) then X3 (3-consistent)\n      -\tBounds consistent: for every variable X and for both lower and upper bound values of X there is some Y that satisfies the constraint between X and Y for every variable Y\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n  -\tCan finish constraint propagation and still have variables with multiple possible values, then we must resort to searching for a solution\n  -\tCSPs are commutative: order of application of set of actions does not matter\n  -\tBacktracking search: keeps a single representation of a state (assignment) and alters the representation of that instead of creating a new one\n    -\tCan be improved using domain-independent heuristics taking advantage of the factored representations of CSPs\n    -\tVs. uninformed search algorithms in chapter 3 can only be improved by domain-specific heuristics\n  HOW TO IMPROVE BACKTRACKING page 383\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n  -\tChoose conflicted variable to change the value to something that brings closer to solution\n    -\tMini-conflicts heuristic: select a value that results in the minimum number of conflicts with other variables\n    -\tTabu search: keeps small list of recently visited states and forbids algorithm to go back to those states\n    -\tConstraint weighting: keep search on the important constraints – at each step of search, algorithm can choose a variable/value pair of which to change resulting in the lowest total weight of all violated constraints. Weights then r adjusted by incrementing weight of each constraint that is violated by current assignment\n      -\t2 benefits\n        -\tAdds topography to plateau\n        -\tMake sure you can improve on current state\n        -\tAdds learning bc difficult constraints are assigned higher weights\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n  -\tIndependent subproblems: subproblems are not dependent\n  -\tIndependence: can be confirmed by finding connected components of the constraint graph; each component corresponds to a subproblem CSP\n  -\tCompletely independent subproblems are rare\n    -\tA constraint graph: tree when any 2 variables are connected by one path\n  -\tDirectional arc consistency (DAC): every Xi is arc-consistent with each Xj for j>i\n    -\tA DAC we can just go down list of variables and choose remaining values because each edge from parent to child is arc-consistent already  this means we don’t have to backtrack and can linearly move through variables\n    -\tA tree with n nodes has n-1 edges so can make graph DAC in  steps which must compare up to d domain values for 2 variables gives total  time\n  -\tSolving a tree-structured CSP:\n    -\tTopological sort: pick variable at root and choose an ordering of variable that each variable is after its parent in the tree\n  -\tReducing constraint graph to a tree \n    -\tCutset conditioning\n      -\tAssign values to some variables so remaining variables form a tree\n      -\tDelete values from domains that are inconsistent\n      -\tCutset conditioning: General algorithm as follows for CSP\n        -\tChoose subset s of CSP’s variables such that constraint graph is a tree after s is removed – s is a cycle cutset\n        -\tFor each possible assignment to the variables in S that satisfy all constraints\n    -\tRemove any values that are inconsistent from domains\n    -\tReturn it together with s assignment if there is a still a possible solution\n      -\tRuntime is  \n  -\tTree decomposition: transform original graph into tree where each node in tree consist of set of variables that \n    -\tDecomposition must satisfy 3 requirements\n      -\tEvery variable in original problem appears in at least one of tree nodes\n      -\t2 variables are connected by constraint in the original problem, must appear together in at least 1 node\n      -\tIf variable appears in 2 nodes, must appear in every node along path connecting those node\n    -\tOnce have tree-structured graph apply tree-csp-solver to get solution in in  time – this is efficient as long as d is small\n      -\tN = number tree nodes\n      -\tD = size of largest domain\n  -\tValue symmetry: 3 colors to 3 regions\n  -\tSymmetry-breaking constraint: reduce search space by breaking symmetry in assignments and imposing an arbitrary ordering constraint\n\n\n## Module 6 Lecture Notes\n\n  - Waltz/Mackworth Constraint Propagation Algorithm:\n    1. assign every node in graph a set of all possible val\n    2. repeat until no change in set of values for any node\n      - for each node i\n        - for each neighbor j\n          - remove any value from i that is not arcconsistent with j\n  - AC-3 inefficiencies:\n    - At each iteration, we only need to examine those Xi where at least one neighbor of Xi has lost a value in the previous iteration\n    - If Xi loses value bc of arc inconsistencies w/Yj, we don’t need to check Yj on the next iteration\n    - Remove value on Xi can only make Yj arcinconsistent with respect to Xi itself\n      - only need to check that (j,i) is still arcconsistent\n  - Worst Case Complexity:\n    - All nodes can be connected to every other node, each of n nodes must be compared against n-1 other nodes, so total # of arcs is 2*n*(n-1) --> O(n^2)\n    - If there are d values, checking arc (i,j) takes O(d^2) time\n    - Each arc (i,j) can only be inserted into the queue dx\n    - Worst case complexity: O(n^2d^3 )\n      - (For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3 ))\n\n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n-\tIntelligent agents need knowledge about world to reach good decisions\n-\tKnowledge is contained in agents in the form of sentences in a knowledge representation language that are stored in a knowledge base\n-\tKnowledge-based agent: composed of knowledge base and inference mechanism\n  -\tOperates by storing sentences about world in knowledge base\n  -\tUsing inference mech to infer new sentences\n  -\tUse sentences to decide what action to take\n-\tRepresentation language: defined by syntax and semantics\n  -\tSyntax: specifies structure of sentences\n  -\tSemantics: defines truth of each sentence in each possible world/model\n-\tEntailment: a sentence alpha entails beta if beta is true in all worlds where alpha is true\n  -\tValidity of sentence alpha -> beta\n  -\tAnd satisfiability of alpha ^ not beta\n-\tInference: process of deriving new sentences from old ones\n  -\tSound inference algorithms: derive only entailed sentences\n  -\tComplete algorithms: derive all sentences that are entailed\n-\tPropositional logic: language with propositional symbols and logical connectives\n  -\tIt can handle propositions that are known true, known false, and unknown\n-\tSet of possible models with fixed propositional vocabulary is finite, so entailment can be checked by enumerating models\n  -\tEfficient model-checking inference algorithms include __ and often solve large problem quickly\n    -\tBacktracking\n    -\tLocal search methods\n-\tInference rules are patterns of sound inference used to find proofs\n  -\tResolution rule = complete inference algorithm for knowledge bases that are expressed in conjunctive normal form (CNF)\n  -\tNatural reasoning algorithms in Horn form for knowledge bases\n    -\tForward chaining: determine if proposition symbol, q—the query, is entailed by a knowledge base of definite clauses (begins from known facts in knowledge base)\n    -\tBackward chaining: works backwards from the query (if query q is true, no work is needed); otherwise find implications in knowledge base whose conclusion is q and the words back down the graph until it reaches set of known facts, A and B that is basis for proof\n- Goal-directed reasoning – useful to answer specific questions\n\n\n## AIMA Chapter 7.2 The Wumpus World\n included above \n\n## AIMA Chapter 7.3 Logic\n included above \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n included above \n\n## AIMA 7.5 Propositional Theorem Proving\n included above \n\n## Module 7 Lecture Notes\n\n  - Proof by Resolution\n    - resolution: yields complete inference algorithm when coupled with any complete search algorithm\n  - Conjuctive Normal Form (CNF)\n    1. Eliminate ⇔ by replacing a ⇔ β with (a ⟹ β) ⋀ (β ⟹a)\n    2. Eliminate ⟹ by replacing a ⟹ β with ¬a ⋁ β\n    3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n    4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible. \n  - Resolution Algorithm: inference procedures use the principle of proof by contradiction (is complete)\n      - To show KB⊨a then we can show that KB ⋀ ¬a is unsatisfiable\n        1. Convert (KB ⋀ ¬a) into CNF\n        2. Apply the resolution rule to the resulting clauses\n        3. Resolve every pair that contains complementary literals to produce a new clause\n        4. If that new clause isn’t already present, then add it to the set\n        5. Continue the process until one of two things happens:\n          - There are no new clauses that can be added. In this case, the KB does not entail a\n          - Two clauses resolve to yield the empty clause, in which case the KB does entail a\n  - Definite clause: disjunction of literals where exactly 1 is positive\n  - Horn Clause: disjunction of literals where at most 1 is positive\n    - includes definite clauses\n    - and clauses with no positive literals\n  - Forward chaining and Backward chaining\n    - forward chaining: kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so\n    - backward chaining: works backwards from a query. If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n      - a form of goal-directed reasoning\n\n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}