{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm_notes_kz.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": "fdca21e2-3b5c-413e-9f2f-e9ae36ab14d7"
      },
      "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": 1,
      "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": "51165fff-42a4-418d-932a-94bc964be08f"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"\n",
        "Definition: Game\n",
        "- Initial state\n",
        "- Player\n",
        "- Set of player's legal moves\n",
        "- Transition model - Defines state resulting from action a\n",
        "- Terminal test\n",
        "- Utility function - Defines final values to players\n",
        "\n",
        "Minimax algorithm:\n",
        "    if node is terminal_node:\n",
        "        return utility(node)\n",
        "    if MAX is playing:\n",
        "        value = -inf\n",
        "        update value based on max of children\n",
        "    if MIN is playing:\n",
        "        value = inf\n",
        "        update value based on min of children\n",
        "    return value\n",
        "\n",
        "Minimax: Time: O(b^m), Space: O(bm)\n",
        "\n",
        "Alpha-beta reduce b to b^0.5 in best-case, b^0.75 in random\n",
        "\n",
        "PROBCUT - Alpha-beta search w/ forward pruning of nodes likely outside of alpha-beta window\n",
        "\n",
        "Computers frequently use table lookup for openings/endings of complex games\n",
        "\n",
        "In stochastic games, there are no likely sequences of moves.\n",
        "\n",
        "$A \\succ B$: Agent prefers A over B \\\\\n",
        "$A \\sim B$: Agent is indifferent on A vs. B \\\\\n",
        "$A \\overset{\\succ}{\\sim} B$: Agent prefers A or is indifferent (i.e., doesn't prefer B) \\\\\n",
        "\n",
        "Note: Agent behaviour may be described by utility function, but the agent doesn't \n",
        "have to be maximizing it.\n",
        "\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 205\n",
            "The length in characters is 1091\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": 3,
      "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 = \"\"\"\"\"\" \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 = \"\"\"\"\"\"\n",
        "chapter27_2 = \"\"\"\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\"\"\"\n",
        "chapter2_2 = \"\"\"\"\"\"\n",
        "chapter2_3 = \"\"\"\"\"\"\n",
        "chapter2_4 = \"\"\"\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\"\"\"\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",
        "    \"Turing test\": \"\"\"Tests if machines can imitate human responses, requiring NLP, knowledge representation, reasoning, ML\"\"\", \n",
        "    \"Total Turing test\": \"Turing test + interaction with real-world (computer vision, robotics)\", \n",
        "    \"Value alignment problem\" : \"Alignment of human values with machine objectives\",\n",
        "    \"Weak AI\": \"Machines act as if they are intelligent\",\n",
        "    \"Strong AI\": \"Machines are actually thinking, not simulating\", \n",
        "    \"Qualification problem\": \"\"\"Difficulty of turning all requirements of behaviour to a set of comprehensive rules\"\"\", \n",
        "    \"Embodied cognition\": \"Studies brain in conjunction with the body, environment, etc.\", \n",
        "    \"Chinese room\": \"\"\"Searle argues that a machine that outputs patterns without true understanding isn't truly intelligent\"\"\", \n",
        "    \"Biological nautralism\": \"Low-level neuronal activity gives rise to mental states\", \n",
        "    \"Brain in a vat\": \"Dennett's thought experiment asserts that brain in a vat = computer, opposes chinese room\",\n",
        "    \"Agent\": \"Anything that can perceive with sensors and act with actuators in an environment\",   \n",
        "    \"Percept\": \"What an agent's sensors perceive\", \n",
        "    \"Percept sequence\": \"\"\"All of what an agent has previously observed, which, along with knowledge, guides an agent's actions\"\"\",\n",
        "    \"Agent function\": \"Maps percept sequences to an action, which determines an agent's behaviour\", \n",
        "    \"Agent program\": \"Actual implementation of an agent function (i.e., code, machine, etc.)\", \n",
        "    \"Rational agent\" : \"Agent that wants to achieve best outcome using available info\",\n",
        "    \"Consequentialism\": \"Agent's behaviour should be judged by the outcomes of its actions\", \n",
        "    \"Performance measure\": \"Way to judge optimality of an agent's actions + states\", \n",
        "    \"Autonomy\": \"Learning on its own to correct prior knowledge\", \n",
        "    \"Task environment\": \"A problem that an agent acts as the solution for\", \n",
        "    \"PEAS\": \"\"\"Performance measure, Environment, Actuators, Sensors, which describe a task environment\"\"\", \n",
        "    \"Fully observable\": \"Agents can perceive entirety of environment (perfect info)\",\n",
        "    \"Partially observable\": \"Agents can perceive part, but not all, of the environment\", \n",
        "    \"Stochastic\": \"Dealing with probabilities\", \n",
        "    \"Episodic\": \"Agent's experiences are divided into independent sections\", \n",
        "    \"Sequential\": \"Current decision is dependent on previous decision\", \n",
        "    \"Environment class\": \"\"\"Set of environments that share similarities but vary in particular ways that might affect agents\"\"\", \n",
        "    \"Agent architecture\": \"The physical hardware that an agent program runs on\", \n",
        "    \"Simple reflex agent\": \"Choose actions based on current percept\", \n",
        "    \"Transition model\": \"\"\"Knowledge about how agent affects world and how world changes independent from agent\"\"\", \n",
        "    \"Sensor model\": \"Knowledge about how an agent perceives the world\", \n",
        "    \"Model-based agent\": \"Uses transition and sensor model to update internal state and act\", \n",
        "    \"Goal-based agent\": \"Acts towards reaching a goal state through search\", \n",
        "    \"Utility function\": \"Internal way to quantify performance measure\", \n",
        "    \"Utility-based agent\": \"Uses utility function to make best action\", \n",
        "    \"Rational choice theory\": \"Group social behaviour emerges from individual, rational actors\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f4efdc1c-2c6a-4332-db2d-1f66f08f0842"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n\n## AIMA 2.1 Agents and Environments\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n\n## AIMA 2.3 The Nature of Environments\n\n\n## AIMA 2.4 The Structure of Agents\n\n\n## Module 1 Lecture Notes\n\n\n## Module 1 Definitions\n* **Turing test** - Tests if machines can imitate human responses, requiring NLP, knowledge representation, reasoning, ML\n* **Total turing test** - Turing test + interaction with real-world (computer vision, robotics)\n* **Value alignment problem** - Alignment of human values with machine objectives\n* **Weak ai** - Machines act as if they are intelligent\n* **Strong ai** - Machines are actually thinking, not simulating\n* **Qualification problem** - Difficulty of turning all requirements of behaviour to a set of comprehensive rules\n* **Embodied cognition** - Studies brain in conjunction with the body, environment, etc.\n* **Chinese room** - Searle argues that a machine that outputs patterns without true understanding isn't truly intelligent\n* **Biological nautralism** - Low-level neuronal activity gives rise to mental states\n* **Brain in a vat** - Dennett's thought experiment asserts that brain in a vat = computer, opposes chinese room\n* **Agent** - Anything that can perceive with sensors and act with actuators in an environment\n* **Percept** - What an agent's sensors perceive\n* **Percept sequence** - All of what an agent has previously observed, which, along with knowledge, guides an agent's actions\n* **Agent function** - Maps percept sequences to an action, which determines an agent's behaviour\n* **Agent program** - Actual implementation of an agent function (i.e., code, machine, etc.)\n* **Rational agent** - Agent that wants to achieve best outcome using available info\n* **Consequentialism** - Agent's behaviour should be judged by the outcomes of its actions\n* **Performance measure** - Way to judge optimality of an agent's actions + states\n* **Autonomy** - Learning on its own to correct prior knowledge\n* **Task environment** - A problem that an agent acts as the solution for\n* **Peas** - Performance measure, Environment, Actuators, Sensors, which describe a task environment\n* **Fully observable** - Agents can perceive entirety of environment (perfect info)\n* **Partially observable** - Agents can perceive part, but not all, of the environment\n* **Stochastic** - Dealing with probabilities\n* **Episodic** - Agent's experiences are divided into independent sections\n* **Sequential** - Current decision is dependent on previous decision\n* **Environment class** - Set of environments that share similarities but vary in particular ways that might affect agents\n* **Agent architecture** - The physical hardware that an agent program runs on\n* **Simple reflex agent** - Choose actions based on current percept\n* **Transition model** - Knowledge about how agent affects world and how world changes independent from agent\n* **Sensor model** - Knowledge about how an agent perceives the world\n* **Model-based agent** - Uses transition and sensor model to update internal state and act\n* **Goal-based agent** - Acts towards reaching a goal state through search\n* **Utility function** - Internal way to quantify performance measure\n* **Utility-based agent** - Uses utility function to make best action\n* **Rational choice theory** - Group social behaviour emerges from individual, rational actors\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 was developed in 1989 by Guido van Rossum and was inspired by ABC.  Python \n",
        "is quick to code with due to its simple syntax, can run on an platform, has many \n",
        "built in types (lists, dictionaries, sets), and has many libraries for data \n",
        "science.\n",
        "\n",
        "### Objects and Typing\n",
        "All data in Python are objects.  Each object has a fixed type; interpreter \n",
        "won't allow for incompatible actions, but will coerce types if necessary.  \n",
        "Python is dynamically typed, so types of variables are updated on assignment.  \n",
        "This is convenient to code with, but means that type errors are only caught in \n",
        "runtime.\n",
        "\n",
        "### Functions\n",
        "In Python, a function can be given default values for its arguments, which make \n",
        "them optional on function call.  These arguments must follow arguments that are \n",
        "not default.  Functions are dynamically scoped, so a function will see the most \n",
        "recently assigned value of a variable.\n",
        "Default arguments use the same default object each function call.  This matters \n",
        "for mutable objects like sets, which allows for memoization.\n",
        "Functions are also first-class objects, so they can be the argument of functions, \n",
        "the returned item, etc.  Functions that take in function arguments are called \n",
        "higher-order functions.\n",
        "\n",
        "### Classes\n",
        "In Python, multiple inheritance is supported.  To override inherited methods, \n",
        "add a new definition for the same function; use self if you want to call a \n",
        "parent's version of a function.\n",
        "\n",
        "### List/Set Comprehensions\n",
        "`[i for i in range(0, n)]` \n",
        "\n",
        "`{k:v for k, v in d.items()}`\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "    \"Tuple\": \"Immutable ordered sequence of mixed-type items\",\n",
        "    \"String\": \"Immutable sequence of 16-bit Unicode characters\", \n",
        "    \"List\": \"Mutable (can't be hashed) ordered sequence of mixed-type items\", \n",
        "    \"Dictionary\": \"Unordered map from hashable keys to values with O(1) add, lookup, update\", \n",
        "    \"*args\": \"Arbitrary number of non-keyword arguments\", \n",
        "    \"*kwargs\": \"Arbitrary number of keyword arguments\", \n",
        "    \"First-class objects\": \"Can be dynamically created, destroyed, used in a function, returned, etc.\", \n",
        "    \"Duck typing\": \"Allowing methods to called on item if it contains the methods\", \n",
        "    \"Iterator\": \"Has __next__(), use memory efficiently\", \n",
        "    \"Generator\": \"Iterator that runs until yield statement, continues where it left off, which is efficient\"\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 749
        },
        "outputId": "31ce4e10-e43c-4893-8da4-9442f54b23b6"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nPython was developed in 1989 by Guido van Rossum and was inspired by ABC.  Python \nis quick to code with due to its simple syntax, can run on an platform, has many \nbuilt in types (lists, dictionaries, sets), and has many libraries for data \nscience.\n\n### Objects and Typing\nAll data in Python are objects.  Each object has a fixed type; interpreter \nwon't allow for incompatible actions, but will coerce types if necessary.  \nPython is dynamically typed, so types of variables are updated on assignment.  \nThis is convenient to code with, but means that type errors are only caught in \nruntime.\n\n### Functions\nIn Python, a function can be given default values for its arguments, which make \nthem optional on function call.  These arguments must follow arguments that are \nnot default.  Functions are dynamically scoped, so a function will see the most \nrecently assigned value of a variable.\nDefault arguments use the same default object each function call.  This matters \nfor mutable objects like sets, which allows for memoization.\nFunctions are also first-class objects, so they can be the argument of functions, \nthe returned item, etc.  Functions that take in function arguments are called \nhigher-order functions.\n\n### Classes\nIn Python, multiple inheritance is supported.  To override inherited methods, \nadd a new definition for the same function; use self if you want to call a \nparent's version of a function.\n\n### List/Set Comprehensions\n`[i for i in range(0, n)]` \n\n`{k:v for k, v in d.items()}`\n\n\n## Module 2 Definitions\n* **Tuple** - Immutable ordered sequence of mixed-type items\n* **String** - Immutable sequence of 16-bit Unicode characters\n* **List** - Mutable (can't be hashed) ordered sequence of mixed-type items\n* **Dictionary** - Unordered map from hashable keys to values with O(1) add, lookup, update\n* ***args** - Arbitrary number of non-keyword arguments\n* ***kwargs** - Arbitrary number of keyword arguments\n* **First-class objects** - Can be dynamically created, destroyed, used in a function, returned, etc.\n* **Duck typing** - Allowing methods to called on item if it contains the methods\n* **Iterator** - Has __next__(), use memory efficiently\n* **Generator** - Iterator that runs until yield statement, continues where it left off, which is efficient\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",
        "The solution to a problem in a fully observable, deterministic, known environment\n",
        "is always a fixed sequence of actions.\n",
        "\n",
        "Definition of search problem:\n",
        "1. Set of possible states (state space)\n",
        "2. Initial state\n",
        "3. Goal state(s)\n",
        "4. Set of possible actions\n",
        "5. Transition model that describes what actions do\n",
        "6. Action cost function \n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Frontiers are implemented with some sort of queue (priority, FIFO, or LIFO/stack).\n",
        "\n",
        "Repeated states -> Risk of exponential runtime\n",
        "\n",
        "Ways to address this:\n",
        "1. Remember reached states to detect redundant paths, keep state's best path\n",
        "2. Ignore repeated states when irrelevant\n",
        "3. Check for cycles, not redundant paths\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "| Criterion   |    BFS     |  Uniform                  |    DFS     |Depth-limited| Iterative  |Bidirectional |\n",
        "| ----------- | ---------- | ------------------------- | ---------- | ----------- | ---------- | ------------ |\n",
        "| Complete?   | Yes        | Yes                       | No         | No          | Yes        | Yes          |\n",
        "|Cost-optimal?| Yes        | Yes                       | No         | No          | Yes        | Yes          |\n",
        "| Time        | $$O(b^d)$$ | $$O(b^{1 + C/\\epsilon})$$ | $$O(b^m)$$ | $$O(b^l)$$  | $$O(b^d)$$ |$$O(b^{d/2})$$|\n",
        "| Space       | $$O(b^d)$$ | $$O(b^{1 + C/\\epsilon})$$ | $$O(bm)$$  |  $$O(bl)$$  | $$O(bd)$$  |$$O(b^{d/2})$$|\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "Biggest issue with BFS is the memory requirement.\n",
        "\n",
        "(Large) search problems that are exponential w.r.t. time/space \n",
        "can't be solved by uninformed search.\n",
        "\n",
        "Uniform-cost search = Dijkstra's\n",
        "- C = Cost of optimal solution\n",
        "- e = Lower bound of cost of action\n",
        "- Strategy: Expand node with lowest total path cost\n",
        "    - Use priority queue ordered by path cost g(n)\n",
        "- Tests if node is goal when expanding it\n",
        "\n",
        "DFS:\n",
        "- m = Max depth of tree\n",
        "- Useful with limited space, no infinite paths, terminate wrong paths early\n",
        "\n",
        "Depth-limited search:\n",
        "- DFS at depth limit l\n",
        "    - l = d: Complete, optimal\n",
        "    - l < d: Incomplete\n",
        "    - l > d: Not optimal\n",
        "\n",
        "Iterative deepening search:\n",
        "- Repeat DFS at increasing depth limits\n",
        "- Complete, optimal\n",
        "\n",
        "Bidirectional search:\n",
        "- Algorithm traverses from both initial, goal states and traverses until they collide\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "    \"Problem-solving agent\": \"An agent that can formulate a plan via search\",\n",
        "    \"Search\": \"Process of generating a series of actions to a goal state\", \n",
        "    \"Atomic representation\": \"States of world have no internal structure (black box)\",  \n",
        "    \"Informed\": \"Able to estimate distance to goal\",  \n",
        "    \"Uninformed\": \"No information about distance to goal\",  \n",
        "    \"Path\": \"Sequence of actions\",  \n",
        "    \"Solution\": \"Path from initial state to a goal state\",  \n",
        "    \"Optimal solution\": \"Solution with lowest path cost out of all solutions\",  \n",
        "    \"Grid world problem\": \"Standardized problem where agents can move between cells\", \n",
        "    \"Travelling salesperson problem (TSP)\": \"Touring problem where every city must be visited with minimal cost\",  \n",
        "    \"VLSI layout\": \"Positioning components on chip to minimize area and maximize efficiency\",  \n",
        "    \"Search algorithm\": \"Returns a solution/failure for a given search problem\",  \n",
        "    \"Search tree\": \"Takes state-space graph and traverses, which turns it into a tree\",  \n",
        "    \"Node\": \"Vertex in search tree = State in state space\",  \n",
        "    \"Frontier\": \"Set of vertices which have been discovered but not expanded\",  \n",
        "    \"Best-first search\": \"General approach of choosing next node with lowest value from evaluation function\",  \n",
        "    \"Graph search\": \"Search problem that checks for redundant paths, which uses more memory but runs faster\", \n",
        "    \"Tree search\": \"Search problem that doesn't check for redundant paths, which uses less memory but runs slower\",  \n",
        "    \"Complete\": \"Algorithm that is guaranteed to find a solution and report when there is none\",  \n",
        "    \"Branching factor\": \"Number of successors that each node must consider\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "15372f04-34f2-43d2-c16e-c6b21a21f39f"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nThe solution to a problem in a fully observable, deterministic, known environment\nis always a fixed sequence of actions.\n\nDefinition of search problem:\n1. Set of possible states (state space)\n2. Initial state\n3. Goal state(s)\n4. Set of possible actions\n5. Transition model that describes what actions do\n6. Action cost function \n\n\n## AIMA Chapter 3.2 Example Problems\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nFrontiers are implemented with some sort of queue (priority, FIFO, or LIFO/stack).\n\nRepeated states -> Risk of exponential runtime\n\nWays to address this:\n1. Remember reached states to detect redundant paths, keep state's best path\n2. Ignore repeated states when irrelevant\n3. Check for cycles, not redundant paths\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n| Criterion   |    BFS     |  Uniform                  |    DFS     |Depth-limited| Iterative  |Bidirectional |\n| ----------- | ---------- | ------------------------- | ---------- | ----------- | ---------- | ------------ |\n| Complete?   | Yes        | Yes                       | No         | No          | Yes        | Yes          |\n|Cost-optimal?| Yes        | Yes                       | No         | No          | Yes        | Yes          |\n| Time        | $$O(b^d)$$ | $$O(b^{1 + C/\\epsilon})$$ | $$O(b^m)$$ | $$O(b^l)$$  | $$O(b^d)$$ |$$O(b^{d/2})$$|\n| Space       | $$O(b^d)$$ | $$O(b^{1 + C/\\epsilon})$$ | $$O(bm)$$  |  $$O(bl)$$  | $$O(bd)$$  |$$O(b^{d/2})$$|\n\n\n## Module 3 Lecture Notes\n\nBiggest issue with BFS is the memory requirement.\n\n(Large) search problems that are exponential w.r.t. time/space \ncan't be solved by uninformed search.\n\nUniform-cost search = Dijkstra's\n- C = Cost of optimal solution\n- e = Lower bound of cost of action\n- Strategy: Expand node with lowest total path cost\n    - Use priority queue ordered by path cost g(n)\n- Tests if node is goal when expanding it\n\nDFS:\n- m = Max depth of tree\n- Useful with limited space, no infinite paths, terminate wrong paths early\n\nDepth-limited search:\n- DFS at depth limit l\n    - l = d: Complete, optimal\n    - l < d: Incomplete\n    - l > d: Not optimal\n\nIterative deepening search:\n- Repeat DFS at increasing depth limits\n- Complete, optimal\n\nBidirectional search:\n- Algorithm traverses from both initial, goal states and traverses until they collide\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - An agent that can formulate a plan via search\n* **Search** - Process of generating a series of actions to a goal state\n* **Atomic representation** - States of world have no internal structure (black box)\n* **Informed** - Able to estimate distance to goal\n* **Uninformed** - No information about distance to goal\n* **Path** - Sequence of actions\n* **Solution** - Path from initial state to a goal state\n* **Optimal solution** - Solution with lowest path cost out of all solutions\n* **Grid world problem** - Standardized problem where agents can move between cells\n* **Travelling salesperson problem (tsp)** - Touring problem where every city must be visited with minimal cost\n* **Vlsi layout** - Positioning components on chip to minimize area and maximize efficiency\n* **Search algorithm** - Returns a solution/failure for a given search problem\n* **Search tree** - Takes state-space graph and traverses, which turns it into a tree\n* **Node** - Vertex in search tree = State in state space\n* **Frontier** - Set of vertices which have been discovered but not expanded\n* **Best-first search** - General approach of choosing next node with lowest value from evaluation function\n* **Graph search** - Search problem that checks for redundant paths, which uses more memory but runs faster\n* **Tree search** - Search problem that doesn't check for redundant paths, which uses less memory but runs slower\n* **Complete** - Algorithm that is guaranteed to find a solution and report when there is none\n* **Branching factor** - Number of successors that each node must consider\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: Lowest complexity = O(bm) for certain problems/heuristics\n",
        "- Not complete in infinite spaces\n",
        "\n",
        "A* with inadmissible heuristic produces satisfying solution with fewer expanded states\n",
        "\n",
        "Downside: A* uses exponential memory, can be improved by:\n",
        "- No duplicates between frontier, reached\n",
        "- Eliminate reached\n",
        "- Reference counts to remove states when no more ways to reach it\n",
        "\n",
        "IDA*/RBFS - Not enough memory -> Revisits states\n",
        "\n",
        "Lack of memory can make some problems unsolvable in terms of runtime\n",
        "\n",
        "Bidirectional > A* with average heuristic, not with great or poor heuristic\n",
        "\n",
        "| Criterion   |   Greedy   |     A*     |    IDA*    |    RBFS    |    SMA*    |Bidirectional |\n",
        "| ----------- | ---------- | -----------| ---------- | ---------- | ---------- | ------------ |\n",
        "| Complete?   | No         | Yes        | Yes        | Yes        | Yes        | Yes          |\n",
        "|Cost-optimal?| No         | Yes        | Yes        | Yes        | Yes        | Yes          |\n",
        "| Time        | $$O(b^d)$$ | $$O(b^d)$$ | $$O(b^m)$$ | $$O(b^m)$$ | $$O(b^d)$$ |$$O(b^{d/2})$$|\n",
        "| Space       | $$O(b^d)$$ | $$O(b^d)$$ | $$O(bm)$$  |  $$O(d)$$  |  $$O(x)$$  |$$O(b^{d/2})$$|\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "The cost function of an optimal solution for a relaxed problem is an \n",
        "admissible heuristic for the original problem.\n",
        "\n",
        "Some heuristics can be discovered through experience - Machine learning\n",
        "- May not be admissible, but approximates true path cost well\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "    \"Heuristic function h(n)\": \"Estimated cost of cheapest path from the state at node n to goal state\", \n",
        "    \"Greedy best-first search\": \"Expands node with lowest h(n) first\", \n",
        "    \"Straight-line distance\": \"Possible heuristic for route finding\", \n",
        "    \"A* search\": \"Best first search with (admissible for cost-optimality) f(n) = estimated cost of best path (g(n) + h(n))\", \n",
        "    \"Admissible/optimistic\": \"Never overestimates the cost to reach a goal\", \n",
        "    \"Consistent\": \"h(n) <= Cost(n, a, n') + h(n')\", \n",
        "    \"Pruning\": \"Removing search tree nodes that don't need to be expanded to reduce search space\", \n",
        "    \"Satisficing\": \"Suboptimal solutions that are good enough\", \n",
        "    \"Weighted A* search\": \"A* with f(n) = g(n) + W * h(n)\", \n",
        "    \"Bounded suboptimal search\": \"Searches for solution within a constant factor of optimal cost\", \n",
        "    \"Bounded-cost search\": \"Searches for solution with cost < C\",\n",
        "    \"Unbounded-cost search\": \"Prioritizes solution that is found quickly\", \n",
        "    \"Speedy search\": \"Example of unbounded-cost + greedy best-first search, uses h(n) estimated number of actions to reach goal\", \n",
        "    \"Beam search\": \"Limits size of the frontier by keeping nodes with best f(n) or within a margin\", \n",
        "    \"Iterative-deepening A* search\": \"Explores nodes in paths using f(n) as cutoff, increasing continuously\", \n",
        "    \"Recursive best-first search\": \"DFS, tracks f(n) of best alternative path from ancestor in path, allowing for reexpansion later in linear space\", \n",
        "    \"Backed-up value\": \"Best f(n) of its children in RBFS\", \n",
        "    \"Simplified memory-bounded A*\": \"A*, prunes nodes from queue with highest f(n), remembers best pruned path to regenerate if needed, linear\", \n",
        "    \"Bidirectional heuristic search\": \"Two heuristics, frontiers to select nodes from front and back - Max cost of C/2 for one side\", \n",
        "    \"Front-to-end\": \"Bidirectional with heuristics estimating distance to goal/start\", \n",
        "    \"Front-to-front\": \"Bidirectional with heuristics estimating distance to frontier, very computationally intensive\", \n",
        "    \"Effective branching factor\": \"Branching factor that a uniform tree with depth d needs for N explored nodes\", \n",
        "    \"Effective depth\": \"Reduced by A* pruning\", \n",
        "    \"Domination\": \"If h1(n) >= h2(n), h1 dominates h2, making it preferred as a heuristic\", \n",
        "    \"Relaxed problem\": \"Problem with fewer restrictions on actions\", \n",
        "    \"Pattern database\": \"Take maximium heuristic of exact solution costs of subproblems\", \n",
        "    \"Disjoint pattern databases\": \"Count each move at most 1 time so that the costs can be added\", \n",
        "    \"Precomputation\": \"Calculate certain optimal path costs once and use the results many times\", \n",
        "    \"Landmark point\": \"Selected points to precompute path costs to/from to create an inadmissible heuristic\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "ddf44080-fae9-48a9-a947-b818289ec194"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nGreedy: Lowest complexity = O(bm) for certain problems/heuristics\n- Not complete in infinite spaces\n\nA* with inadmissible heuristic produces satisfying solution with fewer expanded states\n\nDownside: A* uses exponential memory, can be improved by:\n- No duplicates between frontier, reached\n- Eliminate reached\n- Reference counts to remove states when no more ways to reach it\n\nIDA*/RBFS - Not enough memory -> Revisits states\n\nLack of memory can make some problems unsolvable in terms of runtime\n\nBidirectional > A* with average heuristic, not with great or poor heuristic\n\n| Criterion   |   Greedy   |     A*     |    IDA*    |    RBFS    |    SMA*    |Bidirectional |\n| ----------- | ---------- | -----------| ---------- | ---------- | ---------- | ------------ |\n| Complete?   | No         | Yes        | Yes        | Yes        | Yes        | Yes          |\n|Cost-optimal?| No         | Yes        | Yes        | Yes        | Yes        | Yes          |\n| Time        | $$O(b^d)$$ | $$O(b^d)$$ | $$O(b^m)$$ | $$O(b^m)$$ | $$O(b^d)$$ |$$O(b^{d/2})$$|\n| Space       | $$O(b^d)$$ | $$O(b^d)$$ | $$O(bm)$$  |  $$O(d)$$  |  $$O(x)$$  |$$O(b^{d/2})$$|\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe cost function of an optimal solution for a relaxed problem is an \nadmissible heuristic for the original problem.\n\nSome heuristics can be discovered through experience - Machine learning\n- May not be admissible, but approximates true path cost well\n\n\n## Module 4 Lecture Notes\n\n\n## Module 4 Definitions\n* **Heuristic function h(n)** - Estimated cost of cheapest path from the state at node n to goal state\n* **Greedy best-first search** - Expands node with lowest h(n) first\n* **Straight-line distance** - Possible heuristic for route finding\n* **A* search** - Best first search with (admissible for cost-optimality) f(n) = estimated cost of best path (g(n) + h(n))\n* **Admissible/optimistic** - Never overestimates the cost to reach a goal\n* **Consistent** - h(n) <= Cost(n, a, n') + h(n')\n* **Pruning** - Removing search tree nodes that don't need to be expanded to reduce search space\n* **Satisficing** - Suboptimal solutions that are good enough\n* **Weighted a* search** - A* with f(n) = g(n) + W * h(n)\n* **Bounded suboptimal search** - Searches for solution within a constant factor of optimal cost\n* **Bounded-cost search** - Searches for solution with cost < C\n* **Unbounded-cost search** - Prioritizes solution that is found quickly\n* **Speedy search** - Example of unbounded-cost + greedy best-first search, uses h(n) estimated number of actions to reach goal\n* **Beam search** - Limits size of the frontier by keeping nodes with best f(n) or within a margin\n* **Iterative-deepening a* search** - Explores nodes in paths using f(n) as cutoff, increasing continuously\n* **Recursive best-first search** - DFS, tracks f(n) of best alternative path from ancestor in path, allowing for reexpansion later in linear space\n* **Backed-up value** - Best f(n) of its children in RBFS\n* **Simplified memory-bounded a*** - A*, prunes nodes from queue with highest f(n), remembers best pruned path to regenerate if needed, linear\n* **Bidirectional heuristic search** - Two heuristics, frontiers to select nodes from front and back - Max cost of C/2 for one side\n* **Front-to-end** - Bidirectional with heuristics estimating distance to goal/start\n* **Front-to-front** - Bidirectional with heuristics estimating distance to frontier, very computationally intensive\n* **Effective branching factor** - Branching factor that a uniform tree with depth d needs for N explored nodes\n* **Effective depth** - Reduced by A* pruning\n* **Domination** - If h1(n) >= h2(n), h1 dominates h2, making it preferred as a heuristic\n* **Relaxed problem** - Problem with fewer restrictions on actions\n* **Pattern database** - Take maximium heuristic of exact solution costs of subproblems\n* **Disjoint pattern databases** - Count each move at most 1 time so that the costs can be added\n* **Precomputation** - Calculate certain optimal path costs once and use the results many times\n* **Landmark point** - Selected points to precompute path costs to/from to create an inadmissible heuristic\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",
        "Definition: Game\n",
        "- Initial state\n",
        "- Player\n",
        "- Set of player's legal moves\n",
        "- Transition model - Defines state resulting from action a\n",
        "- Terminal test\n",
        "- Utility function - Defines final values to players\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Minimax algorithm:\n",
        "    if node is terminal_node:\n",
        "        return utility(node)\n",
        "    if MAX is playing:\n",
        "        value = -inf\n",
        "        update value based on max of children\n",
        "    if MIN is playing:\n",
        "        value = inf\n",
        "        update value based on min of children\n",
        "    return value\n",
        "\n",
        "Minimax: Time: O(b^m), Space: O(bm)\n",
        "\n",
        "Alpha-beta reduce b to b^0.5 in best-case, b^0.75 in random\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "PROBCUT - Alpha-beta search w/ forward pruning of nodes likely outside of alpha-beta window\n",
        "\n",
        "Computers frequently use table lookup for openings/endings of complex games\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "In stochastic games, there are no likely sequences of moves.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "$A \\succ B$: Agent prefers A over B \\\\\n",
        "$A \\sim B$: Agent is indifferent on A vs. B \\\\\n",
        "$A \\overset{\\succ}{\\sim} B$: Agent prefers A or is indifferent (i.e., doesn't prefer B) \\\\\n",
        "\n",
        "Note: Agent behaviour may be described by utility function, but the agent doesn't \n",
        "have to be maximizing it.\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "Human life = $10 million \\\\\n",
        "Utility of money = log(money) (under 1 million) \\\\\n",
        "Optimizer's curse resolved with Bayesian probability model \\\\\n",
        "Displaying problems in ways aligned with our evolution typically results in \n",
        "more rational decisions by humans.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "    \"Adversarial search\": \"Search problem involving 2+ agents in competition\", \n",
        "    \"Perfect-information\": \"Fully observable\", \n",
        "    \"Zero-sum\": \"When one player improves, the other player(s) must lose\", \n",
        "    \"Minimax search\": \"Search algorithm to minimize possible loss in a game\", \n",
        "    \"Ply\": \"A player's move\", \n",
        "    \"Minimax value\": \"Utility of MAX at a state assuming that both players play optimally\", \n",
        "    \"Alpha-beta pruning\": \"Technique to limit number of nodes explored in minimax\", \n",
        "    \"alpha\": \"Highest value choice discovered so far - At least\", \n",
        "    \"beta\": \"Lowest value choice discovered so far - At most\", \n",
        "    \"Killer move\": \"Best moves in game\", \n",
        "    \"Transposition\": \"Permutation of sequence of moves leading to same position\", \n",
        "    \"Type A strategy\": \"Wide but shallow exploration of search tree, use heuristic at max depth\", \n",
        "    \"Type B strategy\": \"Deep but narrow exploration\", \n",
        "    \"Heuristic alpha-beta\": \"Replace UTILITY with EVAL heuristic, terminal test with cutoff test\", \n",
        "    \"Weighted linear function\": \"Type of evaluation function\", \n",
        "    \"Quiescent\": \"No potential move that would change the evaluation greatly\", \n",
        "    \"Quiescence search\": \"Frequently considers moves that seek to resolve uncertainties and reach quiescent states\", \n",
        "    \"Horizon effect\": \"Player can deploy strategy to delay an inevitable outcome\", \n",
        "    \"Singular extension\": \"Corrects for horizon effect by allowing for better moves to be played after stopping point\", \n",
        "    \"Forward pruning\": \"Reduces runtime by eliminating moves that seem bad early in-exchange for suboptimal results\", \n",
        "    \"Late move reduction\": \"Reduces depth to explore fewer late moves, which are less likely to be strong choices\", \n",
        "    \"Stochastic games\": \"Games with random elements involved\", \n",
        "    \"Chance nodes\": \"States with some probability attached\", \n",
        "    \"Expectiminimax value\": \"Minimax, calculate expected value for chance nodes\", \n",
        "    \"Decision theory\": \"Choosing actions based on the optimality of their immediate outcomes\", \n",
        "    \"Principle of maximum expected utility (MEU)\": \"Rational agents choose actions that maximize expected utility\",\n",
        "    \"Lottery\": \"Set of outcomes with probabilities associated with them\",\n",
        "    \"Orderability\": \"Constraint that agent must decide, $(A \\succ B) \\lor (B \\succ A) \\lor (A \\sim B)$\",\n",
        "    \"Transitivity\": \"Constraint where $(A \\succ B) \\land (B \\succ C) \\implies (A \\succ C)$\",\n",
        "    \"Continuity\": \"Constraint where $A \\succ B \\succ C \\implies p [p, A: (1 - p), C] \\sim B$\",\n",
        "    \"Substitutability\": \"Constraint that if agent is indifferent to A and B, they can be swapped freely\",\n",
        "    \"Monotonicity\": \"Constraint that if $A \\succ B$, agent prefers the lottery that has more A\",\n",
        "    \"Decomposability\": \"Constraint that compound lotteries can be reduced to less complex ones\",\n",
        "    \"Existence of Utility function\": \"A utility function that matches preferences exists ($U(A) > U(B) \\iff A \\succ B$)\",\n",
        "    \"Value (ordinal utility) function\": \"A utility function where relative order is the key metric\",\n",
        "    \"Preference elicitation\": \"Process of determining a human's utility function\",\n",
        "    \"Normalized utilities\": \"Worst U(S) = u_{\\bot} = 0, best U(S) = u_{\\top} = 1\",\n",
        "    \"Standard lottery\": \"$[p, u_{\\top}; (1 - p), u_{\\bot}]$, frequently used to determine preferences\",\n",
        "    \"Micromort\": \"Unit for safety analysis = 1 in a million chance of death\",\n",
        "    \"Quality-adjusted life year (QALY)\": \"Metric of year of life, weighted by quality of life\",\n",
        "    \"Monotonic preference\": \"Prefer more to less (i.e., money)\",\n",
        "    \"Expected monetary value (EMV)\": \"Expected value of money gained\",\n",
        "    \"Risk-averse\": \"Prefer guaranteed pay-off over a gamble ($U(L) < U(S_{EMV(L)}$)\",\n",
        "    \"Risk-seeking\": \"Prefer gamble for more money than less guaranteed money\", \n",
        "    \"Certainty equivalent\": \"Guaranteed value that an agent takes instead of a lottery\", \n",
        "    \"Insurance premium\": \"Difference between EMV and certainty equivalent\", \n",
        "    \"Risk-neutral\": \"Linear utility function, which is true for small changes\", \n",
        "    \"Unbiased\": \"Expected value of error = 0\", \n",
        "    \"Order statistic\": \"Distribution of any particular ranked element of a sample\", \n",
        "    \"Optimizer's curse\": \"Estimated expected utility of best choice when utility maximizing is too high due to variance\", \n",
        "    \"Normative theory\": \"How a rational agent should act\", \n",
        "    \"Descriptive theory\": \"How an agent does act\", \n",
        "    \"Certainty effect\": \"Humans prefer certain gains due to potential regret, ease, etc.\", \n",
        "    \"Ambiguity aversion\": \"Humans prefer known probabilities over unknown ones\", \n",
        "    \"Framing effect\": \"Way in which problems are worded skew perception of them\", \n",
        "    \"Anchoring effect\": \"Humans prefer making relative utility judgments over absolute ones\", \n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7c61e1d9-0cfd-4ec4-b888-c2214ac74e58"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nDefinition: Game\n- Initial state\n- Player\n- Set of player's legal moves\n- Transition model - Defines state resulting from action a\n- Terminal test\n- Utility function - Defines final values to players\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax algorithm:\n    if node is terminal_node:\n        return utility(node)\n    if MAX is playing:\n        value = -inf\n        update value based on max of children\n    if MIN is playing:\n        value = inf\n        update value based on min of children\n    return value\n\nMinimax: Time: O(b^m), Space: O(bm)\n\nAlpha-beta reduce b to b^0.5 in best-case, b^0.75 in random\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nPROBCUT - Alpha-beta search w/ forward pruning of nodes likely outside of alpha-beta window\n\nComputers frequently use table lookup for openings/endings of complex games\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nIn stochastic games, there are no likely sequences of moves.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n$A \\succ B$: Agent prefers A over B \\\n$A \\sim B$: Agent is indifferent on A vs. B \\\n$A \\overset{\\succ}{\\sim} B$: Agent prefers A or is indifferent (i.e., doesn't prefer B) \\\n\nNote: Agent behaviour may be described by utility function, but the agent doesn't \nhave to be maximizing it.\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nHuman life = $10 million \\\nUtility of money = log(money) (under 1 million) \\\nOptimizer's curse resolved with Bayesian probability model \\\nDisplaying problems in ways aligned with our evolution typically results in \nmore rational decisions by humans.\n\n\n## Module 5 Lecture Notes\n\n\n## Module 5 Definitions\n* **Adversarial search** - Search problem involving 2+ agents in competition\n* **Perfect-information** - Fully observable\n* **Zero-sum** - When one player improves, the other player(s) must lose\n* **Minimax search** - Search algorithm to minimize possible loss in a game\n* **Ply** - A player's move\n* **Minimax value** - Utility of MAX at a state assuming that both players play optimally\n* **Alpha-beta pruning** - Technique to limit number of nodes explored in minimax\n* **Alpha** - Highest value choice discovered so far - At least\n* **Beta** - Lowest value choice discovered so far - At most\n* **Killer move** - Best moves in game\n* **Transposition** - Permutation of sequence of moves leading to same position\n* **Type a strategy** - Wide but shallow exploration of search tree, use heuristic at max depth\n* **Type b strategy** - Deep but narrow exploration\n* **Heuristic alpha-beta** - Replace UTILITY with EVAL heuristic, terminal test with cutoff test\n* **Weighted linear function** - Type of evaluation function\n* **Quiescent** - No potential move that would change the evaluation greatly\n* **Quiescence search** - Frequently considers moves that seek to resolve uncertainties and reach quiescent states\n* **Horizon effect** - Player can deploy strategy to delay an inevitable outcome\n* **Singular extension** - Corrects for horizon effect by allowing for better moves to be played after stopping point\n* **Forward pruning** - Reduces runtime by eliminating moves that seem bad early in-exchange for suboptimal results\n* **Late move reduction** - Reduces depth to explore fewer late moves, which are less likely to be strong choices\n* **Stochastic games** - Games with random elements involved\n* **Chance nodes** - States with some probability attached\n* **Expectiminimax value** - Minimax, calculate expected value for chance nodes\n* **Decision theory** - Choosing actions based on the optimality of their immediate outcomes\n* **Principle of maximum expected utility (meu)** - Rational agents choose actions that maximize expected utility\n* **Lottery** - Set of outcomes with probabilities associated with them\n* **Orderability** - Constraint that agent must decide, $(A \\succ B) \\lor (B \\succ A) \\lor (A \\sim B)$\n* **Transitivity** - Constraint where $(A \\succ B) \\land (B \\succ C) \\implies (A \\succ C)$\n* **Continuity** - Constraint where $A \\succ B \\succ C \\implies p [p, A: (1 - p), C] \\sim B$\n* **Substitutability** - Constraint that if agent is indifferent to A and B, they can be swapped freely\n* **Monotonicity** - Constraint that if $A \\succ B$, agent prefers the lottery that has more A\n* **Decomposability** - Constraint that compound lotteries can be reduced to less complex ones\n* **Existence of utility function** - A utility function that matches preferences exists ($U(A) > U(B) \\iff A \\succ B$)\n* **Value (ordinal utility) function** - A utility function where relative order is the key metric\n* **Preference elicitation** - Process of determining a human's utility function\n* **Normalized utilities** - Worst U(S) = u_{\bot} = 0, best U(S) = u_{\top} = 1\n* **Standard lottery** - $[p, u_{\top}; (1 - p), u_{\bot}]$, frequently used to determine preferences\n* **Micromort** - Unit for safety analysis = 1 in a million chance of death\n* **Quality-adjusted life year (qaly)** - Metric of year of life, weighted by quality of life\n* **Monotonic preference** - Prefer more to less (i.e., money)\n* **Expected monetary value (emv)** - Expected value of money gained\n* **Risk-averse** - Prefer guaranteed pay-off over a gamble ($U(L) < U(S_{EMV(L)}$)\n* **Risk-seeking** - Prefer gamble for more money than less guaranteed money\n* **Certainty equivalent** - Guaranteed value that an agent takes instead of a lottery\n* **Insurance premium** - Difference between EMV and certainty equivalent\n* **Risk-neutral** - Linear utility function, which is true for small changes\n* **Unbiased** - Expected value of error = 0\n* **Order statistic** - Distribution of any particular ranked element of a sample\n* **Optimizer's curse** - Estimated expected utility of best choice when utility maximizing is too high due to variance\n* **Normative theory** - How a rational agent should act\n* **Descriptive theory** - How an agent does act\n* **Certainty effect** - Humans prefer certain gains due to potential regret, ease, etc.\n* **Ambiguity aversion** - Humans prefer known probabilities over unknown ones\n* **Framing effect** - Way in which problems are worded skew perception of them\n* **Anchoring effect** - Humans prefer making relative utility judgments over absolute ones\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:\n",
        "- $\\mathcal{X}$: Set of variables\n",
        "- $\\mathcal{D}$: Set of domains of allowed values per variable\n",
        "- $\\mathcal{C}$: Set of constraints\n",
        "\n",
        "CSP search algorithms are general, not domain-specific\n",
        "- Uses constraints to eliminate portions of search space\n",
        "- Difficult search problems often are solvable as CSPs\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "AC-3: Time = $O(c \\cdot d \\cdot d^2) = O(cd^3)$ - c arcs, d max domain size \\\\\n",
        "Constraint satisfaction is NP-complete, n-consistency requires exponential time/space\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "After constraint propagation, search or inference may still be needed to find a solution \\\\\n",
        "Simple backjumping and forward checking are redundant\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "Using independent subproblems goes from $O(d^n)$ runtime to $O(d^c \\cdot n/c)$\n",
        "- n variables total, c variables in CSP, d domain size\n",
        "Any tree-structured CSP can be solved in linear time in number of variables \\\\\n",
        "Tree decomposition - Solves tree CSP in $O(nd^2)$, domain is set of tuples:\n",
        "- Each original variable appears\n",
        "- Variables in constraints must be included in at least one tree node\n",
        "- If a variable appears in 2 nodes of tree, it must appear in all nodes along the path between the nodes\n",
        "CSPs with constraint graphs of bounded tree width have polynomial time solutions ($O(nd^{w + 1})$)\n",
        "Tree decomposition is faster, but requires exponential space in tree width - Cutset conditioning is linear space\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "Waltz/Mackworth Constraint Propagation:\n",
        "- Assign all nodes full domain\n",
        "- Repeat: For each node i and neighbors j, remove all values from i that aren't consistent with j\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "    \"Factored representation\": \"Representation of problem where we have internal information (set of variables with values)\", \n",
        "    \"Constraint satisfaction problem (CSP)\": \"Problem where each variable has a value that satisfies all restrictions on it\", \n",
        "    \"Scope\": \"Tuple of affected variables in constraint\", \n",
        "    \"Relation\": \"Defines restrictions on variables in scope\", \n",
        "    \"Assignment\": \"Setting of values for variables in CSPs\", \n",
        "    \"Consistent assignment\": \"An assignment that doesn't violate any constraints\", \n",
        "    \"Complete assignment\": \"An assignment that gives all variables a value\", \n",
        "    \"Solution\": \"A consistent, complete assignment\", \n",
        "    \"Partial assignment\": \"An assignment that doesn't assign values to all variables\", \n",
        "    \"Partial solution\": \"A consistent, partial assignment\", \n",
        "    \"Constraint graph\": \"Nodes = variables, edges = variables in a constraint\", \n",
        "    \"Precedence constraint\": \"Some tasks precede others in a constraint\", \n",
        "    \"Disjunctive constraint\": \"Or\", \n",
        "    \"Discrete, finite domains\": \"Simplest type of setting for CSP\",  \n",
        "    \"Linear constraints\": \"Constraints written as a linear combination\", \n",
        "    \"Nonlinear constraints\": \"Constraints with nonlinear relationship between variables, make problem undecidable\", \n",
        "    \"Linear programming problems\": \"Constraints are linear (in)equalities\", \n",
        "    \"Unary constraint\": \"One variable constraint\", \n",
        "    \"Binary constraint\": \"Two variable constraint\", \n",
        "    \"Binary CSP\": \"CSP with only unary and binary constraints\", \n",
        "    \"Global constraint\": \"Constraint with arbitrary number of variables\", \n",
        "    \"Dual graph\": \"Graph with variables as nodes, binary constraints as edges\", \n",
        "    \"Preference constraints\": \"Constraints that are desired to be satisfied, but not strictly required\", \n",
        "    \"Constrained optimization problem\": \"CSPs with preference constraints that can be solved with optimization search methods\", \n",
        "    \"Constraint propagation\": \"Use of CSP constraints to reduce the number of values that a variable can take\", \n",
        "    \"Local consistency\": \"Enforcing constraints in particular sections of graph\", \n",
        "    \"Node-consistent\": \"All values in the variable's domain satisfy the variable's unary constraints\", \n",
        "    \"Arc-consistent\": \"A variable with each value in its domain satisfying its binary constraints\", \n",
        "    \"AC-3\": \"Algorithm to enforce arc consistency checking arcs in queue, removing invalid values, enqueueing neighbouring arcs \", \n",
        "    \"Path consistency\": \"Restricts binary constraints by implicit constraints inferred from variable triples\", \n",
        "    \"K-consistency\": \"Consistent value can always be assigned to kth variable for any consistent assignment to k - 1 variables\", \n",
        "    \"Strongly k-consistent\": \"k-consistent, (k - 1)-consistent, ..., 1-consistent\", \n",
        "    \"Alldiff\": \"Global constraint that all variables must have distinct values\", \n",
        "    \"Resource constraint (Atmost)\": \"Sum of values can't be above a certain threshold\", \n",
        "    \"Bounds propagation\": \"Domains represented by intervals\", \n",
        "    \"Bounds-consistent\": \"For each variable X, there exists a Y that satisfies X-Y constraint for every variable Y\", \n",
        "    \"Backtracking search\": \"Uninformed algorithm, uses DFS to assign values to variables, backtracks when no possible solution\", \n",
        "    \"Minimum-remaining values (MRV)\": \"Heuristic to choose variable with the fewest legal values\", \n",
        "    \"Degree heuristic\": \"Heuristic to select variable that constrains the most other variables\", \n",
        "    \"Least-constraining value\": \"Heuristic to select values that constrain the fewest possible values for other variables\", \n",
        "    \"Forward checking\": \"Inference, establishes arc consistency when a variable is assigned\",\n",
        "    \"Maintaining Arc Consistency (MAC)\": \"Inference, forward checks and runs pseudo-AC-3 to establish consistency for additional variables\",\n",
        "    \"Chronological backtracking\": \"Standard backtracking, where the most recent point is revisited\",\n",
        "    \"Conflict set\": \"The set of assignments that are in conflict with a new assignment\",\n",
        "    \"Backjumping\": \"Backtracking to the most recent assignment in conflict set\",\n",
        "    \"Conflict-directed backjumping\": \"Backjumping that backtracks over all variables resulting in the inconsistency\",\n",
        "    \"Constraint learning\": \"Finding a minimum set of conflict set variables that result in an inconsistency\",\n",
        "    \"No-good\": \"Set of variables and values that are reponsible for an inconsistent assignment in constraint learning\",\n",
        "    \"Min-conflicts\": \"Heuristic that chooses value based on least number of conflicts with other variables\",\n",
        "    \"Plateau search\": \"Search that allows sideways traversal to states with same score to resolve plateau\",\n",
        "    \"Tabu search\": \"Type of tableau search, keeps recently visited states and bans returning to them\",\n",
        "    \"Constraint weighting\": \"Uses weights to focus search on important constraints, increments weights for variables that reach a conflict\",\n",
        "    \"Independent subproblems\": \"Sum of solutions for all independent subproblems = Complete solution for problem\",\n",
        "    \"Connected components\": \"Connected components in constraint graph indicates independent subproblems\",\n",
        "    \"Directional Arc Consistency (DAC)\": \"Variables can be ordered so that each variable is arc-consistent with ones after it\",\n",
        "    \"Topological sort\": \"Ordering, each variable appears after ancestor (in tree), keeps valid domain values\",\n",
        "    \"Cycle cutset\": \"Subset of constraint graph such that after it's removed, it becomes a tree\",\n",
        "    \"Cutset conditioning\": \"Algorithm to find cycle cutset, NP-hard, runs in $O(d^c \\cdot (n - c)d^2)\",\n",
        "    \"Tree decomposition\": \"Transforms graph into tree, where each node is set of variables in a constraint, NP-hard\",\n",
        "    \"Tree width\": \"Size of largest node in tree decomposition - 1\",\n",
        "    \"Value symmetry\": \"d! ways to assign values to otherwise identical assignments\",\n",
        "    \"Symmetry-breaking constraint\": \"Ordering constraint to break value symmetry and reduce search space by d!, NP-hard\",\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "82feb002-fa0f-4a29-8ac3-a045a06cfa1e"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSPs:\n- $\\mathcal{X}$: Set of variables\n- $\\mathcal{D}$: Set of domains of allowed values per variable\n- $\\mathcal{C}$: Set of constraints\n\nCSP search algorithms are general, not domain-specific\n- Uses constraints to eliminate portions of search space\n- Difficult search problems often are solvable as CSPs\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nAC-3: Time = $O(c \\cdot d \\cdot d^2) = O(cd^3)$ - c arcs, d max domain size \\\nConstraint satisfaction is NP-complete, n-consistency requires exponential time/space\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nAfter constraint propagation, search or inference may still be needed to find a solution \\\nSimple backjumping and forward checking are redundant\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nUsing independent subproblems goes from $O(d^n)$ runtime to $O(d^c \\cdot n/c)$\n- n variables total, c variables in CSP, d domain size\nAny tree-structured CSP can be solved in linear time in number of variables \\\nTree decomposition - Solves tree CSP in $O(nd^2)$, domain is set of tuples:\n- Each original variable appears\n- Variables in constraints must be included in at least one tree node\n- If a variable appears in 2 nodes of tree, it must appear in all nodes along the path between the nodes\nCSPs with constraint graphs of bounded tree width have polynomial time solutions ($O(nd^{w + 1})$)\nTree decomposition is faster, but requires exponential space in tree width - Cutset conditioning is linear space\n\n\n## Module 6 Lecture Notes\n\nWaltz/Mackworth Constraint Propagation:\n- Assign all nodes full domain\n- Repeat: For each node i and neighbors j, remove all values from i that aren't consistent with j\n\n\n## Module 6 Definitions\n* **Factored representation** - Representation of problem where we have internal information (set of variables with values)\n* **Constraint satisfaction problem (csp)** - Problem where each variable has a value that satisfies all restrictions on it\n* **Scope** - Tuple of affected variables in constraint\n* **Relation** - Defines restrictions on variables in scope\n* **Assignment** - Setting of values for variables in CSPs\n* **Consistent assignment** - An assignment that doesn't violate any constraints\n* **Complete assignment** - An assignment that gives all variables a value\n* **Solution** - A consistent, complete assignment\n* **Partial assignment** - An assignment that doesn't assign values to all variables\n* **Partial solution** - A consistent, partial assignment\n* **Constraint graph** - Nodes = variables, edges = variables in a constraint\n* **Precedence constraint** - Some tasks precede others in a constraint\n* **Disjunctive constraint** - Or\n* **Discrete, finite domains** - Simplest type of setting for CSP\n* **Linear constraints** - Constraints written as a linear combination\n* **Nonlinear constraints** - Constraints with nonlinear relationship between variables, make problem undecidable\n* **Linear programming problems** - Constraints are linear (in)equalities\n* **Unary constraint** - One variable constraint\n* **Binary constraint** - Two variable constraint\n* **Binary csp** - CSP with only unary and binary constraints\n* **Global constraint** - Constraint with arbitrary number of variables\n* **Dual graph** - Graph with variables as nodes, binary constraints as edges\n* **Preference constraints** - Constraints that are desired to be satisfied, but not strictly required\n* **Constrained optimization problem** - CSPs with preference constraints that can be solved with optimization search methods\n* **Constraint propagation** - Use of CSP constraints to reduce the number of values that a variable can take\n* **Local consistency** - Enforcing constraints in particular sections of graph\n* **Node-consistent** - All values in the variable's domain satisfy the variable's unary constraints\n* **Arc-consistent** - A variable with each value in its domain satisfying its binary constraints\n* **Ac-3** - Algorithm to enforce arc consistency checking arcs in queue, removing invalid values, enqueueing neighbouring arcs \n* **Path consistency** - Restricts binary constraints by implicit constraints inferred from variable triples\n* **K-consistency** - Consistent value can always be assigned to kth variable for any consistent assignment to k - 1 variables\n* **Strongly k-consistent** - k-consistent, (k - 1)-consistent, ..., 1-consistent\n* **Alldiff** - Global constraint that all variables must have distinct values\n* **Resource constraint (atmost)** - Sum of values can't be above a certain threshold\n* **Bounds propagation** - Domains represented by intervals\n* **Bounds-consistent** - For each variable X, there exists a Y that satisfies X-Y constraint for every variable Y\n* **Backtracking search** - Uninformed algorithm, uses DFS to assign values to variables, backtracks when no possible solution\n* **Minimum-remaining values (mrv)** - Heuristic to choose variable with the fewest legal values\n* **Degree heuristic** - Heuristic to select variable that constrains the most other variables\n* **Least-constraining value** - Heuristic to select values that constrain the fewest possible values for other variables\n* **Forward checking** - Inference, establishes arc consistency when a variable is assigned\n* **Maintaining arc consistency (mac)** - Inference, forward checks and runs pseudo-AC-3 to establish consistency for additional variables\n* **Chronological backtracking** - Standard backtracking, where the most recent point is revisited\n* **Conflict set** - The set of assignments that are in conflict with a new assignment\n* **Backjumping** - Backtracking to the most recent assignment in conflict set\n* **Conflict-directed backjumping** - Backjumping that backtracks over all variables resulting in the inconsistency\n* **Constraint learning** - Finding a minimum set of conflict set variables that result in an inconsistency\n* **No-good** - Set of variables and values that are reponsible for an inconsistent assignment in constraint learning\n* **Min-conflicts** - Heuristic that chooses value based on least number of conflicts with other variables\n* **Plateau search** - Search that allows sideways traversal to states with same score to resolve plateau\n* **Tabu search** - Type of tableau search, keeps recently visited states and bans returning to them\n* **Constraint weighting** - Uses weights to focus search on important constraints, increments weights for variables that reach a conflict\n* **Independent subproblems** - Sum of solutions for all independent subproblems = Complete solution for problem\n* **Connected components** - Connected components in constraint graph indicates independent subproblems\n* **Directional arc consistency (dac)** - Variables can be ordered so that each variable is arc-consistent with ones after it\n* **Topological sort** - Ordering, each variable appears after ancestor (in tree), keeps valid domain values\n* **Cycle cutset** - Subset of constraint graph such that after it's removed, it becomes a tree\n* **Cutset conditioning** - Algorithm to find cycle cutset, NP-hard, runs in $O(d^c \\cdot (n - c)d^2)\n* **Tree decomposition** - Transforms graph into tree, where each node is set of variables in a constraint, NP-hard\n* **Tree width** - Size of largest node in tree decomposition - 1\n* **Value symmetry** - d! ways to assign values to otherwise identical assignments\n* **Symmetry-breaking constraint** - Ordering constraint to break value symmetry and reduce search space by d!, NP-hard\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",
        "Knowledge-agent program:\n",
        "- TELL KB what it perceives\n",
        "- ASK KB what action to do\n",
        "- TELL KB what was chosen\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\"\"\"\n",
        "chapter7_3 = \"\"\"\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "Models assign truth values to each proposition symbol in propositional logic\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "Logical equivalence = Both claims entail each other \\\\\n",
        "Proofs can be more efficient than establishing models, as proofs can skip \n",
        "extraneous propositions, no matter how many. \\\\\n",
        "Resolution combines complementary literals and is sound \\\\\n",
        "A resolution-based theorem prover can always determine whether $a \\models b$ \\\\\n",
        "\n",
        "CNF: \n",
        "1. Apply biconditional elimination\n",
        "2. Apply implication elimination\n",
        "3. Use double-negation elimination + De Morgan to put negatives with literals\n",
        "4. Distributivity of $\\land$ over $\\lor$, $\\lor$ over $\\land$\n",
        "\n",
        "All definite clauses can be rewritten as an implication where:\n",
        "- Premise = Conjunction of positive literals\n",
        "- Conclusion = One positive literal\n",
        "\n",
        "Inference with Horn clauses uses forward-chaining, backward-chaining \\\\\n",
        "Entailment with Horn clauses is linear time in size of knowledge base\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "KB is false in models that contradict its sentences \\\\\n",
        "When an inference algorithm i -> $a$ is true:\n",
        "- KB $\\models_{i}$ $a$ - $a$ is derived from KB by $i$\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "    \"Knowledge-based agent\": \"Use reasoning over internal knowledge representation to make action\", \n",
        "    \"Knowledge representation language\": \"Terminology that expresses sentences in KBs\", \n",
        "    \"Knowledge base (KB)\": \"Set of sentences that assert something about the world\", \n",
        "    \"Axiom\": \"A given sentence that isn't derived from another sentence\", \n",
        "    \"Inference\": \"Deriving new sentences from old sentences in KB\", \n",
        "    \"Background knowledge\": \"Baseline info in KB, added onto over time through observations\", \n",
        "    \"Knowledge level\": \"Abstracted view of knowledge-based agent, what it knows and its goals\", \n",
        "    \"Implementation level\": \"Hardware/software view of agent\", \n",
        "    \"Declarative\": \"Telling agents sentences, one by one\", \n",
        "    \"Procedural\": \"Encoding behaviour as program code\", \n",
        "    \"Syntax\": \"Rules that describes what sentences are permitted\",\n",
        "    \"Semantics\": \"Meaning\", \n",
        "    \"Model\": \"A possible world/scenario in which sentences can be judged as true or false\", \n",
        "    \"Entailment\": \"One sentence logically follows from another sentence\", \n",
        "    \"Logical inference\": \"Using entailment to derive logical conclusions\", \n",
        "    \"Model checking\": \"Listing all models to check if a claim is true in every model where the KB is true\", \n",
        "    \"Sound/truth-preserving\": \"Entailed sentences are the only derived result from a sound inference algorithm\", \n",
        "    \"Completeness\": \"Complete inference algorithms can derive all entailed sentences\", \n",
        "    \"Grounding\": \"Connecting internal logic and knowledge with reality, confirming that KB is true enough\", \n",
        "    \"Learning\": \"Allows us to improve knowledge bases over time\", \n",
        "    \"Propositional logic\": \"System of logic that uses true/false propositions and the relationships between them\", \n",
        "    \"Atomic sentence\": \"Smallest sentence unit, composed of one proposition symbol\", \n",
        "    \"Proposition symbol\": \"Represent a statement that can be true or false\", \n",
        "    \"Complex sentence\": \"Combine simpler sentences with logical connectives\", \n",
        "    \"Logical connectives\": \"$\\neg$, $\\land$, $\\lor$, $\\implies$, $\\iff$\", \n",
        "    \"Literal\": \"Atomic sentence or its negation\", \n",
        "    \"Conjunction\": \"A sentence that uses $\\land$ as its primary connective\", \n",
        "    \"Conjunct\": \"Parts of a conjunction\", \n",
        "    \"Disjunction\": \"A sentence that uses $\\lor$ as its primary connective\", \n",
        "    \"Disjunct\": \"Parts of a disjunction\", \n",
        "    \"Implication/rules/if-then statement\": \"A sentence that uses $\\implies$\", \n",
        "    \"Premise/antecedent\": \"If part of implication statement\", \n",
        "    \"Conclusion/consequent\": \"Then part of implication statement\", \n",
        "    \"Biconditional\": \"A sentence that uses $\\iff$\", \n",
        "    \"Truth table\": \"Specify truth values of a complex sentence for each possible truth value assignment\", \n",
        "    \"Theorem proving\": \"Using rules of inference to sentences in KB to prove the veracity of a sentence without outside models\", \n",
        "    \"Logical equivalence\": \"Two sentences are logically equivalent if they are true in the same set of models\", \n",
        "    \"Validity\": \"A valid sentence (tautology) is true in all models\", \n",
        "    \"Deduction theorem\": \"$a \\models b \\iff (a \\implies b)$ is a valid sentence.\", \n",
        "    \"Satisfiability\": \"A satisfiable sentence is true in some model\", \n",
        "    \"Commutativity\": \"$(a \\land b) \\equiv (b \\land a)$, $(a \\lor b) \\equiv (b \\lor a)$\", \n",
        "    \"Associativity\": \"$(a \\land b) \\land c \\equiv (a \\land (b \\land c))$\", \n",
        "    \"Double-negation elimination\": \"$-(-a) \\equiv a$\", \n",
        "    \"Contraposition\": \"$(a \\implies b) \\equiv (-b \\implies -a)$\", \n",
        "    \"Implication elimination\": \"$(a \\implies b) \\equiv (-a \\lor b)$\", \n",
        "    \"Biconditional elimination\": \"$(a \\iff b) \\equiv ((a \\implies b) \\land (b \\implies a))$\", \n",
        "    \"De Morgan\": \"$-(a \\land b) \\equiv (~a \\lor ~b)$\",\n",
        "    \"Distributivity\": \"$(a \\land (b \\lor c)) \\equiv ((a \\land b) \\lor (a \\land c))$\",\n",
        "    \"Inference rules\": \"Sequence of conclusions resulting in a goal\",\n",
        "    \"Modus Ponens\": \"$(a \\implies b, a) \\implies b$\",\n",
        "    \"And-Elimination\": \"$a \\land b \\implies a$\",\n",
        "    \"Monotonicity\": \"Set of entailed sentences always grows, KB $\\models$ $a$ $\\implies$ KB $\\land ~b$ $\\models$ $a$\",\n",
        "    \"Resolution\": \"Single inference rule resulting in a complete inference algorithm when with a complete search algorithm\",\n",
        "    \"Factoring\": \"Removal of multiple copies of literals\",\n",
        "    \"Conjunctive normal form (CNF)\": \"A sentence represented as a conjunction of clauses\",\n",
        "    \"Resolution closure\": \"Set of clauses that can be derived from repeating the resolution rule\",\n",
        "    \"Ground resolution theorem\": \"If a set of clauses is unsatisfiable, then its resolution closure contains the empty clause\",\n",
        "    \"Definite clause\": \"Disjunction of literals with exactly one positive literal\",\n",
        "    \"Horn clause\": \"Disjunction of literals with at most one positive literal\",\n",
        "    \"Goal clause\": \"Disjunction of literals with no positive literals\",\n",
        "    \"k-CNF\": \"CNF where each clause has at most k literals\",\n",
        "    \"Body\": \"Premise of Horn form of definite clause\",\n",
        "    \"Head\": \"Conclusion of Horn form of definite clause\",\n",
        "    \"Fact\": \"Single positive literal\",\n",
        "    \"Forward chaining\": \"Data-driven, agent derives new conclusions from new percepts as new info comes in\",\n",
        "    \"Backward chaining\": \"Goal-directed, starts from end query and looks for implications in KB that lead to the query\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5005b121-06a0-4c48-ddc3-a99ee1293acd"
      },
      "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": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nKnowledge-agent program:\n- TELL KB what it perceives\n- ASK KB what action to do\n- TELL KB what was chosen\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n\n## AIMA Chapter 7.3 Logic\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nModels assign truth values to each proposition symbol in propositional logic\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nLogical equivalence = Both claims entail each other \\\nProofs can be more efficient than establishing models, as proofs can skip \nextraneous propositions, no matter how many. \\\nResolution combines complementary literals and is sound \\\nA resolution-based theorem prover can always determine whether $a \\models b$ \\\n\nCNF: \n1. Apply biconditional elimination\n2. Apply implication elimination\n3. Use double-negation elimination + De Morgan to put negatives with literals\n4. Distributivity of $\\land$ over $\\lor$, $\\lor$ over $\\land$\n\nAll definite clauses can be rewritten as an implication where:\n- Premise = Conjunction of positive literals\n- Conclusion = One positive literal\n\nInference with Horn clauses uses forward-chaining, backward-chaining \\\nEntailment with Horn clauses is linear time in size of knowledge base\n\n\n## Module 7 Lecture Notes\n\nKB is false in models that contradict its sentences \\\nWhen an inference algorithm i -> $a$ is true:\n- KB $\\models_{i}$ $a$ - $a$ is derived from KB by $i$\n\n\n## Module 7 Definitions\n* **Knowledge-based agent** - Use reasoning over internal knowledge representation to make action\n* **Knowledge representation language** - Terminology that expresses sentences in KBs\n* **Knowledge base (kb)** - Set of sentences that assert something about the world\n* **Axiom** - A given sentence that isn't derived from another sentence\n* **Inference** - Deriving new sentences from old sentences in KB\n* **Background knowledge** - Baseline info in KB, added onto over time through observations\n* **Knowledge level** - Abstracted view of knowledge-based agent, what it knows and its goals\n* **Implementation level** - Hardware/software view of agent\n* **Declarative** - Telling agents sentences, one by one\n* **Procedural** - Encoding behaviour as program code\n* **Syntax** - Rules that describes what sentences are permitted\n* **Semantics** - Meaning\n* **Model** - A possible world/scenario in which sentences can be judged as true or false\n* **Entailment** - One sentence logically follows from another sentence\n* **Logical inference** - Using entailment to derive logical conclusions\n* **Model checking** - Listing all models to check if a claim is true in every model where the KB is true\n* **Sound/truth-preserving** - Entailed sentences are the only derived result from a sound inference algorithm\n* **Completeness** - Complete inference algorithms can derive all entailed sentences\n* **Grounding** - Connecting internal logic and knowledge with reality, confirming that KB is true enough\n* **Learning** - Allows us to improve knowledge bases over time\n* **Propositional logic** - System of logic that uses true/false propositions and the relationships between them\n* **Atomic sentence** - Smallest sentence unit, composed of one proposition symbol\n* **Proposition symbol** - Represent a statement that can be true or false\n* **Complex sentence** - Combine simpler sentences with logical connectives\n* **Logical connectives** - $\neg$, $\\land$, $\\lor$, $\\implies$, $\\iff$\n* **Literal** - Atomic sentence or its negation\n* **Conjunction** - A sentence that uses $\\land$ as its primary connective\n* **Conjunct** - Parts of a conjunction\n* **Disjunction** - A sentence that uses $\\lor$ as its primary connective\n* **Disjunct** - Parts of a disjunction\n* **Implication/rules/if-then statement** - A sentence that uses $\\implies$\n* **Premise/antecedent** - If part of implication statement\n* **Conclusion/consequent** - Then part of implication statement\n* **Biconditional** - A sentence that uses $\\iff$\n* **Truth table** - Specify truth values of a complex sentence for each possible truth value assignment\n* **Theorem proving** - Using rules of inference to sentences in KB to prove the veracity of a sentence without outside models\n* **Logical equivalence** - Two sentences are logically equivalent if they are true in the same set of models\n* **Validity** - A valid sentence (tautology) is true in all models\n* **Deduction theorem** - $a \\models b \\iff (a \\implies b)$ is a valid sentence.\n* **Satisfiability** - A satisfiable sentence is true in some model\n* **Commutativity** - $(a \\land b) \\equiv (b \\land a)$, $(a \\lor b) \\equiv (b \\lor a)$\n* **Associativity** - $(a \\land b) \\land c \\equiv (a \\land (b \\land c))$\n* **Double-negation elimination** - $-(-a) \\equiv a$\n* **Contraposition** - $(a \\implies b) \\equiv (-b \\implies -a)$\n* **Implication elimination** - $(a \\implies b) \\equiv (-a \\lor b)$\n* **Biconditional elimination** - $(a \\iff b) \\equiv ((a \\implies b) \\land (b \\implies a))$\n* **De morgan** - $-(a \\land b) \\equiv (~a \\lor ~b)$\n* **Distributivity** - $(a \\land (b \\lor c)) \\equiv ((a \\land b) \\lor (a \\land c))$\n* **Inference rules** - Sequence of conclusions resulting in a goal\n* **Modus ponens** - $(a \\implies b, a) \\implies b$\n* **And-elimination** - $a \\land b \\implies a$\n* **Monotonicity** - Set of entailed sentences always grows, KB $\\models$ $a$ $\\implies$ KB $\\land ~b$ $\\models$ $a$\n* **Resolution** - Single inference rule resulting in a complete inference algorithm when with a complete search algorithm\n* **Factoring** - Removal of multiple copies of literals\n* **Conjunctive normal form (cnf)** - A sentence represented as a conjunction of clauses\n* **Resolution closure** - Set of clauses that can be derived from repeating the resolution rule\n* **Ground resolution theorem** - If a set of clauses is unsatisfiable, then its resolution closure contains the empty clause\n* **Definite clause** - Disjunction of literals with exactly one positive literal\n* **Horn clause** - Disjunction of literals with at most one positive literal\n* **Goal clause** - Disjunction of literals with no positive literals\n* **K-cnf** - CNF where each clause has at most k literals\n* **Body** - Premise of Horn form of definite clause\n* **Head** - Conclusion of Horn form of definite clause\n* **Fact** - Single positive literal\n* **Forward chaining** - Data-driven, agent derives new conclusions from new percepts as new info comes in\n* **Backward chaining** - Goal-directed, starts from end query and looks for implications in KB that lead to the query\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": "0cdb4825-da3e-455c-ec5e-0546002deb19"
      },
      "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": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n\n## AIMA 2.1 Agents and Environments\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n\n## AIMA 2.3 The Nature of Environments\n\n\n## AIMA 2.4 The Structure of Agents\n\n\n## Module 1 Lecture Notes\n\n\n## Module 1 Definitions\n* **Turing test** - Tests if machines can imitate human responses, requiring NLP, knowledge representation, reasoning, ML\n* **Total turing test** - Turing test + interaction with real-world (computer vision, robotics)\n* **Value alignment problem** - Alignment of human values with machine objectives\n* **Weak ai** - Machines act as if they are intelligent\n* **Strong ai** - Machines are actually thinking, not simulating\n* **Qualification problem** - Difficulty of turning all requirements of behaviour to a set of comprehensive rules\n* **Embodied cognition** - Studies brain in conjunction with the body, environment, etc.\n* **Chinese room** - Searle argues that a machine that outputs patterns without true understanding isn't truly intelligent\n* **Biological nautralism** - Low-level neuronal activity gives rise to mental states\n* **Brain in a vat** - Dennett's thought experiment asserts that brain in a vat = computer, opposes chinese room\n* **Agent** - Anything that can perceive with sensors and act with actuators in an environment\n* **Percept** - What an agent's sensors perceive\n* **Percept sequence** - All of what an agent has previously observed, which, along with knowledge, guides an agent's actions\n* **Agent function** - Maps percept sequences to an action, which determines an agent's behaviour\n* **Agent program** - Actual implementation of an agent function (i.e., code, machine, etc.)\n* **Rational agent** - Agent that wants to achieve best outcome using available info\n* **Consequentialism** - Agent's behaviour should be judged by the outcomes of its actions\n* **Performance measure** - Way to judge optimality of an agent's actions + states\n* **Autonomy** - Learning on its own to correct prior knowledge\n* **Task environment** - A problem that an agent acts as the solution for\n* **Peas** - Performance measure, Environment, Actuators, Sensors, which describe a task environment\n* **Fully observable** - Agents can perceive entirety of environment (perfect info)\n* **Partially observable** - Agents can perceive part, but not all, of the environment\n* **Stochastic** - Dealing with probabilities\n* **Episodic** - Agent's experiences are divided into independent sections\n* **Sequential** - Current decision is dependent on previous decision\n* **Environment class** - Set of environments that share similarities but vary in particular ways that might affect agents\n* **Agent architecture** - The physical hardware that an agent program runs on\n* **Simple reflex agent** - Choose actions based on current percept\n* **Transition model** - Knowledge about how agent affects world and how world changes independent from agent\n* **Sensor model** - Knowledge about how an agent perceives the world\n* **Model-based agent** - Uses transition and sensor model to update internal state and act\n* **Goal-based agent** - Acts towards reaching a goal state through search\n* **Utility function** - Internal way to quantify performance measure\n* **Utility-based agent** - Uses utility function to make best action\n* **Rational choice theory** - Group social behaviour emerges from individual, rational actors\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\nPython was developed in 1989 by Guido van Rossum and was inspired by ABC.  Python \nis quick to code with due to its simple syntax, can run on an platform, has many \nbuilt in types (lists, dictionaries, sets), and has many libraries for data \nscience.\n\n### Objects and Typing\nAll data in Python are objects.  Each object has a fixed type; interpreter \nwon't allow for incompatible actions, but will coerce types if necessary.  \nPython is dynamically typed, so types of variables are updated on assignment.  \nThis is convenient to code with, but means that type errors are only caught in \nruntime.\n\n### Functions\nIn Python, a function can be given default values for its arguments, which make \nthem optional on function call.  These arguments must follow arguments that are \nnot default.  Functions are dynamically scoped, so a function will see the most \nrecently assigned value of a variable.\nDefault arguments use the same default object each function call.  This matters \nfor mutable objects like sets, which allows for memoization.\nFunctions are also first-class objects, so they can be the argument of functions, \nthe returned item, etc.  Functions that take in function arguments are called \nhigher-order functions.\n\n### Classes\nIn Python, multiple inheritance is supported.  To override inherited methods, \nadd a new definition for the same function; use self if you want to call a \nparent's version of a function.\n\n### List/Set Comprehensions\n`[i for i in range(0, n)]` \n\n`{k:v for k, v in d.items()}`\n\n\n## Module 2 Definitions\n* **Tuple** - Immutable ordered sequence of mixed-type items\n* **String** - Immutable sequence of 16-bit Unicode characters\n* **List** - Mutable (can't be hashed) ordered sequence of mixed-type items\n* **Dictionary** - Unordered map from hashable keys to values with O(1) add, lookup, update\n* ***args** - Arbitrary number of non-keyword arguments\n* ***kwargs** - Arbitrary number of keyword arguments\n* **First-class objects** - Can be dynamically created, destroyed, used in a function, returned, etc.\n* **Duck typing** - Allowing methods to called on item if it contains the methods\n* **Iterator** - Has __next__(), use memory efficiently\n* **Generator** - Iterator that runs until yield statement, continues where it left off, which is efficient\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nThe solution to a problem in a fully observable, deterministic, known environment\nis always a fixed sequence of actions.\n\nDefinition of search problem:\n1. Set of possible states (state space)\n2. Initial state\n3. Goal state(s)\n4. Set of possible actions\n5. Transition model that describes what actions do\n6. Action cost function \n\n\n## AIMA Chapter 3.2 Example Problems\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nFrontiers are implemented with some sort of queue (priority, FIFO, or LIFO/stack).\n\nRepeated states -> Risk of exponential runtime\n\nWays to address this:\n1. Remember reached states to detect redundant paths, keep state's best path\n2. Ignore repeated states when irrelevant\n3. Check for cycles, not redundant paths\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n| Criterion   |    BFS     |  Uniform                  |    DFS     |Depth-limited| Iterative  |Bidirectional |\n| ----------- | ---------- | ------------------------- | ---------- | ----------- | ---------- | ------------ |\n| Complete?   | Yes        | Yes                       | No         | No          | Yes        | Yes          |\n|Cost-optimal?| Yes        | Yes                       | No         | No          | Yes        | Yes          |\n| Time        | $$O(b^d)$$ | $$O(b^{1 + C/\\epsilon})$$ | $$O(b^m)$$ | $$O(b^l)$$  | $$O(b^d)$$ |$$O(b^{d/2})$$|\n| Space       | $$O(b^d)$$ | $$O(b^{1 + C/\\epsilon})$$ | $$O(bm)$$  |  $$O(bl)$$  | $$O(bd)$$  |$$O(b^{d/2})$$|\n\n\n## Module 3 Lecture Notes\n\nBiggest issue with BFS is the memory requirement.\n\n(Large) search problems that are exponential w.r.t. time/space \ncan't be solved by uninformed search.\n\nUniform-cost search = Dijkstra's\n- C = Cost of optimal solution\n- e = Lower bound of cost of action\n- Strategy: Expand node with lowest total path cost\n    - Use priority queue ordered by path cost g(n)\n- Tests if node is goal when expanding it\n\nDFS:\n- m = Max depth of tree\n- Useful with limited space, no infinite paths, terminate wrong paths early\n\nDepth-limited search:\n- DFS at depth limit l\n    - l = d: Complete, optimal\n    - l < d: Incomplete\n    - l > d: Not optimal\n\nIterative deepening search:\n- Repeat DFS at increasing depth limits\n- Complete, optimal\n\nBidirectional search:\n- Algorithm traverses from both initial, goal states and traverses until they collide\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - An agent that can formulate a plan via search\n* **Search** - Process of generating a series of actions to a goal state\n* **Atomic representation** - States of world have no internal structure (black box)\n* **Informed** - Able to estimate distance to goal\n* **Uninformed** - No information about distance to goal\n* **Path** - Sequence of actions\n* **Solution** - Path from initial state to a goal state\n* **Optimal solution** - Solution with lowest path cost out of all solutions\n* **Grid world problem** - Standardized problem where agents can move between cells\n* **Travelling salesperson problem (tsp)** - Touring problem where every city must be visited with minimal cost\n* **Vlsi layout** - Positioning components on chip to minimize area and maximize efficiency\n* **Search algorithm** - Returns a solution/failure for a given search problem\n* **Search tree** - Takes state-space graph and traverses, which turns it into a tree\n* **Node** - Vertex in search tree = State in state space\n* **Frontier** - Set of vertices which have been discovered but not expanded\n* **Best-first search** - General approach of choosing next node with lowest value from evaluation function\n* **Graph search** - Search problem that checks for redundant paths, which uses more memory but runs faster\n* **Tree search** - Search problem that doesn't check for redundant paths, which uses less memory but runs slower\n* **Complete** - Algorithm that is guaranteed to find a solution and report when there is none\n* **Branching factor** - Number of successors that each node must consider\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nGreedy: Lowest complexity = O(bm) for certain problems/heuristics\n- Not complete in infinite spaces\n\nA* with inadmissible heuristic produces satisfying solution with fewer expanded states\n\nDownside: A* uses exponential memory, can be improved by:\n- No duplicates between frontier, reached\n- Eliminate reached\n- Reference counts to remove states when no more ways to reach it\n\nIDA*/RBFS - Not enough memory -> Revisits states\n\nLack of memory can make some problems unsolvable in terms of runtime\n\nBidirectional > A* with average heuristic, not with great or poor heuristic\n\n| Criterion   |   Greedy   |     A*     |    IDA*    |    RBFS    |    SMA*    |Bidirectional |\n| ----------- | ---------- | -----------| ---------- | ---------- | ---------- | ------------ |\n| Complete?   | No         | Yes        | Yes        | Yes        | Yes        | Yes          |\n|Cost-optimal?| No         | Yes        | Yes        | Yes        | Yes        | Yes          |\n| Time        | $$O(b^d)$$ | $$O(b^d)$$ | $$O(b^m)$$ | $$O(b^m)$$ | $$O(b^d)$$ |$$O(b^{d/2})$$|\n| Space       | $$O(b^d)$$ | $$O(b^d)$$ | $$O(bm)$$  |  $$O(d)$$  |  $$O(x)$$  |$$O(b^{d/2})$$|\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe cost function of an optimal solution for a relaxed problem is an \nadmissible heuristic for the original problem.\n\nSome heuristics can be discovered through experience - Machine learning\n- May not be admissible, but approximates true path cost well\n\n\n## Module 4 Lecture Notes\n\n\n## Module 4 Definitions\n* **Heuristic function h(n)** - Estimated cost of cheapest path from the state at node n to goal state\n* **Greedy best-first search** - Expands node with lowest h(n) first\n* **Straight-line distance** - Possible heuristic for route finding\n* **A* search** - Best first search with (admissible for cost-optimality) f(n) = estimated cost of best path (g(n) + h(n))\n* **Admissible/optimistic** - Never overestimates the cost to reach a goal\n* **Consistent** - h(n) <= Cost(n, a, n') + h(n')\n* **Pruning** - Removing search tree nodes that don't need to be expanded to reduce search space\n* **Satisficing** - Suboptimal solutions that are good enough\n* **Weighted a* search** - A* with f(n) = g(n) + W * h(n)\n* **Bounded suboptimal search** - Searches for solution within a constant factor of optimal cost\n* **Bounded-cost search** - Searches for solution with cost < C\n* **Unbounded-cost search** - Prioritizes solution that is found quickly\n* **Speedy search** - Example of unbounded-cost + greedy best-first search, uses h(n) estimated number of actions to reach goal\n* **Beam search** - Limits size of the frontier by keeping nodes with best f(n) or within a margin\n* **Iterative-deepening a* search** - Explores nodes in paths using f(n) as cutoff, increasing continuously\n* **Recursive best-first search** - DFS, tracks f(n) of best alternative path from ancestor in path, allowing for reexpansion later in linear space\n* **Backed-up value** - Best f(n) of its children in RBFS\n* **Simplified memory-bounded a*** - A*, prunes nodes from queue with highest f(n), remembers best pruned path to regenerate if needed, linear\n* **Bidirectional heuristic search** - Two heuristics, frontiers to select nodes from front and back - Max cost of C/2 for one side\n* **Front-to-end** - Bidirectional with heuristics estimating distance to goal/start\n* **Front-to-front** - Bidirectional with heuristics estimating distance to frontier, very computationally intensive\n* **Effective branching factor** - Branching factor that a uniform tree with depth d needs for N explored nodes\n* **Effective depth** - Reduced by A* pruning\n* **Domination** - If h1(n) >= h2(n), h1 dominates h2, making it preferred as a heuristic\n* **Relaxed problem** - Problem with fewer restrictions on actions\n* **Pattern database** - Take maximium heuristic of exact solution costs of subproblems\n* **Disjoint pattern databases** - Count each move at most 1 time so that the costs can be added\n* **Precomputation** - Calculate certain optimal path costs once and use the results many times\n* **Landmark point** - Selected points to precompute path costs to/from to create an inadmissible heuristic\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nDefinition: Game\n- Initial state\n- Player\n- Set of player's legal moves\n- Transition model - Defines state resulting from action a\n- Terminal test\n- Utility function - Defines final values to players\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax algorithm:\n    if node is terminal_node:\n        return utility(node)\n    if MAX is playing:\n        value = -inf\n        update value based on max of children\n    if MIN is playing:\n        value = inf\n        update value based on min of children\n    return value\n\nMinimax: Time: O(b^m), Space: O(bm)\n\nAlpha-beta reduce b to b^0.5 in best-case, b^0.75 in random\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nPROBCUT - Alpha-beta search w/ forward pruning of nodes likely outside of alpha-beta window\n\nComputers frequently use table lookup for openings/endings of complex games\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nIn stochastic games, there are no likely sequences of moves.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n$A \\succ B$: Agent prefers A over B \\\n$A \\sim B$: Agent is indifferent on A vs. B \\\n$A \\overset{\\succ}{\\sim} B$: Agent prefers A or is indifferent (i.e., doesn't prefer B) \\\n\nNote: Agent behaviour may be described by utility function, but the agent doesn't \nhave to be maximizing it.\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nHuman life = $10 million \\\nUtility of money = log(money) (under 1 million) \\\nOptimizer's curse resolved with Bayesian probability model \\\nDisplaying problems in ways aligned with our evolution typically results in \nmore rational decisions by humans.\n\n\n## Module 5 Lecture Notes\n\n\n## Module 5 Definitions\n* **Adversarial search** - Search problem involving 2+ agents in competition\n* **Perfect-information** - Fully observable\n* **Zero-sum** - When one player improves, the other player(s) must lose\n* **Minimax search** - Search algorithm to minimize possible loss in a game\n* **Ply** - A player's move\n* **Minimax value** - Utility of MAX at a state assuming that both players play optimally\n* **Alpha-beta pruning** - Technique to limit number of nodes explored in minimax\n* **Alpha** - Highest value choice discovered so far - At least\n* **Beta** - Lowest value choice discovered so far - At most\n* **Killer move** - Best moves in game\n* **Transposition** - Permutation of sequence of moves leading to same position\n* **Type a strategy** - Wide but shallow exploration of search tree, use heuristic at max depth\n* **Type b strategy** - Deep but narrow exploration\n* **Heuristic alpha-beta** - Replace UTILITY with EVAL heuristic, terminal test with cutoff test\n* **Weighted linear function** - Type of evaluation function\n* **Quiescent** - No potential move that would change the evaluation greatly\n* **Quiescence search** - Frequently considers moves that seek to resolve uncertainties and reach quiescent states\n* **Horizon effect** - Player can deploy strategy to delay an inevitable outcome\n* **Singular extension** - Corrects for horizon effect by allowing for better moves to be played after stopping point\n* **Forward pruning** - Reduces runtime by eliminating moves that seem bad early in-exchange for suboptimal results\n* **Late move reduction** - Reduces depth to explore fewer late moves, which are less likely to be strong choices\n* **Stochastic games** - Games with random elements involved\n* **Chance nodes** - States with some probability attached\n* **Expectiminimax value** - Minimax, calculate expected value for chance nodes\n* **Decision theory** - Choosing actions based on the optimality of their immediate outcomes\n* **Principle of maximum expected utility (meu)** - Rational agents choose actions that maximize expected utility\n* **Lottery** - Set of outcomes with probabilities associated with them\n* **Orderability** - Constraint that agent must decide, $(A \\succ B) \\lor (B \\succ A) \\lor (A \\sim B)$\n* **Transitivity** - Constraint where $(A \\succ B) \\land (B \\succ C) \\implies (A \\succ C)$\n* **Continuity** - Constraint where $A \\succ B \\succ C \\implies p [p, A: (1 - p), C] \\sim B$\n* **Substitutability** - Constraint that if agent is indifferent to A and B, they can be swapped freely\n* **Monotonicity** - Constraint that if $A \\succ B$, agent prefers the lottery that has more A\n* **Decomposability** - Constraint that compound lotteries can be reduced to less complex ones\n* **Existence of utility function** - A utility function that matches preferences exists ($U(A) > U(B) \\iff A \\succ B$)\n* **Value (ordinal utility) function** - A utility function where relative order is the key metric\n* **Preference elicitation** - Process of determining a human's utility function\n* **Normalized utilities** - Worst U(S) = u_{\bot} = 0, best U(S) = u_{\top} = 1\n* **Standard lottery** - $[p, u_{\top}; (1 - p), u_{\bot}]$, frequently used to determine preferences\n* **Micromort** - Unit for safety analysis = 1 in a million chance of death\n* **Quality-adjusted life year (qaly)** - Metric of year of life, weighted by quality of life\n* **Monotonic preference** - Prefer more to less (i.e., money)\n* **Expected monetary value (emv)** - Expected value of money gained\n* **Risk-averse** - Prefer guaranteed pay-off over a gamble ($U(L) < U(S_{EMV(L)}$)\n* **Risk-seeking** - Prefer gamble for more money than less guaranteed money\n* **Certainty equivalent** - Guaranteed value that an agent takes instead of a lottery\n* **Insurance premium** - Difference between EMV and certainty equivalent\n* **Risk-neutral** - Linear utility function, which is true for small changes\n* **Unbiased** - Expected value of error = 0\n* **Order statistic** - Distribution of any particular ranked element of a sample\n* **Optimizer's curse** - Estimated expected utility of best choice when utility maximizing is too high due to variance\n* **Normative theory** - How a rational agent should act\n* **Descriptive theory** - How an agent does act\n* **Certainty effect** - Humans prefer certain gains due to potential regret, ease, etc.\n* **Ambiguity aversion** - Humans prefer known probabilities over unknown ones\n* **Framing effect** - Way in which problems are worded skew perception of them\n* **Anchoring effect** - Humans prefer making relative utility judgments over absolute ones\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSPs:\n- $\\mathcal{X}$: Set of variables\n- $\\mathcal{D}$: Set of domains of allowed values per variable\n- $\\mathcal{C}$: Set of constraints\n\nCSP search algorithms are general, not domain-specific\n- Uses constraints to eliminate portions of search space\n- Difficult search problems often are solvable as CSPs\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nAC-3: Time = $O(c \\cdot d \\cdot d^2) = O(cd^3)$ - c arcs, d max domain size \\\nConstraint satisfaction is NP-complete, n-consistency requires exponential time/space\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nAfter constraint propagation, search or inference may still be needed to find a solution \\\nSimple backjumping and forward checking are redundant\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nUsing independent subproblems goes from $O(d^n)$ runtime to $O(d^c \\cdot n/c)$\n- n variables total, c variables in CSP, d domain size\nAny tree-structured CSP can be solved in linear time in number of variables \\\nTree decomposition - Solves tree CSP in $O(nd^2)$, domain is set of tuples:\n- Each original variable appears\n- Variables in constraints must be included in at least one tree node\n- If a variable appears in 2 nodes of tree, it must appear in all nodes along the path between the nodes\nCSPs with constraint graphs of bounded tree width have polynomial time solutions ($O(nd^{w + 1})$)\nTree decomposition is faster, but requires exponential space in tree width - Cutset conditioning is linear space\n\n\n## Module 6 Lecture Notes\n\nWaltz/Mackworth Constraint Propagation:\n- Assign all nodes full domain\n- Repeat: For each node i and neighbors j, remove all values from i that aren't consistent with j\n\n\n## Module 6 Definitions\n* **Factored representation** - Representation of problem where we have internal information (set of variables with values)\n* **Constraint satisfaction problem (csp)** - Problem where each variable has a value that satisfies all restrictions on it\n* **Scope** - Tuple of affected variables in constraint\n* **Relation** - Defines restrictions on variables in scope\n* **Assignment** - Setting of values for variables in CSPs\n* **Consistent assignment** - An assignment that doesn't violate any constraints\n* **Complete assignment** - An assignment that gives all variables a value\n* **Solution** - A consistent, complete assignment\n* **Partial assignment** - An assignment that doesn't assign values to all variables\n* **Partial solution** - A consistent, partial assignment\n* **Constraint graph** - Nodes = variables, edges = variables in a constraint\n* **Precedence constraint** - Some tasks precede others in a constraint\n* **Disjunctive constraint** - Or\n* **Discrete, finite domains** - Simplest type of setting for CSP\n* **Linear constraints** - Constraints written as a linear combination\n* **Nonlinear constraints** - Constraints with nonlinear relationship between variables, make problem undecidable\n* **Linear programming problems** - Constraints are linear (in)equalities\n* **Unary constraint** - One variable constraint\n* **Binary constraint** - Two variable constraint\n* **Binary csp** - CSP with only unary and binary constraints\n* **Global constraint** - Constraint with arbitrary number of variables\n* **Dual graph** - Graph with variables as nodes, binary constraints as edges\n* **Preference constraints** - Constraints that are desired to be satisfied, but not strictly required\n* **Constrained optimization problem** - CSPs with preference constraints that can be solved with optimization search methods\n* **Constraint propagation** - Use of CSP constraints to reduce the number of values that a variable can take\n* **Local consistency** - Enforcing constraints in particular sections of graph\n* **Node-consistent** - All values in the variable's domain satisfy the variable's unary constraints\n* **Arc-consistent** - A variable with each value in its domain satisfying its binary constraints\n* **Ac-3** - Algorithm to enforce arc consistency checking arcs in queue, removing invalid values, enqueueing neighbouring arcs \n* **Path consistency** - Restricts binary constraints by implicit constraints inferred from variable triples\n* **K-consistency** - Consistent value can always be assigned to kth variable for any consistent assignment to k - 1 variables\n* **Strongly k-consistent** - k-consistent, (k - 1)-consistent, ..., 1-consistent\n* **Alldiff** - Global constraint that all variables must have distinct values\n* **Resource constraint (atmost)** - Sum of values can't be above a certain threshold\n* **Bounds propagation** - Domains represented by intervals\n* **Bounds-consistent** - For each variable X, there exists a Y that satisfies X-Y constraint for every variable Y\n* **Backtracking search** - Uninformed algorithm, uses DFS to assign values to variables, backtracks when no possible solution\n* **Minimum-remaining values (mrv)** - Heuristic to choose variable with the fewest legal values\n* **Degree heuristic** - Heuristic to select variable that constrains the most other variables\n* **Least-constraining value** - Heuristic to select values that constrain the fewest possible values for other variables\n* **Forward checking** - Inference, establishes arc consistency when a variable is assigned\n* **Maintaining arc consistency (mac)** - Inference, forward checks and runs pseudo-AC-3 to establish consistency for additional variables\n* **Chronological backtracking** - Standard backtracking, where the most recent point is revisited\n* **Conflict set** - The set of assignments that are in conflict with a new assignment\n* **Backjumping** - Backtracking to the most recent assignment in conflict set\n* **Conflict-directed backjumping** - Backjumping that backtracks over all variables resulting in the inconsistency\n* **Constraint learning** - Finding a minimum set of conflict set variables that result in an inconsistency\n* **No-good** - Set of variables and values that are reponsible for an inconsistent assignment in constraint learning\n* **Min-conflicts** - Heuristic that chooses value based on least number of conflicts with other variables\n* **Plateau search** - Search that allows sideways traversal to states with same score to resolve plateau\n* **Tabu search** - Type of tableau search, keeps recently visited states and bans returning to them\n* **Constraint weighting** - Uses weights to focus search on important constraints, increments weights for variables that reach a conflict\n* **Independent subproblems** - Sum of solutions for all independent subproblems = Complete solution for problem\n* **Connected components** - Connected components in constraint graph indicates independent subproblems\n* **Directional arc consistency (dac)** - Variables can be ordered so that each variable is arc-consistent with ones after it\n* **Topological sort** - Ordering, each variable appears after ancestor (in tree), keeps valid domain values\n* **Cycle cutset** - Subset of constraint graph such that after it's removed, it becomes a tree\n* **Cutset conditioning** - Algorithm to find cycle cutset, NP-hard, runs in $O(d^c \\cdot (n - c)d^2)\n* **Tree decomposition** - Transforms graph into tree, where each node is set of variables in a constraint, NP-hard\n* **Tree width** - Size of largest node in tree decomposition - 1\n* **Value symmetry** - d! ways to assign values to otherwise identical assignments\n* **Symmetry-breaking constraint** - Ordering constraint to break value symmetry and reduce search space by d!, NP-hard\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nKnowledge-agent program:\n- TELL KB what it perceives\n- ASK KB what action to do\n- TELL KB what was chosen\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\n\n## AIMA Chapter 7.3 Logic\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nModels assign truth values to each proposition symbol in propositional logic\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nLogical equivalence = Both claims entail each other \\\nProofs can be more efficient than establishing models, as proofs can skip \nextraneous propositions, no matter how many. \\\nResolution combines complementary literals and is sound \\\nA resolution-based theorem prover can always determine whether $a \\models b$ \\\n\nCNF: \n1. Apply biconditional elimination\n2. Apply implication elimination\n3. Use double-negation elimination + De Morgan to put negatives with literals\n4. Distributivity of $\\land$ over $\\lor$, $\\lor$ over $\\land$\n\nAll definite clauses can be rewritten as an implication where:\n- Premise = Conjunction of positive literals\n- Conclusion = One positive literal\n\nInference with Horn clauses uses forward-chaining, backward-chaining \\\nEntailment with Horn clauses is linear time in size of knowledge base\n\n\n## Module 7 Lecture Notes\n\nKB is false in models that contradict its sentences \\\nWhen an inference algorithm i -> $a$ is true:\n- KB $\\models_{i}$ $a$ - $a$ is derived from KB by $i$\n\n\n## Module 7 Definitions\n* **Knowledge-based agent** - Use reasoning over internal knowledge representation to make action\n* **Knowledge representation language** - Terminology that expresses sentences in KBs\n* **Knowledge base (kb)** - Set of sentences that assert something about the world\n* **Axiom** - A given sentence that isn't derived from another sentence\n* **Inference** - Deriving new sentences from old sentences in KB\n* **Background knowledge** - Baseline info in KB, added onto over time through observations\n* **Knowledge level** - Abstracted view of knowledge-based agent, what it knows and its goals\n* **Implementation level** - Hardware/software view of agent\n* **Declarative** - Telling agents sentences, one by one\n* **Procedural** - Encoding behaviour as program code\n* **Syntax** - Rules that describes what sentences are permitted\n* **Semantics** - Meaning\n* **Model** - A possible world/scenario in which sentences can be judged as true or false\n* **Entailment** - One sentence logically follows from another sentence\n* **Logical inference** - Using entailment to derive logical conclusions\n* **Model checking** - Listing all models to check if a claim is true in every model where the KB is true\n* **Sound/truth-preserving** - Entailed sentences are the only derived result from a sound inference algorithm\n* **Completeness** - Complete inference algorithms can derive all entailed sentences\n* **Grounding** - Connecting internal logic and knowledge with reality, confirming that KB is true enough\n* **Learning** - Allows us to improve knowledge bases over time\n* **Propositional logic** - System of logic that uses true/false propositions and the relationships between them\n* **Atomic sentence** - Smallest sentence unit, composed of one proposition symbol\n* **Proposition symbol** - Represent a statement that can be true or false\n* **Complex sentence** - Combine simpler sentences with logical connectives\n* **Logical connectives** - $\neg$, $\\land$, $\\lor$, $\\implies$, $\\iff$\n* **Literal** - Atomic sentence or its negation\n* **Conjunction** - A sentence that uses $\\land$ as its primary connective\n* **Conjunct** - Parts of a conjunction\n* **Disjunction** - A sentence that uses $\\lor$ as its primary connective\n* **Disjunct** - Parts of a disjunction\n* **Implication/rules/if-then statement** - A sentence that uses $\\implies$\n* **Premise/antecedent** - If part of implication statement\n* **Conclusion/consequent** - Then part of implication statement\n* **Biconditional** - A sentence that uses $\\iff$\n* **Truth table** - Specify truth values of a complex sentence for each possible truth value assignment\n* **Theorem proving** - Using rules of inference to sentences in KB to prove the veracity of a sentence without outside models\n* **Logical equivalence** - Two sentences are logically equivalent if they are true in the same set of models\n* **Validity** - A valid sentence (tautology) is true in all models\n* **Deduction theorem** - $a \\models b \\iff (a \\implies b)$ is a valid sentence.\n* **Satisfiability** - A satisfiable sentence is true in some model\n* **Commutativity** - $(a \\land b) \\equiv (b \\land a)$, $(a \\lor b) \\equiv (b \\lor a)$\n* **Associativity** - $(a \\land b) \\land c \\equiv (a \\land (b \\land c))$\n* **Double-negation elimination** - $-(-a) \\equiv a$\n* **Contraposition** - $(a \\implies b) \\equiv (-b \\implies -a)$\n* **Implication elimination** - $(a \\implies b) \\equiv (-a \\lor b)$\n* **Biconditional elimination** - $(a \\iff b) \\equiv ((a \\implies b) \\land (b \\implies a))$\n* **De morgan** - $-(a \\land b) \\equiv (~a \\lor ~b)$\n* **Distributivity** - $(a \\land (b \\lor c)) \\equiv ((a \\land b) \\lor (a \\land c))$\n* **Inference rules** - Sequence of conclusions resulting in a goal\n* **Modus ponens** - $(a \\implies b, a) \\implies b$\n* **And-elimination** - $a \\land b \\implies a$\n* **Monotonicity** - Set of entailed sentences always grows, KB $\\models$ $a$ $\\implies$ KB $\\land ~b$ $\\models$ $a$\n* **Resolution** - Single inference rule resulting in a complete inference algorithm when with a complete search algorithm\n* **Factoring** - Removal of multiple copies of literals\n* **Conjunctive normal form (cnf)** - A sentence represented as a conjunction of clauses\n* **Resolution closure** - Set of clauses that can be derived from repeating the resolution rule\n* **Ground resolution theorem** - If a set of clauses is unsatisfiable, then its resolution closure contains the empty clause\n* **Definite clause** - Disjunction of literals with exactly one positive literal\n* **Horn clause** - Disjunction of literals with at most one positive literal\n* **Goal clause** - Disjunction of literals with no positive literals\n* **K-cnf** - CNF where each clause has at most k literals\n* **Body** - Premise of Horn form of definite clause\n* **Head** - Conclusion of Horn form of definite clause\n* **Fact** - Single positive literal\n* **Forward chaining** - Data-driven, agent derives new conclusions from new percepts as new info comes in\n* **Backward chaining** - Goal-directed, starts from end query and looks for implications in KB that lead to the query\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}