{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "b5513f46-28e7-4903-8118-41d50dad1397"
      },
      "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": 61,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "460e779b-f268-40a8-f708-0ee8067bfedc"
      },
      "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": 62,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 63,
      "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 = \"\"\" Defines the nature of environments. Fully vs. partially observable, \n",
        "single-agent vs. multiagent, deterministic vs. nondeterministic, stochastic, \n",
        "episodic vs. sequential (experience divided into atomic episode, next episode\n",
        "doesn't depend on previous episodes vs. current decision affects all future \n",
        "decisions), static vs. dynamic, discrete vs. continuous, known vs. unknown.\"\"\"\n",
        "chapter2_4 = \"\"\" Simple reflex agents selects actions on the basis of the current\n",
        "percept, ignoring the rest of the percept history; doesn't work if correct decision\n",
        "can't be made on the basis of just the current percept (not fully observable). Model\n",
        "-based reflex agents track part of the world in an internal state that depends on \n",
        "percept history; uses a transition model of the world to track how the world \n",
        "changes over time. Goal-based agents decide on what to do by considering the \n",
        "future. Utility-based agents compare different world states based on how happy \n",
        "they make the agent (utility), using a utility function. Learning agents \n",
        "use learning elements to make improvements, a performance element responsible\n",
        "for selecting external actions, a critic to tell how well the agent is doing \n",
        "wrt a fixed performance standard, and a problem generator that suggests new\n",
        "actions. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment. can't act on non-perceived\",\n",
        "\"agent function\" : \"abstract math description; maps any given percept sequence to an action\", \n",
        "\"agent program\" : \"concrete implementation of agent function\", \n",
        "\"consequentialism\" : \"evaluate an agent's behavior by its consequences\", \n",
        "\"performance measure\" : \"evaluation of any given sequence of environment states\", \n",
        "\"omniscience\" : \"when an agent knows the actual outcome of its actions + can act accordingly\", \n",
        "\"information gathering\" : \"doing actions to modify future percepts\", \n",
        "\"task environments\" : \"problems to which rational agents are the solutions\", \n",
        "\"PEAS\": \"Performance, environment, actuators, sensors\", \n",
        "\"deterministic\" : \"next state of env is determined by current state & action executed\", \n",
        "\"dynamic\" : \"if environment can change while an agent is deliberating\", \n",
        "\"sensor model\" : \"information about how the state of the world is reflected in agent's percepts\", \n",
        "\"utility function\" : \"internalization of the performance measure\", \n",
        "\"expected utility\" : \"utility the agent expects to derive, on average, given probabilities & utilities of each outcome\", \n",
        "\"atomic representation\" : \"no internal structure of each state of the world\", \n",
        "\"factored representation\" : \"splits up each state into a fixed set of variables/attributes\", \n",
        "\"structured representation\" : \"objects & their relationships described explicitly\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 64,
      "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": 1065
        },
        "cellView": "form",
        "outputId": "159e6942-7554-4b61-8d12-081eec87da21"
      },
      "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": 65,
      "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 Defines the nature of environments. Fully vs. partially observable, \nsingle-agent vs. multiagent, deterministic vs. nondeterministic, stochastic, \nepisodic vs. sequential (experience divided into atomic episode, next episode\ndoesn't depend on previous episodes vs. current decision affects all future \ndecisions), static vs. dynamic, discrete vs. continuous, known vs. unknown.\n\n## AIMA 2.4 The Structure of Agents\n Simple reflex agents selects actions on the basis of the current\npercept, ignoring the rest of the percept history; doesn't work if correct decision\ncan't be made on the basis of just the current percept (not fully observable). Model\n-based reflex agents track part of the world in an internal state that depends on \npercept history; uses a transition model of the world to track how the world \nchanges over time. Goal-based agents decide on what to do by considering the \nfuture. Utility-based agents compare different world states based on how happy \nthey make the agent (utility), using a utility function. Learning agents \nuse learning elements to make improvements, a performance element responsible\nfor selecting external actions, a critic to tell how well the agent is doing \nwrt a fixed performance standard, and a problem generator that suggests new\nactions. \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. can't act on non-perceived\n* **Agent function** - abstract math description; maps any given percept sequence to an action\n* **Agent program** - concrete implementation of agent function\n* **Consequentialism** - evaluate an agent's behavior by its consequences\n* **Performance measure** - evaluation of any given sequence of environment states\n* **Omniscience** - when an agent knows the actual outcome of its actions + can act accordingly\n* **Information gathering** - doing actions to modify future percepts\n* **Task environments** - problems to which rational agents are the solutions\n* **Peas** - Performance, environment, actuators, sensors\n* **Deterministic** - next state of env is determined by current state & action executed\n* **Dynamic** - if environment can change while an agent is deliberating\n* **Sensor model** - information about how the state of the world is reflected in agent's percepts\n* **Utility function** - internalization of the performance measure\n* **Expected utility** - utility the agent expects to derive, on average, given probabilities & utilities of each outcome\n* **Atomic representation** - no internal structure of each state of the world\n* **Factored representation** - splits up each state into a fixed set of variables/attributes\n* **Structured representation** - objects & their relationships described explicitly\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 66,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "c3a3ed95-e1b0-442d-fc0e-f1e83dc0a837"
      },
      "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": 67,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Problem solving agents use atomic representation of states. \n",
        "(Unlike planning agents, which use factored/structured) Problem solving \n",
        "process: goal formulation, problem formulation (devise description of the \n",
        "states + actions necessary to reach the goal), search for solution, execution. \n",
        "In fully observable, deterministic, known environments, solution is a fixed \n",
        "sequence of actions. Once a solution is found, agent is in an open-loop system \n",
        "(ignore percepts while executing actions). (closed-loop: agent monitors the \n",
        "percepts). Search problem needs: state space, initial/goal state(s), actions, \n",
        "transition model, action cost function. \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Problem-solving performance measures: completeness, \n",
        "cost optimality, time/space complexity (depth d: number of actions in an optimal\n",
        "solution; m: maximum number of actions in any path; b: number of successors of \n",
        "a node to consider). Best-first search expands next node with minimum value \n",
        "of some evaluation function f(n).  \"\"\"\n",
        "chapter3_4 = \"\"\" BFS: cost-optimal when all actions have the same cost; early \n",
        "goal test.  DFS: tree search. Used bc smaller needs for memory (O(bm)). \n",
        "Backtracking search memory: O(m); generates one successor at a time, successors\n",
        "modify current state description. Depth-limited search. Iterative deepening search\n",
        "is preferred when search state space larger than memory & depth of solution \n",
        "is unknown.Is optimal when actions have the same cost; saves memory at the cost\n",
        "of more time. Bidirectional search: if cost of optimal path is C*, no node with cost\n",
        "greater than C*/2 is expanded. First solution isn't necessarily optimal, best solution \n",
        "found so far is tracked & updated. Graph searches differ from tree searches: \n",
        "space and time complexities are bounded by the state space (number of vertices\n",
        "plus edges)\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\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 algorithms\" : \"agent can estimate how far it is from the goal\", \n",
        "\"state space\" : \"set of states in the world + actions that allow transitions btw spaces\", \n",
        "\"search tree\" : \"paths between states reaching towards the goal\", \n",
        "\"frontier\" : \"set of unexpanded nodes in the search tree\", \n",
        "\"FIFO queue\" : \"pops node that was added to the queue first (used in BFS)\", \n",
        "\"LIFO queue\" : \"pops node that was added to the queue last (used in DFS)\", \n",
        "\"graph search\" : \"checks for redundant paths\", \n",
        "\"tree search\" : \"doesn't check for redundant paths\", \n",
        "\"completeness\" : \"algorithm will find a solution when it exists, or reports failure\", \n",
        "\"systematic\" : \"must be able to reach any state that is connected to the initial state\", \n",
        "\"breadth-first search\" : \"for actions with same cost. expands with depth of node\", \n",
        "\"uniform cost search\" : \"actions with different costs. f(n) = summation of path cost\", \n",
        "\"depth-first search\" : \"expands deepest node on frontier first\", \n",
        "\"depth-limited search\" : \"avoid DFS infinite path; incomplete\", \n",
        "\"iterative deepening search\" : \"trying all depths until solution or returns failure instead of cutoff\", \n",
        "\"bidirectional search\" : \"track 2 frontiers & 2 tables of reached states\", \n",
        "}\n",
        "\n"
      ],
      "execution_count": 68,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 900
        },
        "outputId": "e9ee4896-9458-426a-91f8-fc2d888bd02e"
      },
      "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": 69,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem solving agents use atomic representation of states. \n(Unlike planning agents, which use factored/structured) Problem solving \nprocess: goal formulation, problem formulation (devise description of the \nstates + actions necessary to reach the goal), search for solution, execution. \nIn fully observable, deterministic, known environments, solution is a fixed \nsequence of actions. Once a solution is found, agent is in an open-loop system \n(ignore percepts while executing actions). (closed-loop: agent monitors the \npercepts). Search problem needs: state space, initial/goal state(s), actions, \ntransition model, action cost function. \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Problem-solving performance measures: completeness, \ncost optimality, time/space complexity (depth d: number of actions in an optimal\nsolution; m: maximum number of actions in any path; b: number of successors of \na node to consider). Best-first search expands next node with minimum value \nof some evaluation function f(n).  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS: cost-optimal when all actions have the same cost; early \ngoal test.  DFS: tree search. Used bc smaller needs for memory (O(bm)). \nBacktracking search memory: O(m); generates one successor at a time, successors\nmodify current state description. Depth-limited search. Iterative deepening search\nis preferred when search state space larger than memory & depth of solution \nis unknown.Is optimal when actions have the same cost; saves memory at the cost\nof more time. Bidirectional search: if cost of optimal path is C*, no node with cost\ngreater than C*/2 is expanded. First solution isn't necessarily optimal, best solution \nfound so far is tracked & updated. Graph searches differ from tree searches: \nspace and time complexities are bounded by the state space (number of vertices\nplus edges)\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* **Informed algorithms** - agent can estimate how far it is from the goal\n* **State space** - set of states in the world + actions that allow transitions btw spaces\n* **Search tree** - paths between states reaching towards the goal\n* **Frontier** - set of unexpanded nodes in the search tree\n* **Fifo queue** - pops node that was added to the queue first (used in BFS)\n* **Lifo queue** - pops node that was added to the queue last (used in DFS)\n* **Graph search** - checks for redundant paths\n* **Tree search** - doesn't check for redundant paths\n* **Completeness** - algorithm will find a solution when it exists, or reports failure\n* **Systematic** - must be able to reach any state that is connected to the initial state\n* **Breadth-first search** - for actions with same cost. expands with depth of node\n* **Uniform cost search** - actions with different costs. f(n) = summation of path cost\n* **Depth-first search** - expands deepest node on frontier first\n* **Depth-limited search** - avoid DFS infinite path; incomplete\n* **Iterative deepening search** - trying all depths until solution or returns failure instead of cutoff\n* **Bidirectional search** - track 2 frontiers & 2 tables of reached states\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 = \"\"\" Greedy best-first search: minimal h(n) value; not optimal\n",
        "but complete in finite state spaces. Not complete in infinite state spaces. \n",
        "Time + space complexity: O(|V|). A* search: minimal f(n) = g(n) + h(n); complete, \n",
        "cost-optimal if h(n) is admissible. A* is optimally efficient. Problem: nodes\n",
        "expanded can be exponential in length of solution. Satisficing solutions: \n",
        "suboptimal solutions. Weighted A* search: weigh h(n) with W > 1; focuses contour\n",
        "of reached states towards a goal, fewer states are explored..is complete! Memory bounded searches...store state on\n",
        "only frontier OR reached, remove states from reached when unneeded, eliminate \n",
        "reached table (ensure moving outwards), or keep reference counts + remove a state\n",
        "after no more ways to reach it. Beam search: either keep only k nodes with best\n",
        "f-scores (incomplete + suboptimal) or keep every node within d of the best\n",
        "f-score. IDA* : at each iteration, cutoff value is smallest f-cost of any node\n",
        "that exceeded the cutoff in the previous iteration; bad if every node has \n",
        "different f-cost. Doesn't keep all reached states in m emory at cost of \n",
        "visiting some states multiple times. RBFS: if current node exceeds f_limit, \n",
        "recursion unwinds back to alternative path. During unwinding, replace f-value \n",
        "of each node along path with best f-value of its children. Optimal if h(n)\n",
        "is admissible. SMA* : drops worst leaf to add new nodes; backs up value of \n",
        "forgotten node to parent, complete + optimal if there is any reachable, \n",
        "optimal solution. Bidirectional best-first search: f2(n) = max(2g(n), g(n)+h(n)). \n",
        "Next node expanded comes from either frontier, guarantees node never expanded\n",
        "with g(n) > C* /2. Is complete + optimal if h(n) is admissible. \"\"\"\n",
        "chapter3_6 = \"\"\" Note: N+1=1 + b* + (b* )^2 + ... + (b* )^d. Heuristics can be \n",
        "generated from relaxed problems or pattern databases. Problem databases: h(n)\n",
        "computed for each state encountered during search by looking up the configuration\n",
        "in the database. CAN'T add databases due to move overlaps, but can be combined\n",
        "by taking max values. See disjoint pattern databases (no abstracting, just\n",
        "removing.) Use landmarks to generate h(n): choose landmark points from the \n",
        "vertices, compute exact cost of optimal path from v to L and L to v. Is \n",
        "inadmissible if optimal path doesn't go through a landmark. Try differential\n",
        "heuristic: efficient and admissible; uses a landmark that is somewhere out\n",
        "beyond the goal h(n) = max(L in landmarks) of |C* (n,L)-C* (goal,L)|. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"uses domain-specific hints about the locations of goals\",\n",
        "\"heuristic function\" : \"domain hints. estimated cost of cheapest path from state at n to goal state\", \n",
        "\"consistency\" : \"triangle inequality for h(n); h(n) leq c(n,a,n') + h(n')\", \n",
        "\"optimally efficient\" : \"any alg that extends search from same initial state + h expands all nodes surely expanded by A*\", \n",
        "\"weighted A* search\" : \"satisficing search; weigh h(n) more heavily with W > 1\", \n",
        "\"bounded suboptimal search\" : \"satisficing search; solution within factor W of optimal cost\", \n",
        "\"bounded-cost search\" : \"satisficing search; solution whose cost is less than constant C\", \n",
        "\"unbounded-cost search\" : \"satisficing search; accept solution of any cost\", \n",
        "\"beam search\" : \"memory-bounded; limits size of frontier\", \n",
        "\"IDA*\" : \"memory-bounded; iterative-deepening\", \n",
        "\"recursive best-first search (RBFS)\" : \"memory-bounded; recursive DFS tracking best alt path from any ancestor of current node\", \n",
        "\"SMA*\" : \"memory-bounded; drops oldest worst leaf to add new nodes\", \n",
        "\"bidirectional heuristic search\" : \"pairs of nodes are surely expanded\", \n",
        "\"front-to-end search\" : \"estimates distance to goal/start\", \n",
        "\"front-to-front search\" : \"estimates distance to other frontier\", \n",
        "\"effective branching factor\" : \"b*, b that a uniform tree of depth d would have to contain N+1 nodes\", \n",
        "\"composite heuristic\" : \"picks whichever h'(n) is most accurate on the node; dominates component h'(n)s\", \n",
        "\"pattern database\" : \"store solution costs for every possible subproblem instance\", \n",
        "\"disjoint pattern databases\" : \"rather than abstracting parts, remove them\", \n",
        "\"metalevel state space\" : \"used to learn to search better, each state captures internal state of a program searching\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 70,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 903
        },
        "cellView": "form",
        "outputId": "5a089c89-9a1a-4825-e5a8-626389d91ad7"
      },
      "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": 71,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy best-first search: minimal h(n) value; not optimal\nbut complete in finite state spaces. Not complete in infinite state spaces. \nTime + space complexity: O(|V|). A* search: minimal f(n) = g(n) + h(n); complete, \ncost-optimal if h(n) is admissible. A* is optimally efficient. Problem: nodes\nexpanded can be exponential in length of solution. Satisficing solutions: \nsuboptimal solutions. Weighted A* search: weigh h(n) with W > 1; focuses contour\nof reached states towards a goal, fewer states are explored..is complete! Memory bounded searches...store state on\nonly frontier OR reached, remove states from reached when unneeded, eliminate \nreached table (ensure moving outwards), or keep reference counts + remove a state\nafter no more ways to reach it. Beam search: either keep only k nodes with best\nf-scores (incomplete + suboptimal) or keep every node within d of the best\nf-score. IDA* : at each iteration, cutoff value is smallest f-cost of any node\nthat exceeded the cutoff in the previous iteration; bad if every node has \ndifferent f-cost. Doesn't keep all reached states in m emory at cost of \nvisiting some states multiple times. RBFS: if current node exceeds f_limit, \nrecursion unwinds back to alternative path. During unwinding, replace f-value \nof each node along path with best f-value of its children. Optimal if h(n)\nis admissible. SMA* : drops worst leaf to add new nodes; backs up value of \nforgotten node to parent, complete + optimal if there is any reachable, \noptimal solution. Bidirectional best-first search: f2(n) = max(2g(n), g(n)+h(n)). \nNext node expanded comes from either frontier, guarantees node never expanded\nwith g(n) > C* /2. Is complete + optimal if h(n) is admissible. \n\n## AIMA Chapter 3.6 Heuristic Functions\n Note: N+1=1 + b* + (b* )^2 + ... + (b* )^d. Heuristics can be \ngenerated from relaxed problems or pattern databases. Problem databases: h(n)\ncomputed for each state encountered during search by looking up the configuration\nin the database. CAN'T add databases due to move overlaps, but can be combined\nby taking max values. See disjoint pattern databases (no abstracting, just\nremoving.) Use landmarks to generate h(n): choose landmark points from the \nvertices, compute exact cost of optimal path from v to L and L to v. Is \ninadmissible if optimal path doesn't go through a landmark. Try differential\nheuristic: efficient and admissible; uses a landmark that is somewhere out\nbeyond the goal h(n) = max(L in landmarks) of |C* (n,L)-C* (goal,L)|. \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - uses domain-specific hints about the locations of goals\n* **Heuristic function** - domain hints. estimated cost of cheapest path from state at n to goal state\n* **Consistency** - triangle inequality for h(n); h(n) leq c(n,a,n') + h(n')\n* **Optimally efficient** - any alg that extends search from same initial state + h expands all nodes surely expanded by A*\n* **Weighted a* search** - satisficing search; weigh h(n) more heavily with W > 1\n* **Bounded suboptimal search** - satisficing search; solution within factor W of optimal cost\n* **Bounded-cost search** - satisficing search; solution whose cost is less than constant C\n* **Unbounded-cost search** - satisficing search; accept solution of any cost\n* **Beam search** - memory-bounded; limits size of frontier\n* **Ida*** - memory-bounded; iterative-deepening\n* **Recursive best-first search (rbfs)** - memory-bounded; recursive DFS tracking best alt path from any ancestor of current node\n* **Sma*** - memory-bounded; drops oldest worst leaf to add new nodes\n* **Bidirectional heuristic search** - pairs of nodes are surely expanded\n* **Front-to-end search** - estimates distance to goal/start\n* **Front-to-front search** - estimates distance to other frontier\n* **Effective branching factor** - b*, b that a uniform tree of depth d would have to contain N+1 nodes\n* **Composite heuristic** - picks whichever h'(n) is most accurate on the node; dominates component h'(n)s\n* **Pattern database** - store solution costs for every possible subproblem instance\n* **Disjoint pattern databases** - rather than abstracting parts, remove them\n* **Metalevel state space** - used to learn to search better, each state captures internal state of a program searching\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 = \"\"\" Game is formally defined by: intitial state, player whose\n",
        "turn it is to move in state s, actions in state s, transition model that defines\n",
        "the state resulting from taking action a in state s, terminal test, utility \n",
        "function. Initial state, actions, result define the state space graph. A\n",
        "search tree can be superimposed over the part of the graph to determine what move\n",
        "to make. Game tree may be infinite if state space is unbounded, or if game \n",
        "allows for infinitely repeating positions. \"\"\"\n",
        "chapter5_2 = \"\"\" Minimax: tries all actions, choose the one whose resulting \n",
        "state has highest minimax value. Is a complete depth-first exploration of \n",
        "the game tree. Time complexity: O(b^m), space: O(bm) if all actions at once, \n",
        "O(m) for actions one at a time. For multiplayer games: backed-up value \n",
        "for node n is the utility vector of the successor state with the highest value\n",
        "for the player choosing at n. Alpha-beta pruning: search updates alpha/beta\n",
        "as it prunes remaining braches at a node as soon as the value of the current node\n",
        "is known to be worse than the current alpha/beta. Effectiveness depends on \n",
        "order of states examined. Best case: O(b^(m/2)) nodes examined. Best moves \n",
        "can be found using iterative deepening. Minimax doesn't work for games\n",
        "with too many states.\"\"\"\n",
        "chapter5_3 = \"\"\" If limited computation time: cut off search early, apply\n",
        "heuristic evaluation function to states. Replaces utility function. Cutoff test\n",
        "replaces terminal test. Evaluation functions: should be strongly correlated\n",
        "with the actual chances of winning. Can be a weighted linear function, sums \n",
        "over all features and weights. Cutting off search: control search to fixed\n",
        "depth limit, or apply iterative deepening w/ transposition table until time runs\n",
        "out...can lead to errors due to approximate nature of evaluation function. Consider\n",
        "quiescence search: return false for is-cutoff for nonquiescent positions; search\n",
        "continues until quiescent positions are reached. Horizon effect: delaying \n",
        "inevitable by doing moves past what player can see...combat with allowing\n",
        "singular extensions. Improving search time: forward pruning, beam search, \n",
        "probabilistic cut, late move reduction (doesn't prune moves away completely, \n",
        "just reduces the depth to which we search these moves.)\"\"\"\n",
        "chapter5_5 = \"\"\" Expectiminimax with stochastic games. Min/max/terminal \n",
        "nodes behave the same way. Chance nodes compute expected value weighted by the \n",
        "probability of each chance action. Evaluation function must return values\n",
        "that are a positive linear transformation of the probability of winning \n",
        "(or of the expected utility). Time complexity: O(b^m * n^m), n is number of \n",
        "distinct possibilites for a chance node. Alpha-beta pruning: for chance\n",
        "nodes, put bounds on the possible values of the utility function, gives\n",
        "bounds for the average w/o looking at every number.  \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Decision-theoretic agent makes rational decisions based on \n",
        "what it believes and what it wants. Probability of reachign s' by doing a \n",
        "in the current state = P(result(a) = s') = sum(over all s) of P(s)P(s' | s,a).\n",
        "Decision theory chooses among actions based on the desirability of their \n",
        "immediate outcomes - environment assumed to be episodic. \"\"\"\n",
        "chapter16_2 = \"\"\" Set of outcomes for each action is a lottery of outcomes \n",
        "with probabilities. Each outcome is either an atomic state or another lottery. \n",
        "Utility theory understands how preferences between complex lotteries\n",
        "are related to preferences between underlying states in those lotteries. \n",
        "Axioms: orderability, transitivity, continuity, suitability, monotonicity, \n",
        "decomposability. From axioms: existence of utility function (U(A) > U(B) ⇔ A ≻ B and U(A) = U(B) ⇔ A ∼ B) \n",
        "and expected utility of a lottery is the sum of the probability of each outcome * \n",
        "utility of that outcome.  \"\"\"\n",
        "chapter16_3 = \"\"\" Utility functions map from lotteries to real numbers. For\n",
        "the utility of money, utility is not proportional to monetary value. \n",
        "Risk-averse vs. risk-seeking behavior. Certainty equivalent is the value\n",
        "that an agent will accept in lieu of a lottery; insurance premium is \n",
        "the difference between an expected monetary value of a lottery and its\n",
        "certainty equivalent. Real outcomes are usually worse than expected, due to \n",
        "selecting actions with highest utility estimate, favoring overly optimistic\n",
        "estimates. More choices, more optimistic estimates. Descriptive theory (describes\n",
        " how actual agents act) are affected by certainty effect, ambiguity \n",
        " evasion, framing effect, anchoring effect.  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"fully observable\",\n",
        "\"zero-sum\" : \"what is good for one player is just as bad for the other\", \n",
        "\"terminal test\" : \"true when game is over, false otherwise\", \n",
        "\"utility function\" : \"defines final numeric value to p when game ends in terminal state s\", \n",
        "\"state space graph\" : \"vertices are states, edges are moves\", \n",
        "\"game tree\" : \"search tree that follows every sequence of moves to a terminal state\", \n",
        "\"minimax search\" : \"games with multiple outcome scores\", \n",
        "\"minimax value\" : \"utility of being in a state, assuming both players play perfectly\", \n",
        "\"alpha-beta pruning\" : \"not checking parts of tree that make no difference to the outcome\", \n",
        "\"transpositions\" : \"can cause repeated states in game tree search; different permutations of move sequence\", \n",
        "\"transposition table\" : \"catches heuristic value of states\", \n",
        "\"Type A strategy\" : \"wide but shallow, all moves to a certain depth\", \n",
        "\"Type B strategy\" : \"deep but narrow, follows promising lines as far as possible\", \n",
        "\"evaluation function\" : \"for heuristic a-b search; replaces utility function for estimate of expected utility\", \n",
        "\"quiescent position\" : \"position in which there is no pending move that would swing the evaluation\", \n",
        "\"horizon effect\" : \"delaying the inevitable by doing moves past what player can see\", \n",
        "\"singular extensions\" : \"moves that are clearly better than all other moves in a given position\", \n",
        "\"forward pruning\" : \"prunes moves that appear to be poor moves\", \n",
        "\"beam search\" : \"only consider a beam of the n best moves\", \n",
        "\"PROBCUT\" : \"prunes nodes that are probably outside the (alpha, beta) window\", \n",
        "\"late move reduction\" : \"move ordering done well, so moves that appear later are less likely to be good ones\",\n",
        "\"policy\" : \"mapping from every possible state to the best move in that state\", \n",
        "\"stochastic games\" : \"includes a random element\", \n",
        "\"expected values\" : \"average over all possible outcomes of the chance nodes\", \n",
        "\"utility function U(s)\" : \"agent's preferences, assigns a single number to a state\", \n",
        "\"expected utility EU(a)\" : \"average utility value of the outcomes, weighted by prob that outcome occurs\", \n",
        "\"maximum expected utility (MEU)\" : \"rational agent should choose action that maximizes agent's EU\", \n",
        "\"orderability\" : \"Exactly one of (A ≻ B), (B ≻ A), or (A ∼ B) holds\", \n",
        "\"transitivity\" : \"(A ≻ B)∧(B ≻ C) ⇒ (A ≻ C)\", \n",
        "\"continuity\" : \"A ≻ B ≻ C ⇒ ∃ p [p,A; 1− p,C] ∼ B\",\n",
        "\"suitability\" : \"A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B; 1− p,C]\", \n",
        "\"monotonicity\" : \"A ≻ B ⇒ (p > q ⇔ [p,A; 1− p,B] ≻ [q,A; 1−q,B])\", \n",
        "\"decomposability\" : \"[p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C]\", \n",
        "\"preference elicitation\" : \"understanding a human's utility function\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 72,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1626
        },
        "outputId": "ac7cf142-10ad-49ab-da18-02882df1b20e"
      },
      "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": 73,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Game is formally defined by: intitial state, player whose\nturn it is to move in state s, actions in state s, transition model that defines\nthe state resulting from taking action a in state s, terminal test, utility \nfunction. Initial state, actions, result define the state space graph. A\nsearch tree can be superimposed over the part of the graph to determine what move\nto make. Game tree may be infinite if state space is unbounded, or if game \nallows for infinitely repeating positions. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax: tries all actions, choose the one whose resulting \nstate has highest minimax value. Is a complete depth-first exploration of \nthe game tree. Time complexity: O(b^m), space: O(bm) if all actions at once, \nO(m) for actions one at a time. For multiplayer games: backed-up value \nfor node n is the utility vector of the successor state with the highest value\nfor the player choosing at n. Alpha-beta pruning: search updates alpha/beta\nas it prunes remaining braches at a node as soon as the value of the current node\nis known to be worse than the current alpha/beta. Effectiveness depends on \norder of states examined. Best case: O(b^(m/2)) nodes examined. Best moves \ncan be found using iterative deepening. Minimax doesn't work for games\nwith too many states.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n If limited computation time: cut off search early, apply\nheuristic evaluation function to states. Replaces utility function. Cutoff test\nreplaces terminal test. Evaluation functions: should be strongly correlated\nwith the actual chances of winning. Can be a weighted linear function, sums \nover all features and weights. Cutting off search: control search to fixed\ndepth limit, or apply iterative deepening w/ transposition table until time runs\nout...can lead to errors due to approximate nature of evaluation function. Consider\nquiescence search: return false for is-cutoff for nonquiescent positions; search\ncontinues until quiescent positions are reached. Horizon effect: delaying \ninevitable by doing moves past what player can see...combat with allowing\nsingular extensions. Improving search time: forward pruning, beam search, \nprobabilistic cut, late move reduction (doesn't prune moves away completely, \njust reduces the depth to which we search these moves.)\n\n## AIMA Chapter 5.5 Stochastic Games\n Expectiminimax with stochastic games. Min/max/terminal \nnodes behave the same way. Chance nodes compute expected value weighted by the \nprobability of each chance action. Evaluation function must return values\nthat are a positive linear transformation of the probability of winning \n(or of the expected utility). Time complexity: O(b^m * n^m), n is number of \ndistinct possibilites for a chance node. Alpha-beta pruning: for chance\nnodes, put bounds on the possible values of the utility function, gives\nbounds for the average w/o looking at every number.  \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision-theoretic agent makes rational decisions based on \nwhat it believes and what it wants. Probability of reachign s' by doing a \nin the current state = P(result(a) = s') = sum(over all s) of P(s)P(s' | s,a).\nDecision theory chooses among actions based on the desirability of their \nimmediate outcomes - environment assumed to be episodic. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Set of outcomes for each action is a lottery of outcomes \nwith probabilities. Each outcome is either an atomic state or another lottery. \nUtility theory understands how preferences between complex lotteries\nare related to preferences between underlying states in those lotteries. \nAxioms: orderability, transitivity, continuity, suitability, monotonicity, \ndecomposability. From axioms: existence of utility function (U(A) > U(B) ⇔ A ≻ B and U(A) = U(B) ⇔ A ∼ B) \nand expected utility of a lottery is the sum of the probability of each outcome * \nutility of that outcome.  \n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions map from lotteries to real numbers. For\nthe utility of money, utility is not proportional to monetary value. \nRisk-averse vs. risk-seeking behavior. Certainty equivalent is the value\nthat an agent will accept in lieu of a lottery; insurance premium is \nthe difference between an expected monetary value of a lottery and its\ncertainty equivalent. Real outcomes are usually worse than expected, due to \nselecting actions with highest utility estimate, favoring overly optimistic\nestimates. More choices, more optimistic estimates. Descriptive theory (describes\n how actual agents act) are affected by certainty effect, ambiguity \n evasion, framing effect, anchoring effect.  \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Zero-sum** - what is good for one player is just as bad for the other\n* **Terminal test** - true when game is over, false otherwise\n* **Utility function** - defines final numeric value to p when game ends in terminal state s\n* **State space graph** - vertices are states, edges are moves\n* **Game tree** - search tree that follows every sequence of moves to a terminal state\n* **Minimax search** - games with multiple outcome scores\n* **Minimax value** - utility of being in a state, assuming both players play perfectly\n* **Alpha-beta pruning** - not checking parts of tree that make no difference to the outcome\n* **Transpositions** - can cause repeated states in game tree search; different permutations of move sequence\n* **Transposition table** - catches heuristic value of states\n* **Type a strategy** - wide but shallow, all moves to a certain depth\n* **Type b strategy** - deep but narrow, follows promising lines as far as possible\n* **Evaluation function** - for heuristic a-b search; replaces utility function for estimate of expected utility\n* **Quiescent position** - position in which there is no pending move that would swing the evaluation\n* **Horizon effect** - delaying the inevitable by doing moves past what player can see\n* **Singular extensions** - moves that are clearly better than all other moves in a given position\n* **Forward pruning** - prunes moves that appear to be poor moves\n* **Beam search** - only consider a beam of the n best moves\n* **Probcut** - prunes nodes that are probably outside the (alpha, beta) window\n* **Late move reduction** - move ordering done well, so moves that appear later are less likely to be good ones\n* **Policy** - mapping from every possible state to the best move in that state\n* **Stochastic games** - includes a random element\n* **Expected values** - average over all possible outcomes of the chance nodes\n* **Utility function u(s)** - agent's preferences, assigns a single number to a state\n* **Expected utility eu(a)** - average utility value of the outcomes, weighted by prob that outcome occurs\n* **Maximum expected utility (meu)** - rational agent should choose action that maximizes agent's EU\n* **Orderability** - Exactly one of (A ≻ B), (B ≻ A), or (A ∼ B) holds\n* **Transitivity** - (A ≻ B)∧(B ≻ C) ⇒ (A ≻ C)\n* **Continuity** - A ≻ B ≻ C ⇒ ∃ p [p,A; 1− p,C] ∼ B\n* **Suitability** - A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B; 1− p,C]\n* **Monotonicity** - A ≻ B ⇒ (p > q ⇔ [p,A; 1− p,B] ≻ [q,A; 1−q,B])\n* **Decomposability** - [p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C]\n* **Preference elicitation** - understanding a human's utility function\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" CSP is solved when each variable has a value that satisfies\n",
        "all constraints on the variable. Uses general rather than domain-specific\n",
        "heuristics. Consists of three components: set of variables, set of domains, \n",
        "set of constraints. Solution is a complete, consistent assignment. \"\"\"\n",
        "chapter6_2 = \"\"\" Constraint propagation key idea: maintaining k-consistency. \n",
        "k-consistent: if for any set of k-1 variables and for any consistent assignment \n",
        "to those variables, a consistent value can always be assigned to any kth \n",
        "variable. Strongly k-consistent assigning takes O(n^2*d). Global constraints \n",
        "special-purpose algorithms: Alldiff (values > num variables), resource \n",
        "constraint (atmost constraint), bound propagation, bounds-consistent. \"\"\"\n",
        "chapter6_3 = \"\"\" CSP solutions are commutative. Consider a single variable at \n",
        "each node in the search tree - d^n total nodes. Backtracking search: (chronological\n",
        "backtracking: most recent point is revisited) backtrack to previous state if \n",
        "a variable has no valid values to be assigned. Domain-independent heuristics: \n",
        "MRV, degree, least constraining value. Forward checking: establish arc-consistency\n",
        "for X when X is assigned. MAC: after Xi assigned a value, AC-3 using queue\n",
        "with the arcs (Xj, Xi) for unassigned Xj neighboring variables. If AC-3 fails, \n",
        "backtrack. For intelligent backtracking: backtrack to something that might\n",
        "fix the problem. Conflict set: set of variables that result in a conflict\n",
        "for another variable. Backjumping method: backtracks to most recent assignment\n",
        "in the conflict set; redundant in forward-checking or stronger consistency\n",
        "checking search. Conflict-directed backjumping: uses conflict set of the \n",
        "set of preceding variables that caused a variable, together with any \n",
        "subsequent variables, to have no consistent solution. These sets are made by \n",
        "having variables absorb conflict sets when backjumping. Constraint learning: \n",
        "finding a min set of variables from conflict set that causes the problem. \n",
        "Stored as no-good (set of variables and their corresponding values).  \"\"\"\n",
        "chapter6_4 = \"\"\" complete-state formulation: each state assigns a value\n",
        "to every variable; search changes the value of one variable at a time. Select\n",
        "values that result in the minimum number of conflict with other variables (min-\n",
        "conflicts heuristic). Plateau search: allowing sideways moves to another state\n",
        "with the same score, directed with tabu search: keeping a small list of recently\n",
        "visited states, forbidding the algorithm to return to those states. Constraint\n",
        "weighting: concentrates search on the important constraints. At each step \n",
        "of search, alg chooses variable/value pair that results in the lowest total weight \n",
        "of all violated constraints; weights of each constraint violated is incremented. \n",
        "Difficult constraints are assigned higher weights.  \"\"\"\n",
        "chapter6_5 = \"\"\" Independence of subproblems found by finding connected \n",
        "components of a constraint graph. Total work: O(d^c * n/c) where each \n",
        "subproblem has c variables, total of n variables, d is size of domain. n/c \n",
        "subproblems, each with d^c work to solve. Tree constraint graphs: any 2 \n",
        "variables are connected by only one path. Tree-structured CSP can be solved in \n",
        "linear time to the number of variables. To solve: topologically sort tree; \n",
        "make sorted graph DAC by going right to left; go down list of vars, choose \n",
        "any remaining value. Reducing CSPs to trees: cutset conditioning (time: O(d^c * (n-c)d^2))\n",
        "if favoring memory (linear), tree decomp if favoring time. Tree decomp: must satisfy\n",
        "each var in original problem appears in at least one tree node, if 2 vars\n",
        "are connected by constraint, they must appear together with constraint\n",
        "in at least one tree node, if var appears in 2 nodes in the tree, it must\n",
        "appear in every node along the path connecting those nodes. Time: O(nd^(w+1)) \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Constraint satisfaction problem\" : \"factored representation. assigns values to variables\",\n",
        "\"consistent\" : \"doesn't violate any constraints\", \n",
        "\"complete\" : \"every variable is assigned a value\", \n",
        "\"partial assignment\" : \"leaves some variables unassigned\", \n",
        "\"partial solution\" : \"partial assignment that is consistent\", \n",
        "\"constraint graph\" : \"nodes are variables, edges connect variables that participate in a constraint\", \n",
        "\"precedence constraints\" : \"T1 + dt <= T2\", \n",
        "\"disjunctive constraint\" : \"two things must not overlap in time; either one or the other first\", \n",
        "\"global constraint\" : \"constraint involving an arbitrary number of variables\", \n",
        "\"constraint hypergraph\" : \"ordinary nodes and hypernodes that represent n-ary constraints\", \n",
        "\"constrained optimization problem (COP)\" : \"CSPs with preference constraints\", \n",
        "\"constraint propagation\" : \"uses constraints to reduce the number of legal values of a variable\", \n",
        "\"AC-3\" : \"algorithm for enforcing arc consistency; time: O(cd^3)\", \n",
        "\"MRV (min remaining values) heuristic\" : \"choosing variable; with fewest legal values\", \n",
        "\"degree heuristic\" : \"choosing variable; involved with the largest number of constraints on other unassigned vars\", \n",
        "\"LCV heuristic\" : \"choosing a value; prefer value that rules out the least choices for neighbors\", \n",
        "\"conflict set\" : \"set of variables that result in a conflict for another variable\", \n",
        "\"backjumping  method\" : \"backtracks to most recent assignment in conflict set\", \n",
        "\"constraint learning\" : \"finding a min set of variables from the conflict set that causes the problem\", \n",
        "\"directional arc consistency\" : \"under an ordering of variables X1, ..., DAC iff every Xi is arc-consistent with each Xj for j>i\", \n",
        "\"cutset conditioning\" : \"choose a subset of CSP's variables st constraint graph becomes tree after subset removal\", \n",
        "\"tree decomposition\" : \"transformation of the original graph into a tree of subproblems\", \n",
        "\"tree width\" : \"size of largest node - 1; of graph: min width among all tree decomps\", \n",
        "\"value symmetry\" : \"break using symmetry-breaking constraint\"\n",
        "}\n"
      ],
      "execution_count": 74,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1255
        },
        "outputId": "ce26fea1-9582-4dd5-f273-210b00377854"
      },
      "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": 75,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP is solved when each variable has a value that satisfies\nall constraints on the variable. Uses general rather than domain-specific\nheuristics. Consists of three components: set of variables, set of domains, \nset of constraints. Solution is a complete, consistent assignment. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint propagation key idea: maintaining k-consistency. \nk-consistent: if for any set of k-1 variables and for any consistent assignment \nto those variables, a consistent value can always be assigned to any kth \nvariable. Strongly k-consistent assigning takes O(n^2*d). Global constraints \nspecial-purpose algorithms: Alldiff (values > num variables), resource \nconstraint (atmost constraint), bound propagation, bounds-consistent. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n CSP solutions are commutative. Consider a single variable at \neach node in the search tree - d^n total nodes. Backtracking search: (chronological\nbacktracking: most recent point is revisited) backtrack to previous state if \na variable has no valid values to be assigned. Domain-independent heuristics: \nMRV, degree, least constraining value. Forward checking: establish arc-consistency\nfor X when X is assigned. MAC: after Xi assigned a value, AC-3 using queue\nwith the arcs (Xj, Xi) for unassigned Xj neighboring variables. If AC-3 fails, \nbacktrack. For intelligent backtracking: backtrack to something that might\nfix the problem. Conflict set: set of variables that result in a conflict\nfor another variable. Backjumping method: backtracks to most recent assignment\nin the conflict set; redundant in forward-checking or stronger consistency\nchecking search. Conflict-directed backjumping: uses conflict set of the \nset of preceding variables that caused a variable, together with any \nsubsequent variables, to have no consistent solution. These sets are made by \nhaving variables absorb conflict sets when backjumping. Constraint learning: \nfinding a min set of variables from conflict set that causes the problem. \nStored as no-good (set of variables and their corresponding values).  \n\n## AIMA Chapter 6.4 Local Search for CSPs\n complete-state formulation: each state assigns a value\nto every variable; search changes the value of one variable at a time. Select\nvalues that result in the minimum number of conflict with other variables (min-\nconflicts heuristic). Plateau search: allowing sideways moves to another state\nwith the same score, directed with tabu search: keeping a small list of recently\nvisited states, forbidding the algorithm to return to those states. Constraint\nweighting: concentrates search on the important constraints. At each step \nof search, alg chooses variable/value pair that results in the lowest total weight \nof all violated constraints; weights of each constraint violated is incremented. \nDifficult constraints are assigned higher weights.  \n\n## AIMA Chapter 6.5 The Structure of Problems\n Independence of subproblems found by finding connected \ncomponents of a constraint graph. Total work: O(d^c * n/c) where each \nsubproblem has c variables, total of n variables, d is size of domain. n/c \nsubproblems, each with d^c work to solve. Tree constraint graphs: any 2 \nvariables are connected by only one path. Tree-structured CSP can be solved in \nlinear time to the number of variables. To solve: topologically sort tree; \nmake sorted graph DAC by going right to left; go down list of vars, choose \nany remaining value. Reducing CSPs to trees: cutset conditioning (time: O(d^c * (n-c)d^2))\nif favoring memory (linear), tree decomp if favoring time. Tree decomp: must satisfy\neach var in original problem appears in at least one tree node, if 2 vars\nare connected by constraint, they must appear together with constraint\nin at least one tree node, if var appears in 2 nodes in the tree, it must\nappear in every node along the path connecting those nodes. Time: O(nd^(w+1)) \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Constraint satisfaction problem** - factored representation. assigns values to variables\n* **Consistent** - doesn't violate any constraints\n* **Complete** - every variable is assigned a value\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - partial assignment that is consistent\n* **Constraint graph** - nodes are variables, edges connect variables that participate in a constraint\n* **Precedence constraints** - T1 + dt <= T2\n* **Disjunctive constraint** - two things must not overlap in time; either one or the other first\n* **Global constraint** - constraint involving an arbitrary number of variables\n* **Constraint hypergraph** - ordinary nodes and hypernodes that represent n-ary constraints\n* **Constrained optimization problem (cop)** - CSPs with preference constraints\n* **Constraint propagation** - uses constraints to reduce the number of legal values of a variable\n* **Ac-3** - algorithm for enforcing arc consistency; time: O(cd^3)\n* **Mrv (min remaining values) heuristic** - choosing variable; with fewest legal values\n* **Degree heuristic** - choosing variable; involved with the largest number of constraints on other unassigned vars\n* **Lcv heuristic** - choosing a value; prefer value that rules out the least choices for neighbors\n* **Conflict set** - set of variables that result in a conflict for another variable\n* **Backjumping  method** - backtracks to most recent assignment in conflict set\n* **Constraint learning** - finding a min set of variables from the conflict set that causes the problem\n* **Directional arc consistency** - under an ordering of variables X1, ..., DAC iff every Xi is arc-consistent with each Xj for j>i\n* **Cutset conditioning** - choose a subset of CSP's variables st constraint graph becomes tree after subset removal\n* **Tree decomposition** - transformation of the original graph into a tree of subproblems\n* **Tree width** - size of largest node - 1; of graph: min width among all tree decomps\n* **Value symmetry** - break using symmetry-breaking constraint\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 = \"\"\" If a sentence a is true in model m, m satisfies a/m is a model\n",
        "of a. a entails (|=) b: a is a stronger assertion than b. We're looking for \n",
        "sentences that the KB entails. KB |-ia: a is derived from KB by inference\n",
        "algorithm i. Grounding: KB isn't always true in the real world due to general \n",
        "rules. \"\"\"\n",
        "chapter7_4 = \"\"\" Every known inference algorithm for prop logic has worst-case\n",
        "complexity that is exponential in the size of the input. Model checking approach\n",
        "is sound and complete. Algorithm is like backtracking search: recursive\n",
        "enumeration of a finite space of assignments to symbols. Time complexity: O(2^n), \n",
        "since 2^n models exist for n symbols. Space complexity: O(n) - depth-first \"\"\"\n",
        "chapter7_5 = \"\"\" Proof can ignore irrelevant propositions. For satisfiability: \n",
        "(α ⊨ β if and only if the sentence (α∧ ¬β) is unsatisfiable). Resolution yields\n",
        "a complete inference method when coupled with any complete search algorithm. \n",
        "Note!! You can only resolve one pair of complementary literals at a time. The\n",
        "resulting clause should contain only one copy of each literal. Sentence\n",
        "to CNF: eliminate biconditional; eliminate implication; move not inwards (CNF\n",
        "requires not to only appear in literals), De Morgan; distributivity law \n",
        "to get a clause. Resolution algorithm: proof by contradiction; show that \n",
        "(KB∧ ¬α) is unsatisfiable. Convert to CNF; apply resolution rule to resulting \n",
        "clauses; continue until no new clauses (KB doesn't entail a) or two clauses\n",
        "resolve to yield the empty clause (KB does entail a). Any clause with 2 complementary \n",
        "literals can be discarded. Definite clauses can be written as an implication\n",
        "whose premise: conjunction of positive literals, conclusion: single positive\n",
        "literal. Forward chaining is data-driven reasoning, backward chaining is\n",
        "goal-directed reasoning. Both run in linear time. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base\" : \"set of sentences that represent some assertion about the world\", \n",
        "\"axiom\" : \"sentence that's given, not derived\", \n",
        "\"declarative approach\" : \"to system building. TELL KB-agent what it needs to know\", \n",
        "\"procedural approach\" : \"encodes desired behaviors directly as program code\", \n",
        "\"syntax\" : \"specifies all sentences that are well formed\", \n",
        "\"semantics\" : \"meaning of sentences. defines truth of each sentence wrt each possible world\", \n",
        "\"entailment\" : \"a sentence follows logically from another sentence\", \n",
        "\"logical inference\" : \"derive conclusions using entailment\", \n",
        "\"model checking\" : \"enumerate all possible models to check that a is true in all models in which KB is true\", \n",
        "\"sound\" : \"an inference algorithm that derives only entailed sentences\", \n",
        "\"complete\" : \"an inference algorithm that can derive any sentence that is entailed\", \n",
        "\"grounding\" : \"connection between logical reasoning processes & the real environment\", \n",
        "\"^\" : \"and; conjunction\", \n",
        "\"v\" : \"or; disjunction\", \n",
        "\"implies\" : \"P implies Q only false when P true, Q false\", \n",
        "\"biconditional\" : \"true if both true or both false\", \n",
        "\"validity\" : \"a sentence if it is true in all models; tautologies = valid sentences\", \n",
        "\"deduction theorem\" : \"α ⊨ β if and only if the sentence (α ⇒ β) is valid\", \n",
        "\"satisfiability\" : \"a sentence if it is true in, or satisfied by, some model\", \n",
        "\"monotonicity\" : \"a set of entailed sentences can only increase as info is added to the KB\", \n",
        "\"Modus ponens\" : \"α ⇒ β, α gives β\", \n",
        "\"And elimination\" : \"α∧β gives α\", \n",
        "\"resolution\" : \"resolving complementary literals\", \n",
        "\"clause\" : \"disjunction of literals\", \n",
        "\"factoring\" : \"removal of multiple copies of literals\", \n",
        "\"conjunctive normal form (CNF)\" : \"sentence expressed as a conjunction of clauses\", \n",
        "\"resolution closure RC(S)\" : \"of a set of clauses S. set of all clauses derivable by resolution rule to clauses in S\", \n",
        "\"ground resolution theorem\" : \"completeness for resolution. if clauses unsatisfiable, RC(S) contains empty clause\", \n",
        "\"definite clause\" : \"disjunction of literals, exaclty one is positive\", \n",
        "\"Horn clause\" : \"disjunction of literals, at msot one is positive. deciding entailment linear in size of KB\", \n",
        "\"goal clause\" : \"disjunction of literals, no positives\", \n",
        "\"forward chaining\" : \"determines if q is entailed by KB of definite clauses\", \n",
        "\"backward chaining\" : \"same as forward; works backward from query q\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 76,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1238
        },
        "outputId": "dba58f24-4516-4bf8-e847-7eb1f6a8d41c"
      },
      "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": 77,
      "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 If a sentence a is true in model m, m satisfies a/m is a model\nof a. a entails (|=) b: a is a stronger assertion than b. We're looking for \nsentences that the KB entails. KB |-ia: a is derived from KB by inference\nalgorithm i. Grounding: KB isn't always true in the real world due to general \nrules. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Every known inference algorithm for prop logic has worst-case\ncomplexity that is exponential in the size of the input. Model checking approach\nis sound and complete. Algorithm is like backtracking search: recursive\nenumeration of a finite space of assignments to symbols. Time complexity: O(2^n), \nsince 2^n models exist for n symbols. Space complexity: O(n) - depth-first \n\n## AIMA 7.5 Propositional Theorem Proving\n Proof can ignore irrelevant propositions. For satisfiability: \n(α ⊨ β if and only if the sentence (α∧ ¬β) is unsatisfiable). Resolution yields\na complete inference method when coupled with any complete search algorithm. \nNote!! You can only resolve one pair of complementary literals at a time. The\nresulting clause should contain only one copy of each literal. Sentence\nto CNF: eliminate biconditional; eliminate implication; move not inwards (CNF\nrequires not to only appear in literals), De Morgan; distributivity law \nto get a clause. Resolution algorithm: proof by contradiction; show that \n(KB∧ ¬α) is unsatisfiable. Convert to CNF; apply resolution rule to resulting \nclauses; continue until no new clauses (KB doesn't entail a) or two clauses\nresolve to yield the empty clause (KB does entail a). Any clause with 2 complementary \nliterals can be discarded. Definite clauses can be written as an implication\nwhose premise: conjunction of positive literals, conclusion: single positive\nliteral. Forward chaining is data-driven reasoning, backward chaining is\ngoal-directed reasoning. Both run in linear time. \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge base** - set of sentences that represent some assertion about the world\n* **Axiom** - sentence that's given, not derived\n* **Declarative approach** - to system building. TELL KB-agent what it needs to know\n* **Procedural approach** - encodes desired behaviors directly as program code\n* **Syntax** - specifies all sentences that are well formed\n* **Semantics** - meaning of sentences. defines truth of each sentence wrt each possible world\n* **Entailment** - a sentence follows logically from another sentence\n* **Logical inference** - derive conclusions using entailment\n* **Model checking** - enumerate all possible models to check that a is true in all models in which KB is true\n* **Sound** - an inference algorithm that derives only entailed sentences\n* **Complete** - an inference algorithm that can derive any sentence that is entailed\n* **Grounding** - connection between logical reasoning processes & the real environment\n* **^** - and; conjunction\n* **V** - or; disjunction\n* **Implies** - P implies Q only false when P true, Q false\n* **Biconditional** - true if both true or both false\n* **Validity** - a sentence if it is true in all models; tautologies = valid sentences\n* **Deduction theorem** - α ⊨ β if and only if the sentence (α ⇒ β) is valid\n* **Satisfiability** - a sentence if it is true in, or satisfied by, some model\n* **Monotonicity** - a set of entailed sentences can only increase as info is added to the KB\n* **Modus ponens** - α ⇒ β, α gives β\n* **And elimination** - α∧β gives α\n* **Resolution** - resolving complementary literals\n* **Clause** - disjunction of literals\n* **Factoring** - removal of multiple copies of literals\n* **Conjunctive normal form (cnf)** - sentence expressed as a conjunction of clauses\n* **Resolution closure rc(s)** - of a set of clauses S. set of all clauses derivable by resolution rule to clauses in S\n* **Ground resolution theorem** - completeness for resolution. if clauses unsatisfiable, RC(S) contains empty clause\n* **Definite clause** - disjunction of literals, exaclty one is positive\n* **Horn clause** - disjunction of literals, at msot one is positive. deciding entailment linear in size of KB\n* **Goal clause** - disjunction of literals, no positives\n* **Forward chaining** - determines if q is entailed by KB of definite clauses\n* **Backward chaining** - same as forward; works backward from query q\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 7058
        },
        "id": "T3cm1WV542_a",
        "outputId": "36b27ffe-905f-4277-c57f-baaede5c3b18"
      },
      "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": 78,
      "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 Defines the nature of environments. Fully vs. partially observable, \nsingle-agent vs. multiagent, deterministic vs. nondeterministic, stochastic, \nepisodic vs. sequential (experience divided into atomic episode, next episode\ndoesn't depend on previous episodes vs. current decision affects all future \ndecisions), static vs. dynamic, discrete vs. continuous, known vs. unknown.\n\n## AIMA 2.4 The Structure of Agents\n Simple reflex agents selects actions on the basis of the current\npercept, ignoring the rest of the percept history; doesn't work if correct decision\ncan't be made on the basis of just the current percept (not fully observable). Model\n-based reflex agents track part of the world in an internal state that depends on \npercept history; uses a transition model of the world to track how the world \nchanges over time. Goal-based agents decide on what to do by considering the \nfuture. Utility-based agents compare different world states based on how happy \nthey make the agent (utility), using a utility function. Learning agents \nuse learning elements to make improvements, a performance element responsible\nfor selecting external actions, a critic to tell how well the agent is doing \nwrt a fixed performance standard, and a problem generator that suggests new\nactions. \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. can't act on non-perceived\n* **Agent function** - abstract math description; maps any given percept sequence to an action\n* **Agent program** - concrete implementation of agent function\n* **Consequentialism** - evaluate an agent's behavior by its consequences\n* **Performance measure** - evaluation of any given sequence of environment states\n* **Omniscience** - when an agent knows the actual outcome of its actions + can act accordingly\n* **Information gathering** - doing actions to modify future percepts\n* **Task environments** - problems to which rational agents are the solutions\n* **Peas** - Performance, environment, actuators, sensors\n* **Deterministic** - next state of env is determined by current state & action executed\n* **Dynamic** - if environment can change while an agent is deliberating\n* **Sensor model** - information about how the state of the world is reflected in agent's percepts\n* **Utility function** - internalization of the performance measure\n* **Expected utility** - utility the agent expects to derive, on average, given probabilities & utilities of each outcome\n* **Atomic representation** - no internal structure of each state of the world\n* **Factored representation** - splits up each state into a fixed set of variables/attributes\n* **Structured representation** - objects & their relationships described explicitly\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 Problem solving agents use atomic representation of states. \n(Unlike planning agents, which use factored/structured) Problem solving \nprocess: goal formulation, problem formulation (devise description of the \nstates + actions necessary to reach the goal), search for solution, execution. \nIn fully observable, deterministic, known environments, solution is a fixed \nsequence of actions. Once a solution is found, agent is in an open-loop system \n(ignore percepts while executing actions). (closed-loop: agent monitors the \npercepts). Search problem needs: state space, initial/goal state(s), actions, \ntransition model, action cost function. \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Problem-solving performance measures: completeness, \ncost optimality, time/space complexity (depth d: number of actions in an optimal\nsolution; m: maximum number of actions in any path; b: number of successors of \na node to consider). Best-first search expands next node with minimum value \nof some evaluation function f(n).  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS: cost-optimal when all actions have the same cost; early \ngoal test.  DFS: tree search. Used bc smaller needs for memory (O(bm)). \nBacktracking search memory: O(m); generates one successor at a time, successors\nmodify current state description. Depth-limited search. Iterative deepening search\nis preferred when search state space larger than memory & depth of solution \nis unknown.Is optimal when actions have the same cost; saves memory at the cost\nof more time. Bidirectional search: if cost of optimal path is C*, no node with cost\ngreater than C*/2 is expanded. First solution isn't necessarily optimal, best solution \nfound so far is tracked & updated. Graph searches differ from tree searches: \nspace and time complexities are bounded by the state space (number of vertices\nplus edges)\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* **Informed algorithms** - agent can estimate how far it is from the goal\n* **State space** - set of states in the world + actions that allow transitions btw spaces\n* **Search tree** - paths between states reaching towards the goal\n* **Frontier** - set of unexpanded nodes in the search tree\n* **Fifo queue** - pops node that was added to the queue first (used in BFS)\n* **Lifo queue** - pops node that was added to the queue last (used in DFS)\n* **Graph search** - checks for redundant paths\n* **Tree search** - doesn't check for redundant paths\n* **Completeness** - algorithm will find a solution when it exists, or reports failure\n* **Systematic** - must be able to reach any state that is connected to the initial state\n* **Breadth-first search** - for actions with same cost. expands with depth of node\n* **Uniform cost search** - actions with different costs. f(n) = summation of path cost\n* **Depth-first search** - expands deepest node on frontier first\n* **Depth-limited search** - avoid DFS infinite path; incomplete\n* **Iterative deepening search** - trying all depths until solution or returns failure instead of cutoff\n* **Bidirectional search** - track 2 frontiers & 2 tables of reached states\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy best-first search: minimal h(n) value; not optimal\nbut complete in finite state spaces. Not complete in infinite state spaces. \nTime + space complexity: O(|V|). A* search: minimal f(n) = g(n) + h(n); complete, \ncost-optimal if h(n) is admissible. A* is optimally efficient. Problem: nodes\nexpanded can be exponential in length of solution. Satisficing solutions: \nsuboptimal solutions. Weighted A* search: weigh h(n) with W > 1; focuses contour\nof reached states towards a goal, fewer states are explored..is complete! Memory bounded searches...store state on\nonly frontier OR reached, remove states from reached when unneeded, eliminate \nreached table (ensure moving outwards), or keep reference counts + remove a state\nafter no more ways to reach it. Beam search: either keep only k nodes with best\nf-scores (incomplete + suboptimal) or keep every node within d of the best\nf-score. IDA* : at each iteration, cutoff value is smallest f-cost of any node\nthat exceeded the cutoff in the previous iteration; bad if every node has \ndifferent f-cost. Doesn't keep all reached states in m emory at cost of \nvisiting some states multiple times. RBFS: if current node exceeds f_limit, \nrecursion unwinds back to alternative path. During unwinding, replace f-value \nof each node along path with best f-value of its children. Optimal if h(n)\nis admissible. SMA* : drops worst leaf to add new nodes; backs up value of \nforgotten node to parent, complete + optimal if there is any reachable, \noptimal solution. Bidirectional best-first search: f2(n) = max(2g(n), g(n)+h(n)). \nNext node expanded comes from either frontier, guarantees node never expanded\nwith g(n) > C* /2. Is complete + optimal if h(n) is admissible. \n\n## AIMA Chapter 3.6 Heuristic Functions\n Note: N+1=1 + b* + (b* )^2 + ... + (b* )^d. Heuristics can be \ngenerated from relaxed problems or pattern databases. Problem databases: h(n)\ncomputed for each state encountered during search by looking up the configuration\nin the database. CAN'T add databases due to move overlaps, but can be combined\nby taking max values. See disjoint pattern databases (no abstracting, just\nremoving.) Use landmarks to generate h(n): choose landmark points from the \nvertices, compute exact cost of optimal path from v to L and L to v. Is \ninadmissible if optimal path doesn't go through a landmark. Try differential\nheuristic: efficient and admissible; uses a landmark that is somewhere out\nbeyond the goal h(n) = max(L in landmarks) of |C* (n,L)-C* (goal,L)|. \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - uses domain-specific hints about the locations of goals\n* **Heuristic function** - domain hints. estimated cost of cheapest path from state at n to goal state\n* **Consistency** - triangle inequality for h(n); h(n) leq c(n,a,n') + h(n')\n* **Optimally efficient** - any alg that extends search from same initial state + h expands all nodes surely expanded by A*\n* **Weighted a* search** - satisficing search; weigh h(n) more heavily with W > 1\n* **Bounded suboptimal search** - satisficing search; solution within factor W of optimal cost\n* **Bounded-cost search** - satisficing search; solution whose cost is less than constant C\n* **Unbounded-cost search** - satisficing search; accept solution of any cost\n* **Beam search** - memory-bounded; limits size of frontier\n* **Ida*** - memory-bounded; iterative-deepening\n* **Recursive best-first search (rbfs)** - memory-bounded; recursive DFS tracking best alt path from any ancestor of current node\n* **Sma*** - memory-bounded; drops oldest worst leaf to add new nodes\n* **Bidirectional heuristic search** - pairs of nodes are surely expanded\n* **Front-to-end search** - estimates distance to goal/start\n* **Front-to-front search** - estimates distance to other frontier\n* **Effective branching factor** - b*, b that a uniform tree of depth d would have to contain N+1 nodes\n* **Composite heuristic** - picks whichever h'(n) is most accurate on the node; dominates component h'(n)s\n* **Pattern database** - store solution costs for every possible subproblem instance\n* **Disjoint pattern databases** - rather than abstracting parts, remove them\n* **Metalevel state space** - used to learn to search better, each state captures internal state of a program searching\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Game is formally defined by: intitial state, player whose\nturn it is to move in state s, actions in state s, transition model that defines\nthe state resulting from taking action a in state s, terminal test, utility \nfunction. Initial state, actions, result define the state space graph. A\nsearch tree can be superimposed over the part of the graph to determine what move\nto make. Game tree may be infinite if state space is unbounded, or if game \nallows for infinitely repeating positions. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax: tries all actions, choose the one whose resulting \nstate has highest minimax value. Is a complete depth-first exploration of \nthe game tree. Time complexity: O(b^m), space: O(bm) if all actions at once, \nO(m) for actions one at a time. For multiplayer games: backed-up value \nfor node n is the utility vector of the successor state with the highest value\nfor the player choosing at n. Alpha-beta pruning: search updates alpha/beta\nas it prunes remaining braches at a node as soon as the value of the current node\nis known to be worse than the current alpha/beta. Effectiveness depends on \norder of states examined. Best case: O(b^(m/2)) nodes examined. Best moves \ncan be found using iterative deepening. Minimax doesn't work for games\nwith too many states.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n If limited computation time: cut off search early, apply\nheuristic evaluation function to states. Replaces utility function. Cutoff test\nreplaces terminal test. Evaluation functions: should be strongly correlated\nwith the actual chances of winning. Can be a weighted linear function, sums \nover all features and weights. Cutting off search: control search to fixed\ndepth limit, or apply iterative deepening w/ transposition table until time runs\nout...can lead to errors due to approximate nature of evaluation function. Consider\nquiescence search: return false for is-cutoff for nonquiescent positions; search\ncontinues until quiescent positions are reached. Horizon effect: delaying \ninevitable by doing moves past what player can see...combat with allowing\nsingular extensions. Improving search time: forward pruning, beam search, \nprobabilistic cut, late move reduction (doesn't prune moves away completely, \njust reduces the depth to which we search these moves.)\n\n## AIMA Chapter 5.5 Stochastic Games\n Expectiminimax with stochastic games. Min/max/terminal \nnodes behave the same way. Chance nodes compute expected value weighted by the \nprobability of each chance action. Evaluation function must return values\nthat are a positive linear transformation of the probability of winning \n(or of the expected utility). Time complexity: O(b^m * n^m), n is number of \ndistinct possibilites for a chance node. Alpha-beta pruning: for chance\nnodes, put bounds on the possible values of the utility function, gives\nbounds for the average w/o looking at every number.  \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision-theoretic agent makes rational decisions based on \nwhat it believes and what it wants. Probability of reachign s' by doing a \nin the current state = P(result(a) = s') = sum(over all s) of P(s)P(s' | s,a).\nDecision theory chooses among actions based on the desirability of their \nimmediate outcomes - environment assumed to be episodic. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Set of outcomes for each action is a lottery of outcomes \nwith probabilities. Each outcome is either an atomic state or another lottery. \nUtility theory understands how preferences between complex lotteries\nare related to preferences between underlying states in those lotteries. \nAxioms: orderability, transitivity, continuity, suitability, monotonicity, \ndecomposability. From axioms: existence of utility function (U(A) > U(B) ⇔ A ≻ B and U(A) = U(B) ⇔ A ∼ B) \nand expected utility of a lottery is the sum of the probability of each outcome * \nutility of that outcome.  \n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions map from lotteries to real numbers. For\nthe utility of money, utility is not proportional to monetary value. \nRisk-averse vs. risk-seeking behavior. Certainty equivalent is the value\nthat an agent will accept in lieu of a lottery; insurance premium is \nthe difference between an expected monetary value of a lottery and its\ncertainty equivalent. Real outcomes are usually worse than expected, due to \nselecting actions with highest utility estimate, favoring overly optimistic\nestimates. More choices, more optimistic estimates. Descriptive theory (describes\n how actual agents act) are affected by certainty effect, ambiguity \n evasion, framing effect, anchoring effect.  \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Zero-sum** - what is good for one player is just as bad for the other\n* **Terminal test** - true when game is over, false otherwise\n* **Utility function** - defines final numeric value to p when game ends in terminal state s\n* **State space graph** - vertices are states, edges are moves\n* **Game tree** - search tree that follows every sequence of moves to a terminal state\n* **Minimax search** - games with multiple outcome scores\n* **Minimax value** - utility of being in a state, assuming both players play perfectly\n* **Alpha-beta pruning** - not checking parts of tree that make no difference to the outcome\n* **Transpositions** - can cause repeated states in game tree search; different permutations of move sequence\n* **Transposition table** - catches heuristic value of states\n* **Type a strategy** - wide but shallow, all moves to a certain depth\n* **Type b strategy** - deep but narrow, follows promising lines as far as possible\n* **Evaluation function** - for heuristic a-b search; replaces utility function for estimate of expected utility\n* **Quiescent position** - position in which there is no pending move that would swing the evaluation\n* **Horizon effect** - delaying the inevitable by doing moves past what player can see\n* **Singular extensions** - moves that are clearly better than all other moves in a given position\n* **Forward pruning** - prunes moves that appear to be poor moves\n* **Beam search** - only consider a beam of the n best moves\n* **Probcut** - prunes nodes that are probably outside the (alpha, beta) window\n* **Late move reduction** - move ordering done well, so moves that appear later are less likely to be good ones\n* **Policy** - mapping from every possible state to the best move in that state\n* **Stochastic games** - includes a random element\n* **Expected values** - average over all possible outcomes of the chance nodes\n* **Utility function u(s)** - agent's preferences, assigns a single number to a state\n* **Expected utility eu(a)** - average utility value of the outcomes, weighted by prob that outcome occurs\n* **Maximum expected utility (meu)** - rational agent should choose action that maximizes agent's EU\n* **Orderability** - Exactly one of (A ≻ B), (B ≻ A), or (A ∼ B) holds\n* **Transitivity** - (A ≻ B)∧(B ≻ C) ⇒ (A ≻ C)\n* **Continuity** - A ≻ B ≻ C ⇒ ∃ p [p,A; 1− p,C] ∼ B\n* **Suitability** - A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B; 1− p,C]\n* **Monotonicity** - A ≻ B ⇒ (p > q ⇔ [p,A; 1− p,B] ≻ [q,A; 1−q,B])\n* **Decomposability** - [p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C]\n* **Preference elicitation** - understanding a human's utility function\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP is solved when each variable has a value that satisfies\nall constraints on the variable. Uses general rather than domain-specific\nheuristics. Consists of three components: set of variables, set of domains, \nset of constraints. Solution is a complete, consistent assignment. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint propagation key idea: maintaining k-consistency. \nk-consistent: if for any set of k-1 variables and for any consistent assignment \nto those variables, a consistent value can always be assigned to any kth \nvariable. Strongly k-consistent assigning takes O(n^2*d). Global constraints \nspecial-purpose algorithms: Alldiff (values > num variables), resource \nconstraint (atmost constraint), bound propagation, bounds-consistent. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n CSP solutions are commutative. Consider a single variable at \neach node in the search tree - d^n total nodes. Backtracking search: (chronological\nbacktracking: most recent point is revisited) backtrack to previous state if \na variable has no valid values to be assigned. Domain-independent heuristics: \nMRV, degree, least constraining value. Forward checking: establish arc-consistency\nfor X when X is assigned. MAC: after Xi assigned a value, AC-3 using queue\nwith the arcs (Xj, Xi) for unassigned Xj neighboring variables. If AC-3 fails, \nbacktrack. For intelligent backtracking: backtrack to something that might\nfix the problem. Conflict set: set of variables that result in a conflict\nfor another variable. Backjumping method: backtracks to most recent assignment\nin the conflict set; redundant in forward-checking or stronger consistency\nchecking search. Conflict-directed backjumping: uses conflict set of the \nset of preceding variables that caused a variable, together with any \nsubsequent variables, to have no consistent solution. These sets are made by \nhaving variables absorb conflict sets when backjumping. Constraint learning: \nfinding a min set of variables from conflict set that causes the problem. \nStored as no-good (set of variables and their corresponding values).  \n\n## AIMA Chapter 6.4 Local Search for CSPs\n complete-state formulation: each state assigns a value\nto every variable; search changes the value of one variable at a time. Select\nvalues that result in the minimum number of conflict with other variables (min-\nconflicts heuristic). Plateau search: allowing sideways moves to another state\nwith the same score, directed with tabu search: keeping a small list of recently\nvisited states, forbidding the algorithm to return to those states. Constraint\nweighting: concentrates search on the important constraints. At each step \nof search, alg chooses variable/value pair that results in the lowest total weight \nof all violated constraints; weights of each constraint violated is incremented. \nDifficult constraints are assigned higher weights.  \n\n## AIMA Chapter 6.5 The Structure of Problems\n Independence of subproblems found by finding connected \ncomponents of a constraint graph. Total work: O(d^c * n/c) where each \nsubproblem has c variables, total of n variables, d is size of domain. n/c \nsubproblems, each with d^c work to solve. Tree constraint graphs: any 2 \nvariables are connected by only one path. Tree-structured CSP can be solved in \nlinear time to the number of variables. To solve: topologically sort tree; \nmake sorted graph DAC by going right to left; go down list of vars, choose \nany remaining value. Reducing CSPs to trees: cutset conditioning (time: O(d^c * (n-c)d^2))\nif favoring memory (linear), tree decomp if favoring time. Tree decomp: must satisfy\neach var in original problem appears in at least one tree node, if 2 vars\nare connected by constraint, they must appear together with constraint\nin at least one tree node, if var appears in 2 nodes in the tree, it must\nappear in every node along the path connecting those nodes. Time: O(nd^(w+1)) \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Constraint satisfaction problem** - factored representation. assigns values to variables\n* **Consistent** - doesn't violate any constraints\n* **Complete** - every variable is assigned a value\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - partial assignment that is consistent\n* **Constraint graph** - nodes are variables, edges connect variables that participate in a constraint\n* **Precedence constraints** - T1 + dt <= T2\n* **Disjunctive constraint** - two things must not overlap in time; either one or the other first\n* **Global constraint** - constraint involving an arbitrary number of variables\n* **Constraint hypergraph** - ordinary nodes and hypernodes that represent n-ary constraints\n* **Constrained optimization problem (cop)** - CSPs with preference constraints\n* **Constraint propagation** - uses constraints to reduce the number of legal values of a variable\n* **Ac-3** - algorithm for enforcing arc consistency; time: O(cd^3)\n* **Mrv (min remaining values) heuristic** - choosing variable; with fewest legal values\n* **Degree heuristic** - choosing variable; involved with the largest number of constraints on other unassigned vars\n* **Lcv heuristic** - choosing a value; prefer value that rules out the least choices for neighbors\n* **Conflict set** - set of variables that result in a conflict for another variable\n* **Backjumping  method** - backtracks to most recent assignment in conflict set\n* **Constraint learning** - finding a min set of variables from the conflict set that causes the problem\n* **Directional arc consistency** - under an ordering of variables X1, ..., DAC iff every Xi is arc-consistent with each Xj for j>i\n* **Cutset conditioning** - choose a subset of CSP's variables st constraint graph becomes tree after subset removal\n* **Tree decomposition** - transformation of the original graph into a tree of subproblems\n* **Tree width** - size of largest node - 1; of graph: min width among all tree decomps\n* **Value symmetry** - break using symmetry-breaking constraint\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 If a sentence a is true in model m, m satisfies a/m is a model\nof a. a entails (|=) b: a is a stronger assertion than b. We're looking for \nsentences that the KB entails. KB |-ia: a is derived from KB by inference\nalgorithm i. Grounding: KB isn't always true in the real world due to general \nrules. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Every known inference algorithm for prop logic has worst-case\ncomplexity that is exponential in the size of the input. Model checking approach\nis sound and complete. Algorithm is like backtracking search: recursive\nenumeration of a finite space of assignments to symbols. Time complexity: O(2^n), \nsince 2^n models exist for n symbols. Space complexity: O(n) - depth-first \n\n## AIMA 7.5 Propositional Theorem Proving\n Proof can ignore irrelevant propositions. For satisfiability: \n(α ⊨ β if and only if the sentence (α∧ ¬β) is unsatisfiable). Resolution yields\na complete inference method when coupled with any complete search algorithm. \nNote!! You can only resolve one pair of complementary literals at a time. The\nresulting clause should contain only one copy of each literal. Sentence\nto CNF: eliminate biconditional; eliminate implication; move not inwards (CNF\nrequires not to only appear in literals), De Morgan; distributivity law \nto get a clause. Resolution algorithm: proof by contradiction; show that \n(KB∧ ¬α) is unsatisfiable. Convert to CNF; apply resolution rule to resulting \nclauses; continue until no new clauses (KB doesn't entail a) or two clauses\nresolve to yield the empty clause (KB does entail a). Any clause with 2 complementary \nliterals can be discarded. Definite clauses can be written as an implication\nwhose premise: conjunction of positive literals, conclusion: single positive\nliteral. Forward chaining is data-driven reasoning, backward chaining is\ngoal-directed reasoning. Both run in linear time. \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge base** - set of sentences that represent some assertion about the world\n* **Axiom** - sentence that's given, not derived\n* **Declarative approach** - to system building. TELL KB-agent what it needs to know\n* **Procedural approach** - encodes desired behaviors directly as program code\n* **Syntax** - specifies all sentences that are well formed\n* **Semantics** - meaning of sentences. defines truth of each sentence wrt each possible world\n* **Entailment** - a sentence follows logically from another sentence\n* **Logical inference** - derive conclusions using entailment\n* **Model checking** - enumerate all possible models to check that a is true in all models in which KB is true\n* **Sound** - an inference algorithm that derives only entailed sentences\n* **Complete** - an inference algorithm that can derive any sentence that is entailed\n* **Grounding** - connection between logical reasoning processes & the real environment\n* **^** - and; conjunction\n* **V** - or; disjunction\n* **Implies** - P implies Q only false when P true, Q false\n* **Biconditional** - true if both true or both false\n* **Validity** - a sentence if it is true in all models; tautologies = valid sentences\n* **Deduction theorem** - α ⊨ β if and only if the sentence (α ⇒ β) is valid\n* **Satisfiability** - a sentence if it is true in, or satisfied by, some model\n* **Monotonicity** - a set of entailed sentences can only increase as info is added to the KB\n* **Modus ponens** - α ⇒ β, α gives β\n* **And elimination** - α∧β gives α\n* **Resolution** - resolving complementary literals\n* **Clause** - disjunction of literals\n* **Factoring** - removal of multiple copies of literals\n* **Conjunctive normal form (cnf)** - sentence expressed as a conjunction of clauses\n* **Resolution closure rc(s)** - of a set of clauses S. set of all clauses derivable by resolution rule to clauses in S\n* **Ground resolution theorem** - completeness for resolution. if clauses unsatisfiable, RC(S) contains empty clause\n* **Definite clause** - disjunction of literals, exaclty one is positive\n* **Horn clause** - disjunction of literals, at msot one is positive. deciding entailment linear in size of KB\n* **Goal clause** - disjunction of literals, no positives\n* **Forward chaining** - determines if q is entailed by KB of definite clauses\n* **Backward chaining** - same as forward; works backward from query q\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}