{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "521_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": "344222ad-a216-45e3-9726-b566dead59fe"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ef81cd11-e574-43c8-fb57-4c2e2e3d803c"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 1,
      "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 = \"\"\" Chapter 1.1 summary. \"\"\" \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 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "Episodic vs. Sequential: \n",
        "episodic environments are divided into atomic episodes, recieving a percept and performing an action in each.\n",
        "The next episode does not depend on the actions taken in previous ones. ie. classification tasks\n",
        "Sequential environments - current decisions can affect all future decisions, ie. chess, driving. \n",
        "\n",
        "Static vs. Dynamic\n",
        "dynamic - environment can change while the agent is deliberating\n",
        "semidynamic - environment cant change during deliberation, but performance measure can\n",
        "\n",
        "discrete vs. continuous - chess vs. driving\n",
        "\n",
        "agent = architecture + program\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive (with sensors) and act (with actuators) in an environment\",\n",
        "\"rational agent\" : \"agent that acts to attempt to achieve the best expected outcome, maximize performance measure\",\n",
        "\"percept\" : \"the content that an agents sensors percieve\",\n",
        "\"percept sequence\" : \"complete history of what the agent has percieved\",\n",
        "\"agent function\" : \"describes agent's behavior, maps a percept sequence to an action. abstract\",\n",
        "\"agent program\" : \"internal implementation of the agent function - different from agent function. concrete\",\n",
        "\"consequentialism\" : \"evaluating an agents behavior based on its consequences\",\n",
        "\"performance measure\" : \"evaluates the desirability of a given sequence of environment states\",\n",
        "\"rationality\" : \"depends on performance measure, prior knowledge of environment, actions avaliable, and percept sequence to date\",\n",
        "\"information gathering\" : \"doing things to modify future percepts\",\n",
        "\"task environments\" : \"the problems that rational agents solve\",\n",
        "\"actuators\" : \"for automated taxi driver, control over steering wheel, gas, and brakes\",\n",
        "\"sensors\" : \"for automated taxi driver, video camera to see, sensors to detect cars, speedometer, accelerometor, etc.\",\n",
        "\"fully observable\" : \"sensors give it access to the complete state of the environment\",\n",
        "\"partially observable\" : \"some sensor data is incomplete, or sensors cant work perfectly\",\n",
        "\"multi agent\": \"is another agent's behaviour described as maximizing a performance measure depending on agent's action\",\n",
        "\"deterministic environment\" : \"next state is completely determined by current state and action taken by agent. most are non-deterministic\",\n",
        "\"simple reflex agent\":\"select actions based on current precept, ignoring history, ie. vacuum. problem solving agents must plan ahead using 'search'\",\n",
        "\"transition model\":\"knowledge of how world changes, based on effects of agents actions, and independent of agents actions\",\n",
        "\"sensor model\":\"information about how world state is shown in percepts\",\n",
        "\"model based agent\":\"agents that use transition model and sensor model to keep track of the state of the world.\",\n",
        "\"utility function\":\"internalization of performance measure\",\n",
        "\"factored representation\":\"splits up state into a fixed set of variables\",\n",
        "\"structured representation\":\" objects and underlying relationships can be described explicitly\",\n",
        "\"qualification problem\":\"difficult to capture every contigency of appropriate behavior in logical rules\",\n",
        "\"Turing test\":\"behavioral test for machines. Pass = 30% success convincing person they are conversing with a person\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "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": "8da90261-c30a-4189-d598-8272a1e81c97"
      },
      "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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n \nEpisodic vs. Sequential: \nepisodic environments are divided into atomic episodes, recieving a percept and performing an action in each.\nThe next episode does not depend on the actions taken in previous ones. ie. classification tasks\nSequential environments - current decisions can affect all future decisions, ie. chess, driving. \n\nStatic vs. Dynamic\ndynamic - environment can change while the agent is deliberating\nsemidynamic - environment cant change during deliberation, but performance measure can\n\ndiscrete vs. continuous - chess vs. driving\n\nagent = architecture + program\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive (with sensors) and act (with actuators) in an environment\n* **Rational agent** - agent that acts to attempt to achieve the best expected outcome, maximize performance measure\n* **Percept** - the content that an agents sensors percieve\n* **Percept sequence** - complete history of what the agent has percieved\n* **Agent function** - describes agent's behavior, maps a percept sequence to an action. abstract\n* **Agent program** - internal implementation of the agent function - different from agent function. concrete\n* **Consequentialism** - evaluating an agents behavior based on its consequences\n* **Performance measure** - evaluates the desirability of a given sequence of environment states\n* **Rationality** - depends on performance measure, prior knowledge of environment, actions avaliable, and percept sequence to date\n* **Information gathering** - doing things to modify future percepts\n* **Task environments** - the problems that rational agents solve\n* **Actuators** - for automated taxi driver, control over steering wheel, gas, and brakes\n* **Sensors** - for automated taxi driver, video camera to see, sensors to detect cars, speedometer, accelerometor, etc.\n* **Fully observable** - sensors give it access to the complete state of the environment\n* **Partially observable** - some sensor data is incomplete, or sensors cant work perfectly\n* **Multi agent** - is another agent's behaviour described as maximizing a performance measure depending on agent's action\n* **Deterministic environment** - next state is completely determined by current state and action taken by agent. most are non-deterministic\n* **Simple reflex agent** - select actions based on current precept, ignoring history, ie. vacuum. problem solving agents must plan ahead using 'search'\n* **Transition model** - knowledge of how world changes, based on effects of agents actions, and independent of agents actions\n* **Sensor model** - information about how world state is shown in percepts\n* **Model based agent** - agents that use transition model and sensor model to keep track of the state of the world.\n* **Utility function** - internalization of performance measure\n* **Factored representation** - splits up state into a fixed set of variables\n* **Structured representation** -  objects and underlying relationships can be described explicitly\n* **Qualification problem** - difficult to capture every contigency of appropriate behavior in logical rules\n* **Turing test** - behavioral test for machines. Pass = 30% success convincing person they are conversing with a person\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 as objects. garbage collection --> objects deleted once unreachable \\n\n",
        "Strong Typed -- objects have fixed type, compiler prevents incompatible things\\n\n",
        "Static typing - (java) variables refer to objects of declared type\\n\n",
        "Dynamic typing - (python) variables come into existence when first assigned, type automatically determined\\n\n",
        "String concatenation - \"a\" + \"b\" = \"ab\"\\n\n",
        "Strings are immutable, lists are mutable \\n\n",
        "slicing: t[a:b] from a through b-1. t[a:] = from a till end. t[:a] = from start to a-1. t[:] = copy. t[a:b:c] = every cth item, from a through b-1 \\n\n",
        "----- LIST OPERATIONS ----- \\n\n",
        "append() adds to end.\\n\n",
        "insert(i, x) adds x at index i.\\n \n",
        "can add lists: lst = [8,9] + [2,4]\\n\n",
        "count(x) returns frequence of occurences of x.\\n\n",
        "remove(x) removes first occurence of x.\\n\n",
        "reverse() reverses the list in place \\n\n",
        "sort() sorts the list in place \\n\n",
        "sort(f) sorts list using function f\\n\n",
        "sorted(l) returns a sorted copy of list l\\n\n",
        "-----TUPLES-----\\n\n",
        "unchangable: t = (1,2,3); t[1] = 1 THROWS AN ERROR\\n\n",
        "to change a value, convert it to a list, and convert back\\n\n",
        "you can add tuples: a = (1, 2, 3); b = (4,); a += b #(1,2,3,4)\\n\n",
        "you cannot add items to tuples without converting to list\\n\n",
        "-----SETS-----\\n\n",
        "written with curly brackets\\n\n",
        "unordered, unchangeable, unindexed\\n\n",
        ".add() to add.\\n\n",
        ".remove() to remove. Error thrown if item is not in set.\\n\n",
        "-----STRING OPERATIONS-----\\n\n",
        "('a b c').split(' ') = ['a','b','c']\\n\n",
        "'_'.join(['a','b','c']) = 'a_b_c'\\n\n",
        "'dog'.capitalize() = 'Dog\\n\n",
        "'dog'.upper() = 'DOG'\\n\n",
        "'hi--'.strip('-') = 'hi'\\n\n",
        "a = 'abc'; a[1] = 'a' WILL THROW AN ERROR\\n\n",
        "----- DICTIONARIES ------\\n\n",
        "keys must be immutable. Constant average time add, lookup, and update\\n\n",
        "keys() list of current keys\\n\n",
        "values() list of current values\\n\n",
        "items() list of item tuples\\n\n",
        "----- FUNCTIONS -----\\n\n",
        "multiple return values: return type is tuple\\n\n",
        "no function overloading.\\n\n",
        "you can provide default values for a functions arguments. def myfun(b, c, d='hello'): these argumenst are optional\\n\n",
        "Non-default arguments always should preceed defaults - syntax error otherwise\\n\n",
        "--- *args --- variable number of non keyword arguments can be passed to functions (optionally as a list) def myfun(*args) & accessed as args\\n\n",
        "--- **kwargs --- variable number of keyword arguments can be passed with kwargs (optionally as a dictionary) with myfun(**kwargs)\\n\n",
        "- functions are first class objects can be created, destroyed, passed to functions, etc.\\n\n",
        "----- CLASSES ------\\n\n",
        "every class has a function __init__(self, inputs)\\n\n",
        "subclasses extend def of class. if we already have a class called student, we can define class AI_Student(Student):. you can also redefine methods within subclasses.\n",
        " to execute parent method and additional code, explicitly call parentclass's method with self as a parameter. can access superclass with super()\\n\n",
        "__init__() defines constructor, __len__ defines how len() will work, __copy__ defines how to copy a class,\n",
        "__cmp__ defines how == works, __add__ defines how + works, __neg__ defines how negation works\\n\n",
        "----- LIST COMPREHENSIONS -----\\n\n",
        "[x**2 for x in range(10)] = [0,1,4,9,16,etc.]\\n\n",
        "filtered list comp -- [elem *2 for elem in list if elem > 4] \\n\n",
        "Dictionary, set comprehensions--{k : v for k,v in list l} where l is tuple list, {x for x in l} for set.\\n\n",
        "----- GENERATORS -----\\n\n",
        "Functions that contain the yield keyword automatically return a generator when called\\n\n",
        "Each call to __next__, the method runs until a yield statement, then it stops and returns value. Next time it resumes where it left off.\\n\n",
        "requires less code, maintains state automatically, comptues values 1 at a time, crucial for infinite sequences, bad if you need to inspect individual values\\n\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"ability of an object to be modified once created\",\n",
        "\"Tuple\" : \"immutable, ordered. can have mixed types, including collections. t = (23, 'abc', 3.56, (2,3)). t[1] = 'abc'. t[-3] = 'abc'\",\n",
        "\"List\" : \"Mutable ordered sequence of items of mixed types. l = ['abc', 34, 4.34, 23]\",\n",
        "\"Slicing\" : \"t[a:b] returns copy of sequence starting at a, ending before b.\",\n",
        "\"Duck Typing\" : \"establishes suitability of an object based on presence of methods. if it acts like a duck, its a duck\",\n",
        "\"range(5)\" : \"[0,1,2,3,4]\",\n",
        "\"Iterators\": \"Objects with a __next()__ method\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6fd1483e-6d43-4650-95c4-c0aeeda163c2"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nall data treated as objects. garbage collection --> objects deleted once unreachable \n\nStrong Typed -- objects have fixed type, compiler prevents incompatible things\n\nStatic typing - (java) variables refer to objects of declared type\n\nDynamic typing - (python) variables come into existence when first assigned, type automatically determined\n\nString concatenation - \"a\" + \"b\" = \"ab\"\n\nStrings are immutable, lists are mutable \n\nslicing: t[a:b] from a through b-1. t[a:] = from a till end. t[:a] = from start to a-1. t[:] = copy. t[a:b:c] = every cth item, from a through b-1 \n\n----- LIST OPERATIONS ----- \n\nappend() adds to end.\n\ninsert(i, x) adds x at index i.\n \ncan add lists: lst = [8,9] + [2,4]\n\ncount(x) returns frequence of occurences of x.\n\nremove(x) removes first occurence of x.\n\nreverse() reverses the list in place \n\nsort() sorts the list in place \n\nsort(f) sorts list using function f\n\nsorted(l) returns a sorted copy of list l\n\n-----TUPLES-----\n\nunchangable: t = (1,2,3); t[1] = 1 THROWS AN ERROR\n\nto change a value, convert it to a list, and convert back\n\nyou can add tuples: a = (1, 2, 3); b = (4,); a += b #(1,2,3,4)\n\nyou cannot add items to tuples without converting to list\n\n-----SETS-----\n\nwritten with curly brackets\n\nunordered, unchangeable, unindexed\n\n.add() to add.\n\n.remove() to remove. Error thrown if item is not in set.\n\n-----STRING OPERATIONS-----\n\n('a b c').split(' ') = ['a','b','c']\n\n'_'.join(['a','b','c']) = 'a_b_c'\n\n'dog'.capitalize() = 'Dog\n\n'dog'.upper() = 'DOG'\n\n'hi--'.strip('-') = 'hi'\n\na = 'abc'; a[1] = 'a' WILL THROW AN ERROR\n\n----- DICTIONARIES ------\n\nkeys must be immutable. Constant average time add, lookup, and update\n\nkeys() list of current keys\n\nvalues() list of current values\n\nitems() list of item tuples\n\n----- FUNCTIONS -----\n\nmultiple return values: return type is tuple\n\nno function overloading.\n\nyou can provide default values for a functions arguments. def myfun(b, c, d='hello'): these argumenst are optional\n\nNon-default arguments always should preceed defaults - syntax error otherwise\n\n--- *args --- variable number of non keyword arguments can be passed to functions (optionally as a list) def myfun(*args) & accessed as args\n\n--- **kwargs --- variable number of keyword arguments can be passed with kwargs (optionally as a dictionary) with myfun(**kwargs)\n\n- functions are first class objects can be created, destroyed, passed to functions, etc.\n\n----- CLASSES ------\n\nevery class has a function __init__(self, inputs)\n\nsubclasses extend def of class. if we already have a class called student, we can define class AI_Student(Student):. you can also redefine methods within subclasses.\n to execute parent method and additional code, explicitly call parentclass's method with self as a parameter. can access superclass with super()\n\n__init__() defines constructor, __len__ defines how len() will work, __copy__ defines how to copy a class,\n__cmp__ defines how == works, __add__ defines how + works, __neg__ defines how negation works\n\n----- LIST COMPREHENSIONS -----\n\n[x**2 for x in range(10)] = [0,1,4,9,16,etc.]\n\nfiltered list comp -- [elem *2 for elem in list if elem > 4] \n\nDictionary, set comprehensions--{k : v for k,v in list l} where l is tuple list, {x for x in l} for set.\n\n----- GENERATORS -----\n\nFunctions that contain the yield keyword automatically return a generator when called\n\nEach call to __next__, the method runs until a yield statement, then it stops and returns value. Next time it resumes where it left off.\n\nrequires less code, maintains state automatically, comptues values 1 at a time, crucial for infinite sequences, bad if you need to inspect individual values\n\n\n\n## Module 2 Definitions\n* **Mutability** - ability of an object to be modified once created\n* **Tuple** - immutable, ordered. can have mixed types, including collections. t = (23, 'abc', 3.56, (2,3)). t[1] = 'abc'. t[-3] = 'abc'\n* **List** - Mutable ordered sequence of items of mixed types. l = ['abc', 34, 4.34, 23]\n* **Slicing** - t[a:b] returns copy of sequence starting at a, ending before b.\n* **Duck typing** - establishes suitability of an object based on presence of methods. if it acts like a duck, its a duck\n* **Range(5)** - [0,1,2,3,4]\n* **Iterators** - Objects with a __next()__ method\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Difference between search tree and state space is the fact that state space is the potentially infinite set of states and actions, search tree has paths between these states reaching towards the goal. it may have many paths to a give state, but each node has a unique path to the root. \"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "----UNIFORM COST SEARCH----\\n\n",
        "(see module 4 lecture notes)\n",
        "idea is that while BFS search spreads out in waves of uniform depth, uniform cost spreads out in waves of uniform cost. Basically a call to Best-first search with Path-Cost as an evaluation function.\\n\n",
        "C* is cost of optimal solution.\\n\n",
        "e is lower bound on cost of an action with e>0.\\n\n",
        "Worst case time and space complexity = O(b^( 1 + floor[C*/e] )).\\n\n",
        "THIS CAN BE MUCH GREATER THAN B^D. when all action costs are similar, its similar to BFS.\\n\n",
        "- UCS is COMPLETE AND OPTIMAL.\\n\n",
        "- first solution found has cost at least as low as any other node in frontier. Considers paths systematically in order of increasing cost.\\n\n",
        "----BACKTRACKING SEARCH-----\\n\n",
        "variant of DFS that uses less memory.\\n\n",
        "only one successor generated at a time, rather than all successors. each partially expanded node rememebrs which successor to generate next.\\n\n",
        "successors generated by modifying current stae, rather than reallocating new memory.\\n\n",
        "- O(m) memory vs. O(b*m) for DFS.\\n \n",
        "- we maintain efficient set data structure for states on current path, so we can check for a cycle in O(1) instead of O(m).\\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "- Goal Formulation: agent adopts a goal, limiting the objectives and potential actions taken.\\n\n",
        "- Problem Formulation: agent devises a descroptino of staes/actions necessary to reach the goal.\\n\n",
        "- Search: Agent simulates sequences of actions in its model, until it finds a solution.\\n\n",
        "In a fully observable deterministic known environment, the solutino is a fixed sequence of actions.\\n\n",
        "Search problem consists of:\\n \n",
        "- state space\\n\n",
        "- initial state\\n\n",
        "- goal states\\n\n",
        "- actions avaliable\\n\n",
        "- transition model that describes what actions do\\n\n",
        "- action cost function\\n\n",
        "Frontier is the set of states avaliable for expanding and applying legal actions to.\\n\n",
        "----- TREE SEARCH -----\\n\n",
        "Generalized algorithm. Enumerate all possible paths from initial state.\\n\n",
        "root is initial state, nodes in search tree generated by transition model. Treats different paths to the same node as distinct\\n\n",
        "- initialize frontier to initial state.\\n\n",
        "- if frontier empty --> failure.\\n\n",
        "- choose leaf for expansion according to strategy, remove from frontier.\\n\n",
        "- if node is goal, return solution. Else, expand node and add resulting nodes to frontier\\n\n",
        "Problem - failure to detect repeated states can turn O(n)-->O(exp(n))\\n\n",
        "----- GRAPH SEARCH -----\\n\n",
        "Tree search, except we check if node has been visited before adding to the queue. This can take a lot of memory.\\n\n",
        "- initialize frontier to initial state.\\n\n",
        "- initialize empty explored set\\n\n",
        "- if frontier empty, FAILURE\\n\n",
        "- choose leaf node, remove from frontier\\n\n",
        "- if node is goal, SOLUTION\\n\n",
        "- add to explored set\\n\n",
        "- expand chosen node, add resulting nodes to frontier IF NOT IN EXPLORED SET\\n\n",
        "-----GENERAL SEARCH INFO-----\\n\n",
        "dimensions for evaluation: completeness, optimality, time & space complexity\\n\n",
        "time/space complexity variables:\\n\n",
        "- b = maximum branching factor of search tree\\n\n",
        "- d = depth of shallowest goal node\\n\n",
        "- m = maximum path length in state space, potentially infinite.\\n\n",
        "-----UNINFORMED STRATEGIES-----\\n\n",
        "All non-goal nodes look equally good.\\n\n",
        "---BFS---\\n\n",
        "idea: expand shallowest unexpanded node.\\n\n",
        "frontier is FIFO queue\\n\n",
        "put successors at end of frontier successor list.\\n\n",
        "- Complete if b is finite\\n\n",
        "- Optimal if cost = 1 per step (not optimal in general)\\n\n",
        "- Time complexity - O(b^d)\\n\n",
        "- Space complexity - O(b^d)\\n\n",
        "Exponential complexity is not good, only works for small instances. Memory requirement is big problem.\\n\n",
        "---DFS---\\n\n",
        "idea: expand deepest unexpanded node\\n\n",
        "frontier is LIFO queue, put successors at front of frontier successor list\\n\n",
        "- not complete - fails in infinite depth spaces or spaces with loops (fixable if finite).\\n\n",
        "- not optimal\\n\n",
        "- O(b^m) time complexity. terrible if m>>b. may be much faster than BFS if solutions dense.\\n\n",
        "- O(b*m) linear space.\\n\n",
        "---DFS > BFS WHEN---:\\n\n",
        "- space restricted\\n\n",
        "- many possible long path solutions, wrong paths terminated quickly\\n\n",
        "- search can be quickly fine-tuned\\n\n",
        "---BFS > DFS WHEN---:\\n\n",
        "- possible infinite paths\\n\n",
        "- some solutions have short paths\\n\n",
        "- can quickly discard unlikely paths\\n\n",
        "---DEPTH-LIMITED-SEARCH---\\n\n",
        "DFS with depth limit i. nodes at depth i have no children, eliminates infinite path issue.\\n\n",
        "- optimal if l = d by luck. if l<d then incomplete. if l>d then not optimal.\\n\n",
        "- O(b^l) time\\n\n",
        "- O(b*l) space\\n\n",
        "---ITERATIVE DEEPENING SEARCH---\\n\n",
        "finds best depth limit. Uses depth-limited as subroutine with increasing l, return solution if success.\\n\n",
        "- complete & optimal. goal found at d.\\n\n",
        "- O(b^d) time\\n\n",
        "- O(b*d) space\\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",
        "\"informed search\" : \"agent can estimate how far it is from goal state\",\n",
        "\"open loop\" : \"once solution is found, we can ignore percepts while executing actions.\",\n",
        "\"closed-loop system\" : \"if there is a chance model is wrong, or environment is non-deterministic, its safer to monitor percepts\",\n",
        "\"optimal solution\":\"has lowest path cost among all solutions\",\n",
        "\"model\":\"abstract mathematical description and not the real thing\",\n",
        "\"abstraction\":\"process of removing detail from a representation\",\n",
        "\"completeness\": \"always finds the solution?\",\n",
        "\"optimality\":\"lowest past cost solution found first?\",\n",
        "\"time complexity\":\"worst case # of nodes generated\",\n",
        "\"space complexity\":\"worst case # of nodes simultaneously in memory\",\n",
        "\"best first search\":\"choose a node n with minimum f(n) evaluation function.\",\n",
        "\"node\":\"has a state, parent, action, and a path cost. Following parent pointers brings us to root\",\n",
        "\"priority queue\":\"first pops node w/ minimum cost according to f. Used in best first search.\",\n",
        "\"FIFO queue\": \"pops node added first to queue. Used in BFS\",\n",
        "\"LIFO queue\": \"(stack) pops first the most recently added node. Used in DFS\",\n",
        "\"tree search\" : \"does not check for repeated paths. uses less memory, but runs slower than graph search.\",\n",
        "\"depth (d)\": \"@ of actions in an optimal solution\",\n",
        "\"branching factor (b)\": \"# of successors of a node that need to be considered\",\n",
        "\"Uniform Cost Search (Dijkstra's)\":\"'use best-first where evaluation function is cost of path from root to current node.\",\n",
        "\"Diameter\": \"max number of edges from any node to another\",\n",
        "\"bidirectional search\": \"simultaneously searches forward from root, and backwards from goal.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "997e6a35-33d0-43bc-a883-d025c43b5505"
      },
      "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": 19,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# 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 Difference between search tree and state space is the fact that state space is the potentially infinite set of states and actions, search tree has paths between these states reaching towards the goal. it may have many paths to a give state, but each node has a unique path to the root. \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n----UNIFORM COST SEARCH----\n\n(see module 4 lecture notes)\nidea is that while BFS search spreads out in waves of uniform depth, uniform cost spreads out in waves of uniform cost. Basically a call to Best-first search with Path-Cost as an evaluation function.\n\nC* is cost of optimal solution.\n\ne is lower bound on cost of an action with e>0.\n\nWorst case time and space complexity = O(b^( 1 + floor[C*/e] )).\n\nTHIS CAN BE MUCH GREATER THAN B^D. when all action costs are similar, its similar to BFS.\n\n- UCS is COMPLETE AND OPTIMAL.\n\n- first solution found has cost at least as low as any other node in frontier. Considers paths systematically in order of increasing cost.\n\n----BACKTRACKING SEARCH-----\n\nvariant of DFS that uses less memory.\n\nonly one successor generated at a time, rather than all successors. each partially expanded node rememebrs which successor to generate next.\n\nsuccessors generated by modifying current stae, rather than reallocating new memory.\n\n- O(m) memory vs. O(b*m) for DFS.\n \n- we maintain efficient set data structure for states on current path, so we can check for a cycle in O(1) instead of O(m).\n\n\n \n\n## Module 3 Lecture Notes\n \n- Goal Formulation: agent adopts a goal, limiting the objectives and potential actions taken.\n\n- Problem Formulation: agent devises a descroptino of staes/actions necessary to reach the goal.\n\n- Search: Agent simulates sequences of actions in its model, until it finds a solution.\n\nIn a fully observable deterministic known environment, the solutino is a fixed sequence of actions.\n\nSearch problem consists of:\n \n- state space\n\n- initial state\n\n- goal states\n\n- actions avaliable\n\n- transition model that describes what actions do\n\n- action cost function\n\nFrontier is the set of states avaliable for expanding and applying legal actions to.\n\n----- TREE SEARCH -----\n\nGeneralized algorithm. Enumerate all possible paths from initial state.\n\nroot is initial state, nodes in search tree generated by transition model. Treats different paths to the same node as distinct\n\n- initialize frontier to initial state.\n\n- if frontier empty --> failure.\n\n- choose leaf for expansion according to strategy, remove from frontier.\n\n- if node is goal, return solution. Else, expand node and add resulting nodes to frontier\n\nProblem - failure to detect repeated states can turn O(n)-->O(exp(n))\n\n----- GRAPH SEARCH -----\n\nTree search, except we check if node has been visited before adding to the queue. This can take a lot of memory.\n\n- initialize frontier to initial state.\n\n- initialize empty explored set\n\n- if frontier empty, FAILURE\n\n- choose leaf node, remove from frontier\n\n- if node is goal, SOLUTION\n\n- add to explored set\n\n- expand chosen node, add resulting nodes to frontier IF NOT IN EXPLORED SET\n\n-----GENERAL SEARCH INFO-----\n\ndimensions for evaluation: completeness, optimality, time & space complexity\n\ntime/space complexity variables:\n\n- b = maximum branching factor of search tree\n\n- d = depth of shallowest goal node\n\n- m = maximum path length in state space, potentially infinite.\n\n-----UNINFORMED STRATEGIES-----\n\nAll non-goal nodes look equally good.\n\n---BFS---\n\nidea: expand shallowest unexpanded node.\n\nfrontier is FIFO queue\n\nput successors at end of frontier successor list.\n\n- Complete if b is finite\n\n- Optimal if cost = 1 per step (not optimal in general)\n\n- Time complexity - O(b^d)\n\n- Space complexity - O(b^d)\n\nExponential complexity is not good, only works for small instances. Memory requirement is big problem.\n\n---DFS---\n\nidea: expand deepest unexpanded node\n\nfrontier is LIFO queue, put successors at front of frontier successor list\n\n- not complete - fails in infinite depth spaces or spaces with loops (fixable if finite).\n\n- not optimal\n\n- O(b^m) time complexity. terrible if m>>b. may be much faster than BFS if solutions dense.\n\n- O(b*m) linear space.\n\n---DFS > BFS WHEN---:\n\n- space restricted\n\n- many possible long path solutions, wrong paths terminated quickly\n\n- search can be quickly fine-tuned\n\n---BFS > DFS WHEN---:\n\n- possible infinite paths\n\n- some solutions have short paths\n\n- can quickly discard unlikely paths\n\n---DEPTH-LIMITED-SEARCH---\n\nDFS with depth limit i. nodes at depth i have no children, eliminates infinite path issue.\n\n- optimal if l = d by luck. if l<d then incomplete. if l>d then not optimal.\n\n- O(b^l) time\n\n- O(b*l) space\n\n---ITERATIVE DEEPENING SEARCH---\n\nfinds best depth limit. Uses depth-limited as subroutine with increasing l, return solution if success.\n\n- complete & optimal. goal found at d.\n\n- O(b^d) time\n\n- O(b*d) space\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Informed search** - agent can estimate how far it is from goal state\n* **Open loop** - once solution is found, we can ignore percepts while executing actions.\n* **Closed-loop system** - if there is a chance model is wrong, or environment is non-deterministic, its safer to monitor percepts\n* **Optimal solution** - has lowest path cost among all solutions\n* **Model** - abstract mathematical description and not the real thing\n* **Abstraction** - process of removing detail from a representation\n* **Completeness** - always finds the solution?\n* **Optimality** - lowest past cost solution found first?\n* **Time complexity** - worst case # of nodes generated\n* **Space complexity** - worst case # of nodes simultaneously in memory\n* **Best first search** - choose a node n with minimum f(n) evaluation function.\n* **Node** - has a state, parent, action, and a path cost. Following parent pointers brings us to root\n* **Priority queue** - first pops node w/ minimum cost according to f. Used in best first search.\n* **Fifo queue** - pops node added first to queue. Used in BFS\n* **Lifo queue** - (stack) pops first the most recently added node. Used in DFS\n* **Tree search** - does not check for repeated paths. uses less memory, but runs slower than graph search.\n* **Depth (d)** - @ of actions in an optimal solution\n* **Branching factor (b)** - # of successors of a node that need to be considered\n* **Uniform cost search (dijkstra's)** - 'use best-first where evaluation function is cost of path from root to current node.\n* **Diameter** - max number of edges from any node to another\n* **Bidirectional search** - simultaneously searches forward from root, and backwards from goal.\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 = \"\"\" Every consistent heuristic is admissable, but not vice versa. With a consistent heuristic, A* is optimal.\\n\n",
        "With an inconsistent heuristic, it is possible to have multiple paths leading to the same state, with different path costs. If consistent, we wil never have to re-add a state to the frontier.\\n\n",
        "A* with an inadmissable heuristic could still be optimal.\\n\n",
        "Contours of UCS are cirucular around start state, whereas in A* they skew towards solution.\\n\n",
        "path costs increase monotonically if and only if the heuristic is consistent (contours wont cross).\\n\n",
        "A* never expands nodes with f(n) > C*\\n\n",
        "A* cound expand non goal nodes with f(n) = C* before the goal node\\n\n",
        "---RECURSIVE BEST FIRST SEARCH---\\n\n",
        "rather than continuing infinitely down current path, uses f_limit variable to keep track of f value of best alternative path avaliable from any ancestor of current node.\\n\n",
        "As recursion unwinds, we replace the f values of each node along the path with a backed up value - best f value of its children. It rememebrs the f value of the best leaf \n",
        "in the forgotten subtree, and can then decide if its worth reexpanding the subtree at some later time.\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "A good heuristic would have a b* value close to 1.\\n\n",
        "RBFS and SMA* are robust optimal search algorithms that use limited amount of memory. IF they have enough time, they can solve problems for which A* runs out of memory.\\n\n",
        "BEAM search puts a limit on the size of the frontier, making it incomplete and suboptimal, but often quickly finds reasonably good solutions. \\n\n",
        "IDA* addersses space complexity issue of A*.\\n\n",
        "Bidirectional A* search is sometimes more efficient than A* itself.\\n\n",
        "weighted A* search focuses search towards a goal, sacrificing optimality but expanding fewer nodes.\\n\n",
        "Euclidean distance is a consistent in admissible heuristic for estimating travel distance between two locations.\\n\n",
        "If a heurisitc dominates another, it leads to a more efficient algorithm.\\n\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "Search problem = {states, initial state, actions, transition model, path costs, goal test}\\n\n",
        "search strategy determines the search process. Implemented by different queue structures.\\n\n",
        "----- UNIFORM COST SEARCH (see module 3 reading nodes)----\\n\n",
        "Used to search a weighted tree.\\n\n",
        "Expands nodes with lowest path cost. Frontier is priority queue ordered by g(n).\\n\n",
        "DIFFERENCE FROM BFS:\\n\n",
        "- goal-tests nodes when selected for expansion, not when added to frontier.\\n\n",
        "- updates node on frontier if a better path to same state is found.\\n\n",
        "- enqueues node before checking if its a goal, lets us prioritize which paths to explore. favors lower cost paths.\\n\n",
        "-----GREEDY BEST-FIRST-SEARCH-----\\n\n",
        "expands node with lowest h(n)\\n\n",
        "implement using a priority queue. Exactly the same as UCS replacing g(n) with h(n).\\n\n",
        "- not optimal \n",
        "- not complete, can get stuck in loops. complete on finite spaces if no loops.\\n\n",
        "- O(|V|) = worst case time and space.\\n\n",
        "- with a good heuristic, can be reduced to O(b*m)\\n\n",
        "-----A* SEARCH-----\\n\n",
        "best known form of best-first search.\\n\n",
        "idea: avoid expanding paths that are already expensive, but expand most promising first.\\n\n",
        "f(n)=g(n)+h(n)\\n\n",
        "implemented with frontier queue as a priority queue with increasing f(n)\\n\n",
        "- h(n) is ADMISSABLE if it never overestimates cost to reach the goal. (optimistic)\\n\n",
        "- h(n) <= true cost from n to goal\\n\n",
        "- h(n) >= 0.\\n\n",
        "- if h(n) is admissable, A* tree search is OPTIMAL\\n\n",
        "- A* search is COMPLETE\\n\n",
        "- A* has O(b^d) space\\n\n",
        "algorithm does not end when goal is added to queue, waits until it is popped off queue as we may find a better value.\\n\n",
        "--- Relaxed Problem ---\\n\n",
        "fewer restrictions on the actions than the original.\\n\n",
        "Cost of optimal solution to a relaxed problem is an admissable heuristic for original problem.\\n\n",
        "Dominance: h2 dominates h1 if h2(n) >= h1(n) for all n. (both admissable)\\n\n",
        "if h2 dominates h1, its optimistic but more accurate.\\n\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"uses domain specific hints about location of goals in form of a heuristic.\",\n",
        "\"heuristic h(n)\":\"estimated cost of cheapest path from node n to goal state\",\n",
        "\"Greedy best-first search\":\"expands node with howest h(n) value (appears closest to goal).\",\n",
        "\"consistency\":\"a heuristic h(n) is consistent if for every n, and successor n', h(n)<=c(n,a,n') + h(n')\",\n",
        "\"triangle inequality\":\"side of a triangle cant exceed summed length of other two\",\n",
        "\"recursive best-first search\":\"attempts to mimic the operation of standard best first search using linear space.\",\n",
        "\"effective branching factor (b*)\":\"if N=total # nodes generated by A*, d=solution depth, then b* is branching factor needed to get N+1 nodes.\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "020e292b-adac-4e52-9e70-c9a16f108a53"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Every consistent heuristic is admissable, but not vice versa. With a consistent heuristic, A* is optimal.\n\nWith an inconsistent heuristic, it is possible to have multiple paths leading to the same state, with different path costs. If consistent, we wil never have to re-add a state to the frontier.\n\nA* with an inadmissable heuristic could still be optimal.\n\nContours of UCS are cirucular around start state, whereas in A* they skew towards solution.\n\npath costs increase monotonically if and only if the heuristic is consistent (contours wont cross).\n\nA* never expands nodes with f(n) > C*\n\nA* cound expand non goal nodes with f(n) = C* before the goal node\n\n---RECURSIVE BEST FIRST SEARCH---\n\nrather than continuing infinitely down current path, uses f_limit variable to keep track of f value of best alternative path avaliable from any ancestor of current node.\n\nAs recursion unwinds, we replace the f values of each node along the path with a backed up value - best f value of its children. It rememebrs the f value of the best leaf \nin the forgotten subtree, and can then decide if its worth reexpanding the subtree at some later time.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \nA good heuristic would have a b* value close to 1.\n\nRBFS and SMA* are robust optimal search algorithms that use limited amount of memory. IF they have enough time, they can solve problems for which A* runs out of memory.\n\nBEAM search puts a limit on the size of the frontier, making it incomplete and suboptimal, but often quickly finds reasonably good solutions. \n\nIDA* addersses space complexity issue of A*.\n\nBidirectional A* search is sometimes more efficient than A* itself.\n\nweighted A* search focuses search towards a goal, sacrificing optimality but expanding fewer nodes.\n\nEuclidean distance is a consistent in admissible heuristic for estimating travel distance between two locations.\n\nIf a heurisitc dominates another, it leads to a more efficient algorithm.\n\n \n\n## Module 4 Lecture Notes\n \nSearch problem = {states, initial state, actions, transition model, path costs, goal test}\n\nsearch strategy determines the search process. Implemented by different queue structures.\n\n----- UNIFORM COST SEARCH (see module 3 reading nodes)----\n\nUsed to search a weighted tree.\n\nExpands nodes with lowest path cost. Frontier is priority queue ordered by g(n).\n\nDIFFERENCE FROM BFS:\n\n- goal-tests nodes when selected for expansion, not when added to frontier.\n\n- updates node on frontier if a better path to same state is found.\n\n- enqueues node before checking if its a goal, lets us prioritize which paths to explore. favors lower cost paths.\n\n-----GREEDY BEST-FIRST-SEARCH-----\n\nexpands node with lowest h(n)\n\nimplement using a priority queue. Exactly the same as UCS replacing g(n) with h(n).\n\n- not optimal \n- not complete, can get stuck in loops. complete on finite spaces if no loops.\n\n- O(|V|) = worst case time and space.\n\n- with a good heuristic, can be reduced to O(b*m)\n\n-----A* SEARCH-----\n\nbest known form of best-first search.\n\nidea: avoid expanding paths that are already expensive, but expand most promising first.\n\nf(n)=g(n)+h(n)\n\nimplemented with frontier queue as a priority queue with increasing f(n)\n\n- h(n) is ADMISSABLE if it never overestimates cost to reach the goal. (optimistic)\n\n- h(n) <= true cost from n to goal\n\n- h(n) >= 0.\n\n- if h(n) is admissable, A* tree search is OPTIMAL\n\n- A* search is COMPLETE\n\n- A* has O(b^d) space\n\nalgorithm does not end when goal is added to queue, waits until it is popped off queue as we may find a better value.\n\n--- Relaxed Problem ---\n\nfewer restrictions on the actions than the original.\n\nCost of optimal solution to a relaxed problem is an admissable heuristic for original problem.\n\nDominance: h2 dominates h1 if h2(n) >= h1(n) for all n. (both admissable)\n\nif h2 dominates h1, its optimistic but more accurate.\n\n \n\n## Module 4 Definitions\n* **Informed search** - uses domain specific hints about location of goals in form of a heuristic.\n* **Heuristic h(n)** - estimated cost of cheapest path from node n to goal state\n* **Greedy best-first search** - expands node with howest h(n) value (appears closest to goal).\n* **Consistency** - a heuristic h(n) is consistent if for every n, and successor n', h(n)<=c(n,a,n') + h(n')\n* **Triangle inequality** - side of a triangle cant exceed summed length of other two\n* **Recursive best-first search** - attempts to mimic the operation of standard best first search using linear space.\n* **Effective branching factor (b*)** - if N=total # nodes generated by A*, d=solution depth, then b* is branching factor needed to get N+1 nodes.\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "-----HEURISTIC ALPHA-BETA TREE SEARCH-----\\n\n",
        "- replace utility funcction with an evaluation function which estimates a states utility.\\n\n",
        "- replace terminal test with cutoff test, which must return true for terminal nodes, but is free to decide wheter to cut off seaerch for other nodes.\\n\n",
        "Evaluation function: returns an estimate of the expected utility of state s to player p.\\n\n",
        "For terminal states, Eval = Utility, but for nonterminal nodes, it must be between a loss and a win.\\n\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "-----EXPECTIMINIMAX-----\\n\n",
        "- O(b^m * n^m) time where n is the number of distinct number of rolls (assuming dice)\\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "Simplest Game Environment:\\n\n",
        "- multiagent\\n\n",
        "- static: no change during agent deliberation\\n\n",
        "- discrete: a finite set of percepts and actions\\n\n",
        "- fully observable: agent's sensors give it complete state of environment\\n\n",
        "- strategic: next state determinted by current state and action executed by the agent and actions of one other agent.\\n\n",
        "Key properties of our games:\\n\n",
        "- Two players alternate moves\\n\n",
        "- zero sum: one players loss is another's gain\\n\n",
        "- clear set of legal moves\\n\n",
        "- well defined outcomes\\n\n",
        "More complicated games:\\n\n",
        "- most card games, scrabble, etc. are stochastic not deterministic, and arent fully observable.\\n\n",
        "- real time strategy games: continuous, not discrete. no pause between actions - dont take turns.\\n\n",
        "- cooperative games\\n\n",
        "GAME SETUP:\\n\n",
        "two players:max/min. max goes first. Alternate turns\\n\n",
        "Games as search:\\n\n",
        "- initial state\\n\n",
        "- successor function. list of legal (move,state) pairs.\\n\n",
        "- terminal test\\n\n",
        "- utility function: numerical value of terminal states\\n\n",
        "- MAX uses search tree to determine next move.\\n\n",
        "-----ADVERSARIAL SEARCH-----\\n\n",
        "all play from max's POV\\n\n",
        "MAX attempts to maximize MAX's outcome, MIN wants to minimize it. MAX moves first.\\n\n",
        "Even tree levels represent turns for max, odd ones are Min's turns.\\n\n",
        "Evaluation Functions f(n):\\n\n",
        "- evaluates how good a board is based on static features of the board.\\n\n",
        "- sero sum assumption lets us use one function to describe goodness for both players. losing=negative, winning=positive.\\n\n",
        "-----MINIMAX SEARCH-----\\n\n",
        "idea: make best move for MAX assuming MIN makes best move for MIN.\\n\n",
        "- backed-up value of each node is optimal value of its children.\\n\n",
        "- for MAX, backed-up val is max of children values\\n\n",
        "- for MIN, BUV is min of children values.\\n\n",
        "- performs a complete depth-first exploration of the game tree.\\n\n",
        "- O(b^m) time\\n\n",
        "- O(b*m) space\\n\n",
        "Until game ends:\\n\n",
        "- start with current position as MAX node.\\n\n",
        "- expand game tree a fixed number of ply\\n\n",
        "- apply eval function to leaf positions\\n\n",
        "- calculate back-up values bottom up.\\n\n",
        "- pick move assigned to MAX at the root\\n\n",
        "- wait for min to respond.\\n\n",
        "-----ALPHA-BETA PRUNING-----\\n\n",
        "During minimax, keep track of a/b, MAX's current lower bound on MAX's outcome, & MIN's current upper obund on MIN's outcome.\\n\n",
        "MAX will never allow a move leading to a worse score than a, and Min for b.\\n\n",
        "Stop evaluating a branch if a max node has value v>=B backed up, or a min node has v <= a. That node will never be selected\\n\n",
        "- effectivemess is highly dependent on the order in which states are examined.\\n\n",
        "- if this could be done perfectly, would be O(b^(m/2)) nodes. b-->sqrt(b)\n",
        "-----EXPECTIMAX SEARCH-----\\n\n",
        "Max nodes like Minimax, Chance nodes instead of Min nodes-outcome is uncertain.\\n\n",
        "calculate the expected utilities of the children.\\n\n",
        "as depth increases, probability of reaching a given search node shrinks.\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\", \n",
        "\"minimax value\":\"optimal utility of its children\",\n",
        "\"alpha\":\"value of best choice found so far for MAX. think 'AT LEAST'\",\n",
        "\"beta\":\"the value of the best choice found so far for MIN. think 'AT MOST'\",\n",
        "\"Stochastic Games\":\"involves probability and skill\",\n",
        "\"Expectiminimax value\":\"For chance nodes, we compute the expected value of its children, for non changce nodes it works the same way.\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ae13c4b3-1bb9-4d54-a479-247373aca2dd"
      },
      "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": 32,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# 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 \n-----HEURISTIC ALPHA-BETA TREE SEARCH-----\n\n- replace utility funcction with an evaluation function which estimates a states utility.\n\n- replace terminal test with cutoff test, which must return true for terminal nodes, but is free to decide wheter to cut off seaerch for other nodes.\n\nEvaluation function: returns an estimate of the expected utility of state s to player p.\n\nFor terminal states, Eval = Utility, but for nonterminal nodes, it must be between a loss and a win.\n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \n-----EXPECTIMINIMAX-----\n\n- O(b^m * n^m) time where n is the number of distinct number of rolls (assuming dice)\n\n\n \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 \nSimplest Game Environment:\n\n- multiagent\n\n- static: no change during agent deliberation\n\n- discrete: a finite set of percepts and actions\n\n- fully observable: agent's sensors give it complete state of environment\n\n- strategic: next state determinted by current state and action executed by the agent and actions of one other agent.\n\nKey properties of our games:\n\n- Two players alternate moves\n\n- zero sum: one players loss is another's gain\n\n- clear set of legal moves\n\n- well defined outcomes\n\nMore complicated games:\n\n- most card games, scrabble, etc. are stochastic not deterministic, and arent fully observable.\n\n- real time strategy games: continuous, not discrete. no pause between actions - dont take turns.\n\n- cooperative games\n\nGAME SETUP:\n\ntwo players:max/min. max goes first. Alternate turns\n\nGames as search:\n\n- initial state\n\n- successor function. list of legal (move,state) pairs.\n\n- terminal test\n\n- utility function: numerical value of terminal states\n\n- MAX uses search tree to determine next move.\n\n-----ADVERSARIAL SEARCH-----\n\nall play from max's POV\n\nMAX attempts to maximize MAX's outcome, MIN wants to minimize it. MAX moves first.\n\nEven tree levels represent turns for max, odd ones are Min's turns.\n\nEvaluation Functions f(n):\n\n- evaluates how good a board is based on static features of the board.\n\n- sero sum assumption lets us use one function to describe goodness for both players. losing=negative, winning=positive.\n\n-----MINIMAX SEARCH-----\n\nidea: make best move for MAX assuming MIN makes best move for MIN.\n\n- backed-up value of each node is optimal value of its children.\n\n- for MAX, backed-up val is max of children values\n\n- for MIN, BUV is min of children values.\n\n- performs a complete depth-first exploration of the game tree.\n\n- O(b^m) time\n\n- O(b*m) space\n\nUntil game ends:\n\n- start with current position as MAX node.\n\n- expand game tree a fixed number of ply\n\n- apply eval function to leaf positions\n\n- calculate back-up values bottom up.\n\n- pick move assigned to MAX at the root\n\n- wait for min to respond.\n\n-----ALPHA-BETA PRUNING-----\n\nDuring minimax, keep track of a/b, MAX's current lower bound on MAX's outcome, & MIN's current upper obund on MIN's outcome.\n\nMAX will never allow a move leading to a worse score than a, and Min for b.\n\nStop evaluating a branch if a max node has value v>=B backed up, or a min node has v <= a. That node will never be selected\n\n- effectivemess is highly dependent on the order in which states are examined.\n\n- if this could be done perfectly, would be O(b^(m/2)) nodes. b-->sqrt(b)\n-----EXPECTIMAX SEARCH-----\n\nMax nodes like Minimax, Chance nodes instead of Min nodes-outcome is uncertain.\n\ncalculate the expected utilities of the children.\n\nas depth increases, probability of reaching a given search node shrinks.\n\n\n\n## Module 5 Definitions\n* **Concept** - definition\n* **Minimax value** - optimal utility of its children\n* **Alpha** - value of best choice found so far for MAX. think 'AT LEAST'\n* **Beta** - the value of the best choice found so far for MIN. think 'AT MOST'\n* **Stochastic games** - involves probability and skill\n* **Expectiminimax value** - For chance nodes, we compute the expected value of its children, for non changce nodes it works the same way.\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "45d4b669-51cf-468f-a53b-cb1a47e66fe2"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "CSP consists of three components: X, D, C.\\n\n",
        "- X is set of variables {X1,...,Xn}\\n\n",
        "- D is a set of domains, {D1,...,Dn} one for each Xi.\\n\n",
        "- C is a set of constraints that specify allowable combinations of values.\\n\n",
        "CSPs deal with ASSIGNMENTS of values to variables.\\n\n",
        "- An assignment that does not violate any constraints is called CONSISTENT.\\n\n",
        "An assignment in which every variable is assigned a value is called COMPLETE.\\n\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "---- ARC CONSISTENCY ----\\n\n",
        "A variable Xi is arc-consistent w.r.t Xj if for every value in domain Di, there is some value in the domain Dj that satisfies the binary constraints on the arc (Xi, Xj).\\n\n",
        "A graph is arc-consistent if every variable is arc consistent with every other variable.\\n\n",
        "EXAMPLE:\\n\n",
        "For constraint Y = X^2, where Dy = Dx = {0,1,2,3,4,5,6,7,8,9}.\\n\n",
        "First, look at X --> Y: 0,1,2, and 3 have values in Dy that can fufill the constraint, so we remove\n",
        "4,5,6,7,8, and 9 from Dx.\\n\n",
        "Next, we look at Y-->X. Only 0,1,4, and 9 have consistent values in Dx, so we remove 2,5,6,7, and 8 from Dy.\\n\n",
        "----- AC3 AlGORITHM -----\\n\n",
        "Goal is to enforce arc consistency.\\n\n",
        "Maintains a queue of arcs to consider, initially containing all arcs\\n\n",
        "Each binary constraint becomes two arcs, one in each direction.\\n\n",
        "AC3 then pops off an arbitrary arc (Xi,Xj) from the queue and maeks Xi arc consistent with respect to Xj.\\n\n",
        "IF this leaves Di unchanged: AC3 moves on to next arc.\\n\n",
        "ELSE: we add all arcs (Xk,Xi) where Xk is a neighbor of Xi. We do that because changes in Di may allow further reductions in Dk.\\n\n",
        "IF Di = {}, CSP is inconsistent, FAILURE.\\n\n",
        "ELSE: continue until there are no more arcs in the queue.\\n\n",
        "At this point we are left with a CSP equivalent to the first one, except the AC one is faster to search because variables have smaller domains.\\n\n",
        "----- PATH CONSISTENCY -----\\n\n",
        "A variable-pair {Xi,Xj} is path consistent w.r.t Xm if for every assignment {Xi=a, Xj=b} consistent with the constraints (if any) on {Xi,Xj},there is an\n",
        "assignment to Xm that satisfies the constraints on {Xi,Xm} and {Xm,Xj}. Name refers to the overall consistency of the path from Xi to Xj with Xm in the middle.\\n\n",
        "----- K-CONSISTENCY -----\\n\n",
        "stronger forms of propagation can be definied with k-consistency.\\n\n",
        "CSP is k-consistent if for any set of k-1 variables and for any consistent assignment to those variables,\n",
        "a consistent value can always be assigned to any kth variable.\\n\n",
        "One consistency says given the empty set, we can make any set of one variable consistent. This is node consistency\\n\n",
        "2-consistency is the same as arc consistency.\\n\n",
        "For binary constraint graphs, 3-consistency is the same as path consistency.\\n\n",
        "A CSP is strongly K-consistent if it is k-consistent and is also(k-1)consistent, (k-2)consistent, all the way down to node consistent.\\n\n",
        "If we have an n node CSP that is strongly n-consistent, we can guarentee solving the problem as followed:\\n\n",
        "First, chose a consistent value for X1.\\n\n",
        "We are guarenteed to be able to choose a value for X2 because the graph is 2-consistent. For X3, because its 3-consistent, and so on.\\n\n",
        "For each variable Xi we need only search through the d-values in the domain to find a value consistent with X1,...,Xi-1. The total run time is only O(n^2*d)\\n\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "----- BACKTRACKING SEARCH FOR CSP -----\\n\n",
        "sometimes we finish the constraint propagation process and still have variables with multiple possible values.\\n\n",
        "We must search for a solution.\\n\n",
        "A state would be a partial assignment, and an action would extend the assignment, adding say NSW=red or SA=blue for the australia map coloring problem.\\n\n",
        "For a CSP with n variables of domain size d, we would end up with a search tree where all the complete assignments and thus solutions are leaf nodes at depth n.\\n\n",
        "notice the branching factor at top level is nd, since any of d values can be assigned to any of n variables.\\n\n",
        "Tree has n!*d^n leaves, but only d^n possible complete assignments.\\n\n",
        "BACKTRACKING:\\n\n",
        "repeatedly chooses unassigned variable, tries all values in domain of that varialbe, trying to extend each one into a solution via a recursive call.\\n\n",
        "-----Forward checking:-----\\n\n",
        "Whenever a variable X is assigned, forward checking process establishes arc consistency for it, for each unassigned variable Y that is connected to X by a constraint, delete from Y's domain any value inconsistent with the value chosen for X.\\n\n",
        "---MAC----: maintaining arc consistency.\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "----- TREE DECOMPOSITION -----\\n\n",
        "a transformation of the original graph into a tree where each node in the tree consists of a set of variables. Must satisfy 3 requirements:\\n\n",
        "- every variable in original problem appears in at least one of the tree nodes.\\n\n",
        "- if 2 variables are connected by a constraint in the original problem, they must appear together along w/ the constraint in at least one of the tree nodes.\\n\n",
        "- if a variable appears in 2 nodes in the tree, it must appear in every node along the path connecting those nodes.\\n\n",
        "Tree width of a decomposition is one less than the size of the largest node. tree width of the graph itself is defined to be the minimum width among all its tree decompositions. If a graph has tree width w then the problem can be solved in O(nd^(w+1)) given the corresponding tree decomposition.\\n\n",
        "Hence CSPs with constraint graphs of bounded tree width are solvable in polynomial time.\\n \n",
        "The complexity of solving a CSP is strongly related to the structure of its constraint\n",
        "graph. Tree-structured problems can be solved in linear time. Cutset conditioning can\n",
        "reduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\n",
        "memory) if a small cutset can be found. Tree decomposition techniques transform the\n",
        "CSP into a tree of subproblems and are efficient if the tree width of the constraint graph\n",
        "is small; however they need memory exponential in the tree width of the constraint\n",
        "graph. Combining cutset conditioning with tree decomposition can allow a better\n",
        "tradeoff of memory versus time.\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "CSP consists of:\n",
        "- finite set of variables Xi\\n\n",
        "- nonempty domain of possible values for each value Di={v1,...,vk}\\n\n",
        "- finite constraint set {Ci}. constraints limit the values variables can take. State=assignment of values-->variables\\n\n",
        "- A consistent assignment doesnt violate constraints.\\n\n",
        "An assignment is only complete when every variable is assigned a value.\\n\n",
        "Solution is a complete, consistent assignment.\\n\n",
        "Constraint graph:\\n\n",
        "- nodes are variables, arcs are binary constraints\\n \n",
        "- graph simplifies search\\n\n",
        "Discrete variables:\\n\n",
        "- finite domains:\\n\n",
        "- - n variables, domain size d --> O(d^n) complete assignments\\n\n",
        "- infinite domains:\\n\n",
        "- - integers, strings, eg. job scheduling etc.\\n\n",
        "Continuous Varaibles:\\n\n",
        "- eg. start and end times for hubble space telescope observations. linear constraints solvable in polynomial time.\\n\n",
        "-----CSP AS SEARCH PROBLEM-----\\n\n",
        "- initial state=empty assignment {}\\n\n",
        "- successor function: assign value to unassigned variable with no constraint conflict\\n\n",
        "- goal test: current assignment=complete\\n\n",
        "- path cost: constant cost for every step.\\n\n",
        "- solution always found at depth n--Use DFS\\n\n",
        "n variables of |domain|=d. root branching factor is n*d. next level branching factor is (n-1)*d.\\n\n",
        "tree has n!*d^n leaves.\\n\n",
        "Varaible assignments are commutative--> tree search not graph search.\\n\n",
        "Only need to consider assignments one-at-a-time--> only d^n leaves.\\n\n",
        "- DFS for CSPs with single-variable assignments called backtracking.\\n\n",
        "- chooses variable values one-at-a-time, backtracks when variable has no legal values left.\\n\n",
        "-----IMPROVING BACKTRACKING EFFICIENCY-----\\n\n",
        "- general-purpose methods/heuristics improve avg. speed\\n\n",
        "example heuristics:\\n\n",
        "- Most Constrained variable(fast fail). Chose variable with fewest legal values aka MRV heuristic.\\n\n",
        "- Most Constraining variable. tie breaker among MRV. Choose variables w/ most constraints on remaining variables.\\n\n",
        "- Least constraining variable: choose the one that rules out the fewest remaining variables\\n\n",
        "- Forward Checking: store remaining legal values for unassigned variables. terminate when any unassigned variable has no remaining values.\\n\n",
        "Constraint Propagation:\\n\n",
        "- forward checking propagates info from assigned to unassigned variables. doesnt provide info for early failure detection.\\n\n",
        "- Constraint-propagation goes beyond forward-checking & repeatedly enforces constraints locally.\\n\n",
        "-----INFERENCE IN CSPs-----\\n\n",
        "Constraint Propagation(inference): eliminates possible variable values if it violates local-consistency\\n\n",
        "Local Consistency:\\n\n",
        "- node consistency: satisfies unary constraints trivially\\n\n",
        "- Arc consistency: satisfies binary constraints. Xi is arc-consistent w.r.t Xj if for every v in Dj theres a w in Dj that satisfies binary constraint on arc(i,j).\\n\n",
        "replace all undirected edges with two directed arcs (i,j) and (j,i).\\n\n",
        "simplest form of propagation makes each arc consistent. X-->Y consistent IFF for every x of X theres some allowed y.\\n\n",
        "If theres a value in tail(X) without allowable value in head(Y), we remove it from tail(X), and we must now recheck X's neighbors. \\n\n",
        "Given d values, checking arc(i,j) takes O(d^2) worst case\\n\n",
        "-----Constraint Propagation-----\\n\n",
        "by iterating over graph, arc-consistency constraints can be propagated along arcs.\\n\n",
        "search: use constraints to add labels to find one solution\\n\n",
        "constraint-propagation: use constraints to eliminate labels to find all solutions\\n\n",
        "---Waltz-Mackworth algorithm---\\n\n",
        "Assign every node all possible values\\n\n",
        "repeat until no change in values associated with any node: For every node i:\\n\n",
        "- for each neighboring node j, remove any value from i which isnt arc-consistent with j.\\n\n",
        "-----AC-3-----\\n\n",
        "- At each iteration, need only examine Xi where at least one neighbor lost a value in previous iter.\\n\n",
        "- If Xi loses a value only bc of arc-inconsistencies with Yj, dont need to check Xj next iteration.\\n\n",
        "- Removing a value on Xi can only make Yj arc-inconsistent w.r.t Xi itself, thus we need only check (j,i) still arc-consistent.\n",
        "---Worst-Case Complexity-Analysis:---\\n\n",
        "All nodes connected to every other node.\\n\n",
        "- each of n nodes must be compared against n-1 other nodes\n",
        "total @ of arcs is O(n^2).\\n\n",
        "If there are d values, checking arc(i,j) takes O(d^2)\\n\n",
        "Each arc(i,j) can only be inserted into queue d times\\n\n",
        "Worst-Case runtime = O(n^2*d^3)\\n\n",
        "For planar-constraint graphs, #arcs can only be linear in N, so complexity is O(n*d^3)\\n\n",
        "\n",
        "\"\"\"\n",
        "print(\"The length in words is\", len(module6_lecture_notes.split(' ')))\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\", \n",
        "\"unary constraint\":\"restricts value of one variable\",\n",
        "\"binary constraint\":\"relates two variables\",\n",
        "\"binary CSP\";\"CSP with only unary and binary constraints\",\n",
        "\"global constraint\":\"constraint involving an arbitrary number of variables\",\n",
        "\"constraint propagation\":\"specific type of inference; using constraints to reduce # of legal values for a variable\",\n",
        "\"local consistency\":\"when enforced, causes inconsistent values to be eliminated throughout the graph\",\n",
        "\"node consistency\":\"single variable; all values in variable's domain satisfy its unary constraints\",\n",
        "\"arc consistency\":\"every value in variable's domain satisfies binary constraints\",\n",
        "\"Path consistency\":\"tightens binary constraints by using implicit constraints inferred by looking at triples of variables\",\n",
        "\n",
        "}\n"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 584\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5f3d2500-dfb2-42e4-9373-fb3bec356333"
      },
      "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 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2fc31cf5-b9c0-41b0-9a0e-5f7744a61e68"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "T3cm1WV542_a",
        "outputId": "1e35f8dc-8712-4aad-fced-e8d79768a61b"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}