{
  "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": "d8d081f1-9f7b-46ad-aa0e-5f6bc5569ab2"
      },
      "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": "4bc24eb4-4346-46a9-dccc-9272c7de028e"
      },
      "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 = True"
      ],
      "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 = \"\"\" Intellegence and rationality - thoughtprocesses and reasoning(internal) vs. intelligent behavior(external). The Turing test was a thought experiment \\\n",
        "that would test if a machine can act \"humanly\". The computer would need NLP, knowledge representation (to store), automated reasoning (to answer qs and draw new conclusions), and machine learning to adapt, detect, and extrapolate patterns.\n",
        "Another proposal was the total Turing test, where the robot would need computer vision & speech recognition to perceive the world and robotics to manipulate objects and move.\n",
        "\n",
        "Human thought: introspection, psychological experiments, and brain imaging\n",
        "\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" GOFAI - hard to capture everything in a set of necessary and sufficient logical rules (the qualification problem). But probabilistic reasoning is sometimes better anyways.\n",
        "Argument from disability - \"a machine can never do X\". Mathematical objection - Godel's incompleteness theorem showed that machines are mentally inferior to humans. BUT, \\\n",
        "an agent shouldn't be ashamed that it cannot establish the truth of a sentence. Also, theorem is only applicable to mathematics. Finally, Luca's claim is based on the assertion that computers are equivalent to Turing machines which is not true. \n",
        "Turing argued that we should rather ask if machines can pass a behavioral test (the Turing test).  \"\"\"\n",
        "chapter27_2 = \"\"\" Can machine's think? John Searle used the Chinese room argument. He was also a proponent of biological naturalism. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Agent's choices/actions depends on its built in knowledge and percept sequence but not anything it has yet to perceive. Its behavior is its agent function, which maps a percept sequence to an action.\\\n",
        "The agent function is implemented by an agent program (concrete, run with physical system).  \"\"\"\n",
        "chapter2_2 = \"\"\" Rational agents do the right thing; Consequentialism. A performance measure evaluates any given sequence of environment states. It's better to diesng \\\n",
        "formance measures based on what you want to be achieved in the environment vs. then how we think the agent should behave. Rationality depends on 4 things: performance measure that defines criteria of success, \\\n",
        "agent's prior knowledge of the environment, actions agents can perform, and agent's percept sequence to date. Therefore, a rational agent means that for each percept sequence, it should perform an action that maximizes the performance measure, \\\n",
        "given evidence from the percept sequence and its built-in knowledge.\n",
        "\n",
        "Rationality vs. omniscience - omnicience is impossible. Rationality maximizes expected performance but perfection maxes actual. Rational agents need to do actions in order to modify future percepts, or info gathering.\n",
        "Rational agents should also be autonomous and should learn what to do to compensate for partial/incorrect prior knowledge. \"\"\"\n",
        "chapter2_3 = \"\"\"PEAS - perf, environment, actuators, sensors. We should always specify the task environment as fully as possible for the agent.\n",
        "Fully observable task environments are where the sensors can detect all aspects that are relevant to the action choice (relevance depends on performance measure). \n",
        "There might be partially observable environments due to noisy/inaccurate sensors or missing data. Determine multiagent environemnts my checking if B's behavior is maximizing a performance measure that has a value dependent on A's behavior.\n",
        "An environment is deterministic if the next state can be completely determined by current state and action made by the agent. Stochastic - explicitly deals w/probabilities.\n",
        "\n",
        "Episodic vs. sequential: an episodic task environment is one where the agent's experience is divided into atomic episodes and the agent gets a percept and performs a single action in each episode. The next episode doesn't depend on previous episodes or actions.\n",
        "Sequential environemnts are the ones where the current decision can affect all future decisions. Static vs. Dynamic: environment changing vs. not while agent is deliberating. Semidynamic if environment doesn't change but perf score does with time.\n",
        "Discrete vs. continuous:  state of the environment and how time is handled, and the percepts and actions. E.g. chess is discrete but taxi driving is continuous. Known vs. unknown - outcomes in environment given vs not.\n",
        "Possible for known environments to be partially observable and unknown environments to be fully observable. \n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\" agent - architecture (computing device w/ physical sensors and actuators) + program. program takes current percept as input but function depends on percept history.\n",
        "the key challenge for AI is to find out how to produce rational behavior with a small program vs. building out a big table. There are 4 types of agent programs: \n",
        "\n",
        "Simple Reflex Agents: select action on basis of the current precept and ignores the history. condition-action rule. some unobservability can cause trouble. \n",
        "\n",
        "Model-based reflex Agents: effective way to handle partial observability: keep track of the part of the world we can't see. maintain internal state dependent on percept history. \\\n",
        "to update this internal info state, need to know how agent's actions affects world and how world evolves independently of the agent. transitional model of the world. then, we need info on how state of the world is reflected in the agent's percepts. this is a sensor model.\n",
        "This all put together becomes a model-based agent.\n",
        "\n",
        "Goal-based agents: Need to know what situations are desirable. Needs consideration of the future (search and planning). \n",
        "\n",
        "Utility-based agents: A utility function is an internalization of the performance measure and agents maximize the expected utility. Not all utility agents are model based. Model-free agents exist where it can learn what action is best without knowing how the action impacts the environment. \n",
        "\n",
        "Learning agents - 4 components: learning element, performance element, critic, problem generator.\n",
        "\n",
        "There are finally three ways to represent states and transitions: atomic (no internal structure), factored (vector of attr. values), and structured (objects that have attr and relationships to others)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment (uses sensors and actuators)\",\n",
        "\"rational agent\" : \"agent that acts for the best expected outcome\",\n",
        "\"limited rationality\" : \"acting appropriately when you're limited\",\n",
        "\"value alignment problem\": \"the problem between getting our true preference vs. the objective\",\n",
        "\"weak AI\" : \"machines act as if they're smart\",\n",
        "\"strong AI\" : \"machines are actually consciously thinking\",\n",
        "\"percept\" : \"content agent is perceiving via its sensors\",\n",
        "\"percept sequence\" : \"history of percepts\",\n",
        "\"task environment\" : \"the problems\",\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": "d73e6995-36a2-4f4f-e963-2ef704219169"
      },
      "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 Intellegence and rationality - thoughtprocesses and reasoning(internal) vs. intelligent behavior(external). The Turing test was a thought experiment that would test if a machine can act \"humanly\". The computer would need NLP, knowledge representation (to store), automated reasoning (to answer qs and draw new conclusions), and machine learning to adapt, detect, and extrapolate patterns.\nAnother proposal was the total Turing test, where the robot would need computer vision & speech recognition to perceive the world and robotics to manipulate objects and move.\n\nHuman thought: introspection, psychological experiments, and brain imaging\n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n GOFAI - hard to capture everything in a set of necessary and sufficient logical rules (the qualification problem). But probabilistic reasoning is sometimes better anyways.\nArgument from disability - \"a machine can never do X\". Mathematical objection - Godel's incompleteness theorem showed that machines are mentally inferior to humans. BUT, an agent shouldn't be ashamed that it cannot establish the truth of a sentence. Also, theorem is only applicable to mathematics. Finally, Luca's claim is based on the assertion that computers are equivalent to Turing machines which is not true. \nTuring argued that we should rather ask if machines can pass a behavioral test (the Turing test).  \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Can machine's think? John Searle used the Chinese room argument. He was also a proponent of biological naturalism. \n\n## AIMA 2.1 Agents and Environments\n Agent's choices/actions depends on its built in knowledge and percept sequence but not anything it has yet to perceive. Its behavior is its agent function, which maps a percept sequence to an action.The agent function is implemented by an agent program (concrete, run with physical system).  \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Rational agents do the right thing; Consequentialism. A performance measure evaluates any given sequence of environment states. It's better to diesng formance measures based on what you want to be achieved in the environment vs. then how we think the agent should behave. Rationality depends on 4 things: performance measure that defines criteria of success, agent's prior knowledge of the environment, actions agents can perform, and agent's percept sequence to date. Therefore, a rational agent means that for each percept sequence, it should perform an action that maximizes the performance measure, given evidence from the percept sequence and its built-in knowledge.\n\nRationality vs. omniscience - omnicience is impossible. Rationality maximizes expected performance but perfection maxes actual. Rational agents need to do actions in order to modify future percepts, or info gathering.\nRational agents should also be autonomous and should learn what to do to compensate for partial/incorrect prior knowledge. \n\n## AIMA 2.3 The Nature of Environments\nPEAS - perf, environment, actuators, sensors. We should always specify the task environment as fully as possible for the agent.\nFully observable task environments are where the sensors can detect all aspects that are relevant to the action choice (relevance depends on performance measure). \nThere might be partially observable environments due to noisy/inaccurate sensors or missing data. Determine multiagent environemnts my checking if B's behavior is maximizing a performance measure that has a value dependent on A's behavior.\nAn environment is deterministic if the next state can be completely determined by current state and action made by the agent. Stochastic - explicitly deals w/probabilities.\n\nEpisodic vs. sequential: an episodic task environment is one where the agent's experience is divided into atomic episodes and the agent gets a percept and performs a single action in each episode. The next episode doesn't depend on previous episodes or actions.\nSequential environemnts are the ones where the current decision can affect all future decisions. Static vs. Dynamic: environment changing vs. not while agent is deliberating. Semidynamic if environment doesn't change but perf score does with time.\nDiscrete vs. continuous:  state of the environment and how time is handled, and the percepts and actions. E.g. chess is discrete but taxi driving is continuous. Known vs. unknown - outcomes in environment given vs not.\nPossible for known environments to be partially observable and unknown environments to be fully observable. \n \n\n## AIMA 2.4 The Structure of Agents\n agent - architecture (computing device w/ physical sensors and actuators) + program. program takes current percept as input but function depends on percept history.\nthe key challenge for AI is to find out how to produce rational behavior with a small program vs. building out a big table. There are 4 types of agent programs: \n\nSimple Reflex Agents: select action on basis of the current precept and ignores the history. condition-action rule. some unobservability can cause trouble. \n\nModel-based reflex Agents: effective way to handle partial observability: keep track of the part of the world we can't see. maintain internal state dependent on percept history. to update this internal info state, need to know how agent's actions affects world and how world evolves independently of the agent. transitional model of the world. then, we need info on how state of the world is reflected in the agent's percepts. this is a sensor model.\nThis all put together becomes a model-based agent.\n\nGoal-based agents: Need to know what situations are desirable. Needs consideration of the future (search and planning). \n\nUtility-based agents: A utility function is an internalization of the performance measure and agents maximize the expected utility. Not all utility agents are model based. Model-free agents exist where it can learn what action is best without knowing how the action impacts the environment. \n\nLearning agents - 4 components: learning element, performance element, critic, problem generator.\n\nThere are finally three ways to represent states and transitions: atomic (no internal structure), factored (vector of attr. values), and structured (objects that have attr and relationships to others)\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment (uses sensors and actuators)\n* **Rational agent** - agent that acts for the best expected outcome\n* **Limited rationality** - acting appropriately when you're limited\n* **Value alignment problem** - the problem between getting our true preference vs. the objective\n* **Weak ai** - machines act as if they're smart\n* **Strong ai** - machines are actually consciously thinking\n* **Percept** - content agent is perceiving via its sensors\n* **Percept sequence** - history of percepts\n* **Task environment** - the problems\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 = \"\"\" Python has fast development (concise, whitespace delimited, garbage collected), portable, various built-in types like lists, dicts, sets, and large collection of support libraries.\n",
        "Python REP (read evaluate print loop) environment vs hw scripts. All data treated as objects. strong typing. Java is static typing while python is dynamic typing. \n",
        "\n",
        "Strings are immuatble. prefixing them with r means raw and no need to escape special chars. == same value, is checks same object. \n",
        "Lists are mutable. Tuples immutable. Can be of mixed types, including collection types. Dictionaries are unordered and work by hashing so keys are immutable. Constant time add, lookup, update. \n",
        "Java diff methods by their signature (mthod name and types of its args) but python doesn't allow function overloading. Name alone. Operator overloading is ok though. **kwargs is a dict of the keyword args passed to fn\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 317
        },
        "outputId": "69c73fd1-6081-49a2-9816-4a81aa7c3356"
      },
      "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 Python has fast development (concise, whitespace delimited, garbage collected), portable, various built-in types like lists, dicts, sets, and large collection of support libraries.\nPython REP (read evaluate print loop) environment vs hw scripts. All data treated as objects. strong typing. Java is static typing while python is dynamic typing. \n\nStrings are immuatble. prefixing them with r means raw and no need to escape special chars. == same value, is checks same object. \nLists are mutable. Tuples immutable. Can be of mixed types, including collection types. Dictionaries are unordered and work by hashing so keys are immutable. Constant time add, lookup, update. \nJava diff methods by their signature (mthod name and types of its args) but python doesn't allow function overloading. Name alone. Operator overloading is ok though. **kwargs is a dict of the keyword args passed to fn\n\n \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Problem solving agents use atomic representations where the states of the world are considered as wholes. Planning agents used factored/structured representations. Only consider simplest environments for now, \\\n",
        "where it's episodic, single agent, fully observable, deterministic, static, discrete, and known. If environment is not unknown (if it is, random is best choice), agents follow a 4-phase process: (1) Goal formulation: adopts a goal \\\n",
        "which limits objectives and the actions that are to be considered. (2) Problem formulation: gets a description of the states and actions needed to get to the goal. (3) Search: Before we take any actions, the agent simulates sequences of actions in its model \\\n",
        "and finds all sequences (solutions) that reaches the goal. (4) Execute! VERY IMPORTANT that in a fully observable, deterministic, and known environment, the solution is a fixed sequence of actions. This is an open-loop system, where ignoring the percepts breaks \\\n",
        "the loop between agent and environment. The search problem has a state space, initial state, goal states, transition model, action cost function. There are also actions availbale to the agent, which are applicable to the state. PS agents use action cost functions \\\n",
        "that reflect its own performance measure. Therefore, the optimal solution has the lowest action cost. When we formulate a problem, we find a level of abstraction and it's valid if we can elaborate any abstract solution into a solution in a more detailed world. \\\n",
        "It's useful if carrying out each action in the solution is easier than doing so in the original problem.  \"\"\"\n",
        "chapter3_2 = \"\"\" Standardized vs real-world problems: concise, exact description and more for research purposes while real world problems have formulations that are not standardized. \n",
        "\n",
        "Standardized: grid world - 2D array where agents can move from cell to cell like the vacuum world. Sokoban puzzle (push boxes to locations). Sliding tile puzzle. \n",
        "\n",
        "Real world problems: route-finding problem. Touring problems like TSP. VLSI layout (putting components and connections on a chip to minimize area, circuit delays, stray capacitances, and max manufacturing yield). Robot nav. Auto assembly sequencing (protein design) \"\"\"\n",
        "chapter3_3 = \"\"\" Utilizing search trees in a search algorithm. The frontier is the unexpanded nodes and it separates expanded nodes and those that have not been reached yet.\n",
        "\n",
        "Best First Search: Choose a node using an evaluation function that has minimum value. If it's a goal state, return, else, expand. There can be cycles, which is a special case of a redundant path. So even if a state space has say X states, the complete search tree can \\\n",
        "be infinite since we can loop forever. Best First Search remembers all previously reached states so we can detect redundant paths. Good when many redundancies or when the table of reached states fits in memory (graph search). We can also not worry, if it's impossible/rare (tree-like search). \\\n",
        "Finally, we can check for cycles but not redundant paths. See if state at the end of the path appeared previously. \n",
        "\n",
        "Evaluating algorithms' performance: (1) Completeness: guaranteed to find a solution where it exists and report failure when not? (2)Cost optimality: lowest path cost solution? (3) Time complexity (4) Space complexity || To be complete, a search algo has to systematically approach exploring an \\\n",
        "infinite state space. But if there's an infinite space with no solution, a sound algo actually searches forever :(. Complexities are measured in terms of d (depth/# actions in optimal solution) and m (max actions in any path) and b(branching factor/#successors of a node that need to be considered).\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\"Uninformed Search algos don't know how close they are to the goal state. If all actions have the same cost, BFS is good. FIFO queue here is faster than priority queue and gives us correct order. Our reached can be a set of states, we can also early goal test (check solution on generation \\\n",
        "vs. in BFS wait until it's poppped off queue). BFS always finds solution with min. number of actions. But not necessarily cost optimal for problems with varying costs. But complete regardless. Memory requirements are a bigger issue here than execution time (exponential space bound). We can conclude that exponential \\\n",
        "complexity search problems can only be solved by uninformed search for small problems. \n",
        "\n",
        "Dijkstra's algo or uniform cost search: essentially best first search where evaluation function is cost of path from root to current node! Spread out via uniform path cost. ONLY CHECKS FOR GOAL WHEN NODE IS EXPANDED. Otherwise, prematurely can pick the wrong solution. The complexity of this is in terms of C, \\\n",
        "cost of optimal solution, and e, lower bound on cost of each action. Worst case is O(b^{1 + C/e}) which is actually bigger than b^d. It's complete and cost-optimal!\n",
        "\n",
        "DFS and memory issues: expands deepest node in frontier. Not cost-optimal, finds first solution it hits. For finate spaces it's efficient and complete but for acyclic spaces might expand same state many times but will eventually explore the entire space. On the other hand, it can get stuck in loops in cyclic spaces. \\\n",
        "DFS is incomplete :(. For finite-tree-like-search: DFS has less memory requirements since we don't keep track of visited states and frontiers are very small. Takes time proportional to number of states and only O(bm) memory! Mainly in constraint staisfaction, propositional satis, and logical programming. A variant of this, \\\n",
        "backtracking search, uses even less memory! Only one successor generated and remembers what to generate next and we modify the state vs create a new one. O(m)! \n",
        "\n",
        "Depth-limited and iterative deepening search: Helps keep DFS from going down an infinite path. Supply depth limit l. Time complexity is O(b^l), space O(bl). But if l incorrect, incomplete algo. We can eliminate cycles if we go up the parent chain. Knowing the diameter of the state-space graph is a good start for the depth limit \\\n",
        "but that's hard to know until we solve the problem. For iterative deepening, we solve the issue of finding a good l by continuously deepning until a solution is found or failure is found. O(bd) memory when solution exists and O(bm) on finite space w/no solution. Optimal for same-cost problems and complete on finite acyclic spaces or \\\n",
        "spaces where we check for cycles. Time is O(b^d) with solution, O(b^m) without. Number of nodes generated in worst case is O(b^d) so not too bad.\n",
        "\n",
        "Bidirectional search: from initial and goal states hoping two searches will meet. Need to 2 frontiers and 2 tables of reached states, also need to know backwards successors.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Graph search: we can check to see if a node has been visited before adding it to the search queue. Use DFS if space is restricted, many possible solutions with long paths/wrong ones that terminate fast, or search can be made better quickly. BFS if possible infinite paths, solutions are short, or can quickly find \\\n",
        "wrong paths. For depth limited search, if l = d, then optimal. if l < d, incomplete, if l > d, not optimal. ID is complete if no infintie paths, and optimal if step cost is 1.  \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"informed algorithm\" : \"agents can estimate how far they are from the goal, opposite of uninformed algos\",   \n",
        "\"closed-loop\" : \"an approach where the percepts are monitored (model incorrect/environment nondeterministic)\",\n",
        "\"state space\" : \"set of states that the environment can be in\",\n",
        "\"transition model\" : \"tells us what each action does/returns state that results from action on state\",\n",
        "\"action cost function\" : \"tells us the cost of applying an action on a state\",\n",
        "\"search algorithms\" : \"given a search problem, returns a solution or notes failure\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "cfa472c0-8013-4e31-d3c0-430af2088c99"
      },
      "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 Problem solving agents use atomic representations where the states of the world are considered as wholes. Planning agents used factored/structured representations. Only consider simplest environments for now, where it's episodic, single agent, fully observable, deterministic, static, discrete, and known. If environment is not unknown (if it is, random is best choice), agents follow a 4-phase process: (1) Goal formulation: adopts a goal which limits objectives and the actions that are to be considered. (2) Problem formulation: gets a description of the states and actions needed to get to the goal. (3) Search: Before we take any actions, the agent simulates sequences of actions in its model and finds all sequences (solutions) that reaches the goal. (4) Execute! VERY IMPORTANT that in a fully observable, deterministic, and known environment, the solution is a fixed sequence of actions. This is an open-loop system, where ignoring the percepts breaks the loop between agent and environment. The search problem has a state space, initial state, goal states, transition model, action cost function. There are also actions availbale to the agent, which are applicable to the state. PS agents use action cost functions that reflect its own performance measure. Therefore, the optimal solution has the lowest action cost. When we formulate a problem, we find a level of abstraction and it's valid if we can elaborate any abstract solution into a solution in a more detailed world. It's useful if carrying out each action in the solution is easier than doing so in the original problem.  \n\n## AIMA Chapter 3.2 Example Problems\n Standardized vs real-world problems: concise, exact description and more for research purposes while real world problems have formulations that are not standardized. \n\nStandardized: grid world - 2D array where agents can move from cell to cell like the vacuum world. Sokoban puzzle (push boxes to locations). Sliding tile puzzle. \n\nReal world problems: route-finding problem. Touring problems like TSP. VLSI layout (putting components and connections on a chip to minimize area, circuit delays, stray capacitances, and max manufacturing yield). Robot nav. Auto assembly sequencing (protein design) \n\n## AIMA Chapter 3.3 Search Algorithms\n Utilizing search trees in a search algorithm. The frontier is the unexpanded nodes and it separates expanded nodes and those that have not been reached yet.\n\nBest First Search: Choose a node using an evaluation function that has minimum value. If it's a goal state, return, else, expand. There can be cycles, which is a special case of a redundant path. So even if a state space has say X states, the complete search tree can be infinite since we can loop forever. Best First Search remembers all previously reached states so we can detect redundant paths. Good when many redundancies or when the table of reached states fits in memory (graph search). We can also not worry, if it's impossible/rare (tree-like search). Finally, we can check for cycles but not redundant paths. See if state at the end of the path appeared previously. \n\nEvaluating algorithms' performance: (1) Completeness: guaranteed to find a solution where it exists and report failure when not? (2)Cost optimality: lowest path cost solution? (3) Time complexity (4) Space complexity || To be complete, a search algo has to systematically approach exploring an infinite state space. But if there's an infinite space with no solution, a sound algo actually searches forever :(. Complexities are measured in terms of d (depth/# actions in optimal solution) and m (max actions in any path) and b(branching factor/#successors of a node that need to be considered).\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nUninformed Search algos don't know how close they are to the goal state. If all actions have the same cost, BFS is good. FIFO queue here is faster than priority queue and gives us correct order. Our reached can be a set of states, we can also early goal test (check solution on generation vs. in BFS wait until it's poppped off queue). BFS always finds solution with min. number of actions. But not necessarily cost optimal for problems with varying costs. But complete regardless. Memory requirements are a bigger issue here than execution time (exponential space bound). We can conclude that exponential complexity search problems can only be solved by uninformed search for small problems. \n\nDijkstra's algo or uniform cost search: essentially best first search where evaluation function is cost of path from root to current node! Spread out via uniform path cost. ONLY CHECKS FOR GOAL WHEN NODE IS EXPANDED. Otherwise, prematurely can pick the wrong solution. The complexity of this is in terms of C, cost of optimal solution, and e, lower bound on cost of each action. Worst case is O(b^{1 + C/e}) which is actually bigger than b^d. It's complete and cost-optimal!\n\nDFS and memory issues: expands deepest node in frontier. Not cost-optimal, finds first solution it hits. For finate spaces it's efficient and complete but for acyclic spaces might expand same state many times but will eventually explore the entire space. On the other hand, it can get stuck in loops in cyclic spaces. DFS is incomplete :(. For finite-tree-like-search: DFS has less memory requirements since we don't keep track of visited states and frontiers are very small. Takes time proportional to number of states and only O(bm) memory! Mainly in constraint staisfaction, propositional satis, and logical programming. A variant of this, backtracking search, uses even less memory! Only one successor generated and remembers what to generate next and we modify the state vs create a new one. O(m)! \n\nDepth-limited and iterative deepening search: Helps keep DFS from going down an infinite path. Supply depth limit l. Time complexity is O(b^l), space O(bl). But if l incorrect, incomplete algo. We can eliminate cycles if we go up the parent chain. Knowing the diameter of the state-space graph is a good start for the depth limit but that's hard to know until we solve the problem. For iterative deepening, we solve the issue of finding a good l by continuously deepning until a solution is found or failure is found. O(bd) memory when solution exists and O(bm) on finite space w/no solution. Optimal for same-cost problems and complete on finite acyclic spaces or spaces where we check for cycles. Time is O(b^d) with solution, O(b^m) without. Number of nodes generated in worst case is O(b^d) so not too bad.\n\nBidirectional search: from initial and goal states hoping two searches will meet. Need to 2 frontiers and 2 tables of reached states, also need to know backwards successors.\n\n## Module 3 Lecture Notes\n Graph search: we can check to see if a node has been visited before adding it to the search queue. Use DFS if space is restricted, many possible solutions with long paths/wrong ones that terminate fast, or search can be made better quickly. BFS if possible infinite paths, solutions are short, or can quickly find wrong paths. For depth limited search, if l = d, then optimal. if l < d, incomplete, if l > d, not optimal. ID is complete if no infintie paths, and optimal if step cost is 1.  \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Informed algorithm** - agents can estimate how far they are from the goal, opposite of uninformed algos\n* **Closed-loop** - an approach where the percepts are monitored (model incorrect/environment nondeterministic)\n* **State space** - set of states that the environment can be in\n* **Transition model** - tells us what each action does/returns state that results from action on state\n* **Action cost function** - tells us the cost of applying an action on a state\n* **Search algorithms** - given a search problem, returns a solution or notes failure\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 = \"\"\" Informed search strategies use domain-specific information (heuristic function) to find goals. The heuristic function gives the estimated cost of the cheapest path from current state to goal state. \n",
        "\n",
        "Greedy Best First Search: Expand node with lowest h(n). It's complete in finite spaces, not infinite. Worst time and space is O(|V|) but with a good h(n), can become O(bm)\n",
        "\n",
        "A* : f(n) = g(n) + h(n), cost from initial to node n + estimated cost of shortest path to goal. A* is complete and cost-optimality depends on whether of the heuristic is admissible (never overestimate) and consistent \\\n",
        "think of the triangle inequality.All consistent heuristics are admissible but not vice versa. First time we reach some state, guarantee it's the most optimal so never re-add a state to the frontier or change something in reached. \\\n",
        "If heuristic is inadmissible, still can find cost optimal if it's admissible for all nodes on the path OR never overestimates by more than diff between best and second best. A* technically prunes nodes - dont visit ndoes \\\n",
        "that have cost higher than the optimal. ISSUES: # nodes expanded might be exponential. \n",
        "\n",
        "A* expands a lot, if we accept suboptimal solutions (satisficing solutions), can explore less. We can use inadmissible but more accurate heuristic. Weighted A* search! Slightly costiler solution but search time much faster. \n",
        "Will find solution that costs between optimal C and WxC. \n",
        "\n",
        "Bounded suboptimal search - solution that is guaranteed to be within W of optimal cost vs. unbounded - quickets solution of any cost. Speedy search is unbounded and h(n) = number of actions, regardless of cost. \n",
        "\n",
        "Memory-bounded search: biggest issue of A* is memory. frontier < reached so can save on duplication. Can also remove from reached when the state is not needed. Can also keep reference counds and remove from reached if max times reached. \\\n",
        "Beam search: Limits size of frontier - keep k nodes with best scores. INCOMPLETE AND SUBOPTIMAL though. IDA* search: don't keep reached states. cutoff is (g + h), smallest f-cost that exceeded cutoff in previous iter. \\\n",
        "Worst case is when each node has a different f-cost so we can have num. iterations = num. states. \n",
        "\n",
        "Recursive best-first search (RBFS): Only use linear space with best-first search. uses f_limit to track f of best alt path. If current node greater than f_limit, recursion goes back. More efficient than IDA* but can reexpand a lot. \\\n",
        "RBFS optimal if h(n) admissible - space is linear but time is hard to calculate. Both use too little memory. \n",
        "\n",
        "MA* and SMA* - SMA* expands until memory is full and drops worst node - highest f-val. Complete if reachable solution within memory. Optimal if optimal solution is reachable. \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\"Effective branching factor b* to check quality of a heuristic. N is number of nodes generated by A* with dept d, N+1 = b* ^d. Well-designed heuristics have b* close to 1. \n",
        "\n",
        "Another way to check heuristic h is the reduction of the effective depth vs. its true depth by a constant, kh O(b^d) vs O(b^d-kh).\n",
        "\n",
        "When a heuristic dominates another, it means it's more efficient-it'll never expand more nodes than the one it dominates. We can relax problems to find good heuristics because an optimal solution in a relaxed problem is an \\\n",
        "admissible heuristic for the original. Can also generate heuristics from subproblems using pattern databases. Can also generate it with landmarks - precomputation of some optimal path costs. O(|V|^2) space and O(|E|^3) time but finds perfect one. \\\n",
        "We can use landmarks to make this better - find exact cost of optimal path from a vertext to the landmark. Efficient but not admissible, can use differential heuristic (subtraction of extra). \n",
        "\n",
        "Agents can actually learn how to search better - metalevel state space. Can also learn from experience-construct h with luck and just do it a lot. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"Greedy best first search: f(n) = h(n) and ignores cost to get to n, just looks at closest. A* = f(n) = g(n) + h(n) \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 877
        },
        "outputId": "53c38e87-0e76-4408-bd02-6215dfaead84"
      },
      "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 Informed search strategies use domain-specific information (heuristic function) to find goals. The heuristic function gives the estimated cost of the cheapest path from current state to goal state. \n\nGreedy Best First Search: Expand node with lowest h(n). It's complete in finite spaces, not infinite. Worst time and space is O(|V|) but with a good h(n), can become O(bm)\n\nA* : f(n) = g(n) + h(n), cost from initial to node n + estimated cost of shortest path to goal. A* is complete and cost-optimality depends on whether of the heuristic is admissible (never overestimate) and consistent think of the triangle inequality.All consistent heuristics are admissible but not vice versa. First time we reach some state, guarantee it's the most optimal so never re-add a state to the frontier or change something in reached. If heuristic is inadmissible, still can find cost optimal if it's admissible for all nodes on the path OR never overestimates by more than diff between best and second best. A* technically prunes nodes - dont visit ndoes that have cost higher than the optimal. ISSUES: # nodes expanded might be exponential. \n\nA* expands a lot, if we accept suboptimal solutions (satisficing solutions), can explore less. We can use inadmissible but more accurate heuristic. Weighted A* search! Slightly costiler solution but search time much faster. \nWill find solution that costs between optimal C and WxC. \n\nBounded suboptimal search - solution that is guaranteed to be within W of optimal cost vs. unbounded - quickets solution of any cost. Speedy search is unbounded and h(n) = number of actions, regardless of cost. \n\nMemory-bounded search: biggest issue of A* is memory. frontier < reached so can save on duplication. Can also remove from reached when the state is not needed. Can also keep reference counds and remove from reached if max times reached. Beam search: Limits size of frontier - keep k nodes with best scores. INCOMPLETE AND SUBOPTIMAL though. IDA* search: don't keep reached states. cutoff is (g + h), smallest f-cost that exceeded cutoff in previous iter. Worst case is when each node has a different f-cost so we can have num. iterations = num. states. \n\nRecursive best-first search (RBFS): Only use linear space with best-first search. uses f_limit to track f of best alt path. If current node greater than f_limit, recursion goes back. More efficient than IDA* but can reexpand a lot. RBFS optimal if h(n) admissible - space is linear but time is hard to calculate. Both use too little memory. \n\nMA* and SMA* - SMA* expands until memory is full and drops worst node - highest f-val. Complete if reachable solution within memory. Optimal if optimal solution is reachable. \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\nEffective branching factor b* to check quality of a heuristic. N is number of nodes generated by A* with dept d, N+1 = b* ^d. Well-designed heuristics have b* close to 1. \n\nAnother way to check heuristic h is the reduction of the effective depth vs. its true depth by a constant, kh O(b^d) vs O(b^d-kh).\n\nWhen a heuristic dominates another, it means it's more efficient-it'll never expand more nodes than the one it dominates. We can relax problems to find good heuristics because an optimal solution in a relaxed problem is an admissible heuristic for the original. Can also generate heuristics from subproblems using pattern databases. Can also generate it with landmarks - precomputation of some optimal path costs. O(|V|^2) space and O(|E|^3) time but finds perfect one. We can use landmarks to make this better - find exact cost of optimal path from a vertext to the landmark. Efficient but not admissible, can use differential heuristic (subtraction of extra). \n\nAgents can actually learn how to search better - metalevel state space. Can also learn from experience-construct h with luck and just do it a lot. \n\n## Module 4 Lecture Notes\nGreedy best first search: f(n) = h(n) and ignores cost to get to n, just looks at closest. A* = f(n) = g(n) + h(n) \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" One way to deal with multi-agent environments is to consider them as an economy. We could also consider other aadversarial agents as part \\\n",
        "of the environment but that'll miss a lot of context. A third way is to explcitly model them with game-tree search. Can use a heuristic evaluation function to estimate \\\n",
        "who is winning based on the state's features, but for games that have chance or have imperfect info - 5.5.\n",
        "\n",
        "Two-player zero-sum games - perfect info/fully observable and no win-win outcome. We can realize a tic-tac-toe game tree, but chess is 10^40 nodes so we can't. \"\"\"\n",
        "chapter5_2 = \"\"\"Max wants to win but Min doesn't want Max to win, so Max needs a strategy that takes into account Min's possible moves. Binary outcome we can use AND-OR search. \\\n",
        "We can use minimax search for games that have multiple outcomes. the minimax value is the utility for Max in the given state and assumes that everyone plays optimally. \\\n",
        " MINIMAX algo: recursive that goes down to leaves then backs up the minimax values-a complete DFS of game tree. O(b^m) time and O(bm) or O(m) space depending if actions \\\n",
        " generated all at once or one at a time. Because minimax is exponential, bad for complex games like chess. \n",
        " \n",
        " Alpha-beta pruning: since game states grow exponentially as we go down the tree, no algo can completely eliminate the exponent but we can prune to lower the number of states to examine. \\\n",
        " Alpha - value of the best (highest val) choice we have found so far at any point on the path for max - \"at least\". Beta is the value of the best (lowest val) choice at any point for Min (at most) \\\n",
        " alpha-beta search updates alpha and beta as soon as the value of the current node is worse than the current alpha/beta valuees for max/min respectively. \n",
        " \n",
        " How effective alpha-beta pruning is depends on how the states are examined. Perfect pruning - O(b^{m/2}) nodes examined, square rooting the effective branching factor. Random ordering \\\n",
        " makes it about O(b^{3m/4}). But we can get pretty close to good ordering. If we use dynamic move ordering schemes like trying moves that were best in the past brings us even closer. \\\n",
        " We can also have redundant states because of transpositions (diff permutations end up in same position) so we can store these in a table - enable double search depth in same amt of time. \n",
        " \n",
        " BUT even with alpha-beta pruning and good move ordering, minimax won't work for games like chess/go! Type A strat - considers all moves up to a certain depth, wide but shallow. Type B: \\\n",
        " ignore moves that look bad and follow promising paths as far as possible - deep but narrow.\"\"\"\n",
        "chapter5_3 = \"\"\"We can apply a heuristic eval function to states so the utility function is now the evaluation function. The eval function returns an estimated expected utility, where for \\\n",
        "terminal states, eval(s, p) = utility(s, p) and for nonterminal ones, the eval is between a loss and win utility value. Good eval function: computation doesn't take long, strongly correlated with \\\n",
        "winning chances. Lots of functions look at features of the state like number of pieces left, etc. and these are put into equivalence classes of states where we calculate proportion of states with each outcome. \\\n",
        "Then, we calculate expected value (e.g. 82% of states in 2-pawn vs 1-pawn lead to win then 0.82 * 1 + X) - weighted linear function. We're also assuming that the contribution of each feature is independent \\ \n",
        "of others. \n",
        "\n",
        "In terms of cutting off the search, choose depth d so move is made in time, but can also use iterative deepening so we keep going until time runs out. We can also keep entries in a transposition table to make \\\n",
        "searching in later rounds faster. The evaluation function should only be applied to quiescent positions. Search until we get a quiescent position. Horizon effect: pushing bad spots off beyond the searchable horizon \\\n",
        "but we'll eventually get there. One way to mitigate this is by allowing singular extensions, where we choose a move that is clearly better than the others even if the search would be cut off. \n",
        "\n",
        "We can also foward prune, where we can cut off moves that seem to be poor. However, risk of it actually being a good move (Type B strat). One apprach to this is beam search: only consider n best moves.\n",
        "There's also the ProbCut Algo - uses statistics from previous experience to decrease the chances of pruning out the best move. Alpha-beta search prunes provably bad nodes but probcut prunes probably bad ones. Finally, there's \\\n",
        "late move reduction - assumes move ordering is good so bad moves are later in the list and we just reduce the depth that we search these moves.\"\"\"\n",
        "chapter5_5 = \"\"\"Stochastic games introduce the randomness element. Game trees for these types of games should include chance nodes along with min and max nodes. We calculate the expected value of a position - average over all \\\n",
        "oiutcomes of the chance nodes, which is expectiminimax! The evaluation function here needs to be a transformation of the probability of winning. O(b^mn^m) time, where n is number of distinct rolls. However, we can \\\n",
        "prune chance nodes. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"Rational agents should choose actions that maximizes their expected utility. We should view each set of outcomes as a lottery, where we have probability p for each state S.\"\"\"\n",
        "chapter16_2 = \"\"\"There are six constraints to obey: (1) Orderability - must prefer a lottery or rate them equal. Needs to decide. (2) Transitivity (3) Continuity: If B between A and C, sexists A with prob p and C 1-p where agent becomes indifferent. (4) Substitutability: if the \\\n",
        "agent is indifferent between two lotteries, then can theoretically substitute them. (5) Monotonicity: If agent prefers A to B, then they prefer the lottery that has higher probability for A. (6) Decomposability: compound lotteries reduced to simpler ones. \\ \n",
        "\n",
        "Consequences: Existence of Utility Function: U(A) > U(B) if agent's preferences are A > B and they obey the axioms. Expected utility of a lottery: sub of prob of each outcome times prob of that outcome. \"\"\"\n",
        "chapter16_3 = \"\"\"Agents can have preferences. Preference elicitation - understanding preferences to understand one's utility function. Micromort - one in million chance of death. Another measure is QALY \\ \n",
        "quality adjusted life year. Decision theory is normative - how an agent should act. Descriptive theory describes how actual agents act. Agents can have irrational preferences. One explanation is certainty effect - gains that are certain \\\n",
        "garner higher attraction. There's also ambiguity aversion: known probabilities feel better than unknowns. Framing effect - exact wording of a problem has a big impact on an agent's choices as well. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"In minimax, all play is computer from max's vantage point and typically assume max moves first. In lecture, our example of f(n) was # of potential wins for X minus # of potential wins for O. MAX will never allow a move that could lead to worse off score than alpha for MAX \n",
        "and MIN never allow move that can lead to better score for MAX than beta. \n",
        "\n",
        "Expectimax: we might not know results of an action because of randomness, unpreditable agents, or failing actions. While minimax reflected worst-case outcomes, we should now show average-case outcomes. \\\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"quiescent\" : \"position where there is no upcoming move that can drastically change the outcome of the game\",\n",
        "\"horizon effect\" : \"temporarily avoiding bad spots by delaying\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 970
        },
        "outputId": "2dab563b-22c0-4bbe-c3cb-fae1dde197d0"
      },
      "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 One way to deal with multi-agent environments is to consider them as an economy. We could also consider other aadversarial agents as part of the environment but that'll miss a lot of context. A third way is to explcitly model them with game-tree search. Can use a heuristic evaluation function to estimate who is winning based on the state's features, but for games that have chance or have imperfect info - 5.5.\n\nTwo-player zero-sum games - perfect info/fully observable and no win-win outcome. We can realize a tic-tac-toe game tree, but chess is 10^40 nodes so we can't. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nMax wants to win but Min doesn't want Max to win, so Max needs a strategy that takes into account Min's possible moves. Binary outcome we can use AND-OR search. We can use minimax search for games that have multiple outcomes. the minimax value is the utility for Max in the given state and assumes that everyone plays optimally.  MINIMAX algo: recursive that goes down to leaves then backs up the minimax values-a complete DFS of game tree. O(b^m) time and O(bm) or O(m) space depending if actions  generated all at once or one at a time. Because minimax is exponential, bad for complex games like chess. \n \n Alpha-beta pruning: since game states grow exponentially as we go down the tree, no algo can completely eliminate the exponent but we can prune to lower the number of states to examine.  Alpha - value of the best (highest val) choice we have found so far at any point on the path for max - \"at least\". Beta is the value of the best (lowest val) choice at any point for Min (at most)  alpha-beta search updates alpha and beta as soon as the value of the current node is worse than the current alpha/beta valuees for max/min respectively. \n \n How effective alpha-beta pruning is depends on how the states are examined. Perfect pruning - O(b^{m/2}) nodes examined, square rooting the effective branching factor. Random ordering  makes it about O(b^{3m/4}). But we can get pretty close to good ordering. If we use dynamic move ordering schemes like trying moves that were best in the past brings us even closer.  We can also have redundant states because of transpositions (diff permutations end up in same position) so we can store these in a table - enable double search depth in same amt of time. \n \n BUT even with alpha-beta pruning and good move ordering, minimax won't work for games like chess/go! Type A strat - considers all moves up to a certain depth, wide but shallow. Type B:  ignore moves that look bad and follow promising paths as far as possible - deep but narrow.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"We previously assumed that the states were atomic. Here, we start using a set of variables and a factored representation of the state. Solved when each var \\\n",
        "has a satisfactory value. We have a set of variables X, set of domains D, and constraints C. Domain is set of allowable valures for an X. C: (scope, relation) tuple. \\\n",
        "CSP is NP-complete. CSP solvers prune spaces quickly. Simple CSPs have discrete and finite domains for variables. Discrete domains could be infinite though like the set of ints. \\\n",
        "Use implciit constraints like T1 + d1 <=T2 instead of explicit tuples. No algo exists for solving nonliner constraints. CSP with continuous domains are common. There are also \\\n",
        "different types of constraints like unary constraint (restriction on one variable). Binary ones relates two variables. Binary CSP only has unary and binary constraints and can \\\n",
        "be represented by a constraint graph. A constraint with an arbitrary number of variables is a global constraint. Every finate domain constraint can actually be reduced to a set of \\\n",
        "binary constraints, given enough auxiliary variables. Sometimes we prefer global constraints - easier to write the problem and we can sometimes write inference algos that are more efficient. \\\n",
        "Besides these absolute constraints, there are also preference constraints. This becomes COP.  \"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\"CSPs can use constraint propogation and reduce the legal values of a variable, etc. AC-3 algo is the most popular algo that enforces arc consistency. We have a queue of arcs \\\n",
        "and pop off a random one, then check arc consistency and if the domain is changed, then we add the neighboring arcs back to the queue. arc-consistent CSP is faster because smaller domains to search. \\\n",
        "AC-3 arch consistency checked in O(d^2) and so O(cd^3) worst case time where d is max domain size and c arcs. Sometimes arc consistency doesn't bring us too far so we use path consistency, which \\\n",
        "tightens binary constraints (looks at triple vars). Even stronger, we have k-consistency where for any k-1 variables, it stays consistent if a consistent value can be assigned to a kth variable. \\\n",
        "CSP is strongly k-consistent if its k, k-1, k-2, etc. consistent. This makes runtime O(n^2d). But establishing n-consistency takes exponential time. \n",
        "\n",
        "One higher order constraint is alldiff. Another is resource(atmost) constraint. There's also bounds-consistency. \"\"\"\n",
        "\n",
        "chapter6_3 = \"\"\"If we finish constraint propogation and still have variables with multiple values, we have to search for solutions - backtracking! One property of CSPs is commutativity - the order doesn't \\\n",
        "matter. Backtracking keeps only 1 state and alters it, doesn't create new ones. In backtracking, choosing how to assign variables: in order vs randomly - neither optinal. We can use the one with fewest \\\n",
        "remaining values (MRW) heuristic. Most constrained/first-fail. There's also the degree heuristic - choosethe variable that is involved in the most constraints. \n",
        "\n",
        "After choosing variable, order to examine values: least-constarining-value heuristic! Rules out fewest possibilities for its neighbors. Whenever var X is assigned, we can use foward checking. Only check \\\n",
        "immediate neighbors. Combining MRV with foward checking makes searching more effective. But foward checking might not be enough - Maintaining Arc Consistency (MAC) algo: call AC3 and start with unassigned neighbors. \\\n",
        "Know to backtrack immediately if AC3 creates empty set. MAC >> FC. Constraint learning - finding minimum variables from the conflict set that causes an issue. \"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\"Minimum conflict local search algo for CSP is effective. For NQUEENS, runtime is independent of the problem size! Plateau search which allows sideways moves \\\n",
        "to another state with the same value helps min-conflict get off this plateau. Tabu search - small list of visited states that cannot be revisited. Constraint weighting: place \\\n",
        "more value on important constraights; weights are adjusted over time and ensures improvement while assigning higher weights to difficult constraints over time. Local search is also \\\n",
        "good for something like repairing airplane schedules. Backtracking might find a solution that has many more changes.  \"\"\"\n",
        "\n",
        "chapter6_5 = \"\"\"We decompose the real world to subproblems. We can find independent subproblems by finding CC of a constraingt graph. With decomposition into subproblems, work is \\\n",
        "O(d^c[n/c]) which is linear in n and n/c is the number of subproblems. Without it, work is O(d^n) which is exponential in n. Besides indepedent problems, when the constraint graph is a tree, \\\n",
        "it is also easy to solve - linear time in # of variables. This is because of directional arc consistency (DAC), where every Xi is arc-consistent with Xj when j>i. \\\n",
        "We can solve the tree via a topological sort. O(nd^2). Doesn't need backtracking. We can even reduce problems to trees by removing nodes and collapsing nodes. \n",
        "\n",
        "Cutset conditioning: Assign a value to a variable and \"remove\" it, thereby leaving a tree. (1) Choose set S to make the problem a tree. S is a cycle cutset. \\\n",
        "(2) For every possible values for the variables in S that satisfies constraints in the set, remove inconsistent values from the domains of the remaining variables. \\\n",
        "If CSP has a solution return it with the values we assigned for the variables in S. With cycle cutset size c, runtime becomes O(d^c x (n-c)d^2). \n",
        "\n",
        "Tree decomposition: transform the tree to have nodes that have sets of variables. Each variable is in at least one of the nodes and if two variables are connected \\\n",
        "via constraint, they have to be in at least one of the same nodes. If a variable appears twice, it has to also be in the path connecting those nodes. Then use Tree-CSP-Solver \\\n",
        "and get O(nd^2) runtime. \n",
        "\n",
        "Finally, we can reduce the search space via symmetry-breaking constraints. But it is NP-hard to eliminate all symmetry.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"Search assumptions: single agent, deterministic actions, fully observed state, discrete state space. Planning is the sequence of actions while \\\n",
        "identification is assignments to variables. We represent constraints in a uniform declarative language. CSP is a search problem - n vars, domain d, branching factor at the root is nxd. \\\n",
        "The next level's branching factor is (n-1)d, and the tree has n!d^n leaves. Constraint propogation repeatedly enforces constraints locally. \n",
        "\n",
        "Inference in CSP (constraint propagation). Can either inference first or use it with search.To make an arc (i, j) consistent, we check each value in Xi. If there is no label \\\n",
        "on Yj consistent with the value in Xi, remove the value from Xi. Waltz/Mackworth Constraint Propagation Algo: assign every node in the graph a set of ALL possible values and keep \\\n",
        "constraint propagating until no change is seen. AC3 worst case complexity is O(n^2d^3) because n^2 arcs and checking arcs is d^2, then insert into queue d times at worst. \n",
        "\n",
        "Backjumping is improved backtracking. We find the variable assignments in conflict and jump back to reassign. However, foward checking can build a conflict set so we can fix this \\\n",
        "via conflict-irected backjumping, where we go back to the predecessors of the conflict set. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistent\" : \"a consistent assignment doesn't violate constraints\",\n",
        "\"complete\" : \"every variable assigned a value\",    \n",
        "\"solution\" : \"consistent, complete assignment\",\n",
        "\"local consistency\" : \"with each var as a node and constraint as an edge, we can remove inconsistent values by enforcing local consistency\", \n",
        "\"node-consistent\" : \"every variable in the graph is node consistent if the values in a var's domain satisfy its unary constraints\",  \n",
        "\"arc-consistent\" : \"binary constraints satisfied\", \n",
        "\"chronological backtracking\" : \"most recent decision point revisited, backjumping\", \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c9c63d7f-b8ad-4a93-ea14-6984a539b8ca"
      },
      "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\nWe previously assumed that the states were atomic. Here, we start using a set of variables and a factored representation of the state. Solved when each var has a satisfactory value. We have a set of variables X, set of domains D, and constraints C. Domain is set of allowable valures for an X. C: (scope, relation) tuple. CSP is NP-complete. CSP solvers prune spaces quickly. Simple CSPs have discrete and finite domains for variables. Discrete domains could be infinite though like the set of ints. Use implciit constraints like T1 + d1 <=T2 instead of explicit tuples. No algo exists for solving nonliner constraints. CSP with continuous domains are common. There are also different types of constraints like unary constraint (restriction on one variable). Binary ones relates two variables. Binary CSP only has unary and binary constraints and can be represented by a constraint graph. A constraint with an arbitrary number of variables is a global constraint. Every finate domain constraint can actually be reduced to a set of binary constraints, given enough auxiliary variables. Sometimes we prefer global constraints - easier to write the problem and we can sometimes write inference algos that are more efficient. Besides these absolute constraints, there are also preference constraints. This becomes COP.  \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nCSPs can use constraint propogation and reduce the legal values of a variable, etc. AC-3 algo is the most popular algo that enforces arc consistency. We have a queue of arcs and pop off a random one, then check arc consistency and if the domain is changed, then we add the neighboring arcs back to the queue. arc-consistent CSP is faster because smaller domains to search. AC-3 arch consistency checked in O(d^2) and so O(cd^3) worst case time where d is max domain size and c arcs. Sometimes arc consistency doesn't bring us too far so we use path consistency, which tightens binary constraints (looks at triple vars). Even stronger, we have k-consistency where for any k-1 variables, it stays consistent if a consistent value can be assigned to a kth variable. CSP is strongly k-consistent if its k, k-1, k-2, etc. consistent. This makes runtime O(n^2d). But establishing n-consistency takes exponential time. \n\nOne higher order constraint is alldiff. Another is resource(atmost) constraint. There's also bounds-consistency. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nIf we finish constraint propogation and still have variables with multiple values, we have to search for solutions - backtracking! One property of CSPs is commutativity - the order doesn't matter. Backtracking keeps only 1 state and alters it, doesn't create new ones. In backtracking, choosing how to assign variables: in order vs randomly - neither optinal. We can use the one with fewest remaining values (MRW) heuristic. Most constrained/first-fail. There's also the degree heuristic - choosethe variable that is involved in the most constraints. \n\nAfter choosing variable, order to examine values: least-constarining-value heuristic! Rules out fewest possibilities for its neighbors. Whenever var X is assigned, we can use foward checking. Only check immediate neighbors. Combining MRV with foward checking makes searching more effective. But foward checking might not be enough - Maintaining Arc Consistency (MAC) algo: call AC3 and start with unassigned neighbors. Know to backtrack immediately if AC3 creates empty set. MAC >> FC. Constraint learning - finding minimum variables from the conflict set that causes an issue. \n\n## AIMA Chapter 6.4 Local Search for CSPs\nMinimum conflict local search algo for CSP is effective. For NQUEENS, runtime is independent of the problem size! Plateau search which allows sideways moves to another state with the same value helps min-conflict get off this plateau. Tabu search - small list of visited states that cannot be revisited. Constraint weighting: place more value on important constraights; weights are adjusted over time and ensures improvement while assigning higher weights to difficult constraints over time. Local search is also good for something like repairing airplane schedules. Backtracking might find a solution that has many more changes.  \n\n## AIMA Chapter 6.5 The Structure of Problems\nWe decompose the real world to subproblems. We can find independent subproblems by finding CC of a constraingt graph. With decomposition into subproblems, work is O(d^c[n/c]) which is linear in n and n/c is the number of subproblems. Without it, work is O(d^n) which is exponential in n. Besides indepedent problems, when the constraint graph is a tree, it is also easy to solve - linear time in # of variables. This is because of directional arc consistency (DAC), where every Xi is arc-consistent with Xj when j>i. We can solve the tree via a topological sort. O(nd^2). Doesn't need backtracking. We can even reduce problems to trees by removing nodes and collapsing nodes. \n\nCutset conditioning: Assign a value to a variable and \"remove\" it, thereby leaving a tree. (1) Choose set S to make the problem a tree. S is a cycle cutset. (2) For every possible values for the variables in S that satisfies constraints in the set, remove inconsistent values from the domains of the remaining variables. If CSP has a solution return it with the values we assigned for the variables in S. With cycle cutset size c, runtime becomes O(d^c x (n-c)d^2). \n\nTree decomposition: transform the tree to have nodes that have sets of variables. Each variable is in at least one of the nodes and if two variables are connected via constraint, they have to be in at least one of the same nodes. If a variable appears twice, it has to also be in the path connecting those nodes. Then use Tree-CSP-Solver and get O(nd^2) runtime. \n\nFinally, we can reduce the search space via symmetry-breaking constraints. But it is NP-hard to eliminate all symmetry.\n\n## Module 6 Lecture Notes\nSearch assumptions: single agent, deterministic actions, fully observed state, discrete state space. Planning is the sequence of actions while identification is assignments to variables. We represent constraints in a uniform declarative language. CSP is a search problem - n vars, domain d, branching factor at the root is nxd. The next level's branching factor is (n-1)d, and the tree has n!d^n leaves. Constraint propogation repeatedly enforces constraints locally. \n\nInference in CSP (constraint propagation). Can either inference first or use it with search.To make an arc (i, j) consistent, we check each value in Xi. If there is no label on Yj consistent with the value in Xi, remove the value from Xi. Waltz/Mackworth Constraint Propagation Algo: assign every node in the graph a set of ALL possible values and keep constraint propagating until no change is seen. AC3 worst case complexity is O(n^2d^3) because n^2 arcs and checking arcs is d^2, then insert into queue d times at worst. \n\nBackjumping is improved backtracking. We find the variable assignments in conflict and jump back to reassign. However, foward checking can build a conflict set so we can fix this via conflict-irected backjumping, where we go back to the predecessors of the conflict set. \n\n## Module 6 Definitions\n* **Consistent** - a consistent assignment doesn't violate constraints\n* **Complete** - every variable assigned a value\n* **Solution** - consistent, complete assignment\n* **Local consistency** - with each var as a node and constraint as an edge, we can remove inconsistent values by enforcing local consistency\n* **Node-consistent** - every variable in the graph is node consistent if the values in a var's domain satisfy its unary constraints\n* **Arc-consistent** - binary constraints satisfied\n* **Chronological backtracking** - most recent decision point revisited, backjumping\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 = \"\"\"An agent's KB is a set of sentences which are reprsented in knowledge representation language. Non-derived sentences are axioms. We can use TELL and ASK operations \\ \n",
        "to add new sentences, and these both use inferencing. When the agent program is called it TELLs KB what it perceives, then ASKS the KB what to do (action). Finally it TELLs KB what \\\n",
        "it chose to do. MAKE-ACTION-QUERY & MAKE-ACTION-SENTENCE. KB agents can be built by TELLING it what it needs to know. This is the declarative approach to system building, vs. the procedural \\\n",
        "approach where behaviors are coded in vs. telling it knowledge until the agent knows what to do (declarative). Successful agents use both. \"\"\"\n",
        "chapter7_2 = \"\"\"Wumpus world! There are Performance measures, environment, and actuators (move foward, left, right), sensors (five sensors). The agents draw conclusions from \\\n",
        "available info and it's guaranteed to be right if the info is right. \"\"\"\n",
        "chapter7_3 = \"\"\"All sentences are well-formed. Logic also needs to define semantics/meaning of sentences, which in turn define the truth of it wrt the possible world. Each sentence needs \\\n",
        "to be either T/F in the worlds, there are no in-betweens. If a sentence a is true in model m, m staisfies a / m is a model of a. M(a) is the set of all models of a. Logical entailment \\\n",
        "is a |= b, meaning a entails/follows b. a entails b iff M(a) is a subset of M(b), meaning M(b) true where M(a) true. Model checking (enumerating all models to check that a is true \\\n",
        "where KB is true) is sound, and it works if the model is finite. Completeness is also important - an inference algo is complete if it derives any/all entailed sentences. \\\n",
        "If KB/premises are true, then if we use sound inferencing to derive sentences, those sentences are also true. Finally, grounding, or knowing that KB is true in the real world, is also important.\"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"Monotonicity - if KB |= a then KB ^ B |= a meaning we can add to KB without invalidating anything else. We can search for a proof with the initial state as the KB, \\\n",
        "the actions as all the inference rules, the result is adding to KB, and the goal is what we want to prove. Monotonicity implies soundness. You only need a single inference rule, Resolution, \\\n",
        "that yields a COMPLETE inference algo when coupled with any complete search algo. Resolution algo using CNF. Sometimes This is too strong though and if we put some constraints on our KB, we can \\\n",
        "get linear time algos. Definite clause - disjunction of literals where exactly one is positive. Horn - disjunction where at least one is positive. Horn clauses are closed, meaning we will only \\\n",
        "ever generate horn clauses from resolution. \n",
        "\n",
        "Definite clauses can be rewritten as conjunction of the negation of the negatives whose conclusion is the positive.  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Knowledge-based agents\" : \"these agents reason over an internal representation of knowledge for their decision making process\",\n",
        "\"sound/truth preserving\" : \"inference algos that derive only entailed sentences\",     \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2fc31cf5-b9c0-41b0-9a0e-5f7744a61e68"
      },
      "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 Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "T3cm1WV542_a",
        "outputId": "1e35f8dc-8712-4aad-fced-e8d79768a61b"
      },
      "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 Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}