{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "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": "b52c3a91-6fa7-4c2c-b323-afe9bb62979d"
      },
      "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": 2,
      "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": "6ceed5f0-6993-496f-9242-b86b9bf03f9d"
      },
      "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": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 4,
      "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 =  r\"\"\" $$\\alpha \\implies \\beta$$\"\"\"\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "-Agent is anything that can be viewed as percieving its environment through sensors and acting upon environment\n",
        "through actuators (could be human, animal or robot)\n",
        "\n",
        "-Percept is the agents perceptual inputs at a given instant. Percept sequence is compleate history of \n",
        "everything the agent has every percieved\n",
        "\n",
        "- Agents choice of action can only depend on percept sequence observed to the current date (not on future inference)\n",
        "\n",
        "- Agent behavior described by an agent function (we can tabulate agent function)\n",
        "\n",
        "- Agent function is implemented with agent program (these are not the same thing!!!). Agent function is abstract \n",
        "mathematical description and agent program is concrete implementation.\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "- rational agent is one that does \"the right thing\"\n",
        "\n",
        "- performance measure evalutes a given sequence of environment states\n",
        "\n",
        "- Performance is contigent on environment states not agent states (agents can convince themselves they are doing great)\n",
        "\n",
        "- Performance should be based on environement!!!\n",
        "\n",
        "- Rationaity at any given time depends on four tings\n",
        "  1) Performance mesaure that defines the cireterion of success\n",
        "  2) Agent's prior knowledge of environment\n",
        "  3) Actions that the agent can perform \n",
        "  4) Agents percept sequence to date\n",
        "\n",
        "- Def of Rational Agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure,\n",
        "given the evidence provided by the percept sequence and whatever built-in knowledge the agent has\n",
        "\n",
        "- Careful to distinguish between rationality and omniscense. Omniscent agent knows the acutal outcome of its actions and can act accordingly (but this is impossible!!)\n",
        "\n",
        "- Rationality maximizes expected performance not actual performance \n",
        "\n",
        "- Informatin gathering -> doing actions to modify future percepts\n",
        "\n",
        "- Exploration -> part of information gathering\n",
        "\n",
        "- Rational agent must gather information and learn about what it percieves (expect cases where enivronment is fully known \"a priori\")\n",
        "\n",
        "- The extent to which an agent relies on prior knowledge from its designer rather than its own percepts is known as lack of autonomy \n",
        "\n",
        "- Rational agents should be autonomous -> learn what they do not know\n",
        "\n",
        "- With sufficient exprience, agents can explore, learn and become \"independent\" of thier prior knowledge\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "- Task Environment = Performance, Environment, Actuators, Sensors\n",
        "\n",
        "- Fully Observable is when agents sensors give it access to the complete state of the environment at each point in time. This refers only to \n",
        "sensors detecting aspects from the environment that are relevent to the choice of its actions.\n",
        "\n",
        "- If agent has no sensors, environment is unobservable\n",
        "\n",
        "- Simple agent vs. multiagent. An environment is multi agent if there are other agents whos performance is dependent on the actions taken\n",
        "by the current agent (ex. driver on the road depends on the decisions of a driverless car and vice versa)\n",
        "\n",
        "- Cooperative multi agent environment is when agents actions to maximize performance help to maximize performance of other agents\n",
        "(ex. drivers not running into each other)\n",
        "\n",
        "-Competitive environment: agent maximizing its own performance, minimizes the performance of other agents through its actions\n",
        "(ex. chess)\n",
        "\n",
        "- Communication and randomized behavior are often rational\n",
        "\n",
        "- Deterministic vs. Stochastic: if next stage of environment is compleatly determined by the current state and the action of the agent then the environment\n",
        "is deterministic. Else it is stochastic. In this definition they ignore uncertainty from actions of other agents, thus game can be deterministic even though \n",
        "each agent cannot predict the actions of others\n",
        "\n",
        "- Environment is uncertain if it is not full observable or deterministic \n",
        "\n",
        "\n",
        "- Episodic vs. sequential: In episodic task enviornment, agents' experience is devided into atomic episodes. In each episode, agent recieves percept and performs actions and the next episode does not depend\n",
        "on actions taken in previous episodes. A series of individual problems\n",
        "\n",
        "-In sequential environments, the current decision could affect all future decisions. Chess and taxi driving are sequential\n",
        "\n",
        "-Static vs. Dynamic: If the environment can change while the agent is thikning then it is dynamic, else static\n",
        "\n",
        "- If environment does not change with time but agent's performance score does then environment is semidynamic \n",
        "\n",
        "- Discrete vs. Continous: chess is discrete, taxi driving is continous since actions are contnous \n",
        "\n",
        "- Known vs. unkown:  Agents state of knowledge of the laws of physics of the environment. In an known environment, the outcomes (or probability of outcomes if stochastic) for all actions are given.\n",
        "If environment is unkown agent has to learn to make good decisions\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "- architecture is computing device with sensors and actuators that represent the agent\n",
        "\n",
        "- Simple reflex agent: simplest agent that selects actions on the basis of the current percept ignoring the rest of the percept history\n",
        "\n",
        "- Condition-action rule => if x then y\n",
        "\n",
        "- Simple agents are only effective if the environment is fully observable \n",
        "\n",
        "\n",
        "- Simple reflex agents can enter infinte loops. To escape this they can randomize thier actions. Therefore a randomized simple agent may be better than a deterministic simple agent\n",
        "\n",
        "- Infiinte loops occur if simple agent is in partially observable environment \n",
        "\n",
        "- Model based reflex agents handle partial observability maintian an internal state that depends on the percept history and thereby reflects the unobservable aspects of the current\n",
        "state. Model that tracks this state\n",
        "\n",
        "- Goal based agents: along with current state agent maintains goal information that describes desirable situations. Sometimes goal is one action away, sometimes it is many actions away\n",
        "solved through search. This is defferent from simple reflex agents as it considers how current actions impact the future given percept history. \n",
        "\n",
        "- Utility based agents: Goal alone cannot generate high quality behaivior - need to calculate the utility of a state. A utility function is a way to internalize the performance meausre. If internal\n",
        "utility function and external performance measure are in agreement, agent will be rational and choose actions to maximize utitlity. \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"Non Deterministic\" : \"Environment in which actions are characterized by thier possible outcomes, but no probabilities attached to them\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 5,
      "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": "a1eadf67-7b02-44a5-e6bd-9d614327b254"
      },
      "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": 6,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n $$\\alpha \\implies \\beta$$\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\n-Agent is anything that can be viewed as percieving its environment through sensors and acting upon environment\nthrough actuators (could be human, animal or robot)\n\n-Percept is the agents perceptual inputs at a given instant. Percept sequence is compleate history of \neverything the agent has every percieved\n\n- Agents choice of action can only depend on percept sequence observed to the current date (not on future inference)\n\n- Agent behavior described by an agent function (we can tabulate agent function)\n\n- Agent function is implemented with agent program (these are not the same thing!!!). Agent function is abstract \nmathematical description and agent program is concrete implementation.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n- rational agent is one that does \"the right thing\"\n\n- performance measure evalutes a given sequence of environment states\n\n- Performance is contigent on environment states not agent states (agents can convince themselves they are doing great)\n\n- Performance should be based on environement!!!\n\n- Rationaity at any given time depends on four tings\n  1) Performance mesaure that defines the cireterion of success\n  2) Agent's prior knowledge of environment\n  3) Actions that the agent can perform \n  4) Agents percept sequence to date\n\n- Def of Rational Agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure,\ngiven the evidence provided by the percept sequence and whatever built-in knowledge the agent has\n\n- Careful to distinguish between rationality and omniscense. Omniscent agent knows the acutal outcome of its actions and can act accordingly (but this is impossible!!)\n\n- Rationality maximizes expected performance not actual performance \n\n- Informatin gathering -> doing actions to modify future percepts\n\n- Exploration -> part of information gathering\n\n- Rational agent must gather information and learn about what it percieves (expect cases where enivronment is fully known \"a priori\")\n\n- The extent to which an agent relies on prior knowledge from its designer rather than its own percepts is known as lack of autonomy \n\n- Rational agents should be autonomous -> learn what they do not know\n\n- With sufficient exprience, agents can explore, learn and become \"independent\" of thier prior knowledge\n\n\n## AIMA 2.3 The Nature of Environments\n\n- Task Environment = Performance, Environment, Actuators, Sensors\n\n- Fully Observable is when agents sensors give it access to the complete state of the environment at each point in time. This refers only to \nsensors detecting aspects from the environment that are relevent to the choice of its actions.\n\n- If agent has no sensors, environment is unobservable\n\n- Simple agent vs. multiagent. An environment is multi agent if there are other agents whos performance is dependent on the actions taken\nby the current agent (ex. driver on the road depends on the decisions of a driverless car and vice versa)\n\n- Cooperative multi agent environment is when agents actions to maximize performance help to maximize performance of other agents\n(ex. drivers not running into each other)\n\n-Competitive environment: agent maximizing its own performance, minimizes the performance of other agents through its actions\n(ex. chess)\n\n- Communication and randomized behavior are often rational\n\n- Deterministic vs. Stochastic: if next stage of environment is compleatly determined by the current state and the action of the agent then the environment\nis deterministic. Else it is stochastic. In this definition they ignore uncertainty from actions of other agents, thus game can be deterministic even though \neach agent cannot predict the actions of others\n\n- Environment is uncertain if it is not full observable or deterministic \n\n\n- Episodic vs. sequential: In episodic task enviornment, agents' experience is devided into atomic episodes. In each episode, agent recieves percept and performs actions and the next episode does not depend\non actions taken in previous episodes. A series of individual problems\n\n-In sequential environments, the current decision could affect all future decisions. Chess and taxi driving are sequential\n\n-Static vs. Dynamic: If the environment can change while the agent is thikning then it is dynamic, else static\n\n- If environment does not change with time but agent's performance score does then environment is semidynamic \n\n- Discrete vs. Continous: chess is discrete, taxi driving is continous since actions are contnous \n\n- Known vs. unkown:  Agents state of knowledge of the laws of physics of the environment. In an known environment, the outcomes (or probability of outcomes if stochastic) for all actions are given.\nIf environment is unkown agent has to learn to make good decisions\n\n\n## AIMA 2.4 The Structure of Agents\n\n- architecture is computing device with sensors and actuators that represent the agent\n\n- Simple reflex agent: simplest agent that selects actions on the basis of the current percept ignoring the rest of the percept history\n\n- Condition-action rule => if x then y\n\n- Simple agents are only effective if the environment is fully observable \n\n\n- Simple reflex agents can enter infinte loops. To escape this they can randomize thier actions. Therefore a randomized simple agent may be better than a deterministic simple agent\n\n- Infiinte loops occur if simple agent is in partially observable environment \n\n- Model based reflex agents handle partial observability maintian an internal state that depends on the percept history and thereby reflects the unobservable aspects of the current\nstate. Model that tracks this state\n\n- Goal based agents: along with current state agent maintains goal information that describes desirable situations. Sometimes goal is one action away, sometimes it is many actions away\nsolved through search. This is defferent from simple reflex agents as it considers how current actions impact the future given percept history. \n\n- Utility based agents: Goal alone cannot generate high quality behaivior - need to calculate the utility of a state. A utility function is a way to internalize the performance meausre. If internal\nutility function and external performance measure are in agreement, agent will be rational and choose actions to maximize utitlity. \n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Non deterministic** - Environment in which actions are characterized by thier possible outcomes, but no probabilities attached to them\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "- all data treated s objects delted by garbage collection\n",
        "- type(object), is instance(object, type)\n",
        "- python is dynamically typed -> same varibles can have multiple types\n",
        "- Can string format with % like in C#\n",
        "- strings are immutable \n",
        "- == check whether variables point to objects of the same value \n",
        "- is checks whether variables point to the same object\n",
        "- lists are mutable, list[:] returns a copy\n",
        "- Tuples are immutable\n",
        "- Dictionary keys must be immutable\n",
        "- can have multiple return values\n",
        "- no function overloading allowed, operator overloading is possible\n",
        "- in function signiature specify non default arguments first then default arguments\n",
        "- Functions can be called with arguments out of order so long as they are specified \n",
        "- *args allows you to accept a vairaible number of non keyword arguments\n",
        "- **kwargs allows you to accpet a vairabile number of keyword aguments\n",
        "- Functions can be passed as paramters to other functions are returned by other functions\n",
        "- Python has inheritence, parent init method must be executed explicitly\n",
        "- Methods can be overrident, parent method can be called by parentClass.methodName(self, a, b, c),\n",
        "this is the only time you expliclty pass self\n",
        "- Python has special variables __name__ referes to the current module\n",
        "- if __name__ == '__main__' we know to execute some script (equivelent to main method)\n",
        "- [elem * 2 for elem in li if elem > 4]\n",
        "- Functions with yield keyword automatically return a generator when called\n",
        "- Each time next is called method runs until it encounters next yield statement\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": 578
        },
        "outputId": "b0ecabed-0e90-4f88-d69a-8e1c158ff33e"
      },
      "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\n- all data treated s objects delted by garbage collection\n- type(object), is instance(object, type)\n- python is dynamically typed -> same varibles can have multiple types\n- Can string format with % like in C#\n- strings are immutable \n- == check whether variables point to objects of the same value \n- is checks whether variables point to the same object\n- lists are mutable, list[:] returns a copy\n- Tuples are immutable\n- Dictionary keys must be immutable\n- can have multiple return values\n- no function overloading allowed, operator overloading is possible\n- in function signiature specify non default arguments first then default arguments\n- Functions can be called with arguments out of order so long as they are specified \n- *args allows you to accept a vairaible number of non keyword arguments\n- **kwargs allows you to accpet a vairabile number of keyword aguments\n- Functions can be passed as paramters to other functions are returned by other functions\n- Python has inheritence, parent init method must be executed explicitly\n- Methods can be overrident, parent method can be called by parentClass.methodName(self, a, b, c),\nthis is the only time you expliclty pass self\n- Python has special variables __name__ referes to the current module\n- if __name__ == '__main__' we know to execute some script (equivelent to main method)\n- [elem * 2 for elem in li if elem > 4]\n- Functions with yield keyword automatically return a generator when called\n- Each time next is called method runs until it encounters next yield statement\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 = \"\"\"\n",
        "- agent with several immedite options of unkonw value can decide it course of action by exploring\n",
        "future resulting situations\n",
        "\n",
        "-A problem can be defined by an initial state, possible actions avaialable, transition model\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "- Gaphh Search checks for redundant paths, tree search does not.\n",
        "- For each node in a tree we must have: state, parent, action (applied to generate this node) and \n",
        "path cost (cost from initial state to this node)\n",
        "-In AI, state space could be infinite so we can't represent complexity as O(V + E),\n",
        "\n",
        "- Define complexity in terms of branching factor, the depth of the shallowest node\n",
        "and the maximium length of path in state space\n",
        "\n",
        "- Time measured in number of nodes generated during search. Memory measured in the number\n",
        "of nodes stored during search\n",
        "\n",
        "#####################################\n",
        "\n",
        "- Breadth first search is the same as general graph search. Nodes are added in the order of a \n",
        "FIFO queue where the shallowest unexpanded node is explored first. The key difference between \n",
        "BFS and graph search is that the goal test is applied when the node is generated not when the node is\n",
        "pulled off of the queue. \n",
        "\n",
        "- Breadth first search is complete, provided that branching factor is finite (ie. goal must exist at some shallowest node)\n",
        "\n",
        "- Breadth first search is not alawys optimal (shallowest node is not always the lowest path cost). It is lowest path cost\n",
        "if and only if path cost is a nondecreasing function of depth\n",
        "\n",
        "- BFS runtime is O(b^d) if solution is at a depth d since this many nodes must be generated. If we apply goal test when removing node off\n",
        "FIFO queu then runtime is O(b^(d+1))\n",
        "\n",
        "- BFS space complexity is O(b^d) for frontier queue and O(b^(d-1)) for explored set -> frontier queue dominates space complexity \n",
        "\n",
        "- BFS memory requirments are way worse than runtime -> one computer can possibly hold memory for depth 16+ with b= 10\n",
        "\n",
        "#####################################\n",
        "\n",
        "- Uniform cost search builds on BFS as it is agnostic towards the step-cost function in finding optimal solution.\n",
        "\n",
        "- Uniform cost search does not expand shallowest node, but node with lowest path cost g(n), maintined by storing nodes in prioirty queue.\n",
        "The goal test is applied to a node when it is selected for expansion \n",
        "\n",
        "- Whenever uniform cost search selects a node, the optimal cost path to that node has been found (cost can only increase)\n",
        "\n",
        "- Unifrom cost search gets stuck in an infinite loop if path sequence consistenlty has a cost of zero, all path costs must be greater than 0 to garantee compleatness \n",
        "\n",
        "- Runtime: if the optimal solution has path cost C* and every action has cost at least \"e\" then runtime is O(b^(1+[C*/e])), if all costs are the same this simplifies to O(b^(d+1))\n",
        "\n",
        "####################################\n",
        "\n",
        "- Depth First Search expands deepest node in the frontier of the search tree. Uses LIFO queue instead of FIFO queue\n",
        "\n",
        "- DFS is complete if implemented as a graph search in finite state spaces (checks for redudundant paths). DFS is not complete if implemented as a tree search in finite state space\n",
        "\n",
        "- DFS is never complete in infintate state spaces\n",
        "\n",
        "- DFS is also not optimal since path costs may not be uniform across all actions in the state space\n",
        "\n",
        "- DFS can generate up to O(b^m) nodes at most, where m is the depth of the deepest node -> this is the worst case runtime \n",
        "\n",
        "- DFS has a memory requirement of O(bm) which is sgnificantly better than other seraches\n",
        "\n",
        "- Backtracking DFS search achieves O(m) memory -> similar to problem in google interview \n",
        "\n",
        "#####################################\n",
        "\n",
        "- Depth limited search is same as DFS but limits the depth to some threshold l (avoides infinate searches)\n",
        "- If optimal solution is at a depth d then we have two cases. If l < d then the algorithm cannot be complete. If l > d,\n",
        "then the algorithm is nonoptimal as other solution may be found.\n",
        "\n",
        "#####################################\n",
        "\n",
        "- Iterative Deepending Search is similar to depth limited search. Essentially it runs depth limited search at depths l = 1, l= 1,... l= n until the depth reaches d,\n",
        "the depth of the shallowest goal node. This is complete when branching factor is finite and optimal when cost is nondecreasing function of depth\n",
        "- Memory requirement is O(bd), runtime is O(b^d)\n",
        "\n",
        "#####################################\n",
        "- Bidirectional search runs two simoultanous searches -> One forward from the initial state and one backward from the goal state. If the two searches meet in the middle\n",
        "runtime is O(b^(d/2) + b^(d/2))\n",
        "- Space complexity is O(b^(d/2)). Can be reduced by half if one of the searches uses iterative deepening \n",
        "- Goal test checks if the two searches intersect.\n",
        "-Bidrectional search is complete and optimal. Biggest drawback is space requirements \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"uninformed\": \"algorithms given no information about problem other than its definition\",\n",
        "\"goal formulation\": \"based on current situtation and agent's performance\",\n",
        "\"problem formulation\": \"process of deciding what action and states to consider given goal\",\n",
        "\"search\": \"process of looking for sequence of actions that reaches the goal\",\n",
        "\"open loop\": \"when agent ignores percept when choosing actions given by known solution\",\n",
        "\"transition model\": \"returns the result from doing action a in state s\",\n",
        "\"state space\": \"implicitly defined by transition model, initial state, and actions\",\n",
        "\"sucessor\": \"state reachable from given state by a single action\",\n",
        "\"path\": \"sequence of states connected by sequence of actions\",\n",
        "\"goal test\": \"check if current state is the goal\",\n",
        "\"path cost function\": \"gives a cost to a path sequence\",\n",
        "\"optimal solution\": \"lowest path cost among all solutions\",\n",
        "\"leaf node\": \"node with no children\",\n",
        "\"frontier\": \"set of leaf nodes avialbe for expenasion\",\n",
        "\"search strategy\": \"choosing which state to explore next\",\n",
        "\"redundant paths\": \" when there is more thatn one way to get from one state to another\",\n",
        "\"explored set\": \"set of states that have already been visited\",\n",
        "\"completeness\": \"algorithm garanteed to find a solution if there is one\",\n",
        "\"optimal\": \"algorithm finds lowest cost solution if it exists\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "bbec65d0-9efc-40fc-d06d-ab78bcf746cb"
      },
      "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\n- agent with several immedite options of unkonw value can decide it course of action by exploring\nfuture resulting situations\n\n-A problem can be defined by an initial state, possible actions avaialable, transition model\n\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 \n- Gaphh Search checks for redundant paths, tree search does not.\n- For each node in a tree we must have: state, parent, action (applied to generate this node) and \npath cost (cost from initial state to this node)\n-In AI, state space could be infinite so we can't represent complexity as O(V + E),\n\n- Define complexity in terms of branching factor, the depth of the shallowest node\nand the maximium length of path in state space\n\n- Time measured in number of nodes generated during search. Memory measured in the number\nof nodes stored during search\n\n#####################################\n\n- Breadth first search is the same as general graph search. Nodes are added in the order of a \nFIFO queue where the shallowest unexpanded node is explored first. The key difference between \nBFS and graph search is that the goal test is applied when the node is generated not when the node is\npulled off of the queue. \n\n- Breadth first search is complete, provided that branching factor is finite (ie. goal must exist at some shallowest node)\n\n- Breadth first search is not alawys optimal (shallowest node is not always the lowest path cost). It is lowest path cost\nif and only if path cost is a nondecreasing function of depth\n\n- BFS runtime is O(b^d) if solution is at a depth d since this many nodes must be generated. If we apply goal test when removing node off\nFIFO queu then runtime is O(b^(d+1))\n\n- BFS space complexity is O(b^d) for frontier queue and O(b^(d-1)) for explored set -> frontier queue dominates space complexity \n\n- BFS memory requirments are way worse than runtime -> one computer can possibly hold memory for depth 16+ with b= 10\n\n#####################################\n\n- Uniform cost search builds on BFS as it is agnostic towards the step-cost function in finding optimal solution.\n\n- Uniform cost search does not expand shallowest node, but node with lowest path cost g(n), maintined by storing nodes in prioirty queue.\nThe goal test is applied to a node when it is selected for expansion \n\n- Whenever uniform cost search selects a node, the optimal cost path to that node has been found (cost can only increase)\n\n- Unifrom cost search gets stuck in an infinite loop if path sequence consistenlty has a cost of zero, all path costs must be greater than 0 to garantee compleatness \n\n- Runtime: if the optimal solution has path cost C* and every action has cost at least \"e\" then runtime is O(b^(1+[C*/e])), if all costs are the same this simplifies to O(b^(d+1))\n\n####################################\n\n- Depth First Search expands deepest node in the frontier of the search tree. Uses LIFO queue instead of FIFO queue\n\n- DFS is complete if implemented as a graph search in finite state spaces (checks for redudundant paths). DFS is not complete if implemented as a tree search in finite state space\n\n- DFS is never complete in infintate state spaces\n\n- DFS is also not optimal since path costs may not be uniform across all actions in the state space\n\n- DFS can generate up to O(b^m) nodes at most, where m is the depth of the deepest node -> this is the worst case runtime \n\n- DFS has a memory requirement of O(bm) which is sgnificantly better than other seraches\n\n- Backtracking DFS search achieves O(m) memory -> similar to problem in google interview \n\n#####################################\n\n- Depth limited search is same as DFS but limits the depth to some threshold l (avoides infinate searches)\n- If optimal solution is at a depth d then we have two cases. If l < d then the algorithm cannot be complete. If l > d,\nthen the algorithm is nonoptimal as other solution may be found.\n\n#####################################\n\n- Iterative Deepending Search is similar to depth limited search. Essentially it runs depth limited search at depths l = 1, l= 1,... l= n until the depth reaches d,\nthe depth of the shallowest goal node. This is complete when branching factor is finite and optimal when cost is nondecreasing function of depth\n- Memory requirement is O(bd), runtime is O(b^d)\n\n#####################################\n- Bidirectional search runs two simoultanous searches -> One forward from the initial state and one backward from the goal state. If the two searches meet in the middle\nruntime is O(b^(d/2) + b^(d/2))\n- Space complexity is O(b^(d/2)). Can be reduced by half if one of the searches uses iterative deepening \n- Goal test checks if the two searches intersect.\n-Bidrectional search is complete and optimal. Biggest drawback is space requirements \n\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Uninformed** - algorithms given no information about problem other than its definition\n* **Goal formulation** - based on current situtation and agent's performance\n* **Problem formulation** - process of deciding what action and states to consider given goal\n* **Search** - process of looking for sequence of actions that reaches the goal\n* **Open loop** - when agent ignores percept when choosing actions given by known solution\n* **Transition model** - returns the result from doing action a in state s\n* **State space** - implicitly defined by transition model, initial state, and actions\n* **Sucessor** - state reachable from given state by a single action\n* **Path** - sequence of states connected by sequence of actions\n* **Goal test** - check if current state is the goal\n* **Path cost function** - gives a cost to a path sequence\n* **Optimal solution** - lowest path cost among all solutions\n* **Leaf node** - node with no children\n* **Frontier** - set of leaf nodes avialbe for expenasion\n* **Search strategy** - choosing which state to explore next\n* **Redundant paths** -  when there is more thatn one way to get from one state to another\n* **Explored set** - set of states that have already been visited\n* **Completeness** - algorithm garanteed to find a solution if there is one\n* **Optimal** - algorithm finds lowest cost solution if it exists\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "- quality of a heuristic can be determined by its effective branching factor b*\n",
        "- the effective branching factor is the total number of nodes generated by A* for a particular\n",
        "search problem. Subsequently caluclate branching factor by\n",
        "- if h2(n) > h1(n) for all n and both are admissable heuristic functions then h2 dominates h1\n",
        "\n",
        "$$N + 1 = 1 + b^* + (b*)^2 + ... + (b^*)^d$$\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "\n",
        "- General algorithm known as best first search. Is an instance of Tree-Search or Graph-Search in whihc a node is selected\n",
        "for expansion based on some evaluation function. This function acts as a cost estimate from the current node to the goal\n",
        "- Best First Serach is implemented as Unifrom Cost Search but priority queue is based on evauluation function rathar than cost\n",
        "- node with the lowest evaluation is expanded first\n",
        "- n is the goal node h(n)= 0 where h(n) is euristic function\n",
        "\n",
        "####################\n",
        "- Greedy Best First Search expands node that is closest to the goal using herustic function\n",
        "- Greedy best first serach is not complete even finite space when implemented as a Tree Search\n",
        "- Greedy best first search is complete in finite space when implemented as a Graph Serach, but not compleate in infinite spaces\n",
        "- The worst time and space complexity for the Tree Implementation is O(b^m), where m is the maximium depth of the search space\n",
        "- Good herustic functions can significantly improve runtime \n",
        "\n",
        "###################\n",
        "- A* search evalutes nodes by combining current path cost and heuristic function f(n) = g(n) + h(n)\n",
        "- Nodes are added to prioirty queue with value f(n) = g(n) + h(n)\n",
        "- Goal compleation check performed when nodes popped off from frontie queue\n",
        "- A* search returns optimal solution when: heuristic function is admissable (understimates cost) and the hueristic function is consistent\n",
        "(only required in graph search)\n",
        "- A herustic function is consistent if for every node n and every successor n' generated by some action the estimated cost of reaching the goal from n\n",
        "is no greater than the (... some form of the traingle inequality - no side can be longer than the sum of the two remianing sides)\n",
        "- A* is also complete \n",
        "- A* is optimally effcieint (no other algorithm will expand fewer nodes - virtue of pruning by herusitic function)\n",
        "- A* search is limited since it creates nodes and must keep them in memory (ie. priority queue). Cannot scale to larger problems \n",
        "- Runtime of A* is O((b*)^d) where d is the depth of the solution\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"search that uses knowledge beyond the problem definintion\",\n",
        "\"heuristic function\": \"estimates the cost of cheapest path from current state to goal\"    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "65b989dd-b492-4e50-ad99-b6cae1349de3"
      },
      "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\", module3_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 Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n \n- quality of a heuristic can be determined by its effective branching factor b*\n- the effective branching factor is the total number of nodes generated by A* for a particular\nsearch problem. Subsequently caluclate branching factor by\n- if h2(n) > h1(n) for all n and both are admissable heuristic functions then h2 dominates h1\n\n$$N + 1 = 1 + b^* + (b*)^2 + ... + (b^*)^d$$\n\n\n## Module 4 Lecture Notes\n \n- Gaphh Search checks for redundant paths, tree search does not.\n- For each node in a tree we must have: state, parent, action (applied to generate this node) and \npath cost (cost from initial state to this node)\n-In AI, state space could be infinite so we can't represent complexity as O(V + E),\n\n- Define complexity in terms of branching factor, the depth of the shallowest node\nand the maximium length of path in state space\n\n- Time measured in number of nodes generated during search. Memory measured in the number\nof nodes stored during search\n\n#####################################\n\n- Breadth first search is the same as general graph search. Nodes are added in the order of a \nFIFO queue where the shallowest unexpanded node is explored first. The key difference between \nBFS and graph search is that the goal test is applied when the node is generated not when the node is\npulled off of the queue. \n\n- Breadth first search is complete, provided that branching factor is finite (ie. goal must exist at some shallowest node)\n\n- Breadth first search is not alawys optimal (shallowest node is not always the lowest path cost). It is lowest path cost\nif and only if path cost is a nondecreasing function of depth\n\n- BFS runtime is O(b^d) if solution is at a depth d since this many nodes must be generated. If we apply goal test when removing node off\nFIFO queu then runtime is O(b^(d+1))\n\n- BFS space complexity is O(b^d) for frontier queue and O(b^(d-1)) for explored set -> frontier queue dominates space complexity \n\n- BFS memory requirments are way worse than runtime -> one computer can possibly hold memory for depth 16+ with b= 10\n\n#####################################\n\n- Uniform cost search builds on BFS as it is agnostic towards the step-cost function in finding optimal solution.\n\n- Uniform cost search does not expand shallowest node, but node with lowest path cost g(n), maintined by storing nodes in prioirty queue.\nThe goal test is applied to a node when it is selected for expansion \n\n- Whenever uniform cost search selects a node, the optimal cost path to that node has been found (cost can only increase)\n\n- Unifrom cost search gets stuck in an infinite loop if path sequence consistenlty has a cost of zero, all path costs must be greater than 0 to garantee compleatness \n\n- Runtime: if the optimal solution has path cost C* and every action has cost at least \"e\" then runtime is O(b^(1+[C*/e])), if all costs are the same this simplifies to O(b^(d+1))\n\n####################################\n\n- Depth First Search expands deepest node in the frontier of the search tree. Uses LIFO queue instead of FIFO queue\n\n- DFS is complete if implemented as a graph search in finite state spaces (checks for redudundant paths). DFS is not complete if implemented as a tree search in finite state space\n\n- DFS is never complete in infintate state spaces\n\n- DFS is also not optimal since path costs may not be uniform across all actions in the state space\n\n- DFS can generate up to O(b^m) nodes at most, where m is the depth of the deepest node -> this is the worst case runtime \n\n- DFS has a memory requirement of O(bm) which is sgnificantly better than other seraches\n\n- Backtracking DFS search achieves O(m) memory -> similar to problem in google interview \n\n#####################################\n\n- Depth limited search is same as DFS but limits the depth to some threshold l (avoides infinate searches)\n- If optimal solution is at a depth d then we have two cases. If l < d then the algorithm cannot be complete. If l > d,\nthen the algorithm is nonoptimal as other solution may be found.\n\n#####################################\n\n- Iterative Deepending Search is similar to depth limited search. Essentially it runs depth limited search at depths l = 1, l= 1,... l= n until the depth reaches d,\nthe depth of the shallowest goal node. This is complete when branching factor is finite and optimal when cost is nondecreasing function of depth\n- Memory requirement is O(bd), runtime is O(b^d)\n\n#####################################\n- Bidirectional search runs two simoultanous searches -> One forward from the initial state and one backward from the goal state. If the two searches meet in the middle\nruntime is O(b^(d/2) + b^(d/2))\n- Space complexity is O(b^(d/2)). Can be reduced by half if one of the searches uses iterative deepening \n- Goal test checks if the two searches intersect.\n-Bidrectional search is complete and optimal. Biggest drawback is space requirements \n\n\n\n\n## Module 4 Definitions\n* **Informed search** - search that uses knowledge beyond the problem definintion\n* **Heuristic function** - estimates the cost of cheapest path from current state to goal\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "- Game can be defined as a search problem using initial state, players, actions, result(s, a), terminal test(s), utility(s, p)\n",
        "- Initial state, actions function and result function define the game tree \n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "- optimal solution is sequence of actions leading to goal state (a win)\n",
        "\n",
        "- minmax algorithm computes the minmax decision for state s through recursion \n",
        "\n",
        "- Minmax algo recurses down to the depth of the tree and minmax values are \"backed up\"\n",
        "\n",
        "- Therefore if the depth of the game tree is d, and each state has b legal moves, runtime is O(b^d) and memory is O(bd)/O(d) depending on implementatoin\n",
        "\n",
        "- Can extend this to multiplayer games by making each node a vector of values\n",
        "\n",
        "- Psuedocode of minmax algorithm:\n",
        "  1) Use DFS to go down to leaf node and compute minmax value. Back up the value by choosing the min/max of all child minmax values, depedning on which player is acting\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "- alphabeta purning used to optimize minimiax search and cut exponenet in half \n",
        "\n",
        "- a = the value of the highest value choice we have found so far at any action point for MAX\n",
        "- b=  the value of the lowest value choice we have found so far at any aciton point for MAX\n",
        "\n",
        "- Effectinvness of alpha beta is depending on the order in which states are examined\n",
        "\n",
        "- Given optimal examination the runtime is reduced to O(b^{d/2})\n",
        "\n",
        "- Sometimes we cannot reach a terminal depth. To solve this we create an evaluation function to evaluate states and some \n",
        "cuttof depth. This evaulation function is an herustic for the min max value. \n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "- Game tree in a stochastic game includes chance nodes in addition to Max and MIn nodes\n",
        "\n",
        "- Branches from a Chance node denote the possible outcomes and their probabilities \n",
        "\n",
        "- Now minmax values are modified to be the expected value of a position - the average of all possbile outcomes of chance nodes\n",
        "\n",
        "- When dealing with expectimax evaluation functions must be percise. Evaluation functions do not reamin consistent if values \n",
        "are scaled!!!!!\n",
        "\n",
        "- The run time of expectimax is O(b^m * n^m) where n are the number of possible outcomes in the probability distribution \n",
        "\n",
        "- With uncertainty the problem of zero sum game is not tractable easily\n",
        "\n",
        "- Alpha beta purning can still be applied to expectimax and stochastic games. In this case we can put an upper or lower bound on a node\n",
        "by looking at the range of its possible values, etc. \n",
        "\n",
        "- Alternatively can estimate values of nodes through Monte Carlo simultion (run thousands of trials and see the win percentages)\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "- Agent's preferences captured by utility function. Utitlity function maps each state to a number\n",
        "which captures its desirability \n",
        "\n",
        "- Exepcted utility is the average utility over all outcomes \n",
        "\n",
        "- But estimating expected utility requires perception, learning, knowledge representation and inference\n",
        "\n",
        "- If utility directly reflects performance measure then agent will do well in its environment (explored in chapter 1)\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "\n",
        "- Let us consider the constraints on rational preferences\n",
        "\n",
        "- $A > B$, agent prefers A over B\n",
        "- $A < B$, agent prefers B over A\n",
        "- $A \\geq B$, agent prefers A but is indiffernt to B\n",
        "\n",
        "- Any preference relation must obey six contraints:\n",
        "\n",
        "- Orderability: on of $A > B$, $A < B$, $A \\geq B$ holds\n",
        "- Transitivity: Given three loterries, if an agent prefers A to B and prefers B to C then the agent must prever A to C\n",
        "- Continuity: If some lottery B is between A and C in preference then there must exist some probability p, for which the agent is indifferent \n",
        "to getting B for sure and a lottery that yeilds A with a probability p and C with a probability 1- p\n",
        "- Substitutability: If agent is indifferent between two loterries A and B, then he/she is also indifferent between complexity loterries in which\n",
        "B is substituted for A in them\n",
        "- Monotonicity: If two lotteries A, B have the same set of outcomes, an agent can only prefer A to B if A has a higher probability of ocurring\n",
        "- Decomposability: Compounded loterries can be rediced to simpler ones through probability. \"Two consequtive loterries can be compressed into one\"\n",
        "\n",
        "- If an agent's prefernces obeys laws above then there must exist a utility function where U(A) > U(B) if A is preferred to B and U(A) = U(B) if \n",
        "agent is indifferent\n",
        "\n",
        "- If an agent's preferences obeys laws above then, the expected utility of loterry is the probability of each outcome multiplied by its uility to an agent\n",
        "\n",
        "- By the laws above, Utility function need not be unique \n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"competitive environment\" : \"environment in which agent's goals are in conflict\",\n",
        "\"zero-sum game\": \"utility values at the ned of game are equal and opposite\",\n",
        "\"perfect information\": \"deterministic, fully observable environment\",\n",
        "\"pruning\": \"ignore portions of search tree that are irrelevant\",\n",
        "\"evaluation functions\": \"approximate the true utility of state\",\n",
        "\"minmax value\": \"utility for max being in corresponding state\",\n",
        "\"stochastic games\": \"games where actions are dependant on random elelemt\",\n",
        "\"chance nodes\": \"a node\",\n",
        "\"maximum expected utility MEU\": \"rational agent should choose action that maximizes expected utilty\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f4d83a11-c009-42a3-f503-f4253089a6a6"
      },
      "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 \n- Game can be defined as a search problem using initial state, players, actions, result(s, a), terminal test(s), utility(s, p)\n- Initial state, actions function and result function define the game tree \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n- optimal solution is sequence of actions leading to goal state (a win)\n\n- minmax algorithm computes the minmax decision for state s through recursion \n\n- Minmax algo recurses down to the depth of the tree and minmax values are \"backed up\"\n\n- Therefore if the depth of the game tree is d, and each state has b legal moves, runtime is O(b^d) and memory is O(bd)/O(d) depending on implementatoin\n\n- Can extend this to multiplayer games by making each node a vector of values\n\n- Psuedocode of minmax algorithm:\n  1) Use DFS to go down to leaf node and compute minmax value. Back up the value by choosing the min/max of all child minmax values, depedning on which player is acting\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n- alphabeta purning used to optimize minimiax search and cut exponenet in half \n\n- a = the value of the highest value choice we have found so far at any action point for MAX\n- b=  the value of the lowest value choice we have found so far at any aciton point for MAX\n\n- Effectinvness of alpha beta is depending on the order in which states are examined\n\n- Given optimal examination the runtime is reduced to O(b^{d/2})\n\n- Sometimes we cannot reach a terminal depth. To solve this we create an evaluation function to evaluate states and some \ncuttof depth. This evaulation function is an herustic for the min max value. \n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n- Game tree in a stochastic game includes chance nodes in addition to Max and MIn nodes\n\n- Branches from a Chance node denote the possible outcomes and their probabilities \n\n- Now minmax values are modified to be the expected value of a position - the average of all possbile outcomes of chance nodes\n\n- When dealing with expectimax evaluation functions must be percise. Evaluation functions do not reamin consistent if values \nare scaled!!!!!\n\n- The run time of expectimax is O(b^m * n^m) where n are the number of possible outcomes in the probability distribution \n\n- With uncertainty the problem of zero sum game is not tractable easily\n\n- Alpha beta purning can still be applied to expectimax and stochastic games. In this case we can put an upper or lower bound on a node\nby looking at the range of its possible values, etc. \n\n- Alternatively can estimate values of nodes through Monte Carlo simultion (run thousands of trials and see the win percentages)\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n- Agent's preferences captured by utility function. Utitlity function maps each state to a number\nwhich captures its desirability \n\n- Exepcted utility is the average utility over all outcomes \n\n- But estimating expected utility requires perception, learning, knowledge representation and inference\n\n- If utility directly reflects performance measure then agent will do well in its environment (explored in chapter 1)\n\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n\n- Let us consider the constraints on rational preferences\n\n- $A > B$, agent prefers A over B\n- $A < B$, agent prefers B over A\n- $A \\geq B$, agent prefers A but is indiffernt to B\n\n- Any preference relation must obey six contraints:\n\n- Orderability: on of $A > B$, $A < B$, $A \\geq B$ holds\n- Transitivity: Given three loterries, if an agent prefers A to B and prefers B to C then the agent must prever A to C\n- Continuity: If some lottery B is between A and C in preference then there must exist some probability p, for which the agent is indifferent \nto getting B for sure and a lottery that yeilds A with a probability p and C with a probability 1- p\n- Substitutability: If agent is indifferent between two loterries A and B, then he/she is also indifferent between complexity loterries in which\nB is substituted for A in them\n- Monotonicity: If two lotteries A, B have the same set of outcomes, an agent can only prefer A to B if A has a higher probability of ocurring\n- Decomposability: Compounded loterries can be rediced to simpler ones through probability. \"Two consequtive loterries can be compressed into one\"\n\n- If an agent's prefernces obeys laws above then there must exist a utility function where U(A) > U(B) if A is preferred to B and U(A) = U(B) if \nagent is indifferent\n\n- If an agent's preferences obeys laws above then, the expected utility of loterry is the probability of each outcome multiplied by its uility to an agent\n\n- By the laws above, Utility function need not be unique \n\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* **Competitive environment** - environment in which agent's goals are in conflict\n* **Zero-sum game** - utility values at the ned of game are equal and opposite\n* **Perfect information** - deterministic, fully observable environment\n* **Pruning** - ignore portions of search tree that are irrelevant\n* **Evaluation functions** - approximate the true utility of state\n* **Minmax value** - utility for max being in corresponding state\n* **Stochastic games** - games where actions are dependant on random elelemt\n* **Chance nodes** - a node\n* **Maximum expected utility meu** - rational agent should choose action that maximizes expected utilty\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "- Contraint satisfaction problem has three components: \n",
        "- X => a set of variables $\\{X_1, X_2, ..., X_n\\}$\n",
        "- D => set of domains $\\{D_1, ..., D_n\\} for each variable\n",
        "- C => set of contraints \n",
        "\n",
        "- Each domain $D_i$ consists of a set of allowable values $\\{v_1, ..., v_k\\}$ for every variable X_i\n",
        "\n",
        "- Every constraint C_i can be defined as a scope of variables and a relation that defines the values each variable can take\n",
        "\n",
        "- Example of a constraint: let $X_1$ and $X_2$ be two variables that must have different values. Then it is $C_i = ((X_1, X_2), X_1 \\neq X_2)$\n",
        "\n",
        "- To solve CSP, need state space and solution(goal). Every state in CSP is essentially some assignment of values to a subset of the variables $\\{X_1 = v_1, X_2 = v_2, ..., X_n = v_k\\}$\n",
        "\n",
        "- Visualize CSP as a contraint graph - nodes correspond to variables, and edges connects any two variables that participate in a constraint\n",
        "\n",
        "- We solve problem's as CSPs because problems are easier to represent as a CSP system. CSP is also faster in solving problems than traditional search\n",
        "\n",
        "- If a partial assignment is not a solution, we discard further iterations/specifications of it \n",
        "\n",
        "- Simplest CSP has discrete, finite domains\n",
        "\n",
        "- Continous domain CSPs are linear programming problems \n",
        "\n",
        "- One of most common global constraints is Alldiff (i.e. all variables should be different)\n",
        "\n",
        "- All diff prefered to binary constraints because it is easy and less error prone to write\n",
        "\n",
        "- If a problem includes preference contraints it is solved as a constraint optimization problem (Linear Program)\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "- CSPs can be solved through search or constraint propagation  \n",
        "- Contraint propgation can be intertwined with search\n",
        "- Always possible to elminate unary constraints in CSP by running one iteration of node consistency\n",
        "- As a result CSP solvers generally deal with binary constraints\n",
        "\n",
        "- AC3 is most popular algorithm for arc consistency:\n",
        "\n",
        "- maintain a queue of arcs to consider. Initially make this all arcs in graph\n",
        "- pop an arbitrary arc $(X_i, X_j)$ and make $X_i$ arc consistent with $X_j$\n",
        "- if $D_i$ is unchanged, consider next arc in queue\n",
        "- if $D_i$ is changed, queue all arcs $(X_k, X_i)$\n",
        "- if $D_i$ is revised to empty set then return no solution \n",
        "\n",
        "- After running AC3, we are left with a partial solution to CSP. This is usually much faster to solve with search\n",
        "than problem before (branching factor is smaller)\n",
        "\n",
        "- AC3 complexity: n variables each with domain size at most d. Each arc $(X_i, X_k)$ can be enqueud at most d times, therefore O(d^3* c) since \n",
        "checking arc consistency of each arc is d^2 time and we do this for each n varaible at most d times (but much less realistically)\n",
        "\n",
        "- Can extend notion of arc consistency to n array constraints\n",
        "\n",
        "- But arc consistnecy cannot always solve problems => consider coloring problem of australia with red and blue (all domains are initially valid!!!)\n",
        "\n",
        "- Path consistency can be solved with PC2 algorithm\n",
        "\n",
        "- Given a k consistent solution we can assign values in O(n^2 * d) time\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "- CSPs have a branching factor of n * d, but we can reduce this to d through the principle of commutativity (order of application of set of actions does not affect outcome)\n",
        "- Without commutativity leaves is $n! * d^n$, with commutativity it is $d^n$\n",
        "- We can optimize backtracking serach using herustics these include:\n",
        "- Choosing most constrained variable (minimum remaining values)\n",
        "- Choosing variables invovlved in largest number of constraints with other variables (highly connected nodes), also known as degree heuristic\n",
        "- Choose the least constrained value (maximum remaining values)\n",
        "- We can interleave search and forward checking (ie. backtracking and AC3) to find solution. This is known as MAC algorithm (Maintaining Arc Consistency)\n",
        "\n",
        "- Furthermore, we can improve backtracking by making it more intelligent. The current backtracking algorithm that was oultined backs up to the previous\n",
        "branch and tries a new assigment. This is known as chronological backtracking\n",
        "- But backtracking to previous step does not always help because that assignment may not be what caused the contraint violation. Therefore it is better\n",
        "to backtrack to variable that is part of the contraint violation and fix that.\n",
        "- To do this keep track of a set of conflicts for each node. To backjump backtrack to the most recent assignment in the conflict set\n",
        "- We can keep track of conflict set through forward checking (i.e. when ensuring arc consistency add removed values into conflict set)\n",
        "- More strongly, if forward checking is done backjumping is redundant (in algos like MAC)\n",
        "- Conflict directed back jumping improves on this by focusing on variables that are chosen\n",
        " \"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\" \n",
        "- Local search assigns value to every variable and then modifies the values of each variable one at a time. Each modificaiton looks to \n",
        "eliminate violated constraints. Usually a heurstic is used (min-conflicts), to choose a new value that results in the minimum number\n",
        "of new conflicts\n",
        "- This process is done up to some number of steps\n",
        "- Local search is great but can reach plateux (ie. millions of varaibles on violated constraint away from solution)\n",
        "- Platau search imporves this (allows sidewasys move to another state with the saame score) - i.e. break the plateux\n",
        "- Other improvements like constrain weighting can focus search on the important constraints. In this case, each constraint is given a weight $W_i$. Initially all weights are initialized to 1 and at each step\n",
        "algorithm chooses variable to change that results in lowest total weight of violated constraints. Weights are adjusted by increasing each $W_i$ by current assignment. This adds topography to plateux.\n",
        "- Local seach is also great because it can improve existing solutions that were invalided. In this case we simply start a local seach based on a previous solution. Example airline scheduling on week 2 can \n",
        "be based on schedule in week 1\n",
        "\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "- CSPs can be broken down into subproblems by considering the connected components of a graph, each connected component is then its own CSP. Subproblems allow for parallelizsation \n",
        "- Subproblems also improve runtime from O(d^n) to O(d^c * n/c)\n",
        "- Any tree strucutred CSP can be solved in lienar time of number of variables\n",
        "- To solve tree CSP, find a topological sort : total time O(n * d^2). Once in topological sort, go down from left to right and assign remainign varaibles\n",
        "- It is good to convert CSP graphs to trees by removing nodes or collapsing them together\n",
        "- Alterntively, instead of removing a nodes. We could assign values to them and make remaining nodes arc consistent. Then treat remaining graph as a tree variation CSP problem. Naturally\n",
        "we can easily choose the wrong values for the nodes, so this will have to be done through search. Runtime is O(d^c * (n-c)d^2) => try d^c combintations for cycle cutset and then run topological sort on \n",
        "remaining nodes ensuring forward checking.\n",
        "- Finding the smallest cycle cutset is NP hard, but can be approximated => this is called cutset conditioning \n",
        "\n",
        "- A second approach can be applied known as tree decomposition. In this case graph is portionined into set of subproblems each solved indpenedently. Then graph portions solved as one CSP problem \n",
        "- Tree decomposition must satisfy: every variable in original problems is in subproblem. If two variables share constraint they must be members of at least one subproblem together. If varaible appears\n",
        "in two subproblems it must appear in every path connecting those two subproblems.\n",
        "\n",
        "- Tree problems are efficeint if the tree width is small: runtime is O(nd^{w+1}), where w is width\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"connsistent/legal assignment\" : \"assignment that does not violate any constraints\",    \n",
        "\"complete assignment\": \"Assignment where every variable has a value within its legal domain\",\n",
        "\"partial assignment\": \"Assignment where only some of the variables are given values\",\n",
        "\"unary contraint\": \"restricts the value of a single variable\",\n",
        "\"binary contraint\": \"relates two variables\",\n",
        "\"ternary contraint\": \"high order contraints of three or more variables\",\n",
        "\"global contraint\": \"constraint involving arbitrary number of variables\",\n",
        "\"preference constraint\": \"constraints which indicate solutions that are preferred\",\n",
        "\"contraint propagation\": \"use onctraints to reduce the number of legal values for a variable\",\n",
        "\"local consistency\": \"eliminate incosistent vlaues throughout graph\",\n",
        "\"node-consistent\": \"variable is node consistent if all values in domain satisfy unary contraints\",\n",
        "\"arc consistency\": \"variable is arc consistent if every value in domain statisfies binary constraints\",\n",
        "\"network arc consistent\": \"Every variable is arc consistent with every other variable in network\",\n",
        "\"path consistent\": \"$(X_i, X_j)$ path consistent with $X_m$ if every assignment $(X_i =a, X_j = ab)$ satisfies constraints on $(X_i, X_m)$, $(X_j, X_j)$\",\n",
        "\"strongly k-consistent\": \"CSP if it is k consistent if it is k-1, k-2, ..., 1 consistent\",\n",
        "\"backtracking search\": \"choose values for one variable at a time and backtrack if there are no legal values left\",\n",
        "\"forward checking\": \"When a variable X is assigned, establish arc consistency for it\",\n",
        "\"chronological backtracking\": \"back up to the previous branch and choose another variable during DFS\",\n",
        "\"cycle cutset\": \"set of nodes S that, when removed from a graph, result in a tree formed by remainign nodes\"\n",
        "\n",
        "}\n"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 564
        },
        "outputId": "739a57c2-d770-4c43-e80f-260d9731461e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n 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",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "- inference requires that an answer to a question about the knowledge base follows from previoulsy known knowledge in the knowledge base\n",
        "- successful agents combin declarative and procedural approaches\n",
        "\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "- every sentence must be true or false with respect to its possbile world\n",
        "- a model is the truth of each sentence with respect to the possbile world\n",
        "- models are abstraction that have a feixed set of truth values (true or false) for each sentence\n",
        "- ex. if a sentence a is true in model m, them m satisfies a or m is a model of a\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "- model fixed the truth value for every proposition symbol\n",
        "- Niave algo for inference is model checking approach. Model assigns true of false toe very proposition variable O(2^{proposition variables})\n",
        "- Then we compute which models are true and check the possible values of the poropstion varaiblees\n",
        "- This is solved through depth first search, etc.\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "- entialment by theorom proving\n",
        "- we decide entailment by showing implication of one sentence to another\n",
        "- resolution is only inference rule that yeilds complete infernce algo when coupled with search.\n",
        "- Resolution rule says to substitute in when something is false\n",
        "- Resolution rule applies only to cluases what about other propositional logic.\n",
        "- In this case convert resolution rule to a conjucntion of clauses\n",
        "- Converting to CNF form:\n",
        "- Eliminate $a \\leftrightarrow b$ with $(a \\implies b) \\lor (b \\implies a)$\n",
        "- Eliminate $a \\implies b$ with $\\lnot a \\lor b$\n",
        "- Move $\\lnot$ inwards by $\\lnot( \\lnot a) = a$, $\\lnot (a \\lor b) = ( \\lnot a \\lor \\lnot b)$, $\\lnot (a \\land b) = (\\lnot a \\land \\lnot b)$\n",
        "- Distribute $\\lor$ and $\\land$\n",
        "\n",
        "- There is a resolution algorithm to solve such problems, where we want to show $KB \\imples \\alpha$\n",
        "- This is equivlent to showing that $(KB \\land \\lnot a)$\n",
        "- We convert $(KB \\land \\lnot a)$ to a CNF and resolution rule is applied. \n",
        "- Each pair of cluases that contain complementary literals is resolved to produce new clause. This clause is added to a set\n",
        "- Process continues until there are no new clauses to be added, this means KB does not ential a\n",
        "- Or two clauses resolve to yeild the empty clause which means KB does entail a \n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge based agent\" : \"use reasoning rather than internal represetntation of knowledge to decide action\",    \n",
        "\"knowledge base\": \"set of stentences\",\n",
        "\"sentence\": \"expressed in knowledge representatino langauge and represent asseration about the universe\",\n",
        "\"axiom\": \"sentence taken as a given and not indpendently derived\",\n",
        "\"infernce\": \"derive new sentences from old ones\",\n",
        "\"declarative approach\": \"tell agent all sentences he needs to know to operate in the environment\",\n",
        "\"procedural approach\": \"encode sentneces as program code\",\n",
        "\"semantics\": \"the meaning of sentences. defines truth of each senteces vs. possible world\",\n",
        "\"entailment\": \"a senetece follows logically from another sentance\",\n",
        "\"sound/ truth preserving\": \"algorithm that derives only entialed sentences\",\n",
        "\"compleatness\": \"algo complete if it can derive any inference that wase entialed\",\n",
        "\"grounding\": \"connection between logical reasoning process and real environment\",\n",
        "\"atomic sentence\": \"contains single proposition symbol (variable that can be tru or false)\",\n",
        "\"complex sentence\": \"constructed from atomic sentence using parenthases and logical connectives\",\n",
        "\"theorom proving\": \"applying rules of inference on sentences in knowledge base\",\n",
        "\"logical equivlenece\": \"two sentneces of are logically equivlent if they are true in same set of models\",\n",
        "\"validity\": \"sentence is valid if true in all models\",\n",
        "\"satisfiability\": \"sentence is satsifiable if it is true by virtue of a model\",\n",
        "\"monotencity\": \"set of entailed senteces can only increase as knowledge base grows\",\n",
        "\"CNF, conjuctive normal form\": \"a sentence expressed as conjunction of clases\",\n",
        "\"Complementary literals\": \"one is a negation of the other\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 21,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5bc97f96-ee28-4b05-ec5d-be6aadddf911"
      },
      "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": 22,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n- inference requires that an answer to a question about the knowledge base follows from previoulsy known knowledge in the knowledge base\n- successful agents combin declarative and procedural approaches\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n \n- every sentence must be true or false with respect to its possbile world\n- a model is the truth of each sentence with respect to the possbile world\n- models are abstraction that have a feixed set of truth values (true or false) for each sentence\n- ex. if a sentence a is true in model m, them m satisfies a or m is a model of a\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n- model fixed the truth value for every proposition symbol\n- Niave algo for inference is model checking approach. Model assigns true of false toe very proposition variable O(2^{proposition variables})\n- Then we compute which models are true and check the possible values of the poropstion varaiblees\n- This is solved through depth first search, etc.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n- entialment by theorom proving\n- we decide entailment by showing implication of one sentence to another\n- resolution is only inference rule that yeilds complete infernce algo when coupled with search.\n- Resolution rule says to substitute in when something is false\n- Resolution rule applies only to cluases what about other propositional logic.\n- In this case convert resolution rule to a conjucntion of clauses\n- Converting to CNF form:\n- Eliminate $a \\leftrightarrow b$ with $(a \\implies b) \\lor (b \\implies a)$\n- Eliminate $a \\implies b$ with $\\lnot a \\lor b$\n- Move $\\lnot$ inwards by $\\lnot( \\lnot a) = a$, $\\lnot (a \\lor b) = ( \\lnot a \\lor \\lnot b)$, $\\lnot (a \\land b) = (\\lnot a \\land \\lnot b)$\n- Distribute $\\lor$ and $\\land$\n\n- There is a resolution algorithm to solve such problems, where we want to show $KB \\imples \u0007lpha$\n- This is equivlent to showing that $(KB \u0007nd \not a)$\n \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge based agent** - use reasoning rather than internal represetntation of knowledge to decide action\n* **Knowledge base** - set of stentences\n* **Sentence** - expressed in knowledge representatino langauge and represent asseration about the universe\n* **Axiom** - sentence taken as a given and not indpendently derived\n* **Infernce** - derive new sentences from old ones\n* **Declarative approach** - tell agent all sentences he needs to know to operate in the environment\n* **Procedural approach** - encode sentneces as program code\n* **Semantics** - the meaning of sentences. defines truth of each senteces vs. possible world\n* **Entailment** - a senetece follows logically from another sentance\n* **Sound/ truth preserving** - algorithm that derives only entialed sentences\n* **Compleatness** - algo complete if it can derive any inference that wase entialed\n* **Grounding** - connection between logical reasoning process and real environment\n* **Atomic sentence** - contains single proposition symbol (variable that can be tru or false)\n* **Complex sentence** - constructed from atomic sentence using parenthases and logical connectives\n* **Theorom proving** - applying rules of inference on sentences in knowledge base\n* **Logical equivlenece** - two sentneces of are logically equivlent if they are true in same set of models\n* **Validity** - sentence is valid if true in all models\n* **Satisfiability** - sentence is satsifiable if it is true by virtue of a model\n* **Monotencity** - set of entailed senteces can only increase as knowledge base grows\n* **Cnf, conjuctive normal form** - a sentence expressed as conjunction of clases\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "197055df-27de-47a2-b0d0-6d0748f40bb0"
      },
      "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 This is a summary of the first textbook chapter that was all about what is AI.  It addressed topics like how we can tell if a machine is intelligent, and\ndiscussed The Turing Test. \n\n* Bullet 1\n* Bullet 2\n\n$$\\frac{1}{mc^2}$$\n\n\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": {}
        }
      ]
    }
  ]
}