{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "a5809c2b-af0d-4512-c535-90237128cc99"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "06369eda-2db4-446e-ab57-781f6562fbea"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "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",
        "to learn about human thought: introspection, psychological experiments, brain imaging \\n\n",
        "Agents have 5 requirements: \\n\n",
        "\\t be able to work autonomously \n",
        "\\t perceive the environment they're in\n",
        "\\t keep acting over a time period\n",
        "\\t be adaptable\n",
        "\\t create goals and pursue them \\n\n",
        "AI involves rational agents. Using this approach is good because 1) it is relatively general since accurate inference is just one way to be rational\n",
        "and 2) easy to define mathematically so we can develop on the approach.\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",
        "Turing believed that human actions are too complex for machines to ever perfectly simulate. This has been the source of debate by many people -- that \n",
        "machines will always have incomplete information because they aren't human (incompleteness theorem).\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" \n",
        "Turing and others believe that we haven't defined \"think\" properly but we can just assume that everyone, including machines, thinks. \\n\n",
        "Chinese room argument: regardless of how intelligently a computer behaves, it doesn't generate understanding so a computer will never have a mind of its own \\n\n",
        "Biological naturalism: humans think based on physical processes in neurons, so Searle argues that humans also don't have understanding because the neurons don't have understanding\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "Agents: humans-(sensors: eyes/ears, actuators: hands, legs), software-(sensors: human input, file contents, actuators: write files, display info) \\n\n",
        "\\t the action taken will depend on 1) built-in knowledge and 2) the percept sequence. NOT future actions/something that hasn't yet been received by sensor\n",
        "\\t the agent function is math because it calculates what a percept has received and converts it to action \n",
        "\\t the agent program actually implements this action \\n\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "When we think about designing performance measures, we should focus on evaluating agents based on what they achieve (i.e. # of clean squares), \n",
        "not on their behavior (i.e. how much dirt is removed).\n",
        "Rationality--there is: \\n\n",
        "\\t performance measure \n",
        "\\t prior knowledge of environment\n",
        "\\t actions for the agent\n",
        "\\t historical percept sequence \\n\n",
        "Perfection tries to get best actual performance, but rationality tries to get best expected performance. Rational agents are not guaranteed to find optimal solutions.\\n\n",
        "In order to reach autonomy, we must provide the agent with help at the beginning but also provide it with the ability to learn \n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "<b>PEAS</b>: Performance Measures,Environment, Actuators, Sensors. These make up a task environment. \\n\n",
        "<b>Fully Observable</b>: agent knows complete environment at any time, so it doesn't need to keep an internal state \\n\n",
        "<b>Partially Observable</b>: agent only knows part of environment (i.e. card game, image analysis) \\n\n",
        "<b>Unobservable</b>: agent has no sensors at all \\n\n",
        "<b>Single Agent</b> \\n\n",
        "<b>Multiagent</b>: competitive (i.e. game) vs cooperative(i.e. taxi driver and another vehicle) \\n\n",
        "<b>Deterministic</b>: same result every time. we use only the current state and action to determine the next state \\n\n",
        "<b>Nondeterministic/Stochastic</b>: could have different result every time. most situations are this because nothing is ever fully certain. Stochastic has exact probabilities, but nondeterministic is more qualitative \\n\n",
        "<b>Episodic</b>: agent uses a percept to take 1 action. the next \"episode\" doesn't depend on the previous ones. (i.e. checking each item in line for defects) \\n\n",
        "<b>Sequential</b>: agent's action will affect the future actions. rewards could come only after many actions \\n\n",
        "<b>Static</b>: environment can't change while agent decides what action to take \\n\n",
        "<b>Dynamic</b>: environment is continuously changing (i.e. taxi driving) \\n\n",
        "<b>SemiDynamic</b>: environment isn't continuously changing, but performance measure is (i.e chess with clock) \\n\n",
        "<b>Discrete</b>: environment state, time, percepts, actions (i.e. chess) \\n\n",
        "<b>Continuous</b>: taxi driving \\n\n",
        "<b>Known</b>: agent knows the outcomes/outcome probabilities \\n\n",
        "<b>Unknown</b>: agent has to learn as it progresses through environment \\n\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "A big challenge is creating programs that perform rationally AND are small in size instead of needing to look up percepts in a large table \\n\n",
        "4 agent programs generate actions: simple reflex, model-based reflex, goal-based, utility-based \\n\n",
        "Learning agents: \\n\n",
        "\\t learning element: makes improvements to the agent by learning from percepts \n",
        "\\t performance element: decides the actions taken by taking in percepts\n",
        "\\t critic: provides feedback to the agent about the percept received so performance element can be improved\n",
        "\\t the reward can be the feedback provided to the agent by the critic\n",
        "\\t problem generator: suggests new actions so that agent can try new (maybe suboptimal) actions that may lead it to a better solution\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"Turing test\": \"sees if machine can think. computer needs: NLP, knowledge representation, automated reasoning, ML\",\n",
        "\"total Turing test\": \"machine has to interact with the world. computer also needs: computer vision, robotics\",\n",
        "\"introspection\": \"personal thoughts as they occur\", \n",
        "\"psychological experiments\": \"see a person's actions\",\n",
        "\"brain imaging\": \"see a brain's actions\",\n",
        "\"cognitive science\": \"AI + psychology so that we can test if computers can act like human mind\",\n",
        "\"syllogisms\": \"reasoning that can't be disputed. Aristotle. initiated the term Logic\",\n",
        "\"probability\": \"allows us to perform reasoning when we are unsure of the information\",\n",
        "\"agent\": \"perceive environment using sensors. uses actuators to act in the environment\",\n",
        "\"rational agent\": \"maximizes performance measure based on percept sequence + built-in knowledge. With uncertainty in problem--best expected performance measure\",\n",
        "\"percept\": \"what the sensors are actually receiving\",\n",
        "\"percept sequence\": \"all of the percepts ever received by the agent\",\n",
        "\"agent function\": \"takes percept sequence and executes an action. This is the agent's behavior\",\n",
        "\"agent program\": \"takes the current percept sequence and actually implements the agent function\",\n",
        "\"agent architecture\": \"the actual sensors and actuators. agent = architecture + program\",\n",
        "\"standard model\": \"providing an objective to the agent\",\n",
        "\"omniscience\": \"agent knows what the actual outcome will be if it performs an action--impossible\",\n",
        "\"limited rationality\": \"can't always make perfectly optimal move; sometimes too much computational power so we settle for less\",\n",
        "\"value alignment problem\": \"sometimes what the human wants the machine to do is different from the objective fed to machine\",\n",
        "\"weak AI\": \"machines can act like they are intelligent and actually thinking\",\n",
        "\"strong AI\": \"machines are actually intelligent and thinking for themselves\",\n",
        "\"Good Old-Fashioned AI (GOFAI)\": \"very simple logical agent (doesn't account for advances such as probabilistic reasoning/deep learning)\",\n",
        "\"qualification problem\": \"too hard to capture all behavior with a set of rules\",\n",
        "\"embodied cognition\": \"have to look at entire system, not just the brain. because everything takes place in an environment, not alone\",\n",
        "\"biological naturalism\": \"a mental state is caused by physical neurons\",\n",
        "\"consciousness\": \"being aware of the environment and yourself\",\n",
        "\"qualia\": \"experiences. We don't know if machines have this\",\n",
        "\"consequentialism\": \"we use the consequences of agent's behavior to evaluate it\",\n",
        "\"performance measure\": \"takes the states of the environment based on the agent's actions and evaluates it\",\n",
        "\"information gathering\": \"agent performs actions so future percepts are informed and changed accordingly. Also explores the environment\",\n",
        "\"autonomy\": \"agent should be learning to make up for having just partial knowledge\",\n",
        "\"task environments\": \"problem. an agent is the solution to this problem\",\n",
        "\"environment class\": \"set of environments to draw from to test agent performance\",\n",
        "\"Simple Reflex Agent\": \"agent takes action based on <b>current</b> percept only. Environment must be fully observable. If not, randomization of actions might work\", \n",
        "\"condition-action rule\": \"if something happens, take this action\",\n",
        "\"transition model\": \"1) effects of agent's actions and 2) how world is evolving regardless of what agent does\",\n",
        "\"sensor model\": \"how the environment state is represented in the percepts\",\n",
        "\"Model-based reflex agents\": \"transition + sensor models. Keeps internal state so that current state can be updated with more information.\",\n",
        "\"goal\": \"desired situation\",\n",
        "\"Goal-based agents\": \"instead of condition-action rule, takes model-based reflex agent and uses goal to determine action.\",\n",
        "\"utility\": \"performance measure that allows environment states to be compared\",\n",
        "\"Utility-based agents\": \"Allows agent to decide which goal to pursue by taking action that maximizes the expected utility\",\n",
        "\"Model-free agent\": \"decides what action to take but doesn't know what happens to environment by taking that action\",\n",
        "\"atomic representation\": \"state is a box and has no structure (i.e drive from one city to next city)\",\n",
        "\"factored representation\": \"state is split into variables and attributes with values (i.e. gas level, is headlights on or off)\",\n",
        "\"structured representation\": \"state has variables/attributes that are related to each other, so we have to also represent the relations\",\n",
        "\"expressiveness\": \"structured is the most, atomic is the least\",\n",
        "\"localist representation\": \"each concept has a one-to-one mapping with where it is stored in memory\",\n",
        "\"distributed representation\": \"each concept is stored in multiple locations in memory. More robust than localist\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "1bbe96d5-a8b8-4e97-c2ae-7c78430ddc9b"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nto learn about human thought: introspection, psychological experiments, brain imaging \n\nAgents have 5 requirements: \n\n\t be able to work autonomously \n\t perceive the environment they're in\n\t keep acting over a time period\n\t be adaptable\n\t create goals and pursue them \n\nAI involves rational agents. Using this approach is good because 1) it is relatively general since accurate inference is just one way to be rational\nand 2) easy to define mathematically so we can develop on the approach.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nTuring believed that human actions are too complex for machines to ever perfectly simulate. This has been the source of debate by many people -- that \nmachines will always have incomplete information because they aren't human (incompleteness theorem).\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \nTuring and others believe that we haven't defined \"think\" properly but we can just assume that everyone, including machines, thinks. \n\nChinese room argument: regardless of how intelligently a computer behaves, it doesn't generate understanding so a computer will never have a mind of its own \n\nBiological naturalism: humans think based on physical processes in neurons, so Searle argues that humans also don't have understanding because the neurons don't have understanding\n\n\n## AIMA 2.1 Agents and Environments\n\nAgents: humans-(sensors: eyes/ears, actuators: hands, legs), software-(sensors: human input, file contents, actuators: write files, display info) \n\n\t the action taken will depend on 1) built-in knowledge and 2) the percept sequence. NOT future actions/something that hasn't yet been received by sensor\n\t the agent function is math because it calculates what a percept has received and converts it to action \n\t the agent program actually implements this action \n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nWhen we think about designing performance measures, we should focus on evaluating agents based on what they achieve (i.e. # of clean squares), \nnot on their behavior (i.e. how much dirt is removed).\nRationality--there is: \n\n\t performance measure \n\t prior knowledge of environment\n\t actions for the agent\n\t historical percept sequence \n\nPerfection tries to get best actual performance, but rationality tries to get best expected performance. Rational agents are not guaranteed to find optimal solutions.\n\nIn order to reach autonomy, we must provide the agent with help at the beginning but also provide it with the ability to learn \n \n\n## AIMA 2.3 The Nature of Environments\n\n<b>PEAS</b>: Performance Measures,Environment, Actuators, Sensors. These make up a task environment. \n\n<b>Fully Observable</b>: agent knows complete environment at any time, so it doesn't need to keep an internal state \n\n<b>Partially Observable</b>: agent only knows part of environment (i.e. card game, image analysis) \n\n<b>Unobservable</b>: agent has no sensors at all \n\n<b>Single Agent</b> \n\n<b>Multiagent</b>: competitive (i.e. game) vs cooperative(i.e. taxi driver and another vehicle) \n\n<b>Deterministic</b>: same result every time. we use only the current state and action to determine the next state \n\n<b>Nondeterministic/Stochastic</b>: could have different result every time. most situations are this because nothing is ever fully certain. Stochastic has exact probabilities, but nondeterministic is more qualitative \n\n<b>Episodic</b>: agent uses a percept to take 1 action. the next \"episode\" doesn't depend on the previous ones. (i.e. checking each item in line for defects) \n\n<b>Sequential</b>: agent's action will affect the future actions. rewards could come only after many actions \n\n<b>Static</b>: environment can't change while agent decides what action to take \n\n<b>Dynamic</b>: environment is continuously changing (i.e. taxi driving) \n\n<b>SemiDynamic</b>: environment isn't continuously changing, but performance measure is (i.e chess with clock) \n\n<b>Discrete</b>: environment state, time, percepts, actions (i.e. chess) \n\n<b>Continuous</b>: taxi driving \n\n<b>Known</b>: agent knows the outcomes/outcome probabilities \n\n<b>Unknown</b>: agent has to learn as it progresses through environment \n\n\n\n## AIMA 2.4 The Structure of Agents\n\nA big challenge is creating programs that perform rationally AND are small in size instead of needing to look up percepts in a large table \n\n4 agent programs generate actions: simple reflex, model-based reflex, goal-based, utility-based \n\nLearning agents: \n\n\t learning element: makes improvements to the agent by learning from percepts \n\t performance element: decides the actions taken by taking in percepts\n\t critic: provides feedback to the agent about the percept received so performance element can be improved\n\t the reward can be the feedback provided to the agent by the critic\n\t problem generator: suggests new actions so that agent can try new (maybe suboptimal) actions that may lead it to a better solution\n \n\n## Module 1 Lecture Notes\n \n\n\n\n## Module 1 Definitions\n* **Turing test** - sees if machine can think. computer needs: NLP, knowledge representation, automated reasoning, ML\n* **Total turing test** - machine has to interact with the world. computer also needs: computer vision, robotics\n* **Introspection** - personal thoughts as they occur\n* **Psychological experiments** - see a person's actions\n* **Brain imaging** - see a brain's actions\n* **Cognitive science** - AI + psychology so that we can test if computers can act like human mind\n* **Syllogisms** - reasoning that can't be disputed. Aristotle. initiated the term Logic\n* **Probability** - allows us to perform reasoning when we are unsure of the information\n* **Agent** - perceive environment using sensors. uses actuators to act in the environment\n* **Rational agent** - maximizes performance measure based on percept sequence + built-in knowledge. With uncertainty in problem--best expected performance measure\n* **Percept** - what the sensors are actually receiving\n* **Percept sequence** - all of the percepts ever received by the agent\n* **Agent function** - takes percept sequence and executes an action. This is the agent's behavior\n* **Agent program** - takes the current percept sequence and actually implements the agent function\n* **Agent architecture** - the actual sensors and actuators. agent = architecture + program\n* **Standard model** - providing an objective to the agent\n* **Omniscience** - agent knows what the actual outcome will be if it performs an action--impossible\n* **Limited rationality** - can't always make perfectly optimal move; sometimes too much computational power so we settle for less\n* **Value alignment problem** - sometimes what the human wants the machine to do is different from the objective fed to machine\n* **Weak ai** - machines can act like they are intelligent and actually thinking\n* **Strong ai** - machines are actually intelligent and thinking for themselves\n* **Good old-fashioned ai (gofai)** - very simple logical agent (doesn't account for advances such as probabilistic reasoning/deep learning)\n* **Qualification problem** - too hard to capture all behavior with a set of rules\n* **Embodied cognition** - have to look at entire system, not just the brain. because everything takes place in an environment, not alone\n* **Biological naturalism** - a mental state is caused by physical neurons\n* **Consciousness** - being aware of the environment and yourself\n* **Qualia** - experiences. We don't know if machines have this\n* **Consequentialism** - we use the consequences of agent's behavior to evaluate it\n* **Performance measure** - takes the states of the environment based on the agent's actions and evaluates it\n* **Information gathering** - agent performs actions so future percepts are informed and changed accordingly. Also explores the environment\n* **Autonomy** - agent should be learning to make up for having just partial knowledge\n* **Task environments** - problem. an agent is the solution to this problem\n* **Environment class** - set of environments to draw from to test agent performance\n* **Simple reflex agent** - agent takes action based on <b>current</b> percept only. Environment must be fully observable. If not, randomization of actions might work\n* **Condition-action rule** - if something happens, take this action\n* **Transition model** - 1) effects of agent's actions and 2) how world is evolving regardless of what agent does\n* **Sensor model** - how the environment state is represented in the percepts\n* **Model-based reflex agents** - transition + sensor models. Keeps internal state so that current state can be updated with more information.\n* **Goal** - desired situation\n* **Goal-based agents** - instead of condition-action rule, takes model-based reflex agent and uses goal to determine action.\n* **Utility** - performance measure that allows environment states to be compared\n* **Utility-based agents** - Allows agent to decide which goal to pursue by taking action that maximizes the expected utility\n* **Model-free agent** - decides what action to take but doesn't know what happens to environment by taking that action\n* **Atomic representation** - state is a box and has no structure (i.e drive from one city to next city)\n* **Factored representation** - state is split into variables and attributes with values (i.e. gas level, is headlights on or off)\n* **Structured representation** - state has variables/attributes that are related to each other, so we have to also represent the relations\n* **Expressiveness** - structured is the most, atomic is the least\n* **Localist representation** - each concept has a one-to-one mapping with where it is stored in memory\n* **Distributed representation** - each concept is stored in multiple locations in memory. More robust than localist\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",
        "whitespace is meaningful \\n\n",
        "strongly typed: every object has a fixed type (i.e. can't do \"foo\" + 2) \\n\n",
        "dynamically typed: variables don't have a declared type (i.e. can write z=2 and then z=\"hi\") \\n\n",
        "strings are immutable \\n\n",
        "can escape special characters: r'\\n' \\n\n",
        "dictionaries are unordered and use hashing \\n\n",
        "dictionary keys are immutable. if you try to access a key that isn't there, you get error \\n\n",
        "\\t use defaultdict to initialize nonexistent dict values \\n\n",
        "can't have multiple functions with the same name \\n\n",
        "if you're specifying keyword arguments in a function, arguments with assignments (i.e.a=3 instead of 3) have to come at the end \\n\n",
        "*args to accept any # of keywords in a function, *kwargs if those have to be keywords (i.e. name=\"John\" instead of \"John\") \\n\n",
        "you can override magic methods (i.e. default methods for a class such as __add__) \\n\n",
        "iterators are objects with a \\__next\\__() method (if i=iter(x), you can call next(i)) \\n\n",
        "\n",
        "generators: iterators that have a \\__next()\\__ method \\n\n",
        "\\t yield will automatically return a generator\n",
        "\\t a function with yield will run until yield. after it returns the yield, it resumes from where it left off\n",
        "\\t good for using less memory because values are only computed if they are needed \\n\n",
        "\n",
        "\n",
        "tu[-3] --> get the 4th item from the right \\n\n",
        "x = (1,4,5,6,2) \\n\n",
        "x[1:-1] --> (4,5,6) \\n\n",
        "x[1:-1:2] --> (4,6) \\n\n",
        "a = '123'; a[1]=1 --> error \\n\n",
        "a = (1,2,3); a[1]=1 --> error \\n\n",
        "a = [1,2,3]; a[1]=1 --> no error \\n\n",
        "a = ({},{}); a[1][1]=1 --> no error \\n \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 724
        },
        "outputId": "898c6651-59c8-471f-ce4d-34db1b7c21f5"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nwhitespace is meaningful \n\nstrongly typed: every object has a fixed type (i.e. can't do \"foo\" + 2) \n\ndynamically typed: variables don't have a declared type (i.e. can write z=2 and then z=\"hi\") \n\nstrings are immutable \n\ncan escape special characters: r'\n' \n\ndictionaries are unordered and use hashing \n\ndictionary keys are immutable. if you try to access a key that isn't there, you get error \n\n\t use defaultdict to initialize nonexistent dict values \n\ncan't have multiple functions with the same name \n\nif you're specifying keyword arguments in a function, arguments with assignments (i.e.a=3 instead of 3) have to come at the end \n\n*args to accept any # of keywords in a function, *kwargs if those have to be keywords (i.e. name=\"John\" instead of \"John\") \n\nyou can override magic methods (i.e. default methods for a class such as __add__) \n\niterators are objects with a \\__next\\__() method (if i=iter(x), you can call next(i)) \n\n\ngenerators: iterators that have a \\__next()\\__ method \n\n\t yield will automatically return a generator\n\t a function with yield will run until yield. after it returns the yield, it resumes from where it left off\n\t good for using less memory because values are only computed if they are needed \n\n\n\ntu[-3] --> get the 4th item from the right \n\nx = (1,4,5,6,2) \n\nx[1:-1] --> (4,5,6) \n\nx[1:-1:2] --> (4,6) \n\na = '123'; a[1]=1 --> error \n\na = (1,2,3); a[1]=1 --> error \n\na = [1,2,3]; a[1]=1 --> no error \n\na = ({},{}); a[1][1]=1 --> no error \n \n\n## Module 2 Definitions\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",
        "Uninformed: agent has an estimate of the distance to goal \\n\n",
        "Informed: agent can't estimate distance to goal \\n\n",
        "We use abstractions (i.e. represent a trip through cities with just cities and distances, not the speed the car travels, radio on/off, etc) to make it easier to perform actions and get to a solution \\n\n",
        "\n",
        "Vacuum cleaner problem: n cells means n*2^n states \\n\n",
        "Sokoban puzzle: n non-obstacle cells and b boxes, n*n! / b!(n-b)! states \\n\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "State spaces consist of all of the states in the world + the actions that get you from one state to the next \\n\n",
        "Meanwhile, search trees consist of all of the paths between these states and have a goal. \\n \"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "node has 4 components of its data structure: \\n\n",
        "\\t state, parent, action, path cost \\n\n",
        "queue has 4 components: \\n\n",
        "\\t isEmpty, pop, top, add\n",
        "\\t pop removes, top just returns the pop but doesn't remove \\n\n",
        "\n",
        "How do we eliminate redundant paths? \\n\n",
        "\\t 1. remember all the states we have reached already\n",
        "\\t 2. if it is rare to have 2 redundant paths, don't bother tracking them\n",
        "\\t 3. check for only cycles and not all redundant paths \\n\n",
        "\n",
        "To be complete when there is an infinite search space, make sure the search occurrs in a systematic way\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "If task environment: fully observable, deterministic, known environment \\n\n",
        "\\t solution = fixed sequence of actions \\n\n",
        "If task environment: partially observable or nondeterministic \\n\n",
        "\\t solution based on percepts. Could be branching strategy \\n\n",
        "Search problems: \\n\n",
        "<b>Initial state</b>\n",
        "<b>Actions</b>\n",
        "<b>Transition Model</b>\n",
        "<b>Path Cost</b>: sum of all action costs in the path\n",
        "<b>Goal</b> \\n\n",
        "\n",
        "States don't have parents/children/etc; nodes have those \\n\n",
        "\n",
        "Tree Search: doesn't check for redundant paths (longer runtime) \\n\n",
        "Graph Search: checks for redundant paths by checking to see if a node has already been visited before adding it to frontier \\n\n",
        "\n",
        "<b>Uninformed</b> \\n\n",
        "BFS: FIFO frontier -- expand the shallowest node that hasn't been visited yet \\n\n",
        "\\t use if there could be infinite search space and some solutions have short paths and can remove paths fast\n",
        "\\t optimal as long as all actions have the same cost. always complete.\n",
        "\\t early goal test \\n\n",
        "DFS: LIFO (stack) frontier -- expand the deepest node that hasn't been visited yet \\n\n",
        "\\t use if limited space (great algo when you have limited memory) and a lot of solutions have long paths and can fine-tune the search fast \\n\n",
        "\n",
        "Backtracking: DFS, but only generate one successors at a time, not all successors \\n\n",
        "\\t even less memory usage than DF because successors are stored by modifying the current state, \n",
        "not creating a new version of the state \\n\n",
        "\n",
        "Depth-Limited Search: DFS with a depth limit (l). Removes infinite paths \\n\n",
        "\\t if l<d, algo incomplete. if l>d, algo not optimal\n",
        "\\t can use the diameter --largest distance between 2 states-- to set l \\n\n",
        "\n",
        "Iterative deepening: do Depth=Limited, but keep increasing depth limit (l) until fail or solution \\n\n",
        "\\t complete (finite, no cycles) and optimal (all actions have same cost)\n",
        "\\t best uninformed search algo if we have too large of a state space and don't know what we should set d to \\n\n",
        "\n",
        "Bidirectional search: searches from both initial and goal state at the same time \\n\n",
        "\\t solution when the 2 frontiers are the same \\n\n",
        "\n",
        "Uniform-cost search: Priority Queue frontier -- expand node with lowest path cost (g(n)). Djikstra is UCS without a goal \\n\n",
        "\\t late goal test\n",
        "\\t That way, we prioritize paths with lower costs because they get popped off the queue first. \\n\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. Atomic representation\", \n",
        "\"planning agent\": \"Factored or structured representation\", \n",
        "\"search\": \"finds a sequence of actions. they form a path from the current node to the goal\",  \n",
        "\"solution\": \"sequence of actions that form a path to the goal\",\n",
        "\"open-loop\": \"ignores percepts after finding solution. agent is no longer connected to the environment\",\n",
        "\"closed-loop\": \"tracks percepts after finding solution. better when incorrect model or nondeterministic environment\",\n",
        "\"state space\": \"set of all states that can be reached from the initial state\",\n",
        "\"transition model\": \"from state s and taking action a, what happens?\",\n",
        "\"path\": \"sequence of actions between 2 states\",\n",
        "\"search tree\": \"how we represent all of the paths. nodes = states, edges = actions. root = initial state. leaves = successors\",\n",
        "\"frontier\": \"states that we can pursue further\",\n",
        "\"expand\": \"check all of the possible actions from the node\",\n",
        "\"generate\": \"create a child or successor node for the node. this node has now been reached\",\n",
        "\"optimal solution\": \"there is no other solution that has a lower path cost\",\n",
        "\"complete\": \"always finds a solution where there is one and a failure when there is one\",\n",
        "\"time complexity\": \"# of nodes created. how long to find a solution?\",\n",
        "\"space complexity\": \"# of nodes kept in memory at the same time. how much memory for entire search?\",\n",
        "\"b\": \"maximum branching factor. number of successors we need to look at for a node\",\n",
        "\"d\": \"depth of the shallowest node. # of actions taken to get optimal solution\",\n",
        "\"m\": \"max length of a path (could be inf). max # of actions taken\",\n",
        "\"Uninformed search\": \"only have the information in the problem definition\",\n",
        "\"Informed search\": \"have the problem definition and information about location of goal (heuristic function)\",\n",
        "\"priority queue\": \"pops the node with minimum f(n)\",\n",
        "\"heuristic function\": \"distance from current node to goal node\",\n",
        "\"cycle\": \"check if the state we are at has already appeared earlier in the path\",\n",
        "\"redundant path\": \"same start and end but different path. cycle is an example\",\n",
        "\"abstraction\": \"remove detail to make it easier to do actions--we can take abstract solution and move it into real world\",\n",
        "\"standardized problem\": \"use as an exercise to help people understand how to problem solve\",\n",
        "\"real-world problem\": \"solution is different based on the scenario (i.e. robots navigating-each robot, different sensor)\",\n",
        "\"grid world\": \"2D rectangular array, agent can move between cells\",\n",
        "\"absolute\": \"actions like up, down, left, right\",\n",
        "\"egocentric\": \"actions from the agent's viewpoint. forward, turnRight, etc\",\n",
        "\"sokoban puzzle\": \"agent needs to push boxes to their goal positions\",\n",
        "\"sliding-tile puzzle\": \"(i.e. 8-puzzle) tiles on a grid but 1 or more blank spaces so tiles can move\",\n",
        "\"route-finding problem\": \"each state is a location. the edges are the transitions from location to location\",\n",
        "\"Touring problems\": \"instead of just 1 goal, we have multiple locations to get to\",\n",
        "\"traveling salesperson problem (TSP)\": \"visit every location in the graph but cost < C\",\n",
        "\"VLSI layout\": \"cell layout + channel routing. put components and connections on a chip. Goal is to minimize area taken\",\n",
        "\"cell layout\": \"take components and group them into cells. place cells on chip without overlap and allowing for connections\",\n",
        "\"channel routing\": \"takes space between cells and formulates a route for the wire\",\n",
        "\"Robot navigation\": \"generalization of route finding because robot can create its own path\",\n",
        "\"automatic assembly sequencing\": \"optimize the order of assembling something\",\n",
        "\"early goal test\": \"check if we have solution when we generate a node\",\n",
        "\"late goal test\": \"check if we have solution when we pop the node from the frontier\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "94b75bf9-d858-42e8-b820-39742aa34b00"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nUninformed: agent has an estimate of the distance to goal \n\nInformed: agent can't estimate distance to goal \n\nWe use abstractions (i.e. represent a trip through cities with just cities and distances, not the speed the car travels, radio on/off, etc) to make it easier to perform actions and get to a solution \n\n\nVacuum cleaner problem: n cells means n*2^n states \n\nSokoban puzzle: n non-obstacle cells and b boxes, n*n! / b!(n-b)! states \n\n\n\n## AIMA Chapter 3.2 Example Problems\n \nState spaces consist of all of the states in the world + the actions that get you from one state to the next \n\nMeanwhile, search trees consist of all of the paths between these states and have a goal. \n \n\n## AIMA Chapter 3.3 Search Algorithms\n\nnode has 4 components of its data structure: \n\n\t state, parent, action, path cost \n\nqueue has 4 components: \n\n\t isEmpty, pop, top, add\n\t pop removes, top just returns the pop but doesn't remove \n\n\nHow do we eliminate redundant paths? \n\n\t 1. remember all the states we have reached already\n\t 2. if it is rare to have 2 redundant paths, don't bother tracking them\n\t 3. check for only cycles and not all redundant paths \n\n\nTo be complete when there is an infinite search space, make sure the search occurrs in a systematic way\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n\n## Module 3 Lecture Notes\n\nIf task environment: fully observable, deterministic, known environment \n\n\t solution = fixed sequence of actions \n\nIf task environment: partially observable or nondeterministic \n\n\t solution based on percepts. Could be branching strategy \n\nSearch problems: \n\n<b>Initial state</b>\n<b>Actions</b>\n<b>Transition Model</b>\n<b>Path Cost</b>: sum of all action costs in the path\n<b>Goal</b> \n\n\nStates don't have parents/children/etc; nodes have those \n\n\nTree Search: doesn't check for redundant paths (longer runtime) \n\nGraph Search: checks for redundant paths by checking to see if a node has already been visited before adding it to frontier \n\n\n<b>Uninformed</b> \n\nBFS: FIFO frontier -- expand the shallowest node that hasn't been visited yet \n\n\t use if there could be infinite search space and some solutions have short paths and can remove paths fast\n\t optimal as long as all actions have the same cost. always complete.\n\t early goal test \n\nDFS: LIFO (stack) frontier -- expand the deepest node that hasn't been visited yet \n\n\t use if limited space (great algo when you have limited memory) and a lot of solutions have long paths and can fine-tune the search fast \n\n\nBacktracking: DFS, but only generate one successors at a time, not all successors \n\n\t even less memory usage than DF because successors are stored by modifying the current state, \nnot creating a new version of the state \n\n\nDepth-Limited Search: DFS with a depth limit (l). Removes infinite paths \n\n\t if l<d, algo incomplete. if l>d, algo not optimal\n\t can use the diameter --largest distance between 2 states-- to set l \n\n\nIterative deepening: do Depth=Limited, but keep increasing depth limit (l) until fail or solution \n\n\t complete (finite, no cycles) and optimal (all actions have same cost)\n\t best uninformed search algo if we have too large of a state space and don't know what we should set d to \n\n\nBidirectional search: searches from both initial and goal state at the same time \n\n\t solution when the 2 frontiers are the same \n\n\nUniform-cost search: Priority Queue frontier -- expand node with lowest path cost (g(n)). Djikstra is UCS without a goal \n\n\t late goal test\n\t That way, we prioritize paths with lower costs because they get popped off the queue first. \n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search. Atomic representation\n* **Planning agent** - Factored or structured representation\n* **Search** - finds a sequence of actions. they form a path from the current node to the goal\n* **Solution** - sequence of actions that form a path to the goal\n* **Open-loop** - ignores percepts after finding solution. agent is no longer connected to the environment\n* **Closed-loop** - tracks percepts after finding solution. better when incorrect model or nondeterministic environment\n* **State space** - set of all states that can be reached from the initial state\n* **Transition model** - from state s and taking action a, what happens?\n* **Path** - sequence of actions between 2 states\n* **Search tree** - how we represent all of the paths. nodes = states, edges = actions. root = initial state. leaves = successors\n* **Frontier** - states that we can pursue further\n* **Expand** - check all of the possible actions from the node\n* **Generate** - create a child or successor node for the node. this node has now been reached\n* **Optimal solution** - there is no other solution that has a lower path cost\n* **Complete** - always finds a solution where there is one and a failure when there is one\n* **Time complexity** - # of nodes created. how long to find a solution?\n* **Space complexity** - # of nodes kept in memory at the same time. how much memory for entire search?\n* **B** - maximum branching factor. number of successors we need to look at for a node\n* **D** - depth of the shallowest node. # of actions taken to get optimal solution\n* **M** - max length of a path (could be inf). max # of actions taken\n* **Uninformed search** - only have the information in the problem definition\n* **Informed search** - have the problem definition and information about location of goal (heuristic function)\n* **Priority queue** - pops the node with minimum f(n)\n* **Heuristic function** - distance from current node to goal node\n* **Cycle** - check if the state we are at has already appeared earlier in the path\n* **Redundant path** - same start and end but different path. cycle is an example\n* **Abstraction** - remove detail to make it easier to do actions--we can take abstract solution and move it into real world\n* **Standardized problem** - use as an exercise to help people understand how to problem solve\n* **Real-world problem** - solution is different based on the scenario (i.e. robots navigating-each robot, different sensor)\n* **Grid world** - 2D rectangular array, agent can move between cells\n* **Absolute** - actions like up, down, left, right\n* **Egocentric** - actions from the agent's viewpoint. forward, turnRight, etc\n* **Sokoban puzzle** - agent needs to push boxes to their goal positions\n* **Sliding-tile puzzle** - (i.e. 8-puzzle) tiles on a grid but 1 or more blank spaces so tiles can move\n* **Route-finding problem** - each state is a location. the edges are the transitions from location to location\n* **Touring problems** - instead of just 1 goal, we have multiple locations to get to\n* **Traveling salesperson problem (tsp)** - visit every location in the graph but cost < C\n* **Vlsi layout** - cell layout + channel routing. put components and connections on a chip. Goal is to minimize area taken\n* **Cell layout** - take components and group them into cells. place cells on chip without overlap and allowing for connections\n* **Channel routing** - takes space between cells and formulates a route for the wire\n* **Robot navigation** - generalization of route finding because robot can create its own path\n* **Automatic assembly sequencing** - optimize the order of assembling something\n* **Early goal test** - check if we have solution when we generate a node\n* **Late goal test** - check if we have solution when we pop the node from the frontier\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",
        "All consistent heuristics are admissble; not all admissible heuristics are consistent \\n\n",
        "\n",
        "A* uses a lot of memory. O(b^d) space complexity. How can we save memory? \\n\n",
        "\\t 1. split memory between frontier and reached. By storing states in just 1 of the 2 instead of both, we save space \n",
        "\\t 2. remove states from reached when we don't need them or remove the reached table itself\n",
        "\\t 3. keep reference counts (number of times we have put state in reached). if we know that a state can only be reached x times,\n",
        "remove it from reached when we hit reference count = x \\n\n",
        "\n",
        "Beam search: only keeps k nodes with lowest f(n) in the frontier \\n\n",
        "\\t saves memory, but search is not complete and not optimal \\n\n",
        "\n",
        "Iterative deepening A* search: \\n\n",
        "\\t at each iteration, finds the smallest f(n) that was greater than the limit in that iteration. That is the limit for the next iteration.\n",
        "\\t not good for problems where every node has a different f(n) \\n\n",
        "\n",
        "Recursive best-first search: \\n\n",
        "\\t tracks the f(n) of the best alternative path from any parent of the current node. If tracked f(n) < current f(n) go back to alternative path. \\n\n",
        "While going back, each node's f(n) is replaced with the minimum f(n) --the backed-up value-- of its successors \\n\n",
        "\\t better than iterative deepening A* for memory\n",
        "\\t optimal if h(n) admissible \\n\n",
        "\n",
        "MA* (memory-bounded A*) and SMA* (simplified MA*): \\n\n",
        "\\t SMA*: once memory is full, drops node with highest f(n). Then assigns the parent that f(n) but also store the lowest f(n) in case we need to come back\n",
        "\\t if tie for f(n), expand the newest node and delete the oldest node\n",
        "\\t complete if we can get to solution before running out of memory\n",
        "\\t optimal if we can reach it before running out of memory \\n\n",
        "\n",
        "Bidirectional heuristic search: \\n\n",
        "\\t eval function: f(n) = max(2g(n), g(n) + h(n))\n",
        "\\t complete and optimal if we use the above eval function and h(n) is admissible\n",
        "\"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\"\n",
        "\n",
        "8-puzzle heuristics: number of misplaced tiles, sum of distances of tiles from goal positions \\n\n",
        "\\t Relaxing the 8-puzzle problem: 1) allow tile to move anywhere and 2) tile can move to any adjacent square \\n\n",
        "\n",
        "Good heuristic has branching factor close to 1 \\n\n",
        "We can use precomputation of the costs of some optimal path to generate heuristics faster\n",
        "We can also add shortcuts--artificial edges in a graph that will help in an action with multiple edges-- to improve runtime\n",
        "We can use ML to generate heuristics from experience\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "Best-first search: Priority Queue frontier -- uses f(n) to decide the next node to expand. \\n\n",
        "\n",
        "Greedy Best-first search:  Priority Queue frontier -- uses h(n) to decide the next node to expand \\n\n",
        "\\t NOT optimal\n",
        "\\t NOT complete (only complete in finite state spaces) \\n\n",
        "\n",
        "A* search: best-first search. Use f(n) so we focus on the best paths found but make sure they aren't too expensive \\n\n",
        "\\t if h(n) is admissible, optimal, if h(n) is inadmissible, optimality depends on situation; sometimes we can find a cost-optimal \n",
        "path even without an admissible heuristic.\n",
        "\\t always complete\n",
        "\\t contours will stretch towards the goal state\n",
        "\\t con: expands a lot of nodes \\n\n",
        "\n",
        "If we want to solve problem of expanding too many nodes: \\n\n",
        "Use an inadmissible heuristic, because it will be more accurate despite overestimating \n",
        "(i.e. detour index--need to account for roads curving, so instead of straight line distance (admissible), GPS uses this) \\n\n",
        "We can also use weighted A* search \\n\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"has access to 1) problem definition and 2) heuristic function\",   \n",
        "\"admissible/optimistic\": \"never overestimates the cost to reach the goal\",\n",
        "\"consistent\": \"heuristic for node n <= cost from node n to node n' + heuristic for node n'\",\n",
        "\"triangle inequality\": \"1 side of a triangle has to be less than the sum of the 2 sides\",\n",
        "\"contours\": \"draw them on the graph; inside each circle will be every node with f(n)<=some value\",\n",
        "\"monotonic\": \"strictly increasing. g(n) is monotonic because action costs are > 0\",\n",
        "\"surely expanded nodes\": \"nodes that have f(n) less than the cost of the path of optimal solution\",\n",
        "\"optimally efficient\": \"out of all algorithms that have same initial state+heuristic, A* expands fewest # of paths\",\n",
        "\"pruning\": \"remove nodes without even considering them\",\n",
        "\"satisficing solutions\": \"suboptimal, but still are good\",\n",
        "\"detour index\": \"multiple it with straight=line distance\",\n",
        "\"weighted A* search\": \"multiple the heuristic with a weight so value it more heavily in f(n)\",\n",
        "\"bounded suboptimal search\": \"try to find a solution that is within W*optimal cost\",\n",
        "\"bounded cost search\": \"try to find solution with cost < C\",\n",
        "\"unbounded cost search\": \"try to find a solution of any cost. the focus is on shortest runtime\",\n",
        "\"speedy search\": \"unbounded cost search. heuristic=# of actions to get to goal. so no focus on cost\",\n",
        "\"front-to-end search\": \"estimate distance to goal and distance to start in bidirectional\",\n",
        "\"front-to-front search\": \"estimate distance to the other frontier in bidirectional\",\n",
        "\"effective branching factor\": \"b*. number of new nodes that are added for each node as we increase depth by 1\",\n",
        "\"dominates\": \"h2 dominates h1 if h2 will never expand more nodes than h1 during A* search\",\n",
        "\"manhattan distance\": \"abs(x_1 - x_2) + abs(y_1 - y_2)\",\n",
        "\"relaxed problem\": \"less restrictions on the actions than the original problem. Cost of solution = admissible heuristic for the original problem\",\n",
        "\"pattern databases\": \"store the costs of solutions for subproblems of the original problem to help with heuristic of problem\",\n",
        "\"differential heuristic\": \"subtract something from heuristic\",\n",
        "\"metalevel state space\": \"each action in this changes the internal state\",\n",
        "\"object-level state space\": \"each internal state in metalevel learning is an object-level search tree\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7d68c87b-b664-4421-b778-729b402d9ec6"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nAll consistent heuristics are admissble; not all admissible heuristics are consistent \n\n\nA* uses a lot of memory. O(b^d) space complexity. How can we save memory? \n\n\t 1. split memory between frontier and reached. By storing states in just 1 of the 2 instead of both, we save space \n\t 2. remove states from reached when we don't need them or remove the reached table itself\n\t 3. keep reference counts (number of times we have put state in reached). if we know that a state can only be reached x times,\nremove it from reached when we hit reference count = x \n\n\nBeam search: only keeps k nodes with lowest f(n) in the frontier \n\n\t saves memory, but search is not complete and not optimal \n\n\nIterative deepening A* search: \n\n\t at each iteration, finds the smallest f(n) that was greater than the limit in that iteration. That is the limit for the next iteration.\n\t not good for problems where every node has a different f(n) \n\n\nRecursive best-first search: \n\n\t tracks the f(n) of the best alternative path from any parent of the current node. If tracked f(n) < current f(n) go back to alternative path. \n\nWhile going back, each node's f(n) is replaced with the minimum f(n) --the backed-up value-- of its successors \n\n\t better than iterative deepening A* for memory\n\t optimal if h(n) admissible \n\n\nMA* (memory-bounded A*) and SMA* (simplified MA*): \n\n\t SMA*: once memory is full, drops node with highest f(n). Then assigns the parent that f(n) but also store the lowest f(n) in case we need to come back\n\t if tie for f(n), expand the newest node and delete the oldest node\n\t complete if we can get to solution before running out of memory\n\t optimal if we can reach it before running out of memory \n\n\nBidirectional heuristic search: \n\n\t eval function: f(n) = max(2g(n), g(n) + h(n))\n\t complete and optimal if we use the above eval function and h(n) is admissible\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n\n8-puzzle heuristics: number of misplaced tiles, sum of distances of tiles from goal positions \n\n\t Relaxing the 8-puzzle problem: 1) allow tile to move anywhere and 2) tile can move to any adjacent square \n\n\nGood heuristic has branching factor close to 1 \n\nWe can use precomputation of the costs of some optimal path to generate heuristics faster\nWe can also add shortcuts--artificial edges in a graph that will help in an action with multiple edges-- to improve runtime\nWe can use ML to generate heuristics from experience\n\n\n## Module 4 Lecture Notes\n\nBest-first search: Priority Queue frontier -- uses f(n) to decide the next node to expand. \n\n\nGreedy Best-first search:  Priority Queue frontier -- uses h(n) to decide the next node to expand \n\n\t NOT optimal\n\t NOT complete (only complete in finite state spaces) \n\n\nA* search: best-first search. Use f(n) so we focus on the best paths found but make sure they aren't too expensive \n\n\t if h(n) is admissible, optimal, if h(n) is inadmissible, optimality depends on situation; sometimes we can find a cost-optimal \npath even without an admissible heuristic.\n\t always complete\n\t contours will stretch towards the goal state\n\t con: expands a lot of nodes \n\n\nIf we want to solve problem of expanding too many nodes: \n\nUse an inadmissible heuristic, because it will be more accurate despite overestimating \n(i.e. detour index--need to account for roads curving, so instead of straight line distance (admissible), GPS uses this) \n\nWe can also use weighted A* search \n\n \n\n## Module 4 Definitions\n* **Informed search** - has access to 1) problem definition and 2) heuristic function\n* **Admissible/optimistic** - never overestimates the cost to reach the goal\n* **Consistent** - heuristic for node n <= cost from node n to node n' + heuristic for node n'\n* **Triangle inequality** - 1 side of a triangle has to be less than the sum of the 2 sides\n* **Contours** - draw them on the graph; inside each circle will be every node with f(n)<=some value\n* **Monotonic** - strictly increasing. g(n) is monotonic because action costs are > 0\n* **Surely expanded nodes** - nodes that have f(n) less than the cost of the path of optimal solution\n* **Optimally efficient** - out of all algorithms that have same initial state+heuristic, A* expands fewest # of paths\n* **Pruning** - remove nodes without even considering them\n* **Satisficing solutions** - suboptimal, but still are good\n* **Detour index** - multiple it with straight=line distance\n* **Weighted a* search** - multiple the heuristic with a weight so value it more heavily in f(n)\n* **Bounded suboptimal search** - try to find a solution that is within W*optimal cost\n* **Bounded cost search** - try to find solution with cost < C\n* **Unbounded cost search** - try to find a solution of any cost. the focus is on shortest runtime\n* **Speedy search** - unbounded cost search. heuristic=# of actions to get to goal. so no focus on cost\n* **Front-to-end search** - estimate distance to goal and distance to start in bidirectional\n* **Front-to-front search** - estimate distance to the other frontier in bidirectional\n* **Effective branching factor** - b*. number of new nodes that are added for each node as we increase depth by 1\n* **Dominates** - h2 dominates h1 if h2 will never expand more nodes than h1 during A* search\n* **Manhattan distance** - abs(x_1 - x_2) + abs(y_1 - y_2)\n* **Relaxed problem** - less restrictions on the actions than the original problem. Cost of solution = admissible heuristic for the original problem\n* **Pattern databases** - store the costs of solutions for subproblems of the original problem to help with heuristic of problem\n* **Differential heuristic** - subtract something from heuristic\n* **Metalevel state space** - each action in this changes the internal state\n* **Object-level state space** - each internal state in metalevel learning is an object-level search tree\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",
        "Perfect information = fully-observable \\n\n",
        "Game: \\n\n",
        "\\t initial state\n",
        "\\t player whose turn it is\n",
        "\\t set of legal moves (i.e. actions)\n",
        "\\t transition model\n",
        "\\t terminal states\n",
        "\\t utility function \\n\n",
        "\n",
        "In minimax, if 1 player does not play optimally, then the other player will do at least as well as if the other player was playing optimally, but probably even better \n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "Minimax algorithm: depth-first search. Time complexity: O(b^m). Space: O(bm) \\n\n",
        "\\t won't work on complex games like Chess, Go, etc because too many moves \\n\n",
        "\n",
        "If a game is not zero-sum, the 2 players might collaborate. If a game is multiplayer, alliances may form between some players \\n\n",
        "Alpha-beta pruning: Time complexity: best case O(b^(m/2)). Space: O(b^(3m/4)) \\n\n",
        "\\t alpha is the best possible value for MAX (start at -inf)\n",
        "\\t beta is the best possible value for MIN (start at +inf)\n",
        "\\t dependent on the order of pruning\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "To further improve computation time for alpha-beta search, use heuristics to evaluate instead of utility \\n\n",
        "\\t use a cutoff test that will decide when to stop searching\n",
        "\\t eval(s,p): expected utility at state s for player p \\n\n",
        "\n",
        "For evaluation functions, we can use features of a state (i.e. assign values to each piece in a chess game) \\n\n",
        "\\t use a weighted linear function where we weigh each feature to caluculate the expected value of the state \\n\n",
        "\n",
        "Chess: \\n\n",
        "\\t only apply the eval functions to quiescent states (more other moves to be made after this move)\n",
        "\\t horizon effect: a very damaging move by opponent that is inevitable but can be avoided for now. we try to use singular extensions (don't cutoff search because not a quiescent state, just play the best move) \\n\n",
        "\n",
        "To save time, computers use table lookup instead of search for established games \n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Stochastic games: \\n\n",
        "\\t chance nodes have each move with the probability of it happening\n",
        "\\t MIN and MAX nodes are what happens if that move happens \\n\n",
        "Expectiminimax: Time complexity: O(b^m*n^m) where n is the number of moves \\n\n",
        "\\t it's hard to do alpha-beta pruning when you have to deal with chance. but we can improve this by setting lower and upper bounds on the utility function\n",
        "\\t then, we have upper bounds on the value of a chance node\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "Axioms of utility theory for a rational agent: \\n\n",
        "\\t orderability: agent must be able to decide between 2 sets of outcomes (or set them as equal preference)\n",
        "\\t transitivity: A>B and B>C, then agent prefers A to C\n",
        "\\t continuity: if A>B>C, then agent will have equal preference for B and deciding between A and C for some probability\n",
        "\\t substitutability: if A~B, then [p,A;1-p,C] is the same as [p,B;1-p,C]\n",
        "\\t monotonicity: if A>B, prefer the set of options that has a higher prob of A occurring \n",
        "\\t decomposability: can simplify a set of probabilities \\n\n",
        "\n",
        "If above axioms are followed: \\n\n",
        "\\t existence of utility function: U(A)>U(B) if and only if A>B\n",
        "\\t expected utility of a lottery: weighted sum of utility of each outcome \\n\n",
        "\n",
        "Just because an agent has a utility function, it doesn't mean that the agent is maximizing it.\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "If we normalize the utilities, we can see what probablity (p) to assign to the min utility and (1-p) to max utility\n",
        "so that p equals the value of the outcome we're looking at. The assignment of p to min and 1-p to max is the standard lottery. \\n\n",
        "To find the value that people place on their lives: micromort, QALY \\n\n",
        "Money has a monotonic preference (always prefer more). Utility function is NOT monotonic \n",
        "(i.e. many people would turn down a gamble for more money compared to get less money for sure ) \\n\n",
        "Risk-averse agents have a concave down utility curve. Risk-neutral have linear curve. \\n\n",
        "\n",
        "Allias paradox: \\n\n",
        "Descriptive theory shows a different way of people choosing between 2 options to get money than normative theory. \n",
        "This could be because of the certainty effect -- people want the upside that they are guaranteed of rather than a higher \n",
        "one that they have a chance, not for sure, of getting \\n\n",
        "Ellsberg paradox: \\n\n",
        "\\t people have ambiguity aversion -- they would rather go with a known chance than a chance that is unknown\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Objectivist/frequentist: use history; take an average over repeated experiments \\n\n",
        "Subjectivist/Bayesian: use unobserved variables and some belief of them to inform your probabilities\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"adversarial search\" : \"there are multiple agents, unlike search\",  \n",
        "\"zero-sum games\": \"the positive effect for 1 player = negative effect for the other\",  \n",
        "\"terminal states\": \"the bottom of the graph -- game has ended\",\n",
        "\"utility function\": \"expected value for player p when game ends (is in a terminal state, s)\",\n",
        "\"expected utility\": \"average utilities of the possible outcomes. weight them by the probability of the outcome occurring\",\n",
        "\"maximum expected utility\": \"agent should pick actions based on maximizing its expected utility\",\n",
        "\"ply\": \"a player's move -- progress 1 further in the game tree\",\n",
        "\"minimax value\": \"assuming that both players play optimally, what is the utility for the current player\",\n",
        "\"minimax decision\": \"the action taken by the player based on the minimax value\",\n",
        "\"killer moves\": \"best moves in alpha-beta pruning. can be used as a heuristic\",\n",
        "\"transpositions\": \"permutations of moves that have the same end state\",\n",
        "\"Type A Strategy\": \"only considers moves until a specific depth. then, estimates the utility\", \n",
        "\"Type B Strategy\": \"ignores bad moves. follows the good moves until the end of the tree\",\n",
        "\"material value\": \"how much each piece in game is worth\",\n",
        "\"forward pruning\": \"deletes some moves from search tree, but those moves might be good\",\n",
        "\"late move reduction\": \"assume we have ordered moves well. the moves that are later, we don't search them as deeply to save time\",\n",
        "\"stochastic games\": \"have randomization in them--chance nodes along with MAX and MIN nodes\",\n",
        "\"expectiminimax value\": \"expected value of a node instead of just the non-probabilistic minimax value\",\n",
        "\"lottery\": \"the different outcomes that can occur from an action\",\n",
        "\"value function/ordinal utility function\": \"deterministic games--actual values of utility functions doesn't matter. we care that preference(aka order) for outcomes stays the same\",\n",
        "\"preference elicitation\": \"process of figuring out the utility function by giving choices and then tracking the preferences\",\n",
        "\"normalized utilities\": \"normalization but min possible utility is 0 and max possible utility is 1\",\n",
        "\"value of a statistical life\": \"allows people to decide the costs and benefits of something\",\n",
        "\"micromort\": \"1 in a million chance of dying\",\n",
        "\"QALY\": \"quality adjusted life year\",\n",
        "\"certainty equivalent\": \"value accepted by agent instead of basing what they get on probability (won't play the lottery)\",\n",
        "\"insurance premium\": \"EMV of lottery - certainty equivalent\",\n",
        "\"unbiased\": \"expected value of error is 0\",\n",
        "\"optimizer's curse\": \"we tend to overestimate the expected utility, so we shouldn't just blindly accept utility estimates\",\n",
        "\"normative theory\": \"how should a rational agent act\",\n",
        "\"descriptive theory\": \"how do rational agents actually act\",\n",
        "\"framing effect\": \"the wording of a problem can change actions\",\n",
        "\"anchoring effect\": \"people will always look relatively, so anchoring them on something first can change preferences\",\n",
        "\"random variable\": \"represents an event with an unknown outcome\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "03cfbecf-fefc-4a13-debe-d510b61393e4"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nPerfect information = fully-observable \n\nGame: \n\n\t initial state\n\t player whose turn it is\n\t set of legal moves (i.e. actions)\n\t transition model\n\t terminal states\n\t utility function \n\n\nIn minimax, if 1 player does not play optimally, then the other player will do at least as well as if the other player was playing optimally, but probably even better \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nMinimax algorithm: depth-first search. Time complexity: O(b^m). Space: O(bm) \n\n\t won't work on complex games like Chess, Go, etc because too many moves \n\n\nIf a game is not zero-sum, the 2 players might collaborate. If a game is multiplayer, alliances may form between some players \n\nAlpha-beta pruning: Time complexity: best case O(b^(m/2)). Space: O(b^(3m/4)) \n\n\t alpha is the best possible value for MAX (start at -inf)\n\t beta is the best possible value for MIN (start at +inf)\n\t dependent on the order of pruning\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nTo further improve computation time for alpha-beta search, use heuristics to evaluate instead of utility \n\n\t use a cutoff test that will decide when to stop searching\n\t eval(s,p): expected utility at state s for player p \n\n\nFor evaluation functions, we can use features of a state (i.e. assign values to each piece in a chess game) \n\n\t use a weighted linear function where we weigh each feature to caluculate the expected value of the state \n\n\nChess: \n\n\t only apply the eval functions to quiescent states (more other moves to be made after this move)\n\t horizon effect: a very damaging move by opponent that is inevitable but can be avoided for now. we try to use singular extensions (don't cutoff search because not a quiescent state, just play the best move) \n\n\nTo save time, computers use table lookup instead of search for established games \n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games: \n\n\t chance nodes have each move with the probability of it happening\n\t MIN and MAX nodes are what happens if that move happens \n\nExpectiminimax: Time complexity: O(b^m*n^m) where n is the number of moves \n\n\t it's hard to do alpha-beta pruning when you have to deal with chance. but we can improve this by setting lower and upper bounds on the utility function\n\t then, we have upper bounds on the value of a chance node\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nAxioms of utility theory for a rational agent: \n\n\t orderability: agent must be able to decide between 2 sets of outcomes (or set them as equal preference)\n\t transitivity: A>B and B>C, then agent prefers A to C\n\t continuity: if A>B>C, then agent will have equal preference for B and deciding between A and C for some probability\n\t substitutability: if A~B, then [p,A;1-p,C] is the same as [p,B;1-p,C]\n\t monotonicity: if A>B, prefer the set of options that has a higher prob of A occurring \n\t decomposability: can simplify a set of probabilities \n\n\nIf above axioms are followed: \n\n\t existence of utility function: U(A)>U(B) if and only if A>B\n\t expected utility of a lottery: weighted sum of utility of each outcome \n\n\nJust because an agent has a utility function, it doesn't mean that the agent is maximizing it.\n \n\n## AIMA Chapter 16.3 Utility Functions\n \nIf we normalize the utilities, we can see what probablity (p) to assign to the min utility and (1-p) to max utility\nso that p equals the value of the outcome we're looking at. The assignment of p to min and 1-p to max is the standard lottery. \n\nTo find the value that people place on their lives: micromort, QALY \n\nMoney has a monotonic preference (always prefer more). Utility function is NOT monotonic \n(i.e. many people would turn down a gamble for more money compared to get less money for sure ) \n\nRisk-averse agents have a concave down utility curve. Risk-neutral have linear curve. \n\n\nAllias paradox: \n\nDescriptive theory shows a different way of people choosing between 2 options to get money than normative theory. \nThis could be because of the certainty effect -- people want the upside that they are guaranteed of rather than a higher \none that they have a chance, not for sure, of getting \n\nEllsberg paradox: \n\n\t people have ambiguity aversion -- they would rather go with a known chance than a chance that is unknown\n\n\n## Module 5 Lecture Notes\n\nObjectivist/frequentist: use history; take an average over repeated experiments \n\nSubjectivist/Bayesian: use unobserved variables and some belief of them to inform your probabilities\n\n\n## Module 5 Definitions\n* **Adversarial search** - there are multiple agents, unlike search\n* **Zero-sum games** - the positive effect for 1 player = negative effect for the other\n* **Terminal states** - the bottom of the graph -- game has ended\n* **Utility function** - expected value for player p when game ends (is in a terminal state, s)\n* **Expected utility** - average utilities of the possible outcomes. weight them by the probability of the outcome occurring\n* **Maximum expected utility** - agent should pick actions based on maximizing its expected utility\n* **Ply** - a player's move -- progress 1 further in the game tree\n* **Minimax value** - assuming that both players play optimally, what is the utility for the current player\n* **Minimax decision** - the action taken by the player based on the minimax value\n* **Killer moves** - best moves in alpha-beta pruning. can be used as a heuristic\n* **Transpositions** - permutations of moves that have the same end state\n* **Type a strategy** - only considers moves until a specific depth. then, estimates the utility\n* **Type b strategy** - ignores bad moves. follows the good moves until the end of the tree\n* **Material value** - how much each piece in game is worth\n* **Forward pruning** - deletes some moves from search tree, but those moves might be good\n* **Late move reduction** - assume we have ordered moves well. the moves that are later, we don't search them as deeply to save time\n* **Stochastic games** - have randomization in them--chance nodes along with MAX and MIN nodes\n* **Expectiminimax value** - expected value of a node instead of just the non-probabilistic minimax value\n* **Lottery** - the different outcomes that can occur from an action\n* **Value function/ordinal utility function** - deterministic games--actual values of utility functions doesn't matter. we care that preference(aka order) for outcomes stays the same\n* **Preference elicitation** - process of figuring out the utility function by giving choices and then tracking the preferences\n* **Normalized utilities** - normalization but min possible utility is 0 and max possible utility is 1\n* **Value of a statistical life** - allows people to decide the costs and benefits of something\n* **Micromort** - 1 in a million chance of dying\n* **Qaly** - quality adjusted life year\n* **Certainty equivalent** - value accepted by agent instead of basing what they get on probability (won't play the lottery)\n* **Insurance premium** - EMV of lottery - certainty equivalent\n* **Unbiased** - expected value of error is 0\n* **Optimizer's curse** - we tend to overestimate the expected utility, so we shouldn't just blindly accept utility estimates\n* **Normative theory** - how should a rational agent act\n* **Descriptive theory** - how do rational agents actually act\n* **Framing effect** - the wording of a problem can change actions\n* **Anchoring effect** - people will always look relatively, so anchoring them on something first can change preferences\n* **Random variable** - represents an event with an unknown outcome\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",
        "<b>CSPs</b> \\n\n",
        "-Use general instead of domain-specific heuristics \\n\n",
        "-Eliminate large portions of search space all at once by identifying variables that violate constraints. Search procedures without constraints just check if a state is a goal; CSPs allow us to see why a state hasn’t reached a goal. \\n\n",
        "-Solution must be 1) consistent 2) complete \\n\n",
        "-Represent a state with a set of variable/value pairs \\n\n",
        "-Takes exponential time in number of variables \\n\n",
        "<b>N-Queens</b> \\n\n",
        "-Example of a discrete, finite domain. Finite: can only have N possible values in domain (possible row numbers for queen in column)\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "<b>CSP Algorithms</b> \\n\n",
        "-Normal search: states are black boxes and use transition model to move between states. CSP: agent can see inside states and move between states based on what it sees \\n\n",
        "-Local consistency -- node, arc, path, k \\n\n",
        "\\t arc: X_i arc-consistent with X_j if for every value in D_i there is value in D_j that satisfies binary constraint on (X_i, X_j)\n",
        "\\t node: 1-consistency\n",
        "\\t arc: 2-consistency\n",
        "\\t path: 3-consistency \\n\n",
        "Strongly k-consistent: chose a consistent value for X_1. guaranteed that X_2 will be consistent because 2-consistent. Can keep doing this for each X.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Backtracking: This is a form of depth-first search. It's used when we finish constraint propagation but some variables haven't been assigned yet. \\n\n",
        "\\t Repeatedly choose a value left in domain of unassigned variable. \n",
        "\\t Using recursion, try to extend into a solution. If not a solution, backtrack and try the next possible assignment. Keeps 1 representation of state. \\n\n",
        "Variable selection is fail-first, value-selection is fail-last. This is so we reduce backtracking by picking the hardest variables to assign first and\n",
        "then focus on the best possible values for it. \\n\n",
        "Backjumping allows you to not waste time on variables that won't fix problem. We back up beyond those variables.\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" Local search is good for solving a lot of CSPs. You change the value of one variable at a time, and is good for when a small part of problem\n",
        "changes and we don't want to go use backtracking (which would take longer because it searches through everything again). \"\"\"\n",
        "chapter6_5 = \"\"\" We can take constraint graphs and solve them more efficiently with trees. \\n\n",
        "The first way is Cutset conditioning. \\n\n",
        "\\t Reduce a CSP to a tree structure by assigning a value to variables that won't fit into the tree (cycle cutset). \n",
        "\\t Then, we can test the remaining values in the domains of the remaining variables\n",
        "\\t Linear time (space complexity). Less time efficient than tree decomp.\\n\n",
        "The second way is Tree Decomposition. \\n\n",
        "\\t Each node is a subproblem -- we transform the CSP into a tree of subproblems. \n",
        "\\t Exponential time (space complexity). More time efficient than cutset.\n",
        "\\t\\t 1) all variables must be in at least 1 tree node\n",
        "\\t\\t 2) if 2 variables are in a constraint, they have to be in tree together\n",
        "\\t\\t 3) if variable is in 2 nodes within tree, it also has to be in every node in the path between the 2 nodes\n",
        "\\t\\t lastly, it is efficient if the tree width of the graph is small\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "Difference between MAC and AC-3: MAC interleaves search and inference because it only checks the arcs of the current variable using backtracking.\n",
        "AC-3 is only inference. After MAC checks the variable, it runs like AC-3. \\n\n",
        "\n",
        "AC-3: doesn't solve all CSPs. only solves the ones that need just arc consistency.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP\" : \"represent the conditions for a solution with a set of constraints on the variables. NP-Complete problem.\",\n",
        "\"Cryptarithmetic\" : \"Problem where letters represent numbers. Has constraint hypergraph\",\n",
        "\"Constraint hypergraph\" : \"Has ordinary nodes and hypernodes. The hypernodes are when constraints aren't unary or binary (they are n-ary).\",\n",
        "\"Dual graph\" : \"Take original graph. 1 variable for each constraint. Then, add binary constraint between variables that share constraints for each constraint.\",\n",
        "\"Consistent\" : \"the variable assignment doesn't violate any constraints\",\n",
        "\"Complete assignment\" : \"every variable ends up being assigned a value\",\n",
        "\"Partial assignment\" : \"some variables don't get an assignment\",\n",
        "\"Partial solution\" : \"when there is a partial assignment but the solution is consistent\",\n",
        "\"Constraint graph\" : \"Nodes: variables. Edges: connect variables that participate in a constraint.\",\n",
        "\"Precedence constraints\" : \"a task (i.e. job scheduling) needs to happen before another task, do Task+time to complete <= Next Task\",\n",
        "\"Disjunctive constraints\" : \"2 tasks cannot overlap, do Task+time to complete <= Next Task OR Next Task+time to complete <= Task\",\n",
        "\"Discrete domain\" : \"There are infinite possible values for variable. We have to use implicit constraints (precendence, disjunctive) rather than the values themselves\", \n",
        "\"Linear constraints\" : \"The variable is only in linear form\",\n",
        "\"Nonlinear constraints\" : \"You can't solve algorithms if you have nonlinear constraints\",\n",
        "\"Continuous domains\" : \"Example is job scheduling if jobs are precisely timed. Linear programming problems have this--constraints are equalities/inequalities\",\n",
        "\"Unary constraint\" : \"restricts value of 1 variable (i.e. NSW != green)\",\n",
        "\"Binary constraint\" : \"restricts value of 2 variables (i.e. SA != NSW)\",\n",
        "\"Binary CSP\" : \"Only has unary + binary constraints\",\n",
        "\"Global constraint\" : \"involves arbitrary number of variables (i.e. Sudoku -- all variables in box must have different values)\",\n",
        "\"Resource constraint\": \"aka Atmost constraint. Max number of resources allowed to be allocated to each variable.\",\n",
        "\"Bounds propagation\": \"When you have too many values in domain so can't list in resource constraint, just represent as a bound.\",\n",
        "\"Bounds-consistent\": \"When there is a value that satisfies upper and lower bound in a CSP\",\n",
        "\"Preference constraint\" : \"certain solutions preferred (professor wants to teach morning). Can be cost (lower for preference). Makes it Constrained Optimized Problem\",\n",
        "\"Constraint propagation\" : \"using constraints to reduce number of legal values for variable-->reduces number of legal values for other variables-->etc\",\n",
        "\"Local consistency\" : \"node → variable and edge → binary constraint. Allows us to eliminate inconsistent values throughout graph\",\n",
        "\"Node consistency\" : \"all values in the domain satisfy variable’s unary constraints. Graph = node-consistent if every variable in graph is node-consistent\",\n",
        "\"Arc consistency\" : \"all values in domain satisfy variable’s binary constraints. Graph = arc-consistent if every variable in graph is arc-consistent\",\n",
        "\"Path consistency\" : \"X_i and X_j path consistent with X_m if there is assignment to X_m where {X_i,X_m} and {X_j,X_m} constraints are valid.\",\n",
        "\"K-consistency\" : \"Have k variables (k=number of states), for any k-1 variables with consistent assignments, there is consistent assignment for k.\",\n",
        "\"Strongly k-consistent\" : \"K-consistent AND k-1 consistent AND k-2 consistent .. 1 consistent. O(d*n^2)\",\n",
        "\"Commutativity\": \"All CSPs have this. Order of applying actions doesn't matter.\",\n",
        "\"minimum-remaining-values\": \"MRV heuristic. You choose the variable that has the fewest values left in its domain.\",\n",
        "\"degree heuristic\": \"Pick the variable that is in the most constraints with the variables that haven't been assigned yet.\",\n",
        "\"least-constraining-value heuristic\": \"Pick value for variable that results in least number of choices ruled out for variables in constraints with this variable.\",\n",
        "\"forward checking\": \"Establish arc consistency for variable. When variable assigned value, remove inconsistent values from neighbors (in constraint with variable).\",\n",
        "\"Maintaining Arc Consistency\": \"Addition to forward checking--after assigning value, immediately check the neighbors of variable.\",\n",
        "\"chronological backtracking\": \"In backtracking, we look at the previous decision made if we fail in a specific branch of tree.\",\n",
        "\"conflict set\": \"set of assignments to variables causing conflict for another variable (can't assign anything to the variable).\",\n",
        "\"backjumping\": \"better than chronological backtracking. Go to previous assignment of conflict set.\",\n",
        "\"conflict-directed backjumping\": \"Go to previous assignment of conflict set AND any variables that came after\",\n",
        "\"constraint learning\": \"Get the minimal set of variables in the conflict set that are causing the inconsistency\",\n",
        "\"no-good\": \"Set of variables found by constraint learning. Stored as a set of no-goods or adding a constraint.\",\n",
        "\"min-conflicts\": \"Heuristic. Picks a value for variable that causes least # of conflicts with other variables.\",\n",
        "\"tabu search\": \"Can have many states in plateau -- 1 conflict away from solution. Store recent visited states so algorithm avoids them.\",\n",
        "\"constraint weighting\": \"Pick variable and value that have lowest weight compared to constraints that are being violated. Ensures most important constraints.\",\n",
        "\"independent subproblems\": \"subproblems are not connected components in the graph\",\n",
        "\"tree\": \"2 variables in a constraint graph have only 1 path between them\",\n",
        "\"directional arc consistency\": \"Every variable is consistent with the variables after it\",\n",
        "\"topological sort\": \"A variable is the root and then the order of the variables after it is the topological ordering\",\n",
        "\"tree width\": \"the size of the largest node in a Tree Decomposition - 1.\",\n",
        "\"value symmetry\": \"there are multiple ways to satisfy a constraint (i.e. WA,NT,SA different colors but any combo of 3 colors).\",\n",
        "\"symmetry-breaking constraint\": \"set some ordering of values (i.e. NT<WA<SA) so we only get one of the orderings in the value symmetry\"\n",
        "\n",
        "\n",
        "\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "82932cba-4304-402f-8d3c-10222a522728"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \n<b>CSPs</b> \n\n-Use general instead of domain-specific heuristics \n\n-Eliminate large portions of search space all at once by identifying variables that violate constraints. Search procedures without constraints just check if a state is a goal; CSPs allow us to see why a state hasn’t reached a goal. \n\n-Solution must be 1) consistent 2) complete \n\n-Represent a state with a set of variable/value pairs \n\n-Takes exponential time in number of variables \n\n<b>N-Queens</b> \n\n-Example of a discrete, finite domain. Finite: can only have N possible values in domain (possible row numbers for queen in column)\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n<b>CSP Algorithms</b> \n\n-Normal search: states are black boxes and use transition model to move between states. CSP: agent can see inside states and move between states based on what it sees \n\n-Local consistency -- node, arc, path, k \n\n\t arc: X_i arc-consistent with X_j if for every value in D_i there is value in D_j that satisfies binary constraint on (X_i, X_j)\n\t node: 1-consistency\n\t arc: 2-consistency\n\t path: 3-consistency \n\nStrongly k-consistent: chose a consistent value for X_1. guaranteed that X_2 will be consistent because 2-consistent. Can keep doing this for each X.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nBacktracking: This is a form of depth-first search. It's used when we finish constraint propagation but some variables haven't been assigned yet. \n\n\t Repeatedly choose a value left in domain of unassigned variable. \n\t Using recursion, try to extend into a solution. If not a solution, backtrack and try the next possible assignment. Keeps 1 representation of state. \n\nVariable selection is fail-first, value-selection is fail-last. This is so we reduce backtracking by picking the hardest variables to assign first and\nthen focus on the best possible values for it. \n\nBackjumping allows you to not waste time on variables that won't fix problem. We back up beyond those variables.\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search is good for solving a lot of CSPs. You change the value of one variable at a time, and is good for when a small part of problem\nchanges and we don't want to go use backtracking (which would take longer because it searches through everything again). \n\n## AIMA Chapter 6.5 The Structure of Problems\n We can take constraint graphs and solve them more efficiently with trees. \n\nThe first way is Cutset conditioning. \n\n\t Reduce a CSP to a tree structure by assigning a value to variables that won't fit into the tree (cycle cutset). \n\t Then, we can test the remaining values in the domains of the remaining variables\n\t Linear time (space complexity). Less time efficient than tree decomp.\n\nThe second way is Tree Decomposition. \n\n\t Each node is a subproblem -- we transform the CSP into a tree of subproblems. \n\t Exponential time (space complexity). More time efficient than cutset.\n\t\t 1) all variables must be in at least 1 tree node\n\t\t 2) if 2 variables are in a constraint, they have to be in tree together\n\t\t 3) if variable is in 2 nodes within tree, it also has to be in every node in the path between the 2 nodes\n\t\t lastly, it is efficient if the tree width of the graph is small\n\n\n\n## Module 6 Lecture Notes\n\nDifference between MAC and AC-3: MAC interleaves search and inference because it only checks the arcs of the current variable using backtracking.\nAC-3 is only inference. After MAC checks the variable, it runs like AC-3. \n\n\nAC-3: doesn't solve all CSPs. only solves the ones that need just arc consistency.\n\n\n## Module 6 Definitions\n* **Csp** - represent the conditions for a solution with a set of constraints on the variables. NP-Complete problem.\n* **Cryptarithmetic** - Problem where letters represent numbers. Has constraint hypergraph\n* **Constraint hypergraph** - Has ordinary nodes and hypernodes. The hypernodes are when constraints aren't unary or binary (they are n-ary).\n* **Dual graph** - Take original graph. 1 variable for each constraint. Then, add binary constraint between variables that share constraints for each constraint.\n* **Consistent** - the variable assignment doesn't violate any constraints\n* **Complete assignment** - every variable ends up being assigned a value\n* **Partial assignment** - some variables don't get an assignment\n* **Partial solution** - when there is a partial assignment but the solution is consistent\n* **Constraint graph** - Nodes: variables. Edges: connect variables that participate in a constraint.\n* **Precedence constraints** - a task (i.e. job scheduling) needs to happen before another task, do Task+time to complete <= Next Task\n* **Disjunctive constraints** - 2 tasks cannot overlap, do Task+time to complete <= Next Task OR Next Task+time to complete <= Task\n* **Discrete domain** - There are infinite possible values for variable. We have to use implicit constraints (precendence, disjunctive) rather than the values themselves\n* **Linear constraints** - The variable is only in linear form\n* **Nonlinear constraints** - You can't solve algorithms if you have nonlinear constraints\n* **Continuous domains** - Example is job scheduling if jobs are precisely timed. Linear programming problems have this--constraints are equalities/inequalities\n* **Unary constraint** - restricts value of 1 variable (i.e. NSW != green)\n* **Binary constraint** - restricts value of 2 variables (i.e. SA != NSW)\n* **Binary csp** - Only has unary + binary constraints\n* **Global constraint** - involves arbitrary number of variables (i.e. Sudoku -- all variables in box must have different values)\n* **Resource constraint** - aka Atmost constraint. Max number of resources allowed to be allocated to each variable.\n* **Bounds propagation** - When you have too many values in domain so can't list in resource constraint, just represent as a bound.\n* **Bounds-consistent** - When there is a value that satisfies upper and lower bound in a CSP\n* **Preference constraint** - certain solutions preferred (professor wants to teach morning). Can be cost (lower for preference). Makes it Constrained Optimized Problem\n* **Constraint propagation** - using constraints to reduce number of legal values for variable-->reduces number of legal values for other variables-->etc\n* **Local consistency** - node → variable and edge → binary constraint. Allows us to eliminate inconsistent values throughout graph\n* **Node consistency** - all values in the domain satisfy variable’s unary constraints. Graph = node-consistent if every variable in graph is node-consistent\n* **Arc consistency** - all values in domain satisfy variable’s binary constraints. Graph = arc-consistent if every variable in graph is arc-consistent\n* **Path consistency** - X_i and X_j path consistent with X_m if there is assignment to X_m where {X_i,X_m} and {X_j,X_m} constraints are valid.\n* **K-consistency** - Have k variables (k=number of states), for any k-1 variables with consistent assignments, there is consistent assignment for k.\n* **Strongly k-consistent** - K-consistent AND k-1 consistent AND k-2 consistent .. 1 consistent. O(d*n^2)\n* **Commutativity** - All CSPs have this. Order of applying actions doesn't matter.\n* **Minimum-remaining-values** - MRV heuristic. You choose the variable that has the fewest values left in its domain.\n* **Degree heuristic** - Pick the variable that is in the most constraints with the variables that haven't been assigned yet.\n* **Least-constraining-value heuristic** - Pick value for variable that results in least number of choices ruled out for variables in constraints with this variable.\n* **Forward checking** - Establish arc consistency for variable. When variable assigned value, remove inconsistent values from neighbors (in constraint with variable).\n* **Maintaining arc consistency** - Addition to forward checking--after assigning value, immediately check the neighbors of variable.\n* **Chronological backtracking** - In backtracking, we look at the previous decision made if we fail in a specific branch of tree.\n* **Conflict set** - set of assignments to variables causing conflict for another variable (can't assign anything to the variable).\n* **Backjumping** - better than chronological backtracking. Go to previous assignment of conflict set.\n* **Conflict-directed backjumping** - Go to previous assignment of conflict set AND any variables that came after\n* **Constraint learning** - Get the minimal set of variables in the conflict set that are causing the inconsistency\n* **No-good** - Set of variables found by constraint learning. Stored as a set of no-goods or adding a constraint.\n* **Min-conflicts** - Heuristic. Picks a value for variable that causes least # of conflicts with other variables.\n* **Tabu search** - Can have many states in plateau -- 1 conflict away from solution. Store recent visited states so algorithm avoids them.\n* **Constraint weighting** - Pick variable and value that have lowest weight compared to constraints that are being violated. Ensures most important constraints.\n* **Independent subproblems** - subproblems are not connected components in the graph\n* **Tree** - 2 variables in a constraint graph have only 1 path between them\n* **Directional arc consistency** - Every variable is consistent with the variables after it\n* **Topological sort** - A variable is the root and then the order of the variables after it is the topological ordering\n* **Tree width** - the size of the largest node in a Tree Decomposition - 1.\n* **Value symmetry** - there are multiple ways to satisfy a constraint (i.e. WA,NT,SA different colors but any combo of 3 colors).\n* **Symmetry-breaking constraint** - set some ordering of values (i.e. NT<WA<SA) so we only get one of the orderings in the value symmetry\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",
        "When an agent program is called: \\n\n",
        "\\t tells KB the percepts (what is perceives)\n",
        "\\t queries KB for what action should be performed\n",
        "\\t tells KB the action it chose \\n\n",
        "\n",
        "Use the knowledge base to arrive at a set of possibilities which are a subset of the possible worlds \\n\n",
        "\n",
        "Declarative approach -- just tell agent sentences for how to operate 1 at a time \\n\n",
        "Procedural approach -- encode what the agent should be doing in code \\n\n",
        "Have to combine declarative and procedural.\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "Possible world: x women and y men sitting at a table. Model: all possible nonnegative integers as x and y \\n\n",
        "Model m satisfies sentence s if sentence s is true in model m \\n\n",
        "\n",
        "a⊨B if and only if M(a) is a subset of M(b). a is more specific (Honda) and stronger than b (car). \\n\n",
        "\\t if KB⊨a and in every model in which KB is true a is also true, then KB entails a and the agent can conclude that a is true.\n",
        "\\t if KB⊨a and KB is true in some models but a is false in those models, then KB does not entail a and the agent can't conclude that a is true. \\n\n",
        "\n",
        "You go and check the entire KB. Go through every sentence. If in all the worlds possible with the KB, the statement is also true,\n",
        "we can say that KB entails the statement. If in all the worlds possible with the KB, the statement is false in some (or all) of them,\n",
        "KB does not entail the statement. \\n\n",
        "\n",
        "If KB and statement have n symbols, time complexity of seeing if KB entails statement is O(2^n) and space complexity is O(n) \\n\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "Atomic sentences are represented with single propositional symbols (i.e W, FacingEast) \\n\n",
        "Complex sentences have atomic sentences on each side of operators \\n\n",
        "\\t ∧: and || V: or || ¬: not || ⇒: implies || ⇔: if and only if (biconditional)\n",
        "\\t ¬ has the tightest bind, so ¬A ∧ B = (¬A) ∧ B instead of ¬(A ∧ B) \\n\n",
        "\n",
        "\\t And-Elimination: a ∧ b = a OR a ∧ b = b\n",
        "\\t Modus Ponens: a⇒b and a is a sentence, then we know b\n",
        "\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "≡: logically equivalent. If a⊨B and B⊨a, then ≡ \\n\n",
        "All logical equivalence rules can be rewritten as inference rules (i.e numerator/denominator form) \\n\n",
        "Because of this, we can use search algorithms to solve a KB \\n\n",
        "\n",
        "a⊨b if and only if (a ∧ ¬b) is not satisfiable. can prove this using proof by contradiction \\n\n",
        "\\t convert KB ∧ ¬a to CNF and then apply resolution rule. resolve all the complementary literals\n",
        "\\t if the result of resolution isn't already in KB, add it and keep repeating\n",
        "\\t stop when we can't add anymore new clauses (KB doesn't entail a) or 2 clauses (i.e. B, ¬B) lead to an empty clause (KB entails a)\n",
        "\n",
        "Using inference to get to the goal is 1 way, but how do we know the solution is complete--that we have *all* the entailed sentences? \\n\n",
        "\\t Resolution: the single inference rule that tells us that the algorithm is complete. You take the sentences that have just 1 term and remove that term from other sentences\n",
        "\\t for example, if ¬b is a literal and another sentence says a V b V c, then we can change that to a V c.\n",
        "\\t unit resolution: if we have b and ¬b (complementary), we can eliminate both of them. Take both clauses and combine them without b and ¬b\n",
        "\\t **important: you can only resolve ONE pair of complementary literals at a time\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "To convert to CNF: \\n\n",
        "\\t replace a⇔b with (a⇒b)∧(b⇒a)\n",
        "\\t replace a⇒b with ¬a V b\n",
        "\\t move the ¬ inside by removing double negation and De Morgan's rules\n",
        "\\t apply distributivity law to distribute V over ∧ when you can \n",
        "\n",
        "Horn clauses > Definite Clauses and goal clauses\n",
        "\\t if you apply resolution to a Horn clause, you will get a Horn clause\n",
        "\\t seeing if KB entails a using Horn clauses: linear time \n",
        "\n",
        "Every Definite clause can be written as (conjunction of positive literals) ⇒ positive literal\n",
        "\\t example: ¬A V ¬B V C = A ∧ B ⇒ C\n",
        "\n",
        "Forward chaining\n",
        "\\t start with the known facts (single positive literals). check the implications and if their premises are all known, then add the conclusion of the implication to the KB\n",
        "\\t keep going until no more inferences can be made\n",
        "\\t linear time. sound and complete\n",
        "\n",
        "Backward chaining\n",
        "\\t start with a query. if it's true, do nothing, if not, find implications where the conclusion is the query\n",
        "\\t if the premises in that implications are all true (might have to do more backward chaining), query is true\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"use reasoning and their internal representation of knowledge to decide what action to perform\",\n",
        "\"knowledge base (KB)\": \"set of sentences written in knowledge representation language. can have some background knowlde to start\",\n",
        "\"axiom\": \"sentence that is given\",\n",
        "\"derived sentence\": \"new sentence from old sentence (aka inference)\", \n",
        "\"knowledge level\": \"to decide actions of agent: 1)what it knows and 2)know the goals. don't need to know implementation level\",\n",
        "\"syntax\": \"indicates all sentences are formed properly\",\n",
        "\"semantics\": \"meaning of sentences. For each possible world, what is the truth of each sentence\",\n",
        "\"model\": \"mathematical abstraction of each possible world the agent could be in\",\n",
        "\"entailment\": \"1 sentences follows another sentence logically. In every model a is true, B is true. a⊨B --> a entails B\",\n",
        "\"model checking\": \"assume KB⊨a. go through all possible models and check that a is true where KB is true\",\n",
        "\"sound / truth-preserving\": \"when an inference model derives only entailed sentences\",\n",
        "\"completeness\": \"inference can derive *all* sentences that are entailed\",\n",
        "\"grounding\": \"to know if KB is true in real world, use the agent's sensors\",\n",
        "\"premise/antedecent\": \"what comes before arrow\",\n",
        "\"conclusion/consequent\": \"what comes after arrow\",\n",
        "\"truth value\": \"true or false\",\n",
        "\"theorem proving\": \"alternative to model checking where we just use inference on the sentences without models\",\n",
        "\"logical equivalence\": \"A and B are true in the same set of models. then they are logically equivalent\",\n",
        "\"validity\": \"sentence is true in all models. sentences that are valid are tautologies\",\n",
        "\"deduction theorem\": \"a⊨B if and only if a⇒b is VALID\",\n",
        "\"satisfiability\": \"sentence is true in some (not necessarily all) models. NP-Complete problem\",\n",
        "\"monotonicity\": \"the number of entailed sentences in KB can only increase as we add more info to the KB\",\n",
        "\"complementary literals\": \"one is the negation of the other\",\n",
        "\"clause\": \"multiple literals combined (i.e. a V b V c)\",\n",
        "\"unit clause\": \"a single literal that is a disjunction of 1 literal\",\n",
        "\"factoring\": \"removing multiple copies of a literal -- A V A = A\",\n",
        "\"CNF\": \"sentence that only has V, ¬, and ∧. Eliminate ⇒ and ⇔\",\n",
        "\"definite clause\": \"disjunction of literals but ONLY 1 LITERAL is positive\",\n",
        "\"Horn clause\": \"disjunction of literals but AT MOST 1 is positive\",\n",
        "\"goal clauses\": \"no positive literals\",\n",
        "\"body\": \"in horn clauses, the premise\",\n",
        "\"head\": \"in horn clauses, the conclusion\",\n",
        "\"fact\": \"a single positive literal that is the only literal in the sentence\",\n",
        "\"data-driven reasoning\": \"you begin with known data and then keep adding to your knowledge. forward-chaining\",\n",
        "\"goal-directed reasoning\": \"backward chaining\"\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7052e6db-5ee8-4762-92e0-e3cbb5125344"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nWhen an agent program is called: \n\n\t tells KB the percepts (what is perceives)\n\t queries KB for what action should be performed\n\t tells KB the action it chose \n\n\nUse the knowledge base to arrive at a set of possibilities which are a subset of the possible worlds \n\n\nDeclarative approach -- just tell agent sentences for how to operate 1 at a time \n\nProcedural approach -- encode what the agent should be doing in code \n\nHave to combine declarative and procedural.\n \n\n## AIMA Chapter 7.2 The Wumpus World\n \n\n\n## AIMA Chapter 7.3 Logic\n\nPossible world: x women and y men sitting at a table. Model: all possible nonnegative integers as x and y \n\nModel m satisfies sentence s if sentence s is true in model m \n\n\na⊨B if and only if M(a) is a subset of M(b). a is more specific (Honda) and stronger than b (car). \n\n\t if KB⊨a and in every model in which KB is true a is also true, then KB entails a and the agent can conclude that a is true.\n\t if KB⊨a and KB is true in some models but a is false in those models, then KB does not entail a and the agent can't conclude that a is true. \n\n\nYou go and check the entire KB. Go through every sentence. If in all the worlds possible with the KB, the statement is also true,\nwe can say that KB entails the statement. If in all the worlds possible with the KB, the statement is false in some (or all) of them,\nKB does not entail the statement. \n\n\nIf KB and statement have n symbols, time complexity of seeing if KB entails statement is O(2^n) and space complexity is O(n) \n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nAtomic sentences are represented with single propositional symbols (i.e W, FacingEast) \n\nComplex sentences have atomic sentences on each side of operators \n\n\t ∧: and || V: or || ¬: not || ⇒: implies || ⇔: if and only if (biconditional)\n\t ¬ has the tightest bind, so ¬A ∧ B = (¬A) ∧ B instead of ¬(A ∧ B) \n\n\n\t And-Elimination: a ∧ b = a OR a ∧ b = b\n\t Modus Ponens: a⇒b and a is a sentence, then we know b\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n≡: logically equivalent. If a⊨B and B⊨a, then ≡ \n\nAll logical equivalence rules can be rewritten as inference rules (i.e numerator/denominator form) \n\nBecause of this, we can use search algorithms to solve a KB \n\n\na⊨b if and only if (a ∧ ¬b) is not satisfiable. can prove this using proof by contradiction \n\n\t convert KB ∧ ¬a to CNF and then apply resolution rule. resolve all the complementary literals\n\t if the result of resolution isn't already in KB, add it and keep repeating\n\t stop when we can't add anymore new clauses (KB doesn't entail a) or 2 clauses (i.e. B, ¬B) lead to an empty clause (KB entails a)\n\nUsing inference to get to the goal is 1 way, but how do we know the solution is complete--that we have *all* the entailed sentences? \n\n\t Resolution: the single inference rule that tells us that the algorithm is complete. You take the sentences that have just 1 term and remove that term from other sentences\n\t for example, if ¬b is a literal and another sentence says a V b V c, then we can change that to a V c.\n\t unit resolution: if we have b and ¬b (complementary), we can eliminate both of them. Take both clauses and combine them without b and ¬b\n\t **important: you can only resolve ONE pair of complementary literals at a time\n\n\n\n## Module 7 Lecture Notes\n\nTo convert to CNF: \n\n\t replace a⇔b with (a⇒b)∧(b⇒a)\n\t replace a⇒b with ¬a V b\n\t move the ¬ inside by removing double negation and De Morgan's rules\n\t apply distributivity law to distribute V over ∧ when you can \n\nHorn clauses > Definite Clauses and goal clauses\n\t if you apply resolution to a Horn clause, you will get a Horn clause\n\t seeing if KB entails a using Horn clauses: linear time \n\nEvery Definite clause can be written as (conjunction of positive literals) ⇒ positive literal\n\t example: ¬A V ¬B V C = A ∧ B ⇒ C\n\nForward chaining\n\t start with the known facts (single positive literals). check the implications and if their premises are all known, then add the conclusion of the implication to the KB\n\t keep going until no more inferences can be made\n\t linear time. sound and complete\n\nBackward chaining\n\t start with a query. if it's true, do nothing, if not, find implications where the conclusion is the query\n\t if the premises in that implications are all true (might have to do more backward chaining), query is true\n\n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning and their internal representation of knowledge to decide what action to perform\n* **Knowledge base (kb)** - set of sentences written in knowledge representation language. can have some background knowlde to start\n* **Axiom** - sentence that is given\n* **Derived sentence** - new sentence from old sentence (aka inference)\n* **Knowledge level** - to decide actions of agent: 1)what it knows and 2)know the goals. don't need to know implementation level\n* **Syntax** - indicates all sentences are formed properly\n* **Semantics** - meaning of sentences. For each possible world, what is the truth of each sentence\n* **Model** - mathematical abstraction of each possible world the agent could be in\n* **Entailment** - 1 sentences follows another sentence logically. In every model a is true, B is true. a⊨B --> a entails B\n* **Model checking** - assume KB⊨a. go through all possible models and check that a is true where KB is true\n* **Sound / truth-preserving** - when an inference model derives only entailed sentences\n* **Completeness** - inference can derive *all* sentences that are entailed\n* **Grounding** - to know if KB is true in real world, use the agent's sensors\n* **Premise/antedecent** - what comes before arrow\n* **Conclusion/consequent** - what comes after arrow\n* **Truth value** - true or false\n* **Theorem proving** - alternative to model checking where we just use inference on the sentences without models\n* **Logical equivalence** - A and B are true in the same set of models. then they are logically equivalent\n* **Validity** - sentence is true in all models. sentences that are valid are tautologies\n* **Deduction theorem** - a⊨B if and only if a⇒b is VALID\n* **Satisfiability** - sentence is true in some (not necessarily all) models. NP-Complete problem\n* **Monotonicity** - the number of entailed sentences in KB can only increase as we add more info to the KB\n* **Complementary literals** - one is the negation of the other\n* **Clause** - multiple literals combined (i.e. a V b V c)\n* **Unit clause** - a single literal that is a disjunction of 1 literal\n* **Factoring** - removing multiple copies of a literal -- A V A = A\n* **Cnf** - sentence that only has V, ¬, and ∧. Eliminate ⇒ and ⇔\n* **Definite clause** - disjunction of literals but ONLY 1 LITERAL is positive\n* **Horn clause** - disjunction of literals but AT MOST 1 is positive\n* **Goal clauses** - no positive literals\n* **Body** - in horn clauses, the premise\n* **Head** - in horn clauses, the conclusion\n* **Fact** - a single positive literal that is the only literal in the sentence\n* **Data-driven reasoning** - you begin with known data and then keep adding to your knowledge. forward-chaining\n* **Goal-directed reasoning** - backward chaining\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": "13f3c363-ba7e-4c8a-c3de-b14569f56f62"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nto learn about human thought: introspection, psychological experiments, brain imaging \n\nAgents have 5 requirements: \n\n\t be able to work autonomously \n\t perceive the environment they're in\n\t keep acting over a time period\n\t be adaptable\n\t create goals and pursue them \n\nAI involves rational agents. Using this approach is good because 1) it is relatively general since accurate inference is just one way to be rational\nand 2) easy to define mathematically so we can develop on the approach.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nTuring believed that human actions are too complex for machines to ever perfectly simulate. This has been the source of debate by many people -- that \nmachines will always have incomplete information because they aren't human (incompleteness theorem).\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \nTuring and others believe that we haven't defined \"think\" properly but we can just assume that everyone, including machines, thinks. \n\nChinese room argument: regardless of how intelligently a computer behaves, it doesn't generate understanding so a computer will never have a mind of its own \n\nBiological naturalism: humans think based on physical processes in neurons, so Searle argues that humans also don't have understanding because the neurons don't have understanding\n\n\n## AIMA 2.1 Agents and Environments\n\nAgents: humans-(sensors: eyes/ears, actuators: hands, legs), software-(sensors: human input, file contents, actuators: write files, display info) \n\n\t the action taken will depend on 1) built-in knowledge and 2) the percept sequence. NOT future actions/something that hasn't yet been received by sensor\n\t the agent function is math because it calculates what a percept has received and converts it to action \n\t the agent program actually implements this action \n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nWhen we think about designing performance measures, we should focus on evaluating agents based on what they achieve (i.e. # of clean squares), \nnot on their behavior (i.e. how much dirt is removed).\nRationality--there is: \n\n\t performance measure \n\t prior knowledge of environment\n\t actions for the agent\n\t historical percept sequence \n\nPerfection tries to get best actual performance, but rationality tries to get best expected performance. Rational agents are not guaranteed to find optimal solutions.\n\nIn order to reach autonomy, we must provide the agent with help at the beginning but also provide it with the ability to learn \n \n\n## AIMA 2.3 The Nature of Environments\n\n<b>PEAS</b>: Performance Measures,Environment, Actuators, Sensors. These make up a task environment. \n\n<b>Fully Observable</b>: agent knows complete environment at any time, so it doesn't need to keep an internal state \n\n<b>Partially Observable</b>: agent only knows part of environment (i.e. card game, image analysis) \n\n<b>Unobservable</b>: agent has no sensors at all \n\n<b>Single Agent</b> \n\n<b>Multiagent</b>: competitive (i.e. game) vs cooperative(i.e. taxi driver and another vehicle) \n\n<b>Deterministic</b>: same result every time. we use only the current state and action to determine the next state \n\n<b>Nondeterministic/Stochastic</b>: could have different result every time. most situations are this because nothing is ever fully certain. Stochastic has exact probabilities, but nondeterministic is more qualitative \n\n<b>Episodic</b>: agent uses a percept to take 1 action. the next \"episode\" doesn't depend on the previous ones. (i.e. checking each item in line for defects) \n\n<b>Sequential</b>: agent's action will affect the future actions. rewards could come only after many actions \n\n<b>Static</b>: environment can't change while agent decides what action to take \n\n<b>Dynamic</b>: environment is continuously changing (i.e. taxi driving) \n\n<b>SemiDynamic</b>: environment isn't continuously changing, but performance measure is (i.e chess with clock) \n\n<b>Discrete</b>: environment state, time, percepts, actions (i.e. chess) \n\n<b>Continuous</b>: taxi driving \n\n<b>Known</b>: agent knows the outcomes/outcome probabilities \n\n<b>Unknown</b>: agent has to learn as it progresses through environment \n\n\n\n## AIMA 2.4 The Structure of Agents\n\nA big challenge is creating programs that perform rationally AND are small in size instead of needing to look up percepts in a large table \n\n4 agent programs generate actions: simple reflex, model-based reflex, goal-based, utility-based \n\nLearning agents: \n\n\t learning element: makes improvements to the agent by learning from percepts \n\t performance element: decides the actions taken by taking in percepts\n\t critic: provides feedback to the agent about the percept received so performance element can be improved\n\t the reward can be the feedback provided to the agent by the critic\n\t problem generator: suggests new actions so that agent can try new (maybe suboptimal) actions that may lead it to a better solution\n \n\n## Module 1 Lecture Notes\n \n\n\n\n## Module 1 Definitions\n* **Turing test** - sees if machine can think. computer needs: NLP, knowledge representation, automated reasoning, ML\n* **Total turing test** - machine has to interact with the world. computer also needs: computer vision, robotics\n* **Introspection** - personal thoughts as they occur\n* **Psychological experiments** - see a person's actions\n* **Brain imaging** - see a brain's actions\n* **Cognitive science** - AI + psychology so that we can test if computers can act like human mind\n* **Syllogisms** - reasoning that can't be disputed. Aristotle. initiated the term Logic\n* **Probability** - allows us to perform reasoning when we are unsure of the information\n* **Agent** - perceive environment using sensors. uses actuators to act in the environment\n* **Rational agent** - maximizes performance measure based on percept sequence + built-in knowledge. With uncertainty in problem--best expected performance measure\n* **Percept** - what the sensors are actually receiving\n* **Percept sequence** - all of the percepts ever received by the agent\n* **Agent function** - takes percept sequence and executes an action. This is the agent's behavior\n* **Agent program** - takes the current percept sequence and actually implements the agent function\n* **Agent architecture** - the actual sensors and actuators. agent = architecture + program\n* **Standard model** - providing an objective to the agent\n* **Omniscience** - agent knows what the actual outcome will be if it performs an action--impossible\n* **Limited rationality** - can't always make perfectly optimal move; sometimes too much computational power so we settle for less\n* **Value alignment problem** - sometimes what the human wants the machine to do is different from the objective fed to machine\n* **Weak ai** - machines can act like they are intelligent and actually thinking\n* **Strong ai** - machines are actually intelligent and thinking for themselves\n* **Good old-fashioned ai (gofai)** - very simple logical agent (doesn't account for advances such as probabilistic reasoning/deep learning)\n* **Qualification problem** - too hard to capture all behavior with a set of rules\n* **Embodied cognition** - have to look at entire system, not just the brain. because everything takes place in an environment, not alone\n* **Biological naturalism** - a mental state is caused by physical neurons\n* **Consciousness** - being aware of the environment and yourself\n* **Qualia** - experiences. We don't know if machines have this\n* **Consequentialism** - we use the consequences of agent's behavior to evaluate it\n* **Performance measure** - takes the states of the environment based on the agent's actions and evaluates it\n* **Information gathering** - agent performs actions so future percepts are informed and changed accordingly. Also explores the environment\n* **Autonomy** - agent should be learning to make up for having just partial knowledge\n* **Task environments** - problem. an agent is the solution to this problem\n* **Environment class** - set of environments to draw from to test agent performance\n* **Simple reflex agent** - agent takes action based on <b>current</b> percept only. Environment must be fully observable. If not, randomization of actions might work\n* **Condition-action rule** - if something happens, take this action\n* **Transition model** - 1) effects of agent's actions and 2) how world is evolving regardless of what agent does\n* **Sensor model** - how the environment state is represented in the percepts\n* **Model-based reflex agents** - transition + sensor models. Keeps internal state so that current state can be updated with more information.\n* **Goal** - desired situation\n* **Goal-based agents** - instead of condition-action rule, takes model-based reflex agent and uses goal to determine action.\n* **Utility** - performance measure that allows environment states to be compared\n* **Utility-based agents** - Allows agent to decide which goal to pursue by taking action that maximizes the expected utility\n* **Model-free agent** - decides what action to take but doesn't know what happens to environment by taking that action\n* **Atomic representation** - state is a box and has no structure (i.e drive from one city to next city)\n* **Factored representation** - state is split into variables and attributes with values (i.e. gas level, is headlights on or off)\n* **Structured representation** - state has variables/attributes that are related to each other, so we have to also represent the relations\n* **Expressiveness** - structured is the most, atomic is the least\n* **Localist representation** - each concept has a one-to-one mapping with where it is stored in memory\n* **Distributed representation** - each concept is stored in multiple locations in memory. More robust than localist\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nwhitespace is meaningful \n\nstrongly typed: every object has a fixed type (i.e. can't do \"foo\" + 2) \n\ndynamically typed: variables don't have a declared type (i.e. can write z=2 and then z=\"hi\") \n\nstrings are immutable \n\ncan escape special characters: r'\n' \n\ndictionaries are unordered and use hashing \n\ndictionary keys are immutable. if you try to access a key that isn't there, you get error \n\n\t use defaultdict to initialize nonexistent dict values \n\ncan't have multiple functions with the same name \n\nif you're specifying keyword arguments in a function, arguments with assignments (i.e.a=3 instead of 3) have to come at the end \n\n*args to accept any # of keywords in a function, *kwargs if those have to be keywords (i.e. name=\"John\" instead of \"John\") \n\nyou can override magic methods (i.e. default methods for a class such as __add__) \n\niterators are objects with a \\__next\\__() method (if i=iter(x), you can call next(i)) \n\n\ngenerators: iterators that have a \\__next()\\__ method \n\n\t yield will automatically return a generator\n\t a function with yield will run until yield. after it returns the yield, it resumes from where it left off\n\t good for using less memory because values are only computed if they are needed \n\n\n\ntu[-3] --> get the 4th item from the right \n\nx = (1,4,5,6,2) \n\nx[1:-1] --> (4,5,6) \n\nx[1:-1:2] --> (4,6) \n\na = '123'; a[1]=1 --> error \n\na = (1,2,3); a[1]=1 --> error \n\na = [1,2,3]; a[1]=1 --> no error \n\na = ({},{}); a[1][1]=1 --> no error \n \n\n## Module 2 Definitions\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nUninformed: agent has an estimate of the distance to goal \n\nInformed: agent can't estimate distance to goal \n\nWe use abstractions (i.e. represent a trip through cities with just cities and distances, not the speed the car travels, radio on/off, etc) to make it easier to perform actions and get to a solution \n\n\nVacuum cleaner problem: n cells means n*2^n states \n\nSokoban puzzle: n non-obstacle cells and b boxes, n*n! / b!(n-b)! states \n\n\n\n## AIMA Chapter 3.2 Example Problems\n \nState spaces consist of all of the states in the world + the actions that get you from one state to the next \n\nMeanwhile, search trees consist of all of the paths between these states and have a goal. \n \n\n## AIMA Chapter 3.3 Search Algorithms\n\nnode has 4 components of its data structure: \n\n\t state, parent, action, path cost \n\nqueue has 4 components: \n\n\t isEmpty, pop, top, add\n\t pop removes, top just returns the pop but doesn't remove \n\n\nHow do we eliminate redundant paths? \n\n\t 1. remember all the states we have reached already\n\t 2. if it is rare to have 2 redundant paths, don't bother tracking them\n\t 3. check for only cycles and not all redundant paths \n\n\nTo be complete when there is an infinite search space, make sure the search occurrs in a systematic way\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n\n## Module 3 Lecture Notes\n\nIf task environment: fully observable, deterministic, known environment \n\n\t solution = fixed sequence of actions \n\nIf task environment: partially observable or nondeterministic \n\n\t solution based on percepts. Could be branching strategy \n\nSearch problems: \n\n<b>Initial state</b>\n<b>Actions</b>\n<b>Transition Model</b>\n<b>Path Cost</b>: sum of all action costs in the path\n<b>Goal</b> \n\n\nStates don't have parents/children/etc; nodes have those \n\n\nTree Search: doesn't check for redundant paths (longer runtime) \n\nGraph Search: checks for redundant paths by checking to see if a node has already been visited before adding it to frontier \n\n\n<b>Uninformed</b> \n\nBFS: FIFO frontier -- expand the shallowest node that hasn't been visited yet \n\n\t use if there could be infinite search space and some solutions have short paths and can remove paths fast\n\t optimal as long as all actions have the same cost. always complete.\n\t early goal test \n\nDFS: LIFO (stack) frontier -- expand the deepest node that hasn't been visited yet \n\n\t use if limited space (great algo when you have limited memory) and a lot of solutions have long paths and can fine-tune the search fast \n\n\nBacktracking: DFS, but only generate one successors at a time, not all successors \n\n\t even less memory usage than DF because successors are stored by modifying the current state, \nnot creating a new version of the state \n\n\nDepth-Limited Search: DFS with a depth limit (l). Removes infinite paths \n\n\t if l<d, algo incomplete. if l>d, algo not optimal\n\t can use the diameter --largest distance between 2 states-- to set l \n\n\nIterative deepening: do Depth=Limited, but keep increasing depth limit (l) until fail or solution \n\n\t complete (finite, no cycles) and optimal (all actions have same cost)\n\t best uninformed search algo if we have too large of a state space and don't know what we should set d to \n\n\nBidirectional search: searches from both initial and goal state at the same time \n\n\t solution when the 2 frontiers are the same \n\n\nUniform-cost search: Priority Queue frontier -- expand node with lowest path cost (g(n)). Djikstra is UCS without a goal \n\n\t late goal test\n\t That way, we prioritize paths with lower costs because they get popped off the queue first. \n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search. Atomic representation\n* **Planning agent** - Factored or structured representation\n* **Search** - finds a sequence of actions. they form a path from the current node to the goal\n* **Solution** - sequence of actions that form a path to the goal\n* **Open-loop** - ignores percepts after finding solution. agent is no longer connected to the environment\n* **Closed-loop** - tracks percepts after finding solution. better when incorrect model or nondeterministic environment\n* **State space** - set of all states that can be reached from the initial state\n* **Transition model** - from state s and taking action a, what happens?\n* **Path** - sequence of actions between 2 states\n* **Search tree** - how we represent all of the paths. nodes = states, edges = actions. root = initial state. leaves = successors\n* **Frontier** - states that we can pursue further\n* **Expand** - check all of the possible actions from the node\n* **Generate** - create a child or successor node for the node. this node has now been reached\n* **Optimal solution** - there is no other solution that has a lower path cost\n* **Complete** - always finds a solution where there is one and a failure when there is one\n* **Time complexity** - # of nodes created. how long to find a solution?\n* **Space complexity** - # of nodes kept in memory at the same time. how much memory for entire search?\n* **B** - maximum branching factor. number of successors we need to look at for a node\n* **D** - depth of the shallowest node. # of actions taken to get optimal solution\n* **M** - max length of a path (could be inf). max # of actions taken\n* **Uninformed search** - only have the information in the problem definition\n* **Informed search** - have the problem definition and information about location of goal (heuristic function)\n* **Priority queue** - pops the node with minimum f(n)\n* **Heuristic function** - distance from current node to goal node\n* **Cycle** - check if the state we are at has already appeared earlier in the path\n* **Redundant path** - same start and end but different path. cycle is an example\n* **Abstraction** - remove detail to make it easier to do actions--we can take abstract solution and move it into real world\n* **Standardized problem** - use as an exercise to help people understand how to problem solve\n* **Real-world problem** - solution is different based on the scenario (i.e. robots navigating-each robot, different sensor)\n* **Grid world** - 2D rectangular array, agent can move between cells\n* **Absolute** - actions like up, down, left, right\n* **Egocentric** - actions from the agent's viewpoint. forward, turnRight, etc\n* **Sokoban puzzle** - agent needs to push boxes to their goal positions\n* **Sliding-tile puzzle** - (i.e. 8-puzzle) tiles on a grid but 1 or more blank spaces so tiles can move\n* **Route-finding problem** - each state is a location. the edges are the transitions from location to location\n* **Touring problems** - instead of just 1 goal, we have multiple locations to get to\n* **Traveling salesperson problem (tsp)** - visit every location in the graph but cost < C\n* **Vlsi layout** - cell layout + channel routing. put components and connections on a chip. Goal is to minimize area taken\n* **Cell layout** - take components and group them into cells. place cells on chip without overlap and allowing for connections\n* **Channel routing** - takes space between cells and formulates a route for the wire\n* **Robot navigation** - generalization of route finding because robot can create its own path\n* **Automatic assembly sequencing** - optimize the order of assembling something\n* **Early goal test** - check if we have solution when we generate a node\n* **Late goal test** - check if we have solution when we pop the node from the frontier\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nAll consistent heuristics are admissble; not all admissible heuristics are consistent \n\n\nA* uses a lot of memory. O(b^d) space complexity. How can we save memory? \n\n\t 1. split memory between frontier and reached. By storing states in just 1 of the 2 instead of both, we save space \n\t 2. remove states from reached when we don't need them or remove the reached table itself\n\t 3. keep reference counts (number of times we have put state in reached). if we know that a state can only be reached x times,\nremove it from reached when we hit reference count = x \n\n\nBeam search: only keeps k nodes with lowest f(n) in the frontier \n\n\t saves memory, but search is not complete and not optimal \n\n\nIterative deepening A* search: \n\n\t at each iteration, finds the smallest f(n) that was greater than the limit in that iteration. That is the limit for the next iteration.\n\t not good for problems where every node has a different f(n) \n\n\nRecursive best-first search: \n\n\t tracks the f(n) of the best alternative path from any parent of the current node. If tracked f(n) < current f(n) go back to alternative path. \n\nWhile going back, each node's f(n) is replaced with the minimum f(n) --the backed-up value-- of its successors \n\n\t better than iterative deepening A* for memory\n\t optimal if h(n) admissible \n\n\nMA* (memory-bounded A*) and SMA* (simplified MA*): \n\n\t SMA*: once memory is full, drops node with highest f(n). Then assigns the parent that f(n) but also store the lowest f(n) in case we need to come back\n\t if tie for f(n), expand the newest node and delete the oldest node\n\t complete if we can get to solution before running out of memory\n\t optimal if we can reach it before running out of memory \n\n\nBidirectional heuristic search: \n\n\t eval function: f(n) = max(2g(n), g(n) + h(n))\n\t complete and optimal if we use the above eval function and h(n) is admissible\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n\n8-puzzle heuristics: number of misplaced tiles, sum of distances of tiles from goal positions \n\n\t Relaxing the 8-puzzle problem: 1) allow tile to move anywhere and 2) tile can move to any adjacent square \n\n\nGood heuristic has branching factor close to 1 \n\nWe can use precomputation of the costs of some optimal path to generate heuristics faster\nWe can also add shortcuts--artificial edges in a graph that will help in an action with multiple edges-- to improve runtime\nWe can use ML to generate heuristics from experience\n\n\n## Module 4 Lecture Notes\n\nBest-first search: Priority Queue frontier -- uses f(n) to decide the next node to expand. \n\n\nGreedy Best-first search:  Priority Queue frontier -- uses h(n) to decide the next node to expand \n\n\t NOT optimal\n\t NOT complete (only complete in finite state spaces) \n\n\nA* search: best-first search. Use f(n) so we focus on the best paths found but make sure they aren't too expensive \n\n\t if h(n) is admissible, optimal, if h(n) is inadmissible, optimality depends on situation; sometimes we can find a cost-optimal \npath even without an admissible heuristic.\n\t always complete\n\t contours will stretch towards the goal state\n\t con: expands a lot of nodes \n\n\nIf we want to solve problem of expanding too many nodes: \n\nUse an inadmissible heuristic, because it will be more accurate despite overestimating \n(i.e. detour index--need to account for roads curving, so instead of straight line distance (admissible), GPS uses this) \n\nWe can also use weighted A* search \n\n \n\n## Module 4 Definitions\n* **Informed search** - has access to 1) problem definition and 2) heuristic function\n* **Admissible/optimistic** - never overestimates the cost to reach the goal\n* **Consistent** - heuristic for node n <= cost from node n to node n' + heuristic for node n'\n* **Triangle inequality** - 1 side of a triangle has to be less than the sum of the 2 sides\n* **Contours** - draw them on the graph; inside each circle will be every node with f(n)<=some value\n* **Monotonic** - strictly increasing. g(n) is monotonic because action costs are > 0\n* **Surely expanded nodes** - nodes that have f(n) less than the cost of the path of optimal solution\n* **Optimally efficient** - out of all algorithms that have same initial state+heuristic, A* expands fewest # of paths\n* **Pruning** - remove nodes without even considering them\n* **Satisficing solutions** - suboptimal, but still are good\n* **Detour index** - multiple it with straight=line distance\n* **Weighted a* search** - multiple the heuristic with a weight so value it more heavily in f(n)\n* **Bounded suboptimal search** - try to find a solution that is within W*optimal cost\n* **Bounded cost search** - try to find solution with cost < C\n* **Unbounded cost search** - try to find a solution of any cost. the focus is on shortest runtime\n* **Speedy search** - unbounded cost search. heuristic=# of actions to get to goal. so no focus on cost\n* **Front-to-end search** - estimate distance to goal and distance to start in bidirectional\n* **Front-to-front search** - estimate distance to the other frontier in bidirectional\n* **Effective branching factor** - b*. number of new nodes that are added for each node as we increase depth by 1\n* **Dominates** - h2 dominates h1 if h2 will never expand more nodes than h1 during A* search\n* **Manhattan distance** - abs(x_1 - x_2) + abs(y_1 - y_2)\n* **Relaxed problem** - less restrictions on the actions than the original problem. Cost of solution = admissible heuristic for the original problem\n* **Pattern databases** - store the costs of solutions for subproblems of the original problem to help with heuristic of problem\n* **Differential heuristic** - subtract something from heuristic\n* **Metalevel state space** - each action in this changes the internal state\n* **Object-level state space** - each internal state in metalevel learning is an object-level search tree\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nPerfect information = fully-observable \n\nGame: \n\n\t initial state\n\t player whose turn it is\n\t set of legal moves (i.e. actions)\n\t transition model\n\t terminal states\n\t utility function \n\n\nIn minimax, if 1 player does not play optimally, then the other player will do at least as well as if the other player was playing optimally, but probably even better \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nMinimax algorithm: depth-first search. Time complexity: O(b^m). Space: O(bm) \n\n\t won't work on complex games like Chess, Go, etc because too many moves \n\n\nIf a game is not zero-sum, the 2 players might collaborate. If a game is multiplayer, alliances may form between some players \n\nAlpha-beta pruning: Time complexity: best case O(b^(m/2)). Space: O(b^(3m/4)) \n\n\t alpha is the best possible value for MAX (start at -inf)\n\t beta is the best possible value for MIN (start at +inf)\n\t dependent on the order of pruning\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nTo further improve computation time for alpha-beta search, use heuristics to evaluate instead of utility \n\n\t use a cutoff test that will decide when to stop searching\n\t eval(s,p): expected utility at state s for player p \n\n\nFor evaluation functions, we can use features of a state (i.e. assign values to each piece in a chess game) \n\n\t use a weighted linear function where we weigh each feature to caluculate the expected value of the state \n\n\nChess: \n\n\t only apply the eval functions to quiescent states (more other moves to be made after this move)\n\t horizon effect: a very damaging move by opponent that is inevitable but can be avoided for now. we try to use singular extensions (don't cutoff search because not a quiescent state, just play the best move) \n\n\nTo save time, computers use table lookup instead of search for established games \n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games: \n\n\t chance nodes have each move with the probability of it happening\n\t MIN and MAX nodes are what happens if that move happens \n\nExpectiminimax: Time complexity: O(b^m*n^m) where n is the number of moves \n\n\t it's hard to do alpha-beta pruning when you have to deal with chance. but we can improve this by setting lower and upper bounds on the utility function\n\t then, we have upper bounds on the value of a chance node\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nAxioms of utility theory for a rational agent: \n\n\t orderability: agent must be able to decide between 2 sets of outcomes (or set them as equal preference)\n\t transitivity: A>B and B>C, then agent prefers A to C\n\t continuity: if A>B>C, then agent will have equal preference for B and deciding between A and C for some probability\n\t substitutability: if A~B, then [p,A;1-p,C] is the same as [p,B;1-p,C]\n\t monotonicity: if A>B, prefer the set of options that has a higher prob of A occurring \n\t decomposability: can simplify a set of probabilities \n\n\nIf above axioms are followed: \n\n\t existence of utility function: U(A)>U(B) if and only if A>B\n\t expected utility of a lottery: weighted sum of utility of each outcome \n\n\nJust because an agent has a utility function, it doesn't mean that the agent is maximizing it.\n \n\n## AIMA Chapter 16.3 Utility Functions\n \nIf we normalize the utilities, we can see what probablity (p) to assign to the min utility and (1-p) to max utility\nso that p equals the value of the outcome we're looking at. The assignment of p to min and 1-p to max is the standard lottery. \n\nTo find the value that people place on their lives: micromort, QALY \n\nMoney has a monotonic preference (always prefer more). Utility function is NOT monotonic \n(i.e. many people would turn down a gamble for more money compared to get less money for sure ) \n\nRisk-averse agents have a concave down utility curve. Risk-neutral have linear curve. \n\n\nAllias paradox: \n\nDescriptive theory shows a different way of people choosing between 2 options to get money than normative theory. \nThis could be because of the certainty effect -- people want the upside that they are guaranteed of rather than a higher \none that they have a chance, not for sure, of getting \n\nEllsberg paradox: \n\n\t people have ambiguity aversion -- they would rather go with a known chance than a chance that is unknown\n\n\n## Module 5 Lecture Notes\n\nObjectivist/frequentist: use history; take an average over repeated experiments \n\nSubjectivist/Bayesian: use unobserved variables and some belief of them to inform your probabilities\n\n\n## Module 5 Definitions\n* **Adversarial search** - there are multiple agents, unlike search\n* **Zero-sum games** - the positive effect for 1 player = negative effect for the other\n* **Terminal states** - the bottom of the graph -- game has ended\n* **Utility function** - expected value for player p when game ends (is in a terminal state, s)\n* **Expected utility** - average utilities of the possible outcomes. weight them by the probability of the outcome occurring\n* **Maximum expected utility** - agent should pick actions based on maximizing its expected utility\n* **Ply** - a player's move -- progress 1 further in the game tree\n* **Minimax value** - assuming that both players play optimally, what is the utility for the current player\n* **Minimax decision** - the action taken by the player based on the minimax value\n* **Killer moves** - best moves in alpha-beta pruning. can be used as a heuristic\n* **Transpositions** - permutations of moves that have the same end state\n* **Type a strategy** - only considers moves until a specific depth. then, estimates the utility\n* **Type b strategy** - ignores bad moves. follows the good moves until the end of the tree\n* **Material value** - how much each piece in game is worth\n* **Forward pruning** - deletes some moves from search tree, but those moves might be good\n* **Late move reduction** - assume we have ordered moves well. the moves that are later, we don't search them as deeply to save time\n* **Stochastic games** - have randomization in them--chance nodes along with MAX and MIN nodes\n* **Expectiminimax value** - expected value of a node instead of just the non-probabilistic minimax value\n* **Lottery** - the different outcomes that can occur from an action\n* **Value function/ordinal utility function** - deterministic games--actual values of utility functions doesn't matter. we care that preference(aka order) for outcomes stays the same\n* **Preference elicitation** - process of figuring out the utility function by giving choices and then tracking the preferences\n* **Normalized utilities** - normalization but min possible utility is 0 and max possible utility is 1\n* **Value of a statistical life** - allows people to decide the costs and benefits of something\n* **Micromort** - 1 in a million chance of dying\n* **Qaly** - quality adjusted life year\n* **Certainty equivalent** - value accepted by agent instead of basing what they get on probability (won't play the lottery)\n* **Insurance premium** - EMV of lottery - certainty equivalent\n* **Unbiased** - expected value of error is 0\n* **Optimizer's curse** - we tend to overestimate the expected utility, so we shouldn't just blindly accept utility estimates\n* **Normative theory** - how should a rational agent act\n* **Descriptive theory** - how do rational agents actually act\n* **Framing effect** - the wording of a problem can change actions\n* **Anchoring effect** - people will always look relatively, so anchoring them on something first can change preferences\n* **Random variable** - represents an event with an unknown outcome\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \n<b>CSPs</b> \n\n-Use general instead of domain-specific heuristics \n\n-Eliminate large portions of search space all at once by identifying variables that violate constraints. Search procedures without constraints just check if a state is a goal; CSPs allow us to see why a state hasn’t reached a goal. \n\n-Solution must be 1) consistent 2) complete \n\n-Represent a state with a set of variable/value pairs \n\n-Takes exponential time in number of variables \n\n<b>N-Queens</b> \n\n-Example of a discrete, finite domain. Finite: can only have N possible values in domain (possible row numbers for queen in column)\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n<b>CSP Algorithms</b> \n\n-Normal search: states are black boxes and use transition model to move between states. CSP: agent can see inside states and move between states based on what it sees \n\n-Local consistency -- node, arc, path, k \n\n\t arc: X_i arc-consistent with X_j if for every value in D_i there is value in D_j that satisfies binary constraint on (X_i, X_j)\n\t node: 1-consistency\n\t arc: 2-consistency\n\t path: 3-consistency \n\nStrongly k-consistent: chose a consistent value for X_1. guaranteed that X_2 will be consistent because 2-consistent. Can keep doing this for each X.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nBacktracking: This is a form of depth-first search. It's used when we finish constraint propagation but some variables haven't been assigned yet. \n\n\t Repeatedly choose a value left in domain of unassigned variable. \n\t Using recursion, try to extend into a solution. If not a solution, backtrack and try the next possible assignment. Keeps 1 representation of state. \n\nVariable selection is fail-first, value-selection is fail-last. This is so we reduce backtracking by picking the hardest variables to assign first and\nthen focus on the best possible values for it. \n\nBackjumping allows you to not waste time on variables that won't fix problem. We back up beyond those variables.\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search is good for solving a lot of CSPs. You change the value of one variable at a time, and is good for when a small part of problem\nchanges and we don't want to go use backtracking (which would take longer because it searches through everything again). \n\n## AIMA Chapter 6.5 The Structure of Problems\n We can take constraint graphs and solve them more efficiently with trees. \n\nThe first way is Cutset conditioning. \n\n\t Reduce a CSP to a tree structure by assigning a value to variables that won't fit into the tree (cycle cutset). \n\t Then, we can test the remaining values in the domains of the remaining variables\n\t Linear time (space complexity). Less time efficient than tree decomp.\n\nThe second way is Tree Decomposition. \n\n\t Each node is a subproblem -- we transform the CSP into a tree of subproblems. \n\t Exponential time (space complexity). More time efficient than cutset.\n\t\t 1) all variables must be in at least 1 tree node\n\t\t 2) if 2 variables are in a constraint, they have to be in tree together\n\t\t 3) if variable is in 2 nodes within tree, it also has to be in every node in the path between the 2 nodes\n\t\t lastly, it is efficient if the tree width of the graph is small\n\n\n\n## Module 6 Lecture Notes\n\nDifference between MAC and AC-3: MAC interleaves search and inference because it only checks the arcs of the current variable using backtracking.\nAC-3 is only inference. After MAC checks the variable, it runs like AC-3. \n\n\nAC-3: doesn't solve all CSPs. only solves the ones that need just arc consistency.\n\n\n## Module 6 Definitions\n* **Csp** - represent the conditions for a solution with a set of constraints on the variables. NP-Complete problem.\n* **Cryptarithmetic** - Problem where letters represent numbers. Has constraint hypergraph\n* **Constraint hypergraph** - Has ordinary nodes and hypernodes. The hypernodes are when constraints aren't unary or binary (they are n-ary).\n* **Dual graph** - Take original graph. 1 variable for each constraint. Then, add binary constraint between variables that share constraints for each constraint.\n* **Consistent** - the variable assignment doesn't violate any constraints\n* **Complete assignment** - every variable ends up being assigned a value\n* **Partial assignment** - some variables don't get an assignment\n* **Partial solution** - when there is a partial assignment but the solution is consistent\n* **Constraint graph** - Nodes: variables. Edges: connect variables that participate in a constraint.\n* **Precedence constraints** - a task (i.e. job scheduling) needs to happen before another task, do Task+time to complete <= Next Task\n* **Disjunctive constraints** - 2 tasks cannot overlap, do Task+time to complete <= Next Task OR Next Task+time to complete <= Task\n* **Discrete domain** - There are infinite possible values for variable. We have to use implicit constraints (precendence, disjunctive) rather than the values themselves\n* **Linear constraints** - The variable is only in linear form\n* **Nonlinear constraints** - You can't solve algorithms if you have nonlinear constraints\n* **Continuous domains** - Example is job scheduling if jobs are precisely timed. Linear programming problems have this--constraints are equalities/inequalities\n* **Unary constraint** - restricts value of 1 variable (i.e. NSW != green)\n* **Binary constraint** - restricts value of 2 variables (i.e. SA != NSW)\n* **Binary csp** - Only has unary + binary constraints\n* **Global constraint** - involves arbitrary number of variables (i.e. Sudoku -- all variables in box must have different values)\n* **Resource constraint** - aka Atmost constraint. Max number of resources allowed to be allocated to each variable.\n* **Bounds propagation** - When you have too many values in domain so can't list in resource constraint, just represent as a bound.\n* **Bounds-consistent** - When there is a value that satisfies upper and lower bound in a CSP\n* **Preference constraint** - certain solutions preferred (professor wants to teach morning). Can be cost (lower for preference). Makes it Constrained Optimized Problem\n* **Constraint propagation** - using constraints to reduce number of legal values for variable-->reduces number of legal values for other variables-->etc\n* **Local consistency** - node → variable and edge → binary constraint. Allows us to eliminate inconsistent values throughout graph\n* **Node consistency** - all values in the domain satisfy variable’s unary constraints. Graph = node-consistent if every variable in graph is node-consistent\n* **Arc consistency** - all values in domain satisfy variable’s binary constraints. Graph = arc-consistent if every variable in graph is arc-consistent\n* **Path consistency** - X_i and X_j path consistent with X_m if there is assignment to X_m where {X_i,X_m} and {X_j,X_m} constraints are valid.\n* **K-consistency** - Have k variables (k=number of states), for any k-1 variables with consistent assignments, there is consistent assignment for k.\n* **Strongly k-consistent** - K-consistent AND k-1 consistent AND k-2 consistent .. 1 consistent. O(d*n^2)\n* **Commutativity** - All CSPs have this. Order of applying actions doesn't matter.\n* **Minimum-remaining-values** - MRV heuristic. You choose the variable that has the fewest values left in its domain.\n* **Degree heuristic** - Pick the variable that is in the most constraints with the variables that haven't been assigned yet.\n* **Least-constraining-value heuristic** - Pick value for variable that results in least number of choices ruled out for variables in constraints with this variable.\n* **Forward checking** - Establish arc consistency for variable. When variable assigned value, remove inconsistent values from neighbors (in constraint with variable).\n* **Maintaining arc consistency** - Addition to forward checking--after assigning value, immediately check the neighbors of variable.\n* **Chronological backtracking** - In backtracking, we look at the previous decision made if we fail in a specific branch of tree.\n* **Conflict set** - set of assignments to variables causing conflict for another variable (can't assign anything to the variable).\n* **Backjumping** - better than chronological backtracking. Go to previous assignment of conflict set.\n* **Conflict-directed backjumping** - Go to previous assignment of conflict set AND any variables that came after\n* **Constraint learning** - Get the minimal set of variables in the conflict set that are causing the inconsistency\n* **No-good** - Set of variables found by constraint learning. Stored as a set of no-goods or adding a constraint.\n* **Min-conflicts** - Heuristic. Picks a value for variable that causes least # of conflicts with other variables.\n* **Tabu search** - Can have many states in plateau -- 1 conflict away from solution. Store recent visited states so algorithm avoids them.\n* **Constraint weighting** - Pick variable and value that have lowest weight compared to constraints that are being violated. Ensures most important constraints.\n* **Independent subproblems** - subproblems are not connected components in the graph\n* **Tree** - 2 variables in a constraint graph have only 1 path between them\n* **Directional arc consistency** - Every variable is consistent with the variables after it\n* **Topological sort** - A variable is the root and then the order of the variables after it is the topological ordering\n* **Tree width** - the size of the largest node in a Tree Decomposition - 1.\n* **Value symmetry** - there are multiple ways to satisfy a constraint (i.e. WA,NT,SA different colors but any combo of 3 colors).\n* **Symmetry-breaking constraint** - set some ordering of values (i.e. NT<WA<SA) so we only get one of the orderings in the value symmetry\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nWhen an agent program is called: \n\n\t tells KB the percepts (what is perceives)\n\t queries KB for what action should be performed\n\t tells KB the action it chose \n\n\nUse the knowledge base to arrive at a set of possibilities which are a subset of the possible worlds \n\n\nDeclarative approach -- just tell agent sentences for how to operate 1 at a time \n\nProcedural approach -- encode what the agent should be doing in code \n\nHave to combine declarative and procedural.\n \n\n## AIMA Chapter 7.2 The Wumpus World\n \n\n\n## AIMA Chapter 7.3 Logic\n\nPossible world: x women and y men sitting at a table. Model: all possible nonnegative integers as x and y \n\nModel m satisfies sentence s if sentence s is true in model m \n\n\na⊨B if and only if M(a) is a subset of M(b). a is more specific (Honda) and stronger than b (car). \n\n\t if KB⊨a and in every model in which KB is true a is also true, then KB entails a and the agent can conclude that a is true.\n\t if KB⊨a and KB is true in some models but a is false in those models, then KB does not entail a and the agent can't conclude that a is true. \n\n\nYou go and check the entire KB. Go through every sentence. If in all the worlds possible with the KB, the statement is also true,\nwe can say that KB entails the statement. If in all the worlds possible with the KB, the statement is false in some (or all) of them,\nKB does not entail the statement. \n\n\nIf KB and statement have n symbols, time complexity of seeing if KB entails statement is O(2^n) and space complexity is O(n) \n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nAtomic sentences are represented with single propositional symbols (i.e W, FacingEast) \n\nComplex sentences have atomic sentences on each side of operators \n\n\t ∧: and || V: or || ¬: not || ⇒: implies || ⇔: if and only if (biconditional)\n\t ¬ has the tightest bind, so ¬A ∧ B = (¬A) ∧ B instead of ¬(A ∧ B) \n\n\n\t And-Elimination: a ∧ b = a OR a ∧ b = b\n\t Modus Ponens: a⇒b and a is a sentence, then we know b\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n≡: logically equivalent. If a⊨B and B⊨a, then ≡ \n\nAll logical equivalence rules can be rewritten as inference rules (i.e numerator/denominator form) \n\nBecause of this, we can use search algorithms to solve a KB \n\n\na⊨b if and only if (a ∧ ¬b) is not satisfiable. can prove this using proof by contradiction \n\n\t convert KB ∧ ¬a to CNF and then apply resolution rule. resolve all the complementary literals\n\t if the result of resolution isn't already in KB, add it and keep repeating\n\t stop when we can't add anymore new clauses (KB doesn't entail a) or 2 clauses (i.e. B, ¬B) lead to an empty clause (KB entails a)\n\nUsing inference to get to the goal is 1 way, but how do we know the solution is complete--that we have *all* the entailed sentences? \n\n\t Resolution: the single inference rule that tells us that the algorithm is complete. You take the sentences that have just 1 term and remove that term from other sentences\n\t for example, if ¬b is a literal and another sentence says a V b V c, then we can change that to a V c.\n\t unit resolution: if we have b and ¬b (complementary), we can eliminate both of them. Take both clauses and combine them without b and ¬b\n\t **important: you can only resolve ONE pair of complementary literals at a time\n\n\n\n## Module 7 Lecture Notes\n\nTo convert to CNF: \n\n\t replace a⇔b with (a⇒b)∧(b⇒a)\n\t replace a⇒b with ¬a V b\n\t move the ¬ inside by removing double negation and De Morgan's rules\n\t apply distributivity law to distribute V over ∧ when you can \n\nHorn clauses > Definite Clauses and goal clauses\n\t if you apply resolution to a Horn clause, you will get a Horn clause\n\t seeing if KB entails a using Horn clauses: linear time \n\nEvery Definite clause can be written as (conjunction of positive literals) ⇒ positive literal\n\t example: ¬A V ¬B V C = A ∧ B ⇒ C\n\nForward chaining\n\t start with the known facts (single positive literals). check the implications and if their premises are all known, then add the conclusion of the implication to the KB\n\t keep going until no more inferences can be made\n\t linear time. sound and complete\n\nBackward chaining\n\t start with a query. if it's true, do nothing, if not, find implications where the conclusion is the query\n\t if the premises in that implications are all true (might have to do more backward chaining), query is true\n\n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning and their internal representation of knowledge to decide what action to perform\n* **Knowledge base (kb)** - set of sentences written in knowledge representation language. can have some background knowlde to start\n* **Axiom** - sentence that is given\n* **Derived sentence** - new sentence from old sentence (aka inference)\n* **Knowledge level** - to decide actions of agent: 1)what it knows and 2)know the goals. don't need to know implementation level\n* **Syntax** - indicates all sentences are formed properly\n* **Semantics** - meaning of sentences. For each possible world, what is the truth of each sentence\n* **Model** - mathematical abstraction of each possible world the agent could be in\n* **Entailment** - 1 sentences follows another sentence logically. In every model a is true, B is true. a⊨B --> a entails B\n* **Model checking** - assume KB⊨a. go through all possible models and check that a is true where KB is true\n* **Sound / truth-preserving** - when an inference model derives only entailed sentences\n* **Completeness** - inference can derive *all* sentences that are entailed\n* **Grounding** - to know if KB is true in real world, use the agent's sensors\n* **Premise/antedecent** - what comes before arrow\n* **Conclusion/consequent** - what comes after arrow\n* **Truth value** - true or false\n* **Theorem proving** - alternative to model checking where we just use inference on the sentences without models\n* **Logical equivalence** - A and B are true in the same set of models. then they are logically equivalent\n* **Validity** - sentence is true in all models. sentences that are valid are tautologies\n* **Deduction theorem** - a⊨B if and only if a⇒b is VALID\n* **Satisfiability** - sentence is true in some (not necessarily all) models. NP-Complete problem\n* **Monotonicity** - the number of entailed sentences in KB can only increase as we add more info to the KB\n* **Complementary literals** - one is the negation of the other\n* **Clause** - multiple literals combined (i.e. a V b V c)\n* **Unit clause** - a single literal that is a disjunction of 1 literal\n* **Factoring** - removing multiple copies of a literal -- A V A = A\n* **Cnf** - sentence that only has V, ¬, and ∧. Eliminate ⇒ and ⇔\n* **Definite clause** - disjunction of literals but ONLY 1 LITERAL is positive\n* **Horn clause** - disjunction of literals but AT MOST 1 is positive\n* **Goal clauses** - no positive literals\n* **Body** - in horn clauses, the premise\n* **Head** - in horn clauses, the conclusion\n* **Fact** - a single positive literal that is the only literal in the sentence\n* **Data-driven reasoning** - you begin with known data and then keep adding to your knowledge. forward-chaining\n* **Goal-directed reasoning** - backward chaining\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}