{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521 midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "eda045fe-f40a-4bd7-dee8-a00303c02bc9"
      },
      "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": 89,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6e4979cd-c757-43a8-db42-fe63a373d027"
      },
      "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": 90,
      "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": 91,
      "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 = \"\"\"\n",
        "An agernt's choice of action depends on its built-in konwledge and \\\n",
        "on its percept sequence (history), but not anything it hasn't perceived.\\n\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "Rationality depnds on performance measure, agent's prior knowledge, set of actions, percept sequence.\\n\n",
        "Rational agent should select an action that is expected to maximize its performance measure, \\\n",
        "given the evidence provided by its percept sequence and its built-in knowledge.\\n\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "A rational agent is also autonomous - learning what it can to compensate for partial or incorrect prior knowledge.\\n\n",
        "A task environment includes performance measure, environment, actuators, and sensors (PEAS).\\n\n",
        "Properties of task environment:\n",
        "- fully vs partial observable\n",
        "- single vs multi agent\n",
        "- deterministic vs stochastic (probabilitistic)\n",
        "- episodic (actions are independent) vs sequential\n",
        "- static vs dynamic (environment changes while agent is deliberating)\n",
        "- discrete vs continuous time\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "Agent problems take current percept as input from sensors and return an action to actuators.\\n\n",
        "Model-based agents use transition model and sensor model to keep track of the state of the world.\\n\n",
        "Goal-based agents keeps track of the world and choose actions that achieve the goal.\\n\n",
        "Utility-based agents choose actions that maximize its expected utility (internalization of performance measure)\\\n",
        "which is calculated as the weighted average over all possible outcome states.\\n\n",
        "3 ways to represent states and transitions:\n",
        "- atomic: each state of the world is indivisible (no internal structure)\n",
        "- factored: each state is split up into variables/attributes which can have a value\n",
        "- structured: each state includes objects which may have its own attributes and relationships to other objects\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive through sensors and act in an environment through actuators\",\n",
        "\"agent function\": \"specifies action taken by the agent in response to any pecept sequence\",\n",
        "\"consequentialism\": \"evaluate an agent's behavior by its consequences\",\n",
        "\"fully observable\": \"agent has access to the complete environment state at each point in time\",\n",
        "\"intelligent entities\": \"machines that compute how to act effectively and safely\",\n",
        "\"learning element\": \"uses feedback from critic on how the agent is doing then make improvements\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"performance measure\": \"evaluates behavior of agent in an environment\",\n",
        "\"problem generator\": \"suggests actions that will lead to new and informative experiences\",\n",
        "\"rational agent\": \"acts to achieve the best (expected) performance measure\",\n",
        "\"simple reflex agent\": \"agents that select actions based on current percept\",\n",
        "\"strong AI\": \"actually thinking\",\n",
        "\"transition model\": \"knowledge about how the world changes over time\",\n",
        "\"sensor model\": \"info about the state of the world reflected in agent's percepts\",\n",
        "\"vague alignment problem\": \"the values or objectives put into the machine are aligned with those of the human\",\n",
        "\"weak AI\": \"simulate thinking\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 92,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "83898ee5-45e4-4728-84a0-996f3b13fcb2"
      },
      "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": 93,
      "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\nAn agernt's choice of action depends on its built-in konwledge and on its percept sequence (history), but not anything it hasn't perceived.\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nRationality depnds on performance measure, agent's prior knowledge, set of actions, percept sequence.\n\nRational agent should select an action that is expected to maximize its performance measure, given the evidence provided by its percept sequence and its built-in knowledge.\n\n\n\n## AIMA 2.3 The Nature of Environments\n\nA rational agent is also autonomous - learning what it can to compensate for partial or incorrect prior knowledge.\n\nA task environment includes performance measure, environment, actuators, and sensors (PEAS).\n\nProperties of task environment:\n- fully vs partial observable\n- single vs multi agent\n- deterministic vs stochastic (probabilitistic)\n- episodic (actions are independent) vs sequential\n- static vs dynamic (environment changes while agent is deliberating)\n- discrete vs continuous time\n\n\n## AIMA 2.4 The Structure of Agents\n\nAgent problems take current percept as input from sensors and return an action to actuators.\n\nModel-based agents use transition model and sensor model to keep track of the state of the world.\n\nGoal-based agents keeps track of the world and choose actions that achieve the goal.\n\nUtility-based agents choose actions that maximize its expected utility (internalization of performance measure)which is calculated as the weighted average over all possible outcome states.\n\n3 ways to represent states and transitions:\n- atomic: each state of the world is indivisible (no internal structure)\n- factored: each state is split up into variables/attributes which can have a value\n- structured: each state includes objects which may have its own attributes and relationships to other objects\n\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act in an environment through actuators\n* **Agent function** - specifies action taken by the agent in response to any pecept sequence\n* **Consequentialism** - evaluate an agent's behavior by its consequences\n* **Fully observable** - agent has access to the complete environment state at each point in time\n* **Intelligent entities** - machines that compute how to act effectively and safely\n* **Learning element** - uses feedback from critic on how the agent is doing then make improvements\n* **Percept** - your definitions here\n* **Performance measure** - evaluates behavior of agent in an environment\n* **Problem generator** - suggests actions that will lead to new and informative experiences\n* **Rational agent** - acts to achieve the best (expected) performance measure\n* **Simple reflex agent** - agents that select actions based on current percept\n* **Strong ai** - actually thinking\n* **Transition model** - knowledge about how the world changes over time\n* **Sensor model** - info about the state of the world reflected in agent's percepts\n* **Vague alignment problem** - the values or objectives put into the machine are aligned with those of the human\n* **Weak ai** - simulate thinking\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "Python delinates a code blocks with a clon and indentation.\\n\n",
        "All data treated as objects and is deleted once unreachable.\\n\n",
        "Python is strong but dynamic typing (drawback being that type errors are only caught at runtime).\\n\n",
        "Slicing returns a copy of a subsequence.\\n\n",
        "Common list operations: append, insert, index, count, remove, reverse, sort, sorted...\\n\n",
        "Common string operations: split, join, upper...\\n\n",
        "Common dict methods: keys, values, items...\\n\n",
        "No function overloading but operator overloading is possible.\\n\n",
        "Arguments to functions become optional if they have default values, should be preceded by non-default args.\\n\n",
        "Keyword arguments can appear in any order but positional args need to precede keyword args.\\n\n",
        "Function argument ordering: positional, *args, **kwargs.\\n\n",
        "Functions are first-class objects.\\n\n",
        "Extended subclass allows use of methods and attributes from the super class. Multiple inheritance is supported.\\n\n",
        "To redefine a method of the parent class, give a new definition using the same name in the subclass.\\n\n",
        "Iteratable objects have an __iter__ magic which turn them into iterator objects, so can be used in loops.\\n\n",
        "Iterators work with iterator objects and has a __next__ magic method, throws Stopiteration exception at the end.\\n\n",
        "Iterators use memory more efficiently than iterable objects themselves.\\n\n",
        "Benefits of generators: values are computed as needed, avoids storing entire sequence in memory, good for aggregating items, crucial for infinite sequences.\\n\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"*args\": \"a tuple of positional arguments passed to the function; need to be dereferenced\",\n",
        "\"**kwargs\": \"a dict of the keyword args passed to the function; dereferenced twice\",\n",
        "\"Counter\": \"from collections, count # of occurrences as values\",\n",
        "\"defaultdict\": \"from collections, automatically initializes nonexistent values\",\n",
        "\"dictionary\": \"unordered, immutable keys, O(1) time, values can be mixed type, no reverse lookup\",\n",
        "\"duck typing\": \"establishes suitability of an object by determining presence of methods\",\n",
        "\"first class object\": \"can be dynamically created, destroyed, passed, returned, has rights as variables\",\n",
        "\"generators\": \"iterators created with YIELD keyword; returns yielded value then resumes where it left off\",\n",
        "\"list\": \"mutable, ordered, mixed types\",\n",
        "\"list comprehension\": \"[expression for name in list if filter]\",\n",
        "\"magic methods\": \"allow user-defined classes to behave like built in types (init, len, copy, cmp, add, neg, str, name, main...)\",\n",
        "\"mutability\" : \"whether a variable can be changed; if not need to reassign after making change\",\n",
        "\"REPL\": \"read-evaluate-print loop\",\n",
        "\"string\": \"immutable, Unicode, each char is 2 bytes\",\n",
        "\"tuple\": \"immutable, ordered, mixed types\"\n",
        "}"
      ],
      "execution_count": 94,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 830
        },
        "outputId": "d41dcebc-f520-4ad1-8ee7-430d90e4a3f8"
      },
      "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": 95,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nPython delinates a code blocks with a clon and indentation.\n\nAll data treated as objects and is deleted once unreachable.\n\nPython is strong but dynamic typing (drawback being that type errors are only caught at runtime).\n\nSlicing returns a copy of a subsequence.\n\nCommon list operations: append, insert, index, count, remove, reverse, sort, sorted...\n\nCommon string operations: split, join, upper...\n\nCommon dict methods: keys, values, items...\n\nNo function overloading but operator overloading is possible.\n\nArguments to functions become optional if they have default values, should be preceded by non-default args.\n\nKeyword arguments can appear in any order but positional args need to precede keyword args.\n\nFunction argument ordering: positional, *args, **kwargs.\n\nFunctions are first-class objects.\n\nExtended subclass allows use of methods and attributes from the super class. Multiple inheritance is supported.\n\nTo redefine a method of the parent class, give a new definition using the same name in the subclass.\n\nIteratable objects have an __iter__ magic which turn them into iterator objects, so can be used in loops.\n\nIterators work with iterator objects and has a __next__ magic method, throws Stopiteration exception at the end.\n\nIterators use memory more efficiently than iterable objects themselves.\n\nBenefits of generators: values are computed as needed, avoids storing entire sequence in memory, good for aggregating items, crucial for infinite sequences.\n\n\n\n## Module 2 Definitions\n* ***args** - a tuple of positional arguments passed to the function; need to be dereferenced\n* ****kwargs** - a dict of the keyword args passed to the function; dereferenced twice\n* **Counter** - from collections, count # of occurrences as values\n* **Defaultdict** - from collections, automatically initializes nonexistent values\n* **Dictionary** - unordered, immutable keys, O(1) time, values can be mixed type, no reverse lookup\n* **Duck typing** - establishes suitability of an object by determining presence of methods\n* **First class object** - can be dynamically created, destroyed, passed, returned, has rights as variables\n* **Generators** - iterators created with YIELD keyword; returns yielded value then resumes where it left off\n* **List** - mutable, ordered, mixed types\n* **List comprehension** - [expression for name in list if filter]\n* **Magic methods** - allow user-defined classes to behave like built in types (init, len, copy, cmp, add, neg, str, name, main...)\n* **Mutability** - whether a variable can be changed; if not need to reassign after making change\n* **Repl** - read-evaluate-print loop\n* **String** - immutable, Unicode, each char is 2 bytes\n* **Tuple** - immutable, ordered, mixed types\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "Components of search problem: state space, initial state, goal states, actions, transition model, path cost function (additive).\\n\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "A search algorithm takes a search problem as input and returns a solution.\\n\n",
        "Node -> state, edges -> actions\\n\n",
        "Search algorithms are judged based on: completeness, cost optimality, time complexity, space complexity.\\n\n",
        "Complexities are measured in depth (d, number of actions), maximum numbers of actions in any path (m), and branching factor (b, number of successors).\\n\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "In BFS, we apply early goal test, checking whether a node is a solution as soon as generated. Use FIFO frontier.\\n\n",
        "In uniform cost search (Dijkstra), we use a priority queue to expand the node with the lowest actual path cost. \\\n",
        "we apply late goal test, checking for goals when node is expanded.\\n\n",
        "DFS expands the deepest node (go to the deepest level of the tree then backup). \\\n",
        "Uses LIFO frontier and returns the first solution it finds. More efficient on space.\\n\n",
        "Depth limited search prevents DFS going down infinite path by supplying a depth limit and treat all \\\n",
        "nodes at depth l as if they have no successors. However, need to be careful with choice of l to not make it incomplete.\\n\n",
        "Iterative Deepening search uses depth limited search as subroutine, with increasing l.\\n\n",
        "IDDFS is the preferred uninformed search method when the search state space is larger than can fit \\\n",
        "in memory and the depth of the solution is unknown.\\n\n",
        "Bidirectional search simultaneously searches from the initial state and backwards from the goal state \\\n",
        "by keeping track of 2 frontiers and 2 tables of reached states. \\\n",
        "The node with the minimum value of the eval fn across either frontier is expanded next.\\n\n",
        "\n",
        "| Criterion | BFS      | UCS               | DFS      | Depth-Limited | Iterative Deepening | Bidirectional |\n",
        "| --------- | :---:    | :---:             | :---:    |:-------------:|:-------------------:|:-------------:|\n",
        "| Complete? | Yes      | Yes               | No       | No            | Yes                 | Yes           |\n",
        "| Optimal?  | Yes      | Yes               | No       | No            | Yes                 | Yes           |\n",
        "| Time?     | $O(b^d)$ | $O(b^(1+[C*/e]))$ | $O(b^m)$ | $O(b^l)$      | $O(b^d)$            | $O(b^(d/2))$  |\n",
        "| Space?    | $O(b^d)$ | $O(b^(1+[C*/e]))$ | $O(bm)$  | $O(bl)$       | $O(bd)$             | $O(b^(d/2))$  |\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "We can use search if the task environment is fully observable, deterministic and known.\\n\n",
        "Abstration helps keep search space under control, and should be easier than the real problem.\\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"action cost function\": \"numeric cost of applying action a in state s to reach state s'\",\n",
        "\"best-first search\": \"expand the node with the minimum value of some eval function; uses priority queue\",\n",
        "\"frontier\": \"states that are available for expanding; grows the search tree\",\n",
        "\"graph search\": \"checks for redundant path, stores visited states so requires more space\",\n",
        "\"informed search\": \"has access to both problem definition and some heuristics function\",\n",
        "\"optimal solution\": \"has lowest path cost among all solutions\",\n",
        "\"node\": \"a data structure consisting of parent, children, depth, path cost\",\n",
        "\"path\": \"a sequence of actions leading from one state to another\",\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "\"search tree\": \"represents paths in a search algo as a tree where the root is the initial state, leaves are successor states\",\n",
        "\"solution\": \"a path from initial state to goal state\",\n",
        "\"standardized problem\": \"intended to illustrate or exercise various problem-solving methods\",\n",
        "\"state space\": \"set of all states reachable from the initial state by any sequence of actions\",\n",
        "\"uninformed search\": \"has access to problem definition only\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 96,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6662ed1f-a453-45e2-b101-a5e26ce3dfd9"
      },
      "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": 97,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nComponents of search problem: state space, initial state, goal states, actions, transition model, path cost function (additive).\n\n\n\n## AIMA Chapter 3.2 Example Problems\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nA search algorithm takes a search problem as input and returns a solution.\n\nNode -> state, edges -> actions\n\nSearch algorithms are judged based on: completeness, cost optimality, time complexity, space complexity.\n\nComplexities are measured in depth (d, number of actions), maximum numbers of actions in any path (m), and branching factor (b, number of successors).\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nIn BFS, we apply early goal test, checking whether a node is a solution as soon as generated. Use FIFO frontier.\n\nIn uniform cost search (Dijkstra), we use a priority queue to expand the node with the lowest actual path cost. we apply late goal test, checking for goals when node is expanded.\n\nDFS expands the deepest node (go to the deepest level of the tree then backup). Uses LIFO frontier and returns the first solution it finds. More efficient on space.\n\nDepth limited search prevents DFS going down infinite path by supplying a depth limit and treat all nodes at depth l as if they have no successors. However, need to be careful with choice of l to not make it incomplete.\n\nIterative Deepening search uses depth limited search as subroutine, with increasing l.\n\nIDDFS is the preferred uninformed search method when the search state space is larger than can fit in memory and the depth of the solution is unknown.\n\nBidirectional search simultaneously searches from the initial state and backwards from the goal state by keeping track of 2 frontiers and 2 tables of reached states. The node with the minimum value of the eval fn across either frontier is expanded next.\n\n\n| Criterion | BFS      | UCS               | DFS      | Depth-Limited | Iterative Deepening | Bidirectional |\n| --------- | :---:    | :---:             | :---:    |:-------------:|:-------------------:|:-------------:|\n| Complete? | Yes      | Yes               | No       | No            | Yes                 | Yes           |\n| Optimal?  | Yes      | Yes               | No       | No            | Yes                 | Yes           |\n| Time?     | $O(b^d)$ | $O(b^(1+[C*/e]))$ | $O(b^m)$ | $O(b^l)$      | $O(b^d)$            | $O(b^(d/2))$  |\n| Space?    | $O(b^d)$ | $O(b^(1+[C*/e]))$ | $O(bm)$  | $O(bl)$       | $O(bd)$             | $O(b^(d/2))$  |\n\n\n## Module 3 Lecture Notes\n\nWe can use search if the task environment is fully observable, deterministic and known.\n\nAbstration helps keep search space under control, and should be easier than the real problem.\n\n\n\n\n## Module 3 Definitions\n* **Action cost function** - numeric cost of applying action a in state s to reach state s'\n* **Best-first search** - expand the node with the minimum value of some eval function; uses priority queue\n* **Frontier** - states that are available for expanding; grows the search tree\n* **Graph search** - checks for redundant path, stores visited states so requires more space\n* **Informed search** - has access to both problem definition and some heuristics function\n* **Optimal solution** - has lowest path cost among all solutions\n* **Node** - a data structure consisting of parent, children, depth, path cost\n* **Path** - a sequence of actions leading from one state to another\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Search tree** - represents paths in a search algo as a tree where the root is the initial state, leaves are successor states\n* **Solution** - a path from initial state to goal state\n* **Standardized problem** - intended to illustrate or exercise various problem-solving methods\n* **State space** - set of all states reachable from the initial state by any sequence of actions\n* **Uninformed search** - has access to problem definition only\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "Greedy best-first search is complete but not optimal.\\n\n",
        "A* search is optimal with an admissible heuristic.\\n\n",
        "A consistent heuristic is when we have $h(n) \\leq c(n,a,n')+h(n')$ for every node n and every successor n' generated by an action a.\\n\n",
        "Every consistent heuristic is admissible but not vice versa.\\n\n",
        "With an inconsistent heuristic, we may end up having multiple paths reaching the same state.\\n\n",
        "A* expands all surely expanded nodes which are ones that can be reached from the initial state on a path where every node on the path has $f(n)<C*$ (cost of the optimal path).\\n\n",
        "A* might expand some of the nodes right on the goal contour where $f(n)=C*$, but never those with $f(n)>C*$.\\n\n",
        "A* with a consistent heuristic is optimally efficient because it prunes away search tree nodes that are not on the optimal path.\\n\n",
        "A* search is complete, cost-optimal and optimally efficient.\\n\n",
        "A well-designed heuristic should have an effective branching factor close to 1.\\n\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "UCS (aka Dijkstra) uses actual path cost as evaluation function, expanding node with lowest path cost from a priority queue and doing late goal test.\\n\n",
        "Best-first search uses heuristic functon as eval func, expanding the node closest to the goal, ignoring actual path cost. However, it can easily be stuck in loops.\\n\n",
        "In A*, we implement a priority queue by increasing estimated total cost through n to goal (i.e., g(n)+h(n)).\\n\n",
        "As long as the heurstic is admissible, A* will be optimal.\\n\n",
        "A* also does a late goal test, testing when popping node off the queue, not upon discovering.\\n\n",
        "UCS expands equally in all directions (circle shaped), while A* expands mainly towards the goal and hedge its bets to ensure optimality (contour).\\n\n",
        "The time and space complexity of A* search will depend on its heuristic.\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"A* search\": \"expands first the node with the lowest estimated cost of the best path that continues from n to a goal\",\n",
        "\"Admissibility\": \"aka optimstic, a heuristic that never overestimates the cost to reach a goal\",\n",
        "\"Bounded cost search\": \"solution whose cost is less thansome constant C\",\n",
        "\"Bounded suboptimal search\": \"solution that is within a constant factor W of the optimal cost (such as in weighted A*)\",\n",
        "\"Consistency\": \"we have triangle inequality for every node n and every successor of n\",\n",
        "\"Domination\": \"when h2(n) is strictly greater than h1(n) while still being admissible\",\n",
        "\"Effective branching factor (b*)\": \"the branching factor that a uniform tree of depth d would have to have in order to contain N+1 nodes\",\n",
        "\"Greedy best-first search\": \"expands first the node with the lowest h(n)\",\n",
        "\"Heuristics function\": \"estimated cost of the cheapest ath from the state n to a goal state\",\n",
        "\"Pattern database\": \"store solutions to evey possible subproblem instance\",\n",
        "\"Relaxed problem\": \"problem with fewer restrictions on the actions than the actual problem\",\n",
        "\"Satisficing search\": \"when we allow A* to use an inadmissible heuristic to sometimes overestimate in exchange for fewer expansions and suboptimal solution\",\n",
        "\"Unbounded search\": \"finding a solution quickly with any cost (such as speedy search)\",\n",
        "}\n",
        "\n",
        "\n"
      ],
      "execution_count": 98,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 812
        },
        "outputId": "df8e0fcc-23ef-4f1f-8093-5b9638c59080"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 99,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nGreedy best-first search is complete but not optimal.\n\nA* search is optimal with an admissible heuristic.\n\nA consistent heuristic is when we have $h(n) \\leq c(n,a,n')+h(n')$ for every node n and every successor n' generated by an action a.\n\nEvery consistent heuristic is admissible but not vice versa.\n\nWith an inconsistent heuristic, we may end up having multiple paths reaching the same state.\n\nA* expands all surely expanded nodes which are ones that can be reached from the initial state on a path where every node on the path has $f(n)<C*$ (cost of the optimal path).\n\nA* might expand some of the nodes right on the goal contour where $f(n)=C*$, but never those with $f(n)>C*$.\n\nA* with a consistent heuristic is optimally efficient because it prunes away search tree nodes that are not on the optimal path.\n\nA* search is complete, cost-optimal and optimally efficient.\n\nA well-designed heuristic should have an effective branching factor close to 1.\n\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\n\n\n## Module 4 Lecture Notes\n\nWe can use search if the task environment is fully observable, deterministic and known.\n\nAbstration helps keep search space under control, and should be easier than the real problem.\n\n\n\n\n## Module 4 Definitions\n* **A* search** - expands first the node with the lowest estimated cost of the best path that continues from n to a goal\n* **Admissibility** - aka optimstic, a heuristic that never overestimates the cost to reach a goal\n* **Bounded cost search** - solution whose cost is less thansome constant C\n* **Bounded suboptimal search** - solution that is within a constant factor W of the optimal cost (such as in weighted A*)\n* **Consistency** - we have triangle inequality for every node n and every successor of n\n* **Domination** - when h2(n) is strictly greater than h1(n) while still being admissible\n* **Effective branching factor (b*)** - the branching factor that a uniform tree of depth d would have to have in order to contain N+1 nodes\n* **Greedy best-first search** - expands first the node with the lowest h(n)\n* **Heuristics function** - estimated cost of the cheapest ath from the state n to a goal state\n* **Pattern database** - store solutions to evey possible subproblem instance\n* **Relaxed problem** - problem with fewer restrictions on the actions than the actual problem\n* **Satisficing search** - when we allow A* to use an inadmissible heuristic to sometimes overestimate in exchange for fewer expansions and suboptimal solution\n* **Unbounded search** - finding a solution quickly with any cost (such as speedy search)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "Components of a game includes initial state, transition model, terminal test, and utility function.\\n\n",
        "Initial state, actions function and result function define the state space graph.\\n\n",
        "Game tree is a search tree that follows every sequence of moves all the way to a terminal state.\\n\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Minimax value is the utility of being in that state, assuming that both players play optimally from there to the end of the game.\\n\n",
        "Minimax decision is the the optimal action that leads to the state with the best minimax value.\\n\n",
        "Minimax search is a recursive algorithm that proceeds all the way down to the leaves then backs up the minimax value.\\n\n",
        "Minimax time complexity: $O(b^m)$; space complexity: $O(bm)$.\\n\n",
        "In 2+ player games, replace the single minimax value with a vector of values.\\n\n",
        "The backed-up value of a node n is the utility vector of the successor state with the highest value for the player choosing at n.\\n\n",
        "Alpha-beta pruning depends on the order in which the states are examined, better to examine ones that are likely to be best.\\n\n",
        "We may reduce time complexity to $O(b^{m/2})$ with perfect move ordering, $O(b^{3m/4})$ with random move ordering.\\n\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "An evalution function returns an estimate of the expected utility of some state s, \\\n",
        "for player p. For terminal states, the evaluation function is exactly equal to the utility.\\n\n",
        "Table lookup is used for many opening and ending of games, then switches to search after 10-15 moves.\\n\n",
        "Forward pruning prunes moves that appears to be poor moves, but might hurt good ones too.\\n\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Stochastic games incorporates a random element, therefore needs to include chance nodes in the game tree.\\n\n",
        "We calculate the average over all possible outcomes of the chance nodes, which is the expectiminimax value.\\n\n",
        "To avoid the problem of value changes, we need to apply a positive linear transformation of the probability of the expected utility.\\n\n",
        "Expectiminimax time complexity: $O(b^mn^m)$, where n is the # of distinct rolls.\\n\n",
        "Alpha-beta pruning can be used to prune chance nodes by putting bounds of utility values as the upper bound on the chance node.\\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "Maximum expected utility (MEU) says that a rational agent should choose the action that \\\n",
        "maximizes its expected utility (prescription for intelligent behavior).\\n\n",
        "The central justification of MEU is that if an agent acts so as to maximize a utility function \\\n",
        "that correctly reflects the performance measure, then the agent will achieve the highest possible \\\n",
        "performance score (averaged over all possible environments).\\n\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "Axioms of utility theory:\n",
        "- Orderability: must prefer one or else rate them as equally preferable (cannot avoid deciding).\n",
        "- Transitivity: if prefer A to B and prefer B to C, then must prefer A to C.\n",
        "- Continuity: lottery B is between A and C, then there is some prob p for which agent is indifferent between B vs A and C.\n",
        "- Substitutability: if indifferent between A and B, then also indifferent between two more complex lotteries.\n",
        "- Monotonicity: if prefer A to B, then must prefer the lottery with higher p for A.\n",
        "- Decomposability: compound lotteries can be reduced to simpler ones using laws of probability.\n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "The difference between the EMV of a lottery and its certainty equivalent is the insurance premium.\\n\n",
        "Normative theory describes how a rational agent should act while descriptive theory describes how they actually act.\\n\n",
        "Irrational behaviors can arise due to:\n",
        "- certainty effect: strongly attracted to gains that are certain\n",
        "- ambiguity aversion: prefer known probabilities over unknown unknowns\n",
        "- framing effect: impact from the exact wording of a decision problem\n",
        "- anchoring effect: feeling more comfortable making relative utility rather than absolute ones\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Two players, max and min, take turns; max moves first.\\n\n",
        "To formalize game as search: we need initial state, successor function, terminal test, utility function.\\n\n",
        "Max player needs to consider all legal successors to the current state, evaluate each successor board position, \\\n",
        "pick the move which leads to the highest utility value (best position), then repeat after opponent moves.\\n\n",
        "In the game tree, nodes represent board positions and edges represent legal moves, and each level represents alternating moves.\\n\n",
        "When MAX mvoes, it attempts to maximize its outcomes; when MIN moves, it attempts to minimize MAX's outcomes.\\n\n",
        "Chess eval fn: sum of A's piece values - sum of B's piece values, or use weighted sum of positional features.\\n\n",
        "Minimax procedure (in itself is a complete DFS): 1) expand, 2) apply eval fn to leaf positions, \\\n",
        "3) calculate back-up values bottom up, 4) pick the best move assigned to MAX at root, 5) repeat after MIN has played.\\n\n",
        "To do alpha-beta pruning, keep track of alpha (MAX's lowest value so far) and beta (MIN's highest value so far) during minimax.\\n\n",
        "Prune a branch when $v \\geq β$ for MAX or $v \\leq α$ for MIN.\\n\n",
        "In expectimax, MIN nodes are replaced with chance nodes where the outcome depends on a probability. \\\n",
        "We're given a probabilistic model and need to calculate the expected utilities (take weighted average of children nodes).\\n\n",
        "Pruning is not possible during expectimax due to its probalistic nature.\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"alpha\" : \"MAX's current lower bound on its outcome, think 'at least for MAX'\",\n",
        "\"beam search\": \"consider only a subset of best moves according to eval fn rather than all\",\n",
        "\"beta\": \"MIN's current upper bound on its outcome, think 'at most for MIN'\",\n",
        "\"backtracking\": \"a type of DFS\",\n",
        "\"evaluation function\": \"estiamtes how good a board position is based on terminal nodes\",\n",
        "\"expectimax\": \"gives the average case outcome under optimal play\",\n",
        "\"games\": \"multiple agents, zero-sum, fully observable, static, finite set of actions and well-defined outcomes\",\n",
        "\"insurance premium\": \"difference between the EMV of a lottery and its certainty equivalent\",\n",
        "\"minimax\": \"gives the worst case outcome of the best achievable utility against a rational adversary\",\n",
        "\"monotonic preference\": \"prefers more to less\",\n",
        "\"normalized utilities\": \"normalized from 0 to 1\",\n",
        "\"objectivist\": \"aka frequentist; averages over repeated experiments\",\n",
        "\"preference elicitation\": \"the process of presenting choices and using observed preferences to pin down underlying utility function\",\n",
        "\"stochastic games\": \"includes a random element into games (e.g., backgammon)\",\n",
        "\"subjectivist\": \"aka Bayesian; degrees of belief about unobserved variables\",\n",
        "\"terminal nodes\": \"represent ways the game could end, often labeled with a score\",\n",
        "\"transpositions\": \"different permutations of the moves sequence result in repeated states; can be addressed with transposition table\",\n",
        "\"Type A strategy\": \"considers all possible moves to a certain depth (wide but shallow) -> for chess\",\n",
        "\"Type B strategy\": \"ignores moves that look bad and follows promising branches as far as possible (deep but narrow) -> for Go\",\n",
        "\"utility function\": \"defines the final numeric value to player when the game ends in terminal state\",\n",
        "\"value function\": \"agent needs only preference ranking on states, numeric values don't matter in game playing\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 100,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "34677aef-6ff4-4af8-a995-83f8ef0226b2"
      },
      "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": 101,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nComponents of a game includes initial state, transition model, terminal test, and utility function.\n\nInitial state, actions function and result function define the state space graph.\n\nGame tree is a search tree that follows every sequence of moves all the way to a terminal state.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax value is the utility of being in that state, assuming that both players play optimally from there to the end of the game.\n\nMinimax decision is the the optimal action that leads to the state with the best minimax value.\n\nMinimax search is a recursive algorithm that proceeds all the way down to the leaves then backs up the minimax value.\n\nMinimax time complexity: $O(b^m)$; space complexity: $O(bm)$.\n\nIn 2+ player games, replace the single minimax value with a vector of values.\n\nThe backed-up value of a node n is the utility vector of the successor state with the highest value for the player choosing at n.\n\nAlpha-beta pruning depends on the order in which the states are examined, better to examine ones that are likely to be best.\n\nWe may reduce time complexity to $O(b^{m/2})$ with perfect move ordering, $O(b^{3m/4})$ with random move ordering.\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nAn evalution function returns an estimate of the expected utility of some state s, for player p. For terminal states, the evaluation function is exactly equal to the utility.\n\nTable lookup is used for many opening and ending of games, then switches to search after 10-15 moves.\n\nForward pruning prunes moves that appears to be poor moves, but might hurt good ones too.\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games incorporates a random element, therefore needs to include chance nodes in the game tree.\n\nWe calculate the average over all possible outcomes of the chance nodes, which is the expectiminimax value.\n\nTo avoid the problem of value changes, we need to apply a positive linear transformation of the probability of the expected utility.\n\nExpectiminimax time complexity: $O(b^mn^m)$, where n is the # of distinct rolls.\n\nAlpha-beta pruning can be used to prune chance nodes by putting bounds of utility values as the upper bound on the chance node.\n\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nMaximum expected utility (MEU) says that a rational agent should choose the action that maximizes its expected utility (prescription for intelligent behavior).\n\nThe central justification of MEU is that if an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all possible environments).\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nAxioms of utility theory:\n- Orderability: must prefer one or else rate them as equally preferable (cannot avoid deciding).\n- Transitivity: if prefer A to B and prefer B to C, then must prefer A to C.\n- Continuity: lottery B is between A and C, then there is some prob p for which agent is indifferent between B vs A and C.\n- Substitutability: if indifferent between A and B, then also indifferent between two more complex lotteries.\n- Monotonicity: if prefer A to B, then must prefer the lottery with higher p for A.\n- Decomposability: compound lotteries can be reduced to simpler ones using laws of probability.\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nThe difference between the EMV of a lottery and its certainty equivalent is the insurance premium.\n\nNormative theory describes how a rational agent should act while descriptive theory describes how they actually act.\n\nIrrational behaviors can arise due to:\n- certainty effect: strongly attracted to gains that are certain\n- ambiguity aversion: prefer known probabilities over unknown unknowns\n- framing effect: impact from the exact wording of a decision problem\n- anchoring effect: feeling more comfortable making relative utility rather than absolute ones\n\n\n## Module 5 Lecture Notes\n\nTwo players, max and min, take turns; max moves first.\n\nTo formalize game as search: we need initial state, successor function, terminal test, utility function.\n\nMax player needs to consider all legal successors to the current state, evaluate each successor board position, pick the move which leads to the highest utility value (best position), then repeat after opponent moves.\n\nIn the game tree, nodes represent board positions and edges represent legal moves, and each level represents alternating moves.\n\nWhen MAX mvoes, it attempts to maximize its outcomes; when MIN moves, it attempts to minimize MAX's outcomes.\n\nChess eval fn: sum of A's piece values - sum of B's piece values, or use weighted sum of positional features.\n\nMinimax procedure (in itself is a complete DFS): 1) expand, 2) apply eval fn to leaf positions, 3) calculate back-up values bottom up, 4) pick the best move assigned to MAX at root, 5) repeat after MIN has played.\n\nTo do alpha-beta pruning, keep track of alpha (MAX's lowest value so far) and beta (MIN's highest value so far) during minimax.\n\nPrune a branch when $v \\geq β$ for MAX or $v \\leq α$ for MIN.\n\nIn expectimax, MIN nodes are replaced with chance nodes where the outcome depends on a probability. We're given a probabilistic model and need to calculate the expected utilities (take weighted average of children nodes).\n\nPruning is not possible during expectimax due to its probalistic nature.\n\n\n\n## Module 5 Definitions\n* **Alpha** - MAX's current lower bound on its outcome, think 'at least for MAX'\n* **Beam search** - consider only a subset of best moves according to eval fn rather than all\n* **Beta** - MIN's current upper bound on its outcome, think 'at most for MIN'\n* **Backtracking** - a type of DFS\n* **Evaluation function** - estiamtes how good a board position is based on terminal nodes\n* **Expectimax** - gives the average case outcome under optimal play\n* **Games** - multiple agents, zero-sum, fully observable, static, finite set of actions and well-defined outcomes\n* **Insurance premium** - difference between the EMV of a lottery and its certainty equivalent\n* **Minimax** - gives the worst case outcome of the best achievable utility against a rational adversary\n* **Monotonic preference** - prefers more to less\n* **Normalized utilities** - normalized from 0 to 1\n* **Objectivist** - aka frequentist; averages over repeated experiments\n* **Preference elicitation** - the process of presenting choices and using observed preferences to pin down underlying utility function\n* **Stochastic games** - includes a random element into games (e.g., backgammon)\n* **Subjectivist** - aka Bayesian; degrees of belief about unobserved variables\n* **Terminal nodes** - represent ways the game could end, often labeled with a score\n* **Transpositions** - different permutations of the moves sequence result in repeated states; can be addressed with transposition table\n* **Type a strategy** - considers all possible moves to a certain depth (wide but shallow) -> for chess\n* **Type b strategy** - ignores moves that look bad and follows promising branches as far as possible (deep but narrow) -> for Go\n* **Utility function** - defines the final numeric value to player when the game ends in terminal state\n* **Value function** - agent needs only preference ranking on states, numeric values don't matter in game playing\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "CSPs algorithms use general rather than domain-specific heuristics to reduce search space.\\n\n",
        "CSPs are comprised of 1) a set of variables X, 2) a set of domains D for each var, 3) a set of constraints.\\n\n",
        "CSP solvers can quickly prune large portions of the search space compared to searches.\\n\n",
        "We can discard completely any partial assignment that violates a constraint.\\n\n",
        "No CSP algo exists for solving general nonlinear constraints on integer variables.\\n\n",
        "Preferences are soft constraints and can be encoded as costs on individual variable assignments.\\n\n",
        "CSPs with preferences is a constrained optimiazation problem (COP).\\n\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "Constraint propagation can be done as a preprocessing or be intertwined with search.\\n\n",
        "To achieve arc consistency, we use AC-3 algorithm to maintain a queue of arcs to consider.\\n\n",
        "Initially the queue consists of all arcs, then we pop off the arcs and make $X_i$ consistent \\\n",
        "with $X_j$. If $D_i$ is reduced, then we propagate to check arcs with $X_i$'s neighbors $X_k$.\\n\n",
        "AC-3 time complexity: $O(cd^3)$ where $c$=# of arc constraints, $d$=max domain size.\\n\n",
        "To be path consistent, both ($X_i$, $X_m$) and ($X_m$, $X_j$) needs to be arc consistent.\\n\n",
        "Time complexity for strongly k-consistent CSP is $O(n^2d)$.\\n\n",
        "For alldiff CSPs, an early failure is detected if if at any point an empty domain is produeced.\\n\n",
        "In large-scale resource-limited CSPs, domains are represented using bounds and managed by bounds propagation.\\n\n",
        "When seeing naked triplets in Sudoku, we can remove the three numbers from the domain of every other cell in the unit.\\n\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "CSPs are commutative, so the search tree has $d^n$ leaves, not $n! \\cdot d^n$.\\n\n",
        "Backtracking search for CSP involves repeatedly choosing an unassigned variable, tries one value \\\n",
        "in its domain, trying to it into a solution. If success, solution is returned, \\\n",
        "if failure, the assignment is restored to previous state and try the next value.\\n\n",
        "Heuristics that can be used when searching in CSPs include: minimum-remaining-value (variable fail-first), \\\n",
        "degree (tie breaking), least-constraining-value (value fail-last).\n",
        "MAC is more strict than forward checking because forward checking does not recursively propagate constraints \\\n",
        "when changes are made to the domains of variables.\\n\n",
        "In intelligent backtracking, we create a conflict set and backtrack to the most recent assignment in \\\n",
        "the conflict set (called backjumping). The conflict set can be supplied as part of forward checking.\\n\n",
        "We record no-good variables as part of constraint learning to avoid running into the same assignment again.\\n\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "We can apply min-conflicts heuristic to select the value that results in the least number of conflicts \\\n",
        "with other variables.\\n\n",
        "Run time for min-conflicts is independently of problem size.\\n\n",
        "In constraint weighting, each constraint is given a weight (initially 1), and we prioritize the variable/value pair \\\n",
        "that results in the lowest total weight of all violated constraints.\\n\n",
        "The weights are incremented by the weight of each constraint that is violated.\\n\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "Each connected component of the constraint graph corresponds to a subproblem in CSP.\\n\n",
        "Any tree-structured CSP can be solved in time linear in the number of variables because we don't have to backtrack.\\n\n",
        "In cutset conditioning, we assign values to some variables (cycle cutset) so that the remaining variables form a tree.\\n\n",
        "Once cycle cutset is assigned (\"removed\"), remove any inconsistent arcs from the domains of the remaining variables \\\n",
        "and see if the remaining CSP has a solution.\\n\n",
        "Cuset conditioning CSP run time is $O(d^c \\cdot (n-c)d^2)$, note however finding the smallest cycle cutset is NP-hard.\\n\n",
        "In tree decomposition, we transform the original graph into a tree where each node in the tree consists \\\n",
        "of a set of variables with 3 criterias:\n",
        "- every variable must appear at least once\n",
        "- must appear together if connected by a constraint\n",
        "- must appear in every node along the path\n",
        "Tree decomposition CSP run time is $O(nd^{w+1})$, note however finding the minimal tree decomposition is NP-hard.\\n\n",
        "CSPs with constraint graphs of bounded tree width are solvable in poly time.\\n\n",
        "Tree decomposition is better in terms of time complexity, while cutset conditioning is more memory efficient.\\n\n",
        "Value symmetry can be broken with symmetry-breaking constraint by imposing an arbitrary ordering; \\\n",
        "also NP-hard to eliminate all symmetry.\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "CSPs knows where to focus the search and can automatically prune off branches that violate constraints.\\n\n",
        "CSPs as search problem:\n",
        "- initial state: empty assignment\n",
        "- successor function: assign value to unassigned variables that doesn't violate constraint\n",
        "- goal test: assignment is complete and consistent\n",
        "- path cost: constant cost every step\n",
        "Solution for CSPs is always found at depth n, for n variables.\\n\n",
        "To improve backtracking efficiency, use following heuristics:\n",
        "- assign most constrained variable next (most constraining if ties)\n",
        "- try least constraining value first for unassigned variables\n",
        "- do forward checking to detect possible failure\n",
        "In forward checking, keep track of remaining legal values for unassigned variables and terminate search \\\n",
        "whenever any domain becomes empty.\\n\n",
        "Constraint propagation repeatedly enforces arc consistency locally. \\\n",
        "If X loses a value recheck on all its neighbors. Takes $O(d^2)$ time in the worst case.\\n\n",
        "AC-3 works to place all the arcs in a queue. Pop arcs. For each arc, remove inconsistent values. \\\n",
        "If we change the values of a node, add its arcs to the queue. Terminate when the queue is empty.\\n\n",
        "AC-3 worst case time complexity is $O(n^2d^3)$ (with a complete graph).\n",
        "MAC is a way of interleaving search and inference. AC-3 is pure inference. MAC runs while assigning variables in backtracking search. \\\n",
        "Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3.\\n\n",
        "MAC recursively propogrates constraints, whereas forward checking does not. \\\n",
        "MAC does this, and if the domain of a variable YY changes, does the same for YY (and so on...) .\\n\n",
        "Solving a tree-structued CSP takes O(n) time in the number of variables.\\n\n",
        "Tree decomposition subproblems are efficient if the tree width of the constraint graph is small.\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"arc consistency\": \"there is some value in domain j that satsifies the binary constraint for every value in the current domain i\",\n",
        "\"backjumping\": \"intelligently backtrack to the most recent assignment in the conflict set\",\n",
        "\"bound consistency\": \"there exists some value Y that satisifies the upper and lower bound constraints for every variable X\",\n",
        "\"commutativity\": \"when the order of application of any given set of actions does not matter\",\n",
        "\"constraint learning\": \"find the minimum set of variables (no-good）from conflict set that causes the problem\",\n",
        "\"constraint propagation\": \"use constraints to reduce the number of legal values for one variable, which in turn does the same for another\",\n",
        "\"constraint weighting\": \"concentrates the search on the important constraints\",\n",
        "\"CSP\": \"given a set of variables, a problem is solved when each var has a valuethat satisfies all constraints\",\n",
        "\"cutset conditioning\" : \"used to reduce a general CSP to a tree structured one; more space efficient (linear)\",\n",
        "\"degree heuristic\": \"choose the variable involed in the largest number of constraints on other unassigned variables; useful for tie-breaking\",\n",
        "\"directional arc consistency (DAC)\": \"iff every $X_i$ is arc-consistency with each $X_j$ for $j>i$\",\n",
        "\"factored representation\": \"a set of variables, each of which has a value\",\n",
        "\"forward checking\": \"delete from $D_y$ values that are inconsistent with value chosen for X\",\n",
        "\"global constraint\": \"a constraint involving an arbitrary number of variables (not necessary all)\",\n",
        "\"k consistency\": \"a consistent value can be assigned to kth variable given k-1 consistency\",\n",
        "\"least-constraining-value (LCV)\": \"orders the values in the domain such that fewest choices for neighboring variables are ruled out\",\n",
        "\"linear programming\": \"best-known category of continous-domain CSPs\",\n",
        "\"maintaining arc consistency (MAC)\": \"calls AC-3 on arcs that contain unassigned variables that $X_i$'s neighbors\",\n",
        "\"min-conflicts\": \"a heuristic that selects the value that results in the least number of conflicts with other variables\",\n",
        "\"minimum-remaining-value (MRV)\": \"a heuristic that chooses the variable with the fewest legal moves\",\n",
        "\"naked triplets\": \"three cells that each have a domain with the same 3 numbers or a subset in sudoku\",\n",
        "\"node consistency\": \"all values in the variable's domain satisfy the variable's unary constraints\",\n",
        "\"path consistency\": \"use implicit constraints that are inferred by triples of variables\",\n",
        "\"preference constraints\": \"soft constraints that indicate which solutions are preferred\",\n",
        "\"tree decomposition\": \"used to transfrom CSP into a tree of subproblems; more time efficient\",\n",
        "\"solution\": \"a consistent, complete assignment to CSP\",\n",
        "\"strongly k consistency\": \"k consistent and k-1 consistent and k-2 consistent, etc.\",\n",
        "\"value symmetry\": \"existence of a set of $d!$ solutions formed by permutation\"\n",
        "}\n"
      ],
      "execution_count": 102,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "eb6505a7-98d2-4321-fc55-549af21137df"
      },
      "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": 103,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSPs algorithms use general rather than domain-specific heuristics to reduce search space.\n\nCSPs are comprised of 1) a set of variables X, 2) a set of domains D for each var, 3) a set of constraints.\n\nCSP solvers can quickly prune large portions of the search space compared to searches.\n\nWe can discard completely any partial assignment that violates a constraint.\n\nNo CSP algo exists for solving general nonlinear constraints on integer variables.\n\nPreferences are soft constraints and can be encoded as costs on individual variable assignments.\n\nCSPs with preferences is a constrained optimiazation problem (COP).\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nConstraint propagation can be done as a preprocessing or be intertwined with search.\n\nTo achieve arc consistency, we use AC-3 algorithm to maintain a queue of arcs to consider.\n\nInitially the queue consists of all arcs, then we pop off the arcs and make $X_i$ consistent with $X_j$. If $D_i$ is reduced, then we propagate to check arcs with $X_i$'s neighbors $X_k$.\n\nAC-3 time complexity: $O(cd^3)$ where $c$=# of arc constraints, $d$=max domain size.\n\nTo be path consistent, both ($X_i$, $X_m$) and ($X_m$, $X_j$) needs to be arc consistent.\n\nTime complexity for strongly k-consistent CSP is $O(n^2d)$.\n\nFor alldiff CSPs, an early failure is detected if if at any point an empty domain is produeced.\n\nIn large-scale resource-limited CSPs, domains are represented using bounds and managed by bounds propagation.\n\nWhen seeing naked triplets in Sudoku, we can remove the three numbers from the domain of every other cell in the unit.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nCSPs are commutative, so the search tree has $d^n$ leaves, not $n! \\cdot d^n$.\n\nBacktracking search for CSP involves repeatedly choosing an unassigned variable, tries one value in its domain, trying to it into a solution. If success, solution is returned, if failure, the assignment is restored to previous state and try the next value.\n\nHeuristics that can be used when searching in CSPs include: minimum-remaining-value (variable fail-first), degree (tie breaking), least-constraining-value (value fail-last).\nMAC is more strict than forward checking because forward checking does not recursively propagate constraints when changes are made to the domains of variables.\n\nIn intelligent backtracking, we create a conflict set and backtrack to the most recent assignment in the conflict set (called backjumping). The conflict set can be supplied as part of forward checking.\n\nWe record no-good variables as part of constraint learning to avoid running into the same assignment again.\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nWe can apply min-conflicts heuristic to select the value that results in the least number of conflicts with other variables.\n\nRun time for min-conflicts is independently of problem size.\n\nIn constraint weighting, each constraint is given a weight (initially 1), and we prioritize the variable/value pair that results in the lowest total weight of all violated constraints.\n\nThe weights are incremented by the weight of each constraint that is violated.\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nEach connected component of the constraint graph corresponds to a subproblem in CSP.\n\nAny tree-structured CSP can be solved in time linear in the number of variables because we don't have to backtrack.\n\nIn cutset conditioning, we assign values to some variables (cycle cutset) so that the remaining variables form a tree.\n\nOnce cycle cutset is assigned (\"removed\"), remove any inconsistent arcs from the domains of the remaining variables and see if the remaining CSP has a solution.\n\nCuset conditioning CSP run time is $O(d^c \\cdot (n-c)d^2)$, note however finding the smallest cycle cutset is NP-hard.\n\nIn tree decomposition, we transform the original graph into a tree where each node in the tree consists of a set of variables with 3 criterias:\n- every variable must appear at least once\n- must appear together if connected by a constraint\n- must appear in every node along the path\nTree decomposition CSP run time is $O(nd^{w+1})$, note however finding the minimal tree decomposition is NP-hard.\n\nCSPs with constraint graphs of bounded tree width are solvable in poly time.\n\nTree decomposition is better in terms of time complexity, while cutset conditioning is more memory efficient.\n\nValue symmetry can be broken with symmetry-breaking constraint by imposing an arbitrary ordering; also NP-hard to eliminate all symmetry.\n\n\n\n## Module 6 Lecture Notes\n\nCSPs knows where to focus the search and can automatically prune off branches that violate constraints.\n\nCSPs as search problem:\n- initial state: empty assignment\n- successor function: assign value to unassigned variables that doesn't violate constraint\n- goal test: assignment is complete and consistent\n- path cost: constant cost every step\nSolution for CSPs is always found at depth n, for n variables.\n\nTo improve backtracking efficiency, use following heuristics:\n- assign most constrained variable next (most constraining if ties)\n- try least constraining value first for unassigned variables\n- do forward checking to detect possible failure\nIn forward checking, keep track of remaining legal values for unassigned variables and terminate search whenever any domain becomes empty.\n\nConstraint propagation repeatedly enforces arc consistency locally. If X loses a value recheck on all its neighbors. Takes $O(d^2)$ time in the worst case.\n\nAC-3 works to place all the arcs in a queue. Pop arcs. For each arc, remove inconsistent values. If we change the values of a node, add its arcs to the queue. Terminate when the queue is empty.\n\nAC-3 worst case time complexity is $O(n^2d^3)$ (with a complete graph).\nMAC is a way of interleaving search and inference. AC-3 is pure inference. MAC runs while assigning variables in backtracking search. Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3.\n\nMAC recursively propogrates constraints, whereas forward checking does not. MAC does this, and if the domain of a variable YY changes, does the same for YY (and so on...) .\n\nSolving a tree-structued CSP takes O(n) time in the number of variables.\n\nTree decomposition subproblems are efficient if the tree width of the constraint graph is small.\n\n\n\n## Module 6 Definitions\n* **Arc consistency** - there is some value in domain j that satsifies the binary constraint for every value in the current domain i\n* **Backjumping** - intelligently backtrack to the most recent assignment in the conflict set\n* **Bound consistency** - there exists some value Y that satisifies the upper and lower bound constraints for every variable X\n* **Commutativity** - when the order of application of any given set of actions does not matter\n* **Constraint learning** - find the minimum set of variables (no-good）from conflict set that causes the problem\n* **Constraint propagation** - use constraints to reduce the number of legal values for one variable, which in turn does the same for another\n* **Constraint weighting** - concentrates the search on the important constraints\n* **Csp** - given a set of variables, a problem is solved when each var has a valuethat satisfies all constraints\n* **Cutset conditioning** - used to reduce a general CSP to a tree structured one; more space efficient (linear)\n* **Degree heuristic** - choose the variable involed in the largest number of constraints on other unassigned variables; useful for tie-breaking\n* **Directional arc consistency (dac)** - iff every $X_i$ is arc-consistency with each $X_j$ for $j>i$\n* **Factored representation** - a set of variables, each of which has a value\n* **Forward checking** - delete from $D_y$ values that are inconsistent with value chosen for X\n* **Global constraint** - a constraint involving an arbitrary number of variables (not necessary all)\n* **K consistency** - a consistent value can be assigned to kth variable given k-1 consistency\n* **Least-constraining-value (lcv)** - orders the values in the domain such that fewest choices for neighboring variables are ruled out\n* **Linear programming** - best-known category of continous-domain CSPs\n* **Maintaining arc consistency (mac)** - calls AC-3 on arcs that contain unassigned variables that $X_i$'s neighbors\n* **Min-conflicts** - a heuristic that selects the value that results in the least number of conflicts with other variables\n* **Minimum-remaining-value (mrv)** - a heuristic that chooses the variable with the fewest legal moves\n* **Naked triplets** - three cells that each have a domain with the same 3 numbers or a subset in sudoku\n* **Node consistency** - all values in the variable's domain satisfy the variable's unary constraints\n* **Path consistency** - use implicit constraints that are inferred by triples of variables\n* **Preference constraints** - soft constraints that indicate which solutions are preferred\n* **Tree decomposition** - used to transfrom CSP into a tree of subproblems; more time efficient\n* **Solution** - a consistent, complete assignment to CSP\n* **Strongly k consistency** - k consistent and k-1 consistent and k-2 consistent, etc.\n* **Value symmetry** - existence of a set of $d!$ solutions formed by permutation\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "Each sentence in KB is expressed in knowledge representation language that represents some \\\n",
        "assertions about the world.\\n\n",
        "Inference is the process of deriving new sentences from old.\\n\n",
        "The knowledge base (KB) is maintained by the agent, and may start with some background knowledge.\\n\n",
        "In the declarative approach, the designer tells sentences to the agent until the agent has \\\n",
        "enough knowledge to operate in the environment.\\n\n",
        "In the procedural approach, the designer encodes desired behaviors directly as program code.\\n\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "In the wumpus world, there is performance measure, an environment. The agent has actuators and sensors.\\n\n",
        "The percepts are often given to agent in the form of list of symbols.\\n\n",
        "The wumpus world is deterministic, discrete, static, single-agent and partially observable.\\n\n",
        "Logic reasoning ensures that in each case for which the agent draws a conclusion \\\n",
        "from the available info, that conclusion is guaranteed to be correct if the \\\n",
        "available info is correct.\\n\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "If a sentence α is true in model m: m satisifes α or m is model of α. \\\n",
        "$M(α)$ means the set of all models of α.\\n\n",
        "α entails β means sentence β follows logically from sentence α.\\n\n",
        "\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "Propositional entailment is co-NP-complete, so every known inference algorithm for \\\n",
        "propsitional logic has a worst-case complexity that is exponential in the size of the input.\\n\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "With large models and short proofs, theorem proving can be more efficient than model checking.\\n\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "A logic defines the semantics (meaning) of the sentences, which defines the truth of each \\\n",
        "sentence with respect to a possible world, which we call a model.\\n\n",
        "Logical entailment in possible worlds: $KB ⊨ α$ iff $M(KB) ⊆ M(α)$, KB needs to be a subset of α here.\\n\n",
        "Propositional symbols stand for a statement that can be true or false.\\n\n",
        "Logical inference in possible worlds: $KB ⊢_i α$ if an inference algo i allows us to conclude that α is true \\\n",
        "(α is derived from KB by i).\\n\n",
        "Monotonicity implies soundness.\\n\n",
        "Resolution is a single inference rule that guarantees completeness.\\n\n",
        "Steps to arrive at CNF:\n",
        "- eliminate ⟺ by replacing α ⟺ β with (α ⟹ β) ∧ (β ⟹ α)\n",
        "- eliminate ⟹ by replacing α ⟹ β with ¬α ∨ β\n",
        "- eliminate any double negations, apply De Morgan's rules\n",
        "- apply distributivity law to distribute ∨ over ∧ wherever possible\n",
        "In resolution algorithm, we need to show that KB ∧ ¬α is unsatisfiable (proof by contradiction); \\\n",
        "if two clauses resolve to yield the empty clause, then KB does ential α.\\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"axiom\": \"a sentence taken as being given without being derived from other sentences\",\n",
        "\"backward chaining\": \"goal-directed reasoning; start with a query and finds implications in the KB that leads to the query\",\n",
        "\"completeness\": \"any sentence that is entailed can be derived\",\n",
        "\"conjunctive normal form (CNF)\": \"a sentence expressed as a conjunction of clauses\",\n",
        "\"declarative approach\": \"agent is being told what it needs to know\",\n",
        "\"definite clause\": \"disjunction of literals where exactly one is positive\",\n",
        "\"entailment\": \"a sentence follows logically from another sentence\",\n",
        "\"forward chaining\": \"data-driven reasoning; start with known data, adding premises based on new percepts\",\n",
        "\"grounding\": \"connection between logical reasoning processes and the real environment\",\n",
        "\"horn clause\": \"disjunction of literals where at most one is positive; closed under resolution\",\n",
        "\"knowledge base (KB)\": \"a set of sentences where each represents some assertion about the world\",\n",
        "\"logical equivalence\": \"if two sentences α and β are true in the same set of models (α ≡ β)\",\n",
        "\"logical inference\": \"how definition of entailment can be applied to derive conclusions\",\n",
        "\"model checking\": \"enumerate over all possible models to check that α is true in all models in which KB is true\",\n",
        "\"procedural approach\": \"agent is being encoded the desired behaviors as program code\",\n",
        "\"resolution\": \"if l and m are complementary literals (negation of each other), eliminate them via unit resolution\",\n",
        "\"satisfiability\": \"if a setence is true in/satisfied by some model\",\n",
        "\"soundness\": \"truth-preserving, when only entailed sentences are derived\",\n",
        "\"theorem proving\": \"applying rules of inference directly to sentences in KB to construct a proof of the desired sentence\",\n",
        "\"validity\": \"true in all models, necessarily true (tautologies)\",\n",
        "\"wumpus world\": \"a cave consisting of rooms connected by passageways\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 104,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "3d765bfe-48d5-4b87-cbee-66e7599771df"
      },
      "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": 105,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nEach sentence in KB is expressed in knowledge representation language that represents some assertions about the world.\n\nInference is the process of deriving new sentences from old.\n\nThe knowledge base (KB) is maintained by the agent, and may start with some background knowledge.\n\nIn the declarative approach, the designer tells sentences to the agent until the agent has enough knowledge to operate in the environment.\n\nIn the procedural approach, the designer encodes desired behaviors directly as program code.\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\nIn the wumpus world, there is performance measure, an environment. The agent has actuators and sensors.\n\nThe percepts are often given to agent in the form of list of symbols.\n\nThe wumpus world is deterministic, discrete, static, single-agent and partially observable.\n\nLogic reasoning ensures that in each case for which the agent draws a conclusion from the available info, that conclusion is guaranteed to be correct if the available info is correct.\n\n\n\n## AIMA Chapter 7.3 Logic\n\nIf a sentence α is true in model m: m satisifes α or m is model of α. $M(α)$ means the set of all models of α.\n\nα entails β means sentence β follows logically from sentence α.\n\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nPropositional entailment is co-NP-complete, so every known inference algorithm for propsitional logic has a worst-case complexity that is exponential in the size of the input.\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nWith large models and short proofs, theorem proving can be more efficient than model checking.\n\n\n\n## Module 7 Lecture Notes\n\nA logic defines the semantics (meaning) of the sentences, which defines the truth of each sentence with respect to a possible world, which we call a model.\n\nLogical entailment in possible worlds: $KB ⊨ α$ iff $M(KB) ⊆ M(α)$, KB needs to be a subset of α here.\n\nPropositional symbols stand for a statement that can be true or false.\n\nLogical inference in possible worlds: $KB ⊢_i α$ if an inference algo i allows us to conclude that α is true (α is derived from KB by i).\n\nMonotonicity implies soundness.\n\nResolution is a single inference rule that guarantees completeness.\n\nSteps to arrive at CNF:\n- eliminate ⟺ by replacing α ⟺ β with (α ⟹ β) ∧ (β ⟹ α)\n- eliminate ⟹ by replacing α ⟹ β with ¬α ∨ β\n- eliminate any double negations, apply De Morgan's rules\n- apply distributivity law to distribute ∨ over ∧ wherever possible\nIn resolution algorithm, we need to show that KB ∧ ¬α is unsatisfiable (proof by contradiction); if two clauses resolve to yield the empty clause, then KB does ential α.\n\n\n\n\n\n## Module 7 Definitions\n* **Axiom** - a sentence taken as being given without being derived from other sentences\n* **Backward chaining** - goal-directed reasoning; start with a query and finds implications in the KB that leads to the query\n* **Completeness** - any sentence that is entailed can be derived\n* **Conjunctive normal form (cnf)** - a sentence expressed as a conjunction of clauses\n* **Declarative approach** - agent is being told what it needs to know\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Entailment** - a sentence follows logically from another sentence\n* **Forward chaining** - data-driven reasoning; start with known data, adding premises based on new percepts\n* **Grounding** - connection between logical reasoning processes and the real environment\n* **Horn clause** - disjunction of literals where at most one is positive; closed under resolution\n* **Knowledge base (kb)** - a set of sentences where each represents some assertion about the world\n* **Logical equivalence** - if two sentences α and β are true in the same set of models (α ≡ β)\n* **Logical inference** - how definition of entailment can be applied to derive conclusions\n* **Model checking** - enumerate over all possible models to check that α is true in all models in which KB is true\n* **Procedural approach** - agent is being encoded the desired behaviors as program code\n* **Resolution** - if l and m are complementary literals (negation of each other), eliminate them via unit resolution\n* **Satisfiability** - if a setence is true in/satisfied by some model\n* **Soundness** - truth-preserving, when only entailed sentences are derived\n* **Theorem proving** - applying rules of inference directly to sentences in KB to construct a proof of the desired sentence\n* **Validity** - true in all models, necessarily true (tautologies)\n* **Wumpus world** - a cave consisting of rooms connected by passageways\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "a087f42d-c8f5-421f-9c85-aa9ba1fcc715"
      },
      "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": 106,
      "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\nAn agernt's choice of action depends on its built-in konwledge and on its percept sequence (history), but not anything it hasn't perceived.\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nRationality depnds on performance measure, agent's prior knowledge, set of actions, percept sequence.\n\nRational agent should select an action that is expected to maximize its performance measure, given the evidence provided by its percept sequence and its built-in knowledge.\n\n\n\n## AIMA 2.3 The Nature of Environments\n\nA rational agent is also autonomous - learning what it can to compensate for partial or incorrect prior knowledge.\n\nA task environment includes performance measure, environment, actuators, and sensors (PEAS).\n\nProperties of task environment:\n- fully vs partial observable\n- single vs multi agent\n- deterministic vs stochastic (probabilitistic)\n- episodic (actions are independent) vs sequential\n- static vs dynamic (environment changes while agent is deliberating)\n- discrete vs continuous time\n\n\n## AIMA 2.4 The Structure of Agents\n\nAgent problems take current percept as input from sensors and return an action to actuators.\n\nModel-based agents use transition model and sensor model to keep track of the state of the world.\n\nGoal-based agents keeps track of the world and choose actions that achieve the goal.\n\nUtility-based agents choose actions that maximize its expected utility (internalization of performance measure)which is calculated as the weighted average over all possible outcome states.\n\n3 ways to represent states and transitions:\n- atomic: each state of the world is indivisible (no internal structure)\n- factored: each state is split up into variables/attributes which can have a value\n- structured: each state includes objects which may have its own attributes and relationships to other objects\n\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act in an environment through actuators\n* **Agent function** - specifies action taken by the agent in response to any pecept sequence\n* **Consequentialism** - evaluate an agent's behavior by its consequences\n* **Fully observable** - agent has access to the complete environment state at each point in time\n* **Intelligent entities** - machines that compute how to act effectively and safely\n* **Learning element** - uses feedback from critic on how the agent is doing then make improvements\n* **Percept** - your definitions here\n* **Performance measure** - evaluates behavior of agent in an environment\n* **Problem generator** - suggests actions that will lead to new and informative experiences\n* **Rational agent** - acts to achieve the best (expected) performance measure\n* **Simple reflex agent** - agents that select actions based on current percept\n* **Strong ai** - actually thinking\n* **Transition model** - knowledge about how the world changes over time\n* **Sensor model** - info about the state of the world reflected in agent's percepts\n* **Vague alignment problem** - the values or objectives put into the machine are aligned with those of the human\n* **Weak ai** - simulate thinking\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\nPython delinates a code blocks with a clon and indentation.\n\nAll data treated as objects and is deleted once unreachable.\n\nPython is strong but dynamic typing (drawback being that type errors are only caught at runtime).\n\nSlicing returns a copy of a subsequence.\n\nCommon list operations: append, insert, index, count, remove, reverse, sort, sorted...\n\nCommon string operations: split, join, upper...\n\nCommon dict methods: keys, values, items...\n\nNo function overloading but operator overloading is possible.\n\nArguments to functions become optional if they have default values, should be preceded by non-default args.\n\nKeyword arguments can appear in any order but positional args need to precede keyword args.\n\nFunction argument ordering: positional, *args, **kwargs.\n\nFunctions are first-class objects.\n\nExtended subclass allows use of methods and attributes from the super class. Multiple inheritance is supported.\n\nTo redefine a method of the parent class, give a new definition using the same name in the subclass.\n\nIteratable objects have an __iter__ magic which turn them into iterator objects, so can be used in loops.\n\nIterators work with iterator objects and has a __next__ magic method, throws Stopiteration exception at the end.\n\nIterators use memory more efficiently than iterable objects themselves.\n\nBenefits of generators: values are computed as needed, avoids storing entire sequence in memory, good for aggregating items, crucial for infinite sequences.\n\n\n\n## Module 2 Definitions\n* ***args** - a tuple of positional arguments passed to the function; need to be dereferenced\n* ****kwargs** - a dict of the keyword args passed to the function; dereferenced twice\n* **Counter** - from collections, count # of occurrences as values\n* **Defaultdict** - from collections, automatically initializes nonexistent values\n* **Dictionary** - unordered, immutable keys, O(1) time, values can be mixed type, no reverse lookup\n* **Duck typing** - establishes suitability of an object by determining presence of methods\n* **First class object** - can be dynamically created, destroyed, passed, returned, has rights as variables\n* **Generators** - iterators created with YIELD keyword; returns yielded value then resumes where it left off\n* **List** - mutable, ordered, mixed types\n* **List comprehension** - [expression for name in list if filter]\n* **Magic methods** - allow user-defined classes to behave like built in types (init, len, copy, cmp, add, neg, str, name, main...)\n* **Mutability** - whether a variable can be changed; if not need to reassign after making change\n* **Repl** - read-evaluate-print loop\n* **String** - immutable, Unicode, each char is 2 bytes\n* **Tuple** - immutable, ordered, mixed types\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nComponents of search problem: state space, initial state, goal states, actions, transition model, path cost function (additive).\n\n\n\n## AIMA Chapter 3.2 Example Problems\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nA search algorithm takes a search problem as input and returns a solution.\n\nNode -> state, edges -> actions\n\nSearch algorithms are judged based on: completeness, cost optimality, time complexity, space complexity.\n\nComplexities are measured in depth (d, number of actions), maximum numbers of actions in any path (m), and branching factor (b, number of successors).\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nIn BFS, we apply early goal test, checking whether a node is a solution as soon as generated. Use FIFO frontier.\n\nIn uniform cost search (Dijkstra), we use a priority queue to expand the node with the lowest actual path cost. we apply late goal test, checking for goals when node is expanded.\n\nDFS expands the deepest node (go to the deepest level of the tree then backup). Uses LIFO frontier and returns the first solution it finds. More efficient on space.\n\nDepth limited search prevents DFS going down infinite path by supplying a depth limit and treat all nodes at depth l as if they have no successors. However, need to be careful with choice of l to not make it incomplete.\n\nIterative Deepening search uses depth limited search as subroutine, with increasing l.\n\nIDDFS is the preferred uninformed search method when the search state space is larger than can fit in memory and the depth of the solution is unknown.\n\nBidirectional search simultaneously searches from the initial state and backwards from the goal state by keeping track of 2 frontiers and 2 tables of reached states. The node with the minimum value of the eval fn across either frontier is expanded next.\n\n\n| Criterion | BFS      | UCS               | DFS      | Depth-Limited | Iterative Deepening | Bidirectional |\n| --------- | :---:    | :---:             | :---:    |:-------------:|:-------------------:|:-------------:|\n| Complete? | Yes      | Yes               | No       | No            | Yes                 | Yes           |\n| Optimal?  | Yes      | Yes               | No       | No            | Yes                 | Yes           |\n| Time?     | $O(b^d)$ | $O(b^(1+[C*/e]))$ | $O(b^m)$ | $O(b^l)$      | $O(b^d)$            | $O(b^(d/2))$  |\n| Space?    | $O(b^d)$ | $O(b^(1+[C*/e]))$ | $O(bm)$  | $O(bl)$       | $O(bd)$             | $O(b^(d/2))$  |\n\n\n## Module 3 Lecture Notes\n\nWe can use search if the task environment is fully observable, deterministic and known.\n\nAbstration helps keep search space under control, and should be easier than the real problem.\n\n\n\n\n## Module 3 Definitions\n* **Action cost function** - numeric cost of applying action a in state s to reach state s'\n* **Best-first search** - expand the node with the minimum value of some eval function; uses priority queue\n* **Frontier** - states that are available for expanding; grows the search tree\n* **Graph search** - checks for redundant path, stores visited states so requires more space\n* **Informed search** - has access to both problem definition and some heuristics function\n* **Optimal solution** - has lowest path cost among all solutions\n* **Node** - a data structure consisting of parent, children, depth, path cost\n* **Path** - a sequence of actions leading from one state to another\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Search tree** - represents paths in a search algo as a tree where the root is the initial state, leaves are successor states\n* **Solution** - a path from initial state to goal state\n* **Standardized problem** - intended to illustrate or exercise various problem-solving methods\n* **State space** - set of all states reachable from the initial state by any sequence of actions\n* **Uninformed search** - has access to problem definition only\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nGreedy best-first search is complete but not optimal.\n\nA* search is optimal with an admissible heuristic.\n\nA consistent heuristic is when we have $h(n) \\leq c(n,a,n')+h(n')$ for every node n and every successor n' generated by an action a.\n\nEvery consistent heuristic is admissible but not vice versa.\n\nWith an inconsistent heuristic, we may end up having multiple paths reaching the same state.\n\nA* expands all surely expanded nodes which are ones that can be reached from the initial state on a path where every node on the path has $f(n)<C*$ (cost of the optimal path).\n\nA* might expand some of the nodes right on the goal contour where $f(n)=C*$, but never those with $f(n)>C*$.\n\nA* with a consistent heuristic is optimally efficient because it prunes away search tree nodes that are not on the optimal path.\n\nA* search is complete, cost-optimal and optimally efficient.\n\nA well-designed heuristic should have an effective branching factor close to 1.\n\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\n\n\n## Module 4 Lecture Notes\n\nWe can use search if the task environment is fully observable, deterministic and known.\n\nAbstration helps keep search space under control, and should be easier than the real problem.\n\n\n\n\n## Module 4 Definitions\n* **A* search** - expands first the node with the lowest estimated cost of the best path that continues from n to a goal\n* **Admissibility** - aka optimstic, a heuristic that never overestimates the cost to reach a goal\n* **Bounded cost search** - solution whose cost is less thansome constant C\n* **Bounded suboptimal search** - solution that is within a constant factor W of the optimal cost (such as in weighted A*)\n* **Consistency** - we have triangle inequality for every node n and every successor of n\n* **Domination** - when h2(n) is strictly greater than h1(n) while still being admissible\n* **Effective branching factor (b*)** - the branching factor that a uniform tree of depth d would have to have in order to contain N+1 nodes\n* **Greedy best-first search** - expands first the node with the lowest h(n)\n* **Heuristics function** - estimated cost of the cheapest ath from the state n to a goal state\n* **Pattern database** - store solutions to evey possible subproblem instance\n* **Relaxed problem** - problem with fewer restrictions on the actions than the actual problem\n* **Satisficing search** - when we allow A* to use an inadmissible heuristic to sometimes overestimate in exchange for fewer expansions and suboptimal solution\n* **Unbounded search** - finding a solution quickly with any cost (such as speedy search)\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nComponents of a game includes initial state, transition model, terminal test, and utility function.\n\nInitial state, actions function and result function define the state space graph.\n\nGame tree is a search tree that follows every sequence of moves all the way to a terminal state.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax value is the utility of being in that state, assuming that both players play optimally from there to the end of the game.\n\nMinimax decision is the the optimal action that leads to the state with the best minimax value.\n\nMinimax search is a recursive algorithm that proceeds all the way down to the leaves then backs up the minimax value.\n\nMinimax time complexity: $O(b^m)$; space complexity: $O(bm)$.\n\nIn 2+ player games, replace the single minimax value with a vector of values.\n\nThe backed-up value of a node n is the utility vector of the successor state with the highest value for the player choosing at n.\n\nAlpha-beta pruning depends on the order in which the states are examined, better to examine ones that are likely to be best.\n\nWe may reduce time complexity to $O(b^{m/2})$ with perfect move ordering, $O(b^{3m/4})$ with random move ordering.\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nAn evalution function returns an estimate of the expected utility of some state s, for player p. For terminal states, the evaluation function is exactly equal to the utility.\n\nTable lookup is used for many opening and ending of games, then switches to search after 10-15 moves.\n\nForward pruning prunes moves that appears to be poor moves, but might hurt good ones too.\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic games incorporates a random element, therefore needs to include chance nodes in the game tree.\n\nWe calculate the average over all possible outcomes of the chance nodes, which is the expectiminimax value.\n\nTo avoid the problem of value changes, we need to apply a positive linear transformation of the probability of the expected utility.\n\nExpectiminimax time complexity: $O(b^mn^m)$, where n is the # of distinct rolls.\n\nAlpha-beta pruning can be used to prune chance nodes by putting bounds of utility values as the upper bound on the chance node.\n\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nMaximum expected utility (MEU) says that a rational agent should choose the action that maximizes its expected utility (prescription for intelligent behavior).\n\nThe central justification of MEU is that if an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all possible environments).\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nAxioms of utility theory:\n- Orderability: must prefer one or else rate them as equally preferable (cannot avoid deciding).\n- Transitivity: if prefer A to B and prefer B to C, then must prefer A to C.\n- Continuity: lottery B is between A and C, then there is some prob p for which agent is indifferent between B vs A and C.\n- Substitutability: if indifferent between A and B, then also indifferent between two more complex lotteries.\n- Monotonicity: if prefer A to B, then must prefer the lottery with higher p for A.\n- Decomposability: compound lotteries can be reduced to simpler ones using laws of probability.\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nThe difference between the EMV of a lottery and its certainty equivalent is the insurance premium.\n\nNormative theory describes how a rational agent should act while descriptive theory describes how they actually act.\n\nIrrational behaviors can arise due to:\n- certainty effect: strongly attracted to gains that are certain\n- ambiguity aversion: prefer known probabilities over unknown unknowns\n- framing effect: impact from the exact wording of a decision problem\n- anchoring effect: feeling more comfortable making relative utility rather than absolute ones\n\n\n## Module 5 Lecture Notes\n\nTwo players, max and min, take turns; max moves first.\n\nTo formalize game as search: we need initial state, successor function, terminal test, utility function.\n\nMax player needs to consider all legal successors to the current state, evaluate each successor board position, pick the move which leads to the highest utility value (best position), then repeat after opponent moves.\n\nIn the game tree, nodes represent board positions and edges represent legal moves, and each level represents alternating moves.\n\nWhen MAX mvoes, it attempts to maximize its outcomes; when MIN moves, it attempts to minimize MAX's outcomes.\n\nChess eval fn: sum of A's piece values - sum of B's piece values, or use weighted sum of positional features.\n\nMinimax procedure (in itself is a complete DFS): 1) expand, 2) apply eval fn to leaf positions, 3) calculate back-up values bottom up, 4) pick the best move assigned to MAX at root, 5) repeat after MIN has played.\n\nTo do alpha-beta pruning, keep track of alpha (MAX's lowest value so far) and beta (MIN's highest value so far) during minimax.\n\nPrune a branch when $v \\geq β$ for MAX or $v \\leq α$ for MIN.\n\nIn expectimax, MIN nodes are replaced with chance nodes where the outcome depends on a probability. We're given a probabilistic model and need to calculate the expected utilities (take weighted average of children nodes).\n\nPruning is not possible during expectimax due to its probalistic nature.\n\n\n\n## Module 5 Definitions\n* **Alpha** - MAX's current lower bound on its outcome, think 'at least for MAX'\n* **Beam search** - consider only a subset of best moves according to eval fn rather than all\n* **Beta** - MIN's current upper bound on its outcome, think 'at most for MIN'\n* **Backtracking** - a type of DFS\n* **Evaluation function** - estiamtes how good a board position is based on terminal nodes\n* **Expectimax** - gives the average case outcome under optimal play\n* **Games** - multiple agents, zero-sum, fully observable, static, finite set of actions and well-defined outcomes\n* **Insurance premium** - difference between the EMV of a lottery and its certainty equivalent\n* **Minimax** - gives the worst case outcome of the best achievable utility against a rational adversary\n* **Monotonic preference** - prefers more to less\n* **Normalized utilities** - normalized from 0 to 1\n* **Objectivist** - aka frequentist; averages over repeated experiments\n* **Preference elicitation** - the process of presenting choices and using observed preferences to pin down underlying utility function\n* **Stochastic games** - includes a random element into games (e.g., backgammon)\n* **Subjectivist** - aka Bayesian; degrees of belief about unobserved variables\n* **Terminal nodes** - represent ways the game could end, often labeled with a score\n* **Transpositions** - different permutations of the moves sequence result in repeated states; can be addressed with transposition table\n* **Type a strategy** - considers all possible moves to a certain depth (wide but shallow) -> for chess\n* **Type b strategy** - ignores moves that look bad and follows promising branches as far as possible (deep but narrow) -> for Go\n* **Utility function** - defines the final numeric value to player when the game ends in terminal state\n* **Value function** - agent needs only preference ranking on states, numeric values don't matter in game playing\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSPs algorithms use general rather than domain-specific heuristics to reduce search space.\n\nCSPs are comprised of 1) a set of variables X, 2) a set of domains D for each var, 3) a set of constraints.\n\nCSP solvers can quickly prune large portions of the search space compared to searches.\n\nWe can discard completely any partial assignment that violates a constraint.\n\nNo CSP algo exists for solving general nonlinear constraints on integer variables.\n\nPreferences are soft constraints and can be encoded as costs on individual variable assignments.\n\nCSPs with preferences is a constrained optimiazation problem (COP).\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nConstraint propagation can be done as a preprocessing or be intertwined with search.\n\nTo achieve arc consistency, we use AC-3 algorithm to maintain a queue of arcs to consider.\n\nInitially the queue consists of all arcs, then we pop off the arcs and make $X_i$ consistent with $X_j$. If $D_i$ is reduced, then we propagate to check arcs with $X_i$'s neighbors $X_k$.\n\nAC-3 time complexity: $O(cd^3)$ where $c$=# of arc constraints, $d$=max domain size.\n\nTo be path consistent, both ($X_i$, $X_m$) and ($X_m$, $X_j$) needs to be arc consistent.\n\nTime complexity for strongly k-consistent CSP is $O(n^2d)$.\n\nFor alldiff CSPs, an early failure is detected if if at any point an empty domain is produeced.\n\nIn large-scale resource-limited CSPs, domains are represented using bounds and managed by bounds propagation.\n\nWhen seeing naked triplets in Sudoku, we can remove the three numbers from the domain of every other cell in the unit.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nCSPs are commutative, so the search tree has $d^n$ leaves, not $n! \\cdot d^n$.\n\nBacktracking search for CSP involves repeatedly choosing an unassigned variable, tries one value in its domain, trying to it into a solution. If success, solution is returned, if failure, the assignment is restored to previous state and try the next value.\n\nHeuristics that can be used when searching in CSPs include: minimum-remaining-value (variable fail-first), degree (tie breaking), least-constraining-value (value fail-last).\nMAC is more strict than forward checking because forward checking does not recursively propagate constraints when changes are made to the domains of variables.\n\nIn intelligent backtracking, we create a conflict set and backtrack to the most recent assignment in the conflict set (called backjumping). The conflict set can be supplied as part of forward checking.\n\nWe record no-good variables as part of constraint learning to avoid running into the same assignment again.\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nWe can apply min-conflicts heuristic to select the value that results in the least number of conflicts with other variables.\n\nRun time for min-conflicts is independently of problem size.\n\nIn constraint weighting, each constraint is given a weight (initially 1), and we prioritize the variable/value pair that results in the lowest total weight of all violated constraints.\n\nThe weights are incremented by the weight of each constraint that is violated.\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nEach connected component of the constraint graph corresponds to a subproblem in CSP.\n\nAny tree-structured CSP can be solved in time linear in the number of variables because we don't have to backtrack.\n\nIn cutset conditioning, we assign values to some variables (cycle cutset) so that the remaining variables form a tree.\n\nOnce cycle cutset is assigned (\"removed\"), remove any inconsistent arcs from the domains of the remaining variables and see if the remaining CSP has a solution.\n\nCuset conditioning CSP run time is $O(d^c \\cdot (n-c)d^2)$, note however finding the smallest cycle cutset is NP-hard.\n\nIn tree decomposition, we transform the original graph into a tree where each node in the tree consists of a set of variables with 3 criterias:\n- every variable must appear at least once\n- must appear together if connected by a constraint\n- must appear in every node along the path\nTree decomposition CSP run time is $O(nd^{w+1})$, note however finding the minimal tree decomposition is NP-hard.\n\nCSPs with constraint graphs of bounded tree width are solvable in poly time.\n\nTree decomposition is better in terms of time complexity, while cutset conditioning is more memory efficient.\n\nValue symmetry can be broken with symmetry-breaking constraint by imposing an arbitrary ordering; also NP-hard to eliminate all symmetry.\n\n\n\n## Module 6 Lecture Notes\n\nCSPs knows where to focus the search and can automatically prune off branches that violate constraints.\n\nCSPs as search problem:\n- initial state: empty assignment\n- successor function: assign value to unassigned variables that doesn't violate constraint\n- goal test: assignment is complete and consistent\n- path cost: constant cost every step\nSolution for CSPs is always found at depth n, for n variables.\n\nTo improve backtracking efficiency, use following heuristics:\n- assign most constrained variable next (most constraining if ties)\n- try least constraining value first for unassigned variables\n- do forward checking to detect possible failure\nIn forward checking, keep track of remaining legal values for unassigned variables and terminate search whenever any domain becomes empty.\n\nConstraint propagation repeatedly enforces arc consistency locally. If X loses a value recheck on all its neighbors. Takes $O(d^2)$ time in the worst case.\n\nAC-3 works to place all the arcs in a queue. Pop arcs. For each arc, remove inconsistent values. If we change the values of a node, add its arcs to the queue. Terminate when the queue is empty.\n\nAC-3 worst case time complexity is $O(n^2d^3)$ (with a complete graph).\nMAC is a way of interleaving search and inference. AC-3 is pure inference. MAC runs while assigning variables in backtracking search. Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3.\n\nMAC recursively propogrates constraints, whereas forward checking does not. MAC does this, and if the domain of a variable YY changes, does the same for YY (and so on...) .\n\nSolving a tree-structued CSP takes O(n) time in the number of variables.\n\nTree decomposition subproblems are efficient if the tree width of the constraint graph is small.\n\n\n\n## Module 6 Definitions\n* **Arc consistency** - there is some value in domain j that satsifies the binary constraint for every value in the current domain i\n* **Backjumping** - intelligently backtrack to the most recent assignment in the conflict set\n* **Bound consistency** - there exists some value Y that satisifies the upper and lower bound constraints for every variable X\n* **Commutativity** - when the order of application of any given set of actions does not matter\n* **Constraint learning** - find the minimum set of variables (no-good）from conflict set that causes the problem\n* **Constraint propagation** - use constraints to reduce the number of legal values for one variable, which in turn does the same for another\n* **Constraint weighting** - concentrates the search on the important constraints\n* **Csp** - given a set of variables, a problem is solved when each var has a valuethat satisfies all constraints\n* **Cutset conditioning** - used to reduce a general CSP to a tree structured one; more space efficient (linear)\n* **Degree heuristic** - choose the variable involed in the largest number of constraints on other unassigned variables; useful for tie-breaking\n* **Directional arc consistency (dac)** - iff every $X_i$ is arc-consistency with each $X_j$ for $j>i$\n* **Factored representation** - a set of variables, each of which has a value\n* **Forward checking** - delete from $D_y$ values that are inconsistent with value chosen for X\n* **Global constraint** - a constraint involving an arbitrary number of variables (not necessary all)\n* **K consistency** - a consistent value can be assigned to kth variable given k-1 consistency\n* **Least-constraining-value (lcv)** - orders the values in the domain such that fewest choices for neighboring variables are ruled out\n* **Linear programming** - best-known category of continous-domain CSPs\n* **Maintaining arc consistency (mac)** - calls AC-3 on arcs that contain unassigned variables that $X_i$'s neighbors\n* **Min-conflicts** - a heuristic that selects the value that results in the least number of conflicts with other variables\n* **Minimum-remaining-value (mrv)** - a heuristic that chooses the variable with the fewest legal moves\n* **Naked triplets** - three cells that each have a domain with the same 3 numbers or a subset in sudoku\n* **Node consistency** - all values in the variable's domain satisfy the variable's unary constraints\n* **Path consistency** - use implicit constraints that are inferred by triples of variables\n* **Preference constraints** - soft constraints that indicate which solutions are preferred\n* **Tree decomposition** - used to transfrom CSP into a tree of subproblems; more time efficient\n* **Solution** - a consistent, complete assignment to CSP\n* **Strongly k consistency** - k consistent and k-1 consistent and k-2 consistent, etc.\n* **Value symmetry** - existence of a set of $d!$ solutions formed by permutation\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nEach sentence in KB is expressed in knowledge representation language that represents some assertions about the world.\n\nInference is the process of deriving new sentences from old.\n\nThe knowledge base (KB) is maintained by the agent, and may start with some background knowledge.\n\nIn the declarative approach, the designer tells sentences to the agent until the agent has enough knowledge to operate in the environment.\n\nIn the procedural approach, the designer encodes desired behaviors directly as program code.\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\nIn the wumpus world, there is performance measure, an environment. The agent has actuators and sensors.\n\nThe percepts are often given to agent in the form of list of symbols.\n\nThe wumpus world is deterministic, discrete, static, single-agent and partially observable.\n\nLogic reasoning ensures that in each case for which the agent draws a conclusion from the available info, that conclusion is guaranteed to be correct if the available info is correct.\n\n\n\n## AIMA Chapter 7.3 Logic\n\nIf a sentence α is true in model m: m satisifes α or m is model of α. $M(α)$ means the set of all models of α.\n\nα entails β means sentence β follows logically from sentence α.\n\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nPropositional entailment is co-NP-complete, so every known inference algorithm for propsitional logic has a worst-case complexity that is exponential in the size of the input.\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nWith large models and short proofs, theorem proving can be more efficient than model checking.\n\n\n\n## Module 7 Lecture Notes\n\nA logic defines the semantics (meaning) of the sentences, which defines the truth of each sentence with respect to a possible world, which we call a model.\n\nLogical entailment in possible worlds: $KB ⊨ α$ iff $M(KB) ⊆ M(α)$, KB needs to be a subset of α here.\n\nPropositional symbols stand for a statement that can be true or false.\n\nLogical inference in possible worlds: $KB ⊢_i α$ if an inference algo i allows us to conclude that α is true (α is derived from KB by i).\n\nMonotonicity implies soundness.\n\nResolution is a single inference rule that guarantees completeness.\n\nSteps to arrive at CNF:\n- eliminate ⟺ by replacing α ⟺ β with (α ⟹ β) ∧ (β ⟹ α)\n- eliminate ⟹ by replacing α ⟹ β with ¬α ∨ β\n- eliminate any double negations, apply De Morgan's rules\n- apply distributivity law to distribute ∨ over ∧ wherever possible\nIn resolution algorithm, we need to show that KB ∧ ¬α is unsatisfiable (proof by contradiction); if two clauses resolve to yield the empty clause, then KB does ential α.\n\n\n\n\n\n## Module 7 Definitions\n* **Axiom** - a sentence taken as being given without being derived from other sentences\n* **Backward chaining** - goal-directed reasoning; start with a query and finds implications in the KB that leads to the query\n* **Completeness** - any sentence that is entailed can be derived\n* **Conjunctive normal form (cnf)** - a sentence expressed as a conjunction of clauses\n* **Declarative approach** - agent is being told what it needs to know\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Entailment** - a sentence follows logically from another sentence\n* **Forward chaining** - data-driven reasoning; start with known data, adding premises based on new percepts\n* **Grounding** - connection between logical reasoning processes and the real environment\n* **Horn clause** - disjunction of literals where at most one is positive; closed under resolution\n* **Knowledge base (kb)** - a set of sentences where each represents some assertion about the world\n* **Logical equivalence** - if two sentences α and β are true in the same set of models (α ≡ β)\n* **Logical inference** - how definition of entailment can be applied to derive conclusions\n* **Model checking** - enumerate over all possible models to check that α is true in all models in which KB is true\n* **Procedural approach** - agent is being encoded the desired behaviors as program code\n* **Resolution** - if l and m are complementary literals (negation of each other), eliminate them via unit resolution\n* **Satisfiability** - if a setence is true in/satisfied by some model\n* **Soundness** - truth-preserving, when only entailed sentences are derived\n* **Theorem proving** - applying rules of inference directly to sentences in KB to construct a proof of the desired sentence\n* **Validity** - true in all models, necessarily true (tautologies)\n* **Wumpus world** - a cave consisting of rooms connected by passageways\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}