{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "ST FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "93b20014-e02f-445c-9da1-64670a47feda"
      },
      "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": 19,
      "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": "a783de82-2a20-4f19-d1ff-26e716d3fefb"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 21,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive through sensors and act through actuators in an environment.\",\n",
        "\"Agent (eg)\" : \" = architecture + program. EG agent : robots, softbots, thermostats, animals \",\n",
        "\"percept\" : \"agent's perceptual inputs at any given instance\",\n",
        "\"Agent function\" : \"'f:P ->a' : maps a sequence of percept vectors P to an action a from set A\",\n",
        "\"Agent Program\" : \"runs on the physical architecture to produce f\",\n",
        "\"Rational agent\" : \"agent that perceives its environments and behaves rationally, ie. doing the right thing. \\\n",
        "For each possible percept sequence P, rational agent selects action a to maximize the expected value of its performance measure. NOTE : \\\n",
        "Rationality is NOT guaranteed success\",\n",
        "\"Performance measure\" : \"objective criterion for success of agent's behaviour, given the evidence provided by percept sequence \",\n",
        "\"Task environment\" : \"problem spec for agent to solve sol'n : PEAS : performance measure, environment, actuators, sensors\",\n",
        "\"Rational agent designer's goal\" : \"Given a PEAS task environment, construct agent f'n f to maximize expected value of performane measure, \\\n",
        "2) design agent program that implements f on a particular architecture\",\n",
        "\"Types of environment, Deterministic vs Stochastic\" : \"DETERMINISTIC : one action has clear consequence; state of world determined by current state and recent choice of agent. \\\n",
        "Stochastic = probabilistic : many new states can arise from new action, depends on probability\",\n",
        "\"Types of environment, fully observable vs partially observable\" : \"FULLY OBSEVABLE : task agent sensors can detect ALL aspects of environment relevant to agent's choice of actions. \\\n",
        "PARTIALLY OBSERVABLE : some parts of environment may be obscured (eg self driving cars\",\n",
        "\"Types of environment, episodic vs sequential\" : \"EPISODIC : agent perceives environment, then performs a SINGLE action and the choice each action \\\n",
        "is NOT dependent on any previous action. \\\n",
        "SEQUENTIAL : current decision can affect all future actions : imeddiate decision impacts space of possible next choices\",\n",
        "\"Types of environment, Static vs dynamic\" : \"STATIC : environment remains unchanged while agent is deliberating about what action to take, eg. crossword puzzle. \\\n",
        "DYNAMIC : environment changing all the time even while agent is not acting\",\n",
        "\"Types of environment, Discrete vs continuous\" : \"DISCRETE = limited number of clearly defined definitions\",\n",
        "\"Types of environment, single vs multi-agent\" : \"can be single agent, or multi agent with single opponent, or multi with multiple opponents\",\n",
        "}\n"
      ],
      "execution_count": 22,
      "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": "6f8194f6-3600-43e8-caf1-5f8777dd9bb7"
      },
      "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": 23,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Rational agent' is too long!\nWARNING: Your definition of 'Rational agent designer's goal' is too long!\nWARNING: Your definition of 'Types of environment, Deterministic vs Stochastic' is too long!\nWARNING: Your definition of 'Types of environment, fully observable vs partially observable' is too long!\nWARNING: Your definition of 'Types of environment, episodic vs sequential' is too long!\nWARNING: Your definition of 'Types of environment, Static vs dynamic' is too long!\n# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act through actuators in an environment.\n* **Agent (eg)** -  = architecture + program. EG agent : robots, softbots, thermostats, animals \n* **Percept** - agent's perceptual inputs at any given instance\n* **Agent function** - 'f:P ->a' : maps a sequence of percept vectors P to an action a from set A\n* **Agent program** - runs on the physical architecture to produce f\n* **Rational agent** - agent that perceives its environments and behaves rationally, ie. doing the right thing. For each possible percept sequence P, rational agent selects action a to maximize the expected value of its performance measure. NOTE : Rationality is NOT guaranteed success\n* **Performance measure** - objective criterion for success of agent's behaviour, given the evidence provided by percept sequence \n* **Task environment** - problem spec for agent to solve sol'n : PEAS : performance measure, environment, actuators, sensors\n* **Rational agent designer's goal** - Given a PEAS task environment, construct agent f'n f to maximize expected value of performane measure, 2) design agent program that implements f on a particular architecture\n* **Types of environment, deterministic vs stochastic** - DETERMINISTIC : one action has clear consequence; state of world determined by current state and recent choice of agent. Stochastic = probabilistic : many new states can arise from new action, depends on probability\n* **Types of environment, fully observable vs partially observable** - FULLY OBSEVABLE : task agent sensors can detect ALL aspects of environment relevant to agent's choice of actions. PARTIALLY OBSERVABLE : some parts of environment may be obscured (eg self driving cars\n* **Types of environment, episodic vs sequential** - EPISODIC : agent perceives environment, then performs a SINGLE action and the choice each action is NOT dependent on any previous action. SEQUENTIAL : current decision can affect all future actions : imeddiate decision impacts space of possible next choices\n* **Types of environment, static vs dynamic** - STATIC : environment remains unchanged while agent is deliberating about what action to take, eg. crossword puzzle. DYNAMIC : environment changing all the time even while agent is not acting\n* **Types of environment, discrete vs continuous** - DISCRETE = limited number of clearly defined definitions\n* **Types of environment, single vs multi-agent** - can be single agent, or multi agent with single opponent, or multi with multiple opponents\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",
        "Objects and types : \n",
        "\n",
        "- All data treated as objects. An object is deleted (garbage collection) once \\\n",
        "unreachable. \n",
        "\n",
        "- Strong typing : every object has a fixed type interpreter that doesn't allow \\\n",
        "things incompatible with that type, eg. \"foo\" + 2, str + int not allowed. Can \\\n",
        "call type(object) or isinstance(object, type) to check.\n",
        "\n",
        "- Python  has DYNAMIC typing : variables come into existence when first assigned.\\\n",
        "Type(var) automatically determined. If assigned again, type(var) updated. \n",
        "  - Functions have no type signatures, meaning type errors are only caught \\\n",
        "  at runtime : not caught at compiler time. \n",
        "\n",
        "- Mutability : something that has the ability to be changed once created.\n",
        "\n",
        "  - IMMUTABLE : strings, ints, boolean, tuples\n",
        "\n",
        "  - MUTABLE : lists, sets, dicts\n",
        "\n",
        "- Slicing : returns a copy of a subsequence : \n",
        "  \n",
        "  - lst[1:4] :-> returns copy of list from index 1 to index(4-1)\n",
        "  \n",
        "  - lst[:] :-> returns copy of list\n",
        "\n",
        "  - lst[1:-1] :-> from index 1 until last item (-1 from end)\n",
        "\n",
        "\n",
        "- Dictionairies : unordered, work by hashing, so keys must be immutable. \n",
        "\n",
        "  - Constant avg time add, lookup, update\n",
        "\n",
        "\n",
        "- Generators : a kind of iterator object automatically created when keyword \\\n",
        "\"yield\" is used in code. We dynamically create iterator without having to \\\n",
        "explicitly create iterator object.\n",
        "\n",
        "- Functions : are \"first class objects\", meaning that they can be dynamically \\\n",
        "created, destroyed, passed to a function, returned as a value, and have all the \\\n",
        "rights as other variables in python have. \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 37,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 605
        },
        "outputId": "bdfb557d-d3a7-498f-a3b2-6ee9fb2da287"
      },
      "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": 25,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nObjects and types : \n\n- All data treated as objects. An object is deleted (garbage collection) once unreachable. \n\n- Strong typing : every object has a fixed type interpreter that doesn't allow things incompatible with that type, eg. \"foo\" + 2, str + int not allowed. Can call type(object) or isinstance(object, type) to check.\n\n- Python  has DYNAMIC typing : variables come into existence when first assigned.Type(var) automatically determined. If assigned again, type(var) updated. \n  - Functions have no type signatures, meaning type errors are only caught   at runtime : not caught at compiler time. \n\n- Mutability : something that has the ability to be changed once created.\n\n  - IMMUTABLE : strings, ints, boolean, tuples\n\n  - MUTABLE : lists, sets, dicts\n\n- Slicing : returns a copy of a subsequence : \n  \n  - lst[1:4] :-> returns copy of list from index 1 to index(4-1)\n  \n  - lst[:] :-> returns copy of list\n\n  - lst[1:-1] :-> from index 1 until last item (-1 from end)\n\n\n- Dictionairies : unordered, work by hashing, so keys must be immutable. \n\n  - Constant avg time add, lookup, update\n\n\n- Generators : a kind of iterator object automatically created when keyword \"yield\" is used in code. We dynamically create iterator without having to explicitly create iterator object.\n\n- Functions : are \"first class objects\", meaning that they can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in python have. \n\n\n\n\n\n\n\n\n\n\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" We explore problem-searching agents : computational process is called SEARCH. \\\n",
        "Assume simple environment : single agent, fully observable, deterministic, static, discrete, known. \\\n",
        "If environment is Fully Observable, Deterministc, and Known, then solution to any problem is a FIXED SEQUENCE OF ACTIONS. \\\n",
        "Difference between Tree search and graph search : tree search simply lists all the states that can be reached.\\\n",
        " Graph search : checks to see if node has already been visited before adding to search queue. Uses more mem since must keep track of all poss states.\\\n",
        "\n",
        "```python\n",
        "BFS\n",
        "{\n",
        "  function BFS(problem) returns solution node or failure\n",
        "    node = NODE(problem.INITIAL)\n",
        "    if problem.IS_GOAL(node.STATE) : \n",
        "      return node\n",
        "    frontier = FIFO queue of nodes\n",
        "    reached = set of reached states\n",
        "    reached.add(problem.INITIAL)\n",
        "    while frontier not empty : \n",
        "      node = POP(frontier)\n",
        "      for child in EXPAND(problem, node) : \n",
        "        s = child.STATE\n",
        "        if problem.IS-GOAL(s) : \n",
        "          return child\n",
        "        if s is not in reached : \n",
        "          add s to reached\n",
        "          add child to frontier\n",
        "    return failure //ie. frontier is empty\n",
        "}\n",
        "{ //node data structure : contains variables like the state, pointer to parent node, action used to create this state, path cost.\n",
        "  function EXPAND(problem, node) yields successor nodes\n",
        "    s = node.STATE\n",
        "    for each action in problem.ACTIONS(s) : \n",
        "      s' = problem.RESULT(s, action)\n",
        "      cost = node.PATH_COST() + problem.ACTION_COST(s, action, s')\n",
        "      yield NODE(STATE = s', PARENT = node, ACTION = action, PATH_COST = cost) \n",
        "    \n",
        "}\n",
        "```\n",
        "DFS : expand deepest unexpanded node : Frontier is LIFO, so put successors at the FRONT of frontier successor list\n",
        "```python\n",
        "DFS\n",
        "{ function ITERATIVE_DEEPENING_SEARCH(problem) returns a solution node or failure\n",
        "  for depth = 0 to infinity : \n",
        "    result = DEPTH_LIMITED_SEARCH(problem, depth)\n",
        "    if result != cutoff : \n",
        "      return result\n",
        "  }\n",
        "{\n",
        "  function DEPTH_LIMITED_SEARCH(problem, l) returns node or failure or cutoff\n",
        "    frontier = LIFO queue (stack) with NODE(problem.INITIAL) as an element\n",
        "    result = failure\n",
        "    while frontier is not empty :\n",
        "      node = POP(frontier)\n",
        "      if problem.IS_GOAL(node.STATE) :\n",
        "        return node\n",
        "      if DEPTH(node) > l : \n",
        "        result = cutoff\n",
        "      else if not IS_CYCLE(node) : \n",
        "        for each child in EXPAND(problem, node) : \n",
        "          add child to frontier\n",
        "    return result\n",
        "}\n",
        "```\n",
        "Depth vs Breadth first search : use DEPTH-first search if 1) space restricted, 2) there are many poss solutions with long paths and if \\\n",
        "wrong paths are usually terminated quickly; 3) search can be fine-tuned quickly. \\\n",
        "Use BREATH-first search if : 1) possibly infinite paths; 2) if some sol'ns have short paths; 3) if you can quickly discard unlikely paths. \\\n",
        "DFS is not complete since it fails in infinite-depth spaces OR spaces with loops. In order to make DFS complete, we need to limit the depth, so that we avoid the infinite-path problem! \\\n",
        "If modify to avoid repeated states along path : DFS is complete IF finite spaces. \\\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"Reflex agent\" : \"selects action based only on the current percept, ie. ignores percept history\",\n",
        "\"PROCEDURE to solve\" : \"1. GOAL FORMULATION; 2) PROBLEM FORMULATION, 3) SEARCH, 4)EXECUTION\",\n",
        "\"State space\" : \"set S of possible states environment can be in. Includes initial state and goal states\",\n",
        "\"Actions\" : \"set of Actions available to agent given a state s. Action is applicable in s.\",\n",
        "\"Transition model\" : \"describes what each action does. RESULT(s,a) reutrns state that results from doing action a in state s.\",\n",
        "\"Action cost function / path cost\" : \"c(s,a,s') : numeric cost of applying action a in state s to reach state s'. Should reflect agent's \\\n",
        "performance measure.\",\n",
        "\"Path\" : \"sequence of actions\",\n",
        "\"Solution\" : \"path from s_i to s_g : from inital to goal state\",\n",
        "\"OPTIMAL solution\" : \"lowest path cost among all solutions\",\n",
        "\"GOAL TEST\" : \"s is a goal state if goal test function, 'GOAL(s)', is true\",\n",
        "\"Search Tree\" : \"representing the paths that a search algo has explored. Root = initial state, leaves are successor states\",\n",
        "\"Frontier\" : \"states that are available for expanding (ie. applying legal actions to)\",\n",
        "\"Uninformed search\" : \"all non-goal nodes in frontier look equally good\",\n",
        "\"Informed search\" : \"some non-goal nodes can be RANKED above others\",\n",
        "\"Strategy\" : \"order of tree expansion. We evaluate based on 1) Completeness(always find sol), optimality (least cost path), time complexity, space complexity\",\n",
        "\"time/space complexity variables\" : \"b = maximum branching factor, ie. max set of poss actions between 2 states; \\\n",
        "d = depth of shallowest goal node; \\\n",
        "m = max length of any path in state space\",\n",
        "\n",
        "}\n",
        "\n",
        "\n",
        "\n"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "3a27ce72-b794-4de6-c515-58e7fcba8a06"
      },
      "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": 27,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'time/space complexity variables' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n We explore problem-searching agents : computational process is called SEARCH. Assume simple environment : single agent, fully observable, deterministic, static, discrete, known. If environment is Fully Observable, Deterministc, and Known, then solution to any problem is a FIXED SEQUENCE OF ACTIONS. Difference between Tree search and graph search : tree search simply lists all the states that can be reached. Graph search : checks to see if node has already been visited before adding to search queue. Uses more mem since must keep track of all poss states.\n```python\nBFS\n{\n  function BFS(problem) returns solution node or failure\n    node = NODE(problem.INITIAL)\n    if problem.IS_GOAL(node.STATE) : \n      return node\n    frontier = FIFO queue of nodes\n    reached = set of reached states\n    reached.add(problem.INITIAL)\n    while frontier not empty : \n      node = POP(frontier)\n      for child in EXPAND(problem, node) : \n        s = child.STATE\n        if problem.IS-GOAL(s) : \n          return child\n        if s is not in reached : \n          add s to reached\n          add child to frontier\n    return failure //ie. frontier is empty\n}\n{ //node data structure : contains variables like the state, pointer to parent node, action used to create this state, path cost.\n  function EXPAND(problem, node) yields successor nodes\n    s = node.STATE\n    for each action in problem.ACTIONS(s) : \n      s' = problem.RESULT(s, action)\n      cost = node.PATH_COST() + problem.ACTION_COST(s, action, s')\n      yield NODE(STATE = s', PARENT = node, ACTION = action, PATH_COST = cost) \n    \n}\n```\nDFS : expand deepest unexpanded node : Frontier is LIFO, so put successors at the FRONT of frontier successor list\n```python\nDFS\n{ function ITERATIVE_DEEPENING_SEARCH(problem) returns a solution node or failure\n  for depth = 0 to infinity : \n    result = DEPTH_LIMITED_SEARCH(problem, depth)\n    if result != cutoff : \n      return result\n  }\n{\n  function DEPTH_LIMITED_SEARCH(problem, l) returns node or failure or cutoff\n    frontier = LIFO queue (stack) with NODE(problem.INITIAL) as an element\n    result = failure\n    while frontier is not empty :\n      node = POP(frontier)\n      if problem.IS_GOAL(node.STATE) :\n        return node\n      if DEPTH(node) > l : \n        result = cutoff\n      else if not IS_CYCLE(node) : \n        for each child in EXPAND(problem, node) : \n          add child to frontier\n    return result\n}\n```\nDepth vs Breadth first search : use DEPTH-first search if 1) space restricted, 2) there are many poss solutions with long paths and if wrong paths are usually terminated quickly; 3) search can be fine-tuned quickly. Use BREATH-first search if : 1) possibly infinite paths; 2) if some sol'ns have short paths; 3) if you can quickly discard unlikely paths. DFS is not complete since it fails in infinite-depth spaces OR spaces with loops. In order to make DFS complete, we need to limit the depth, so that we avoid the infinite-path problem! If modify to avoid repeated states along path : DFS is complete IF finite spaces. \n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Reflex agent** - selects action based only on the current percept, ie. ignores percept history\n* **Procedure to solve** - 1. GOAL FORMULATION; 2) PROBLEM FORMULATION, 3) SEARCH, 4)EXECUTION\n* **State space** - set S of possible states environment can be in. Includes initial state and goal states\n* **Actions** - set of Actions available to agent given a state s. Action is applicable in s.\n* **Transition model** - describes what each action does. RESULT(s,a) reutrns state that results from doing action a in state s.\n* **Action cost function / path cost** - c(s,a,s') : numeric cost of applying action a in state s to reach state s'. Should reflect agent's performance measure.\n* **Path** - sequence of actions\n* **Solution** - path from s_i to s_g : from inital to goal state\n* **Optimal solution** - lowest path cost among all solutions\n* **Goal test** - s is a goal state if goal test function, 'GOAL(s)', is true\n* **Search tree** - representing the paths that a search algo has explored. Root = initial state, leaves are successor states\n* **Frontier** - states that are available for expanding (ie. applying legal actions to)\n* **Uninformed search** - all non-goal nodes in frontier look equally good\n* **Informed search** - some non-goal nodes can be RANKED above others\n* **Strategy** - order of tree expansion. We evaluate based on 1) Completeness(always find sol), optimality (least cost path), time complexity, space complexity\n* **Time/space complexity variables** - b = maximum branching factor, ie. max set of poss actions between 2 states; d = depth of shallowest goal node; m = max length of any path in state space\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Now we consider INFORMED strategies. \\\n",
        "\n",
        "Uniform-cost search : ie Dijkstra's algo : expand node with lowest path cost. \\\n",
        "Frontier = priority queue ordered by g(n) : path cost. Difference with BFS : \\\n",
        "test if node is goal state when it is selected for EXPANSION, NOT when it is \\\n",
        "added to the frontier. The algo updates a node on the frontier if a better path \\\n",
        "to the same state is found : so always enqueue a node before checking if goal, since \\\n",
        "there can be 2 ways of reaching that nmode, and the other stil on the queue \\\n",
        " would be less costly! \\\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "Now, for informed search, we want to expand nodes based on an ESTIMATE which \\\n",
        "includes distance to goal. Sort frontier queue by this new f(n).\n",
        "\n",
        "Greedy Best-First-Search : attempt #1 at integrating heuristic knowledge. \n",
        "f(n) is some function that includes the estimate heuristic h(n) of the remaining \\\n",
        "distance to goal. \n",
        "Basic idea : set f(n) = h(n). \n",
        "Ignore g(n), ie. the cost to get to n.  \\\n",
        "Select node for expansion with MINIMAL f(n) : IE. expand node that is estimated \\\n",
        " to be closest to goal. \\\n",
        "\n",
        " Properties of Greedy BFS : \n",
        "\n",
        " Complete : NOT Complete, since can get stuck in loops. \n",
        "\n",
        " Optimal : NO! Not guaranteed to return the lowest path FIRST.\n",
        "\n",
        " To guarantee optimality : A* SEARCH : best known form of best-first search. \n",
        " \n",
        " Key Idea : avoid expanding paths that area already expensive. Expand most promising first.\n",
        "\n",
        " total cost heuristic $ f(n) = g(n) + h(n)$ : sum of g(n) - actual cost so far to n, + h(n) - estimated\\\n",
        " cost to get from node to goal. \n",
        "\n",
        " Implementation : similar to Greedy : Frontier queue is priority queue by \\\n",
        " increasing f(n). \n",
        "\n",
        " Admissible heuristics : $0 <= h(n) <= h*(n)$, where you $h*(n)$ is the true cost from n to goal.\n",
        "\n",
        " Since $h(n) >= 0$, so h(G) = 0 for any goal G.\n",
        "\n",
        " THEOREM : If h(n) is admissible, A* using Tree Search is OPTIMAL.\n",
        "\n",
        " Why?? -> Because admissible heuristics slow down bad plans but never outweigh true costs. \\\n",
        " So true best plan will always eventually be expanded.\n",
        "\n",
        " Inadmissible (pessimistic) heuristics break optimality by trapping good plans \\\n",
        " low on frontier = never get explored.\n",
        "\n",
        " - With an inadmissible heuristic, A* may or may NOT be cost optimal. Algorithm \\\n",
        " may also never return solution given infinite search space.\n",
        "\n",
        " Algorithm : \n",
        "\n",
        " NOTE : algorithm doesn't end until the goal node is expanded, and so must be at the \\\n",
        " top of the Frontier queue to ensure optimality.\n",
        "\n",
        " To find Admissible Heuristics : \n",
        " Cost of an optimal solution to a relaxed problem (fewer restrictions) is an \\\n",
        " admissible heuristic for the original problem..\n",
        "\n",
        " Dominance : metric on which heuristic is better : \n",
        " If $h_2(n) >= h_1(n)$ for all n (both admissible) : ie. h2 gives higher remaining \\\n",
        " distance\n",
        "\n",
        " Then $h_2$ dominates $h_1$. h2 is less optimistic but is more accurate than $h_1$ \n",
        "\n",
        " Note : h*(n) dominates all other heuristics.\n",
        "\n",
        "CONSISTENCY : \n",
        "Consistency is a stronger property to admissibility. \n",
        "\n",
        "A heuristic h(n) is consistent if, for every node n and every successor n' of \\\n",
        "n generated by an action a, we have : $$ h(n) <= c(n,a,n') + h(n') $$\n",
        "\n",
        "- Every consistent heuristic is admissible, but NOT vice versa. \n",
        "\n",
        "- With a consistent heuristic, A* is thus cost-optimal. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Informed search strategy\" : \"one that uses domain-specific hints about the \\\n",
        "location of goals, ie. uses some knowledge about remaining distance to goal\",\n",
        "\"Uniform-cost search\" :  \"extension of BFS but now assuming actions have different costs\",\n",
        "\"Heuristic function, h(n)\" : \"estimated cost of the cheapest path from state \\\n",
        "at node n to goal. EG manhattan (straight line) distance\",\n",
        "\"Greedy best-first search\" : \"expands node with the lowest h(n) (estimated cost to goal) : $f(n) = h(n)$ \",  \n",
        "\"A* search\" : \"f(n) = g(n) + h(n) : sum of actual cost so far + estimated cost to goal\",\n",
        "\"Admissible heuristics\" : \"never overestimates cost to reach goal, ie. OPTIMISTIC\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "8acdc9db-b5a1-4774-c1b5-13eaceaebf47"
      },
      "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": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Now we consider INFORMED strategies. \nUniform-cost search : ie Dijkstra's algo : expand node with lowest path cost. Frontier = priority queue ordered by g(n) : path cost. Difference with BFS : test if node is goal state when it is selected for EXPANSION, NOT when it is added to the frontier. The algo updates a node on the frontier if a better path to the same state is found : so always enqueue a node before checking if goal, since there can be 2 ways of reaching that nmode, and the other stil on the queue  would be less costly! \n\n\n\nNow, for informed search, we want to expand nodes based on an ESTIMATE which includes distance to goal. Sort frontier queue by this new f(n).\n\nGreedy Best-First-Search : attempt #1 at integrating heuristic knowledge. \nf(n) is some function that includes the estimate heuristic h(n) of the remaining distance to goal. \nBasic idea : set f(n) = h(n). \nIgnore g(n), ie. the cost to get to n.  Select node for expansion with MINIMAL f(n) : IE. expand node that is estimated  to be closest to goal. \n Properties of Greedy BFS : \n\n Complete : NOT Complete, since can get stuck in loops. \n\n Optimal : NO! Not guaranteed to return the lowest path FIRST.\n\n To guarantee optimality : A* SEARCH : best known form of best-first search. \n \n Key Idea : avoid expanding paths that area already expensive. Expand most promising first.\n\n total cost heuristic $ f(n) = g(n) + h(n)$ : sum of g(n) - actual cost so far to n, + h(n) - estimated cost to get from node to goal. \n\n Implementation : similar to Greedy : Frontier queue is priority queue by  increasing f(n). \n\n Admissible heuristics : $0 <= h(n) <= h*(n)$, where you $h*(n)$ is the true cost from n to goal.\n\n Since $h(n) >= 0$, so h(G) = 0 for any goal G.\n\n THEOREM : If h(n) is admissible, A* using Tree Search is OPTIMAL.\n\n Why?? -> Because admissible heuristics slow down bad plans but never outweigh true costs.  So true best plan will always eventually be expanded.\n\n Inadmissible (pessimistic) heuristics break optimality by trapping good plans  low on frontier = never get explored.\n\n - With an inadmissible heuristic, A* may or may NOT be cost optimal. Algorithm  may also never return solution given infinite search space.\n\n Algorithm : \n\n NOTE : algorithm doesn't end until the goal node is expanded, and so must be at the  top of the Frontier queue to ensure optimality.\n\n To find Admissible Heuristics : \n Cost of an optimal solution to a relaxed problem (fewer restrictions) is an  admissible heuristic for the original problem..\n\n Dominance : metric on which heuristic is better : \n If $h_2(n) >= h_1(n)$ for all n (both admissible) : ie. h2 gives higher remaining  distance\n\n Then $h_2$ dominates $h_1$. h2 is less optimistic but is more accurate than $h_1$ \n\n Note : h*(n) dominates all other heuristics.\n\nCONSISTENCY : \nConsistency is a stronger property to admissibility. \n\nA heuristic h(n) is consistent if, for every node n and every successor n' of n generated by an action a, we have : $$ h(n) <= c(n,a,n') + h(n') $$\n\n- Every consistent heuristic is admissible, but NOT vice versa. \n\n- With a consistent heuristic, A* is thus cost-optimal. \n\n\n## Module 4 Definitions\n* **Informed search strategy** - one that uses domain-specific hints about the location of goals, ie. uses some knowledge about remaining distance to goal\n* **Uniform-cost search** - extension of BFS but now assuming actions have different costs\n* **Heuristic function, h(n)** - estimated cost of the cheapest path from state at node n to goal. EG manhattan (straight line) distance\n* **Greedy best-first search** - expands node with the lowest h(n) (estimated cost to goal) : $f(n) = h(n)$ \n* **A* search** - f(n) = g(n) + h(n) : sum of actual cost so far + estimated cost to goal\n* **Admissible heuristics** - never overestimates cost to reach goal, ie. OPTIMISTIC\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 = \"\"\" How to model games with adversaries: model game as game tree \"\"\"\n",
        "chapter5_2 = \"\"\" Optimal decision in games : MINIMAX algorithm and alpha-beta pruning \"\"\"\n",
        "chapter5_3 = \"\"\" Heuristic alpha-beta and cutoff search \"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic games : must evaluate expected value of chance nodes, \\\n",
        "then conduct minimax the same way. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Principle of maximum expected utility (MEU) : \\\n",
        "rational agent should choose the action that maximizes the agent's expected utility \"\"\"\n",
        "chapter16_2 = \"\"\" Utility theory \"\"\"\n",
        "chapter16_3 = \"\"\" Utility functions (various) \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Introduction of competitive environments : \\\n",
        "where 2+ agents have conflicting goals = adversarial search.\n",
        "\n",
        "Assume simplest game environment : multiagent, static, discrete, fully observable, \\\n",
        "strategic (next state determined by current state and action exectuted by the agent \\\n",
        "and the actions of one other agent.)\n",
        "\n",
        "Assume zero-sum : one agent wins = other loses.\n",
        "\n",
        "MINI-MAX algorithm : \n",
        "- All play is computed from MAX's vantage point.\n",
        "\n",
        "- When MAX moves, MAX attempts to MAXimize MAX's outcomes.\n",
        "\n",
        "- When MAX's OPPONENT moves, they attempt to MINimize MAX's outcome.\n",
        "\n",
        "- Root level (ie. level 0)= MAX\n",
        "\n",
        "- Alternate MAX/MIN labels for each successive ply (tree level) from root.\\\n",
        "Even levels : MAX. Odd levels : MIN.\n",
        "\n",
        "- Nodes represent \"board positions\"; edges represent legal moves. \n",
        "\n",
        "- Evaluation function f(n) : evaluates how \"good\" a board position is. \\\n",
        "IE. assigns a real-number score to board positions(static features of the \\\n",
        " board alone) without reference to path. \n",
        "\n",
        " - $f(n) > 0 $ if MAX is winning in position n. \n",
        "\n",
        " - $f(n) = 0 $ if position n is tied\n",
        "\n",
        " - $f(n) < 0 $ if MIN is winning in position n.\n",
        "\n",
        " Can count f(n) as 'number of moves available for MAX - number of moves \\\n",
        " available for MIN. \n",
        " \n",
        " OR eg. for chess : f(n) =  (sum of A's piece values) - (sum of B's piece values)\n",
        "\n",
        " MINIMAX rule : make the best move for MAX assuming that MIN will always reply\\\n",
        " with the best move for MIN. Can find the backed up value of each node by \\\n",
        " determining the values of its children : \n",
        "\n",
        " - For MAX node, backed-up value is the MAXIMUM of the values of its children \\\n",
        " (ie. best for MAX)\n",
        "\n",
        " - For MIN node, backed-up value is the MINIMUM of the values of its children \\\n",
        " (ie. best for MIN)\n",
        "\n",
        " ```\n",
        " MINIMAX IMPLEMENTATION : Recursively call max and min functions until base case\n",
        " {\n",
        "   def MAX-VALUE(state) : \n",
        "     if IS_TERMINAL(state) : \n",
        "       return state's utility\n",
        "      initialize v = -inf\n",
        "      for successor in state.successors() : \n",
        "        v = max(v, MIN-VALUE(successor))\n",
        "      return v\n",
        " }\n",
        " {\n",
        "   def MIN-VALUE(state) : \n",
        "     if IS_TERMINAL(state) : \n",
        "       return state's utility\n",
        "      initialize v = +inf\n",
        "      for successor in state.successors() : \n",
        "        v = min(v, MAX-VALUE(successor))\n",
        "      return v\n",
        "\n",
        " }\n",
        " ```\n",
        " Runtime of MINIMAX : $O(b^m)$, since we essentially implement DFS on \\\n",
        " entire game tree. \n",
        "\n",
        "ALPHA - BETA PRUNING : \n",
        "\n",
        "We can make this more efficient by pruning, or saving ourselves from exploring \\\n",
        " large parts of the tree that would ultimately not affect the outcome. \\\n",
        " Conceptually : consider node n on tree, such that Player has a choice of \\\n",
        " moving to n. If Player has a better choice either at the same level OR \\\n",
        " at any point higher up in the tree, then Player will never move to n. So \\\n",
        " we can prune n.\n",
        "\n",
        " - ALPHA: MAX's current LOWER bound on MAX's outcome. MAX is 'at least' alpha.\n",
        "\n",
        " - BETA: MIN's current UPPER bound on MIN's outcome. MIN is 'at most' beta.\n",
        "\n",
        " PRUNE whenever:\n",
        "  - for MAX node : whenever value $v >= BETA$ is backed up : MIN will never \\\n",
        "  select that MAX node since beta is MIN's upper bound. Prune the remaining subtree.\n",
        "\n",
        "  - for MIN node : whenever value $v <= ALPHA $ is backed up : MAX will never \\\n",
        "  select that MIN node since alpha is MAX's upper bound. Prune the remaining subtree.\n",
        "\n",
        "Notes on effectiveness of alpha-beta pruning : \n",
        "\n",
        "- Effectivenss depends heavily on order in which states are examined. Could prune \\\n",
        "more or less of tree depending on this order.\n",
        "\n",
        "- If done perfectly, alpha-beta could only examine $O(b^{(m/2)})$, instead of \\\n",
        "$O(b^{m})$ for MINIMAX. Ie. effective branching factor becomes $\\sqrt{b}$. \n",
        "\n",
        "EXPECTIMAX : \n",
        "\n",
        "For undertain outcomes controlled by chance, NOT an adversary, eg. dice rolls\n",
        "\n",
        "- Value should now reflect average-case : EXPECTIMAX, and not worst-case (MINIMAX) outcomes. \n",
        "\n",
        "- Chance nodes are like min nodes but outcome is uncertain : calculate expected utilities\n",
        "\n",
        "- Take weighted average (expectation) of children\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "66edd7e2-874b-43ff-8e33-8a6e92d855a0"
      },
      "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": 31,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n How to model games with adversaries: model game as game tree \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Optimal decision in games : MINIMAX algorithm and alpha-beta pruning \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic alpha-beta and cutoff search \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games : must evaluate expected value of chance nodes, then conduct minimax the same way. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Principle of maximum expected utility (MEU) : rational agent should choose the action that maximizes the agent's expected utility \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Utility theory \n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions (various) \n\n## Module 5 Lecture Notes\n Introduction of competitive environments : where 2+ agents have conflicting goals = adversarial search.\n\nAssume simplest game environment : multiagent, static, discrete, fully observable, strategic (next state determined by current state and action exectuted by the agent and the actions of one other agent.)\n\nAssume zero-sum : one agent wins = other loses.\n\nMINI-MAX algorithm : \n- All play is computed from MAX's vantage point.\n\n- When MAX moves, MAX attempts to MAXimize MAX's outcomes.\n\n- When MAX's OPPONENT moves, they attempt to MINimize MAX's outcome.\n\n- Root level (ie. level 0)= MAX\n\n- Alternate MAX/MIN labels for each successive ply (tree level) from root.Even levels : MAX. Odd levels : MIN.\n\n- Nodes represent \"board positions\"; edges represent legal moves. \n\n- Evaluation function f(n) : evaluates how \"good\" a board position is. IE. assigns a real-number score to board positions(static features of the  board alone) without reference to path. \n\n - $f(n) > 0 $ if MAX is winning in position n. \n\n - $f(n) = 0 $ if position n is tied\n\n - $f(n) < 0 $ if MIN is winning in position n.\n\n Can count f(n) as 'number of moves available for MAX - number of moves  available for MIN. \n \n OR eg. for chess : f(n) =  (sum of A's piece values) - (sum of B's piece values)\n\n MINIMAX rule : make the best move for MAX assuming that MIN will always reply with the best move for MIN. Can find the backed up value of each node by  determining the values of its children : \n\n - For MAX node, backed-up value is the MAXIMUM of the values of its children  (ie. best for MAX)\n\n - For MIN node, backed-up value is the MINIMUM of the values of its children  (ie. best for MIN)\n\n ```\n MINIMAX IMPLEMENTATION : Recursively call max and min functions until base case\n {\n   def MAX-VALUE(state) : \n     if IS_TERMINAL(state) : \n       return state's utility\n      initialize v = -inf\n      for successor in state.successors() : \n        v = max(v, MIN-VALUE(successor))\n      return v\n }\n {\n   def MIN-VALUE(state) : \n     if IS_TERMINAL(state) : \n       return state's utility\n      initialize v = +inf\n      for successor in state.successors() : \n        v = min(v, MAX-VALUE(successor))\n      return v\n\n }\n ```\n Runtime of MINIMAX : $O(b^m)$, since we essentially implement DFS on  entire game tree. \n\nALPHA - BETA PRUNING : \n\nWe can make this more efficient by pruning, or saving ourselves from exploring  large parts of the tree that would ultimately not affect the outcome.  Conceptually : consider node n on tree, such that Player has a choice of  moving to n. If Player has a better choice either at the same level OR  at any point higher up in the tree, then Player will never move to n. So  we can prune n.\n\n - ALPHA: MAX's current LOWER bound on MAX's outcome. MAX is 'at least' alpha.\n\n - BETA: MIN's current UPPER bound on MIN's outcome. MIN is 'at most' beta.\n\n PRUNE whenever:\n  - for MAX node : whenever value $v >= BETA$ is backed up : MIN will never   select that MAX node since beta is MIN's upper bound. Prune the remaining subtree.\n\n  - for MIN node : whenever value $v <= ALPHA $ is backed up : MAX will never   select that MIN node since alpha is MAX's upper bound. Prune the remaining subtree.\n\nNotes on effectiveness of alpha-beta pruning : \n\n- Effectivenss depends heavily on order in which states are examined. Could prune more or less of tree depending on this order.\n\n- If done perfectly, alpha-beta could only examine $O(b^{(m/2)})$, instead of $O(b^{m})$ for MINIMAX. Ie. effective branching factor becomes $\\sqrt{b}$. \n\nEXPECTIMAX : \n\nFor undertain outcomes controlled by chance, NOT an adversary, eg. dice rolls\n\n- Value should now reflect average-case : EXPECTIMAX, and not worst-case (MINIMAX) outcomes. \n\n- Chance nodes are like min nodes but outcome is uncertain : calculate expected utilities\n\n- Take weighted average (expectation) of children\n\n\n \n\n## Module 5 Definitions\n* **Concept** - definition\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 = \"\"\" Define CSPs \"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "CSPs take structure of problem into the account. Instead of treating each state \\\n",
        "as atomic/indivisible, we now represent a state as a set of variables. \n",
        "\n",
        "Problem is solved when each variable has a value that satisfies all the constraints \\\n",
        "on the variable. A state is defined as an assignment of values to some or all variables.\n",
        "\n",
        "CSPs assign values to variables. \n",
        "\n",
        "CSPs consist of : \n",
        "\n",
        "- Finite set of variables $X_{1}, ....X_{n}$\n",
        "\n",
        "- Nonempty domain of possible values for each variable : $D_{1}, ..., D_{n}$ \\\n",
        "where $D_{i} = {v_1, ...., v_k}$\n",
        "\n",
        "- Finite set of constraints $C_{1}, ..., C_{m}$ where each constraint limits \\\n",
        "the values that variables can take, eg. $X_{1} != X_{2}$.\n",
        "\n",
        "**Solution to a CSP is a consistent, complete assignment. \n",
        "\n",
        "Benefits of CSPs : \n",
        "\n",
        "- Can capture many more types of problems, is more generic. \n",
        "\n",
        "- Since CSP \"knows\" which variables violate a constraint, can prune off all \\\n",
        "branches that violate. \n",
        "\n",
        "\n",
        "Can represent CSP using a CONSTRAINT graph : \n",
        "\n",
        "- nodes = variables\n",
        "\n",
        "- arcs = (binary) constraints, ie. when each constraint relates 2 variables\n",
        "\n",
        "CSPs can be expressed as a search problem : \n",
        "\n",
        "- Initial state : {} empty assignment\n",
        "\n",
        "- Successor f'n : assign value to any unasigned variable provided that there \\\n",
        "is no constraint conflict (to ensure consistent)\n",
        "\n",
        "- Goal test : the current assignment is complete\n",
        "\n",
        "- path cost : constant cost for each step.\n",
        "\n",
        "Note : Solution always found at depth n, for n variables : use DFS.\n",
        "\n",
        "Search and branching factor : \n",
        "\n",
        "- n variables, domain size d. So branching factor at root is n*d. And branching factor \\\n",
        "at next level is (n-1) * d. So tree has $n!d^{n}$ leaves.\n",
        "\n",
        "- Variable assignments are COMMUTATIVE : order in which we assign variables does \\\n",
        "not matter. Only need to consider assignments to a single variable at each node. \\\n",
        "So instead of $n!d^{n}$ leaves, b = d so there are just $d^{n}$ leaves. \n",
        "\n",
        "- Backtracking search : ie. DFS for CSPs. Basic uninformed algo for CSPs.\n",
        "\n",
        "  - DFS chooses values for one variable at a time, and backtracks when a variable \\\n",
        "  has no legal values left to assign (ie. this will not lead to complete sol'n)\n",
        "\n",
        "- How to improve Backtracking search : \n",
        "\n",
        "  - 1. Next varaible assigned : most CONSTRAINED variable, IE. MRV \\\n",
        "   (minimum remaining values) heuristic\n",
        "  \n",
        "    - If ties : most CONSTRAINING variable (choose variable with the most constraints on the  \\\n",
        "  remaining variables.). \n",
        "\n",
        "  - 2. Order of variable's values : LEAST CONSTRAINING VALUE. (the one that \\\n",
        "  rules out the fewest values in remaining variables)\n",
        "\n",
        "  - 3. How to detect inevitable failure early : FORWARD CHECKING. Keep track of \\\n",
        "  remaining legal values for unassigned variables. Terminate search when any \\\n",
        "  unassigned variable has no remaining legal values. \n",
        "\n",
        "BUT issue is that forward checking propagates information from assigned to \\\n",
        "unassigned variables, but deson't provide early detection for ALL failures. \n",
        "\n",
        "So instead of forward checking, need to have CONSTRAINT PROPAGATION : \\\n",
        "repeatedly enforce constraints locally to eliminate failures early.\n",
        "\n",
        "Local consistency means : \n",
        "\n",
        "- Node consistency : satisfies unary constraints. eg. SA != WA. \n",
        "\n",
        "- Arc consistency : satisfies binary constraints. \n",
        "\n",
        "  - $X_{i}$ is arc-consistent w.r.t. $X_{j}$ if for every value v in $D_{i}$, \\\n",
        "  there is some value w in $D_{j}$ that satisfies the binary constraint on the \\\n",
        "  arc between $X_{i}$ and $X_{j}$. \n",
        "\n",
        "  - Graph is arc-consistent if every variable is arc-consistent with every \\\n",
        "  other variable. \n",
        "\n",
        "\n",
        "AC3 : most popular algo for enforcing arc consistency : \n",
        "\n",
        "- At each interetion, we only need to examine those $X_{i}$ where at least one \\\n",
        "neighbor or $X_{i}$ has lost a value in previous iteration. \n",
        "\n",
        "  - This is because : removing a value from tail can only make head arc-consistent \\\n",
        "  to the tail. So we only need to check the inverse pair, ie. switch order of \\\n",
        "  head and tail on next consistency check on next iteration. \n",
        "\n",
        "  -  If $X_{i}$ loses a value only because of arc inconsistencies with $Y_{j}$, \\\n",
        "we don't check $Y_{j}$ on the next iteration.\n",
        "\n",
        "```\n",
        "AC3 algo : \n",
        "{\n",
        "  dev AC3 (csp) : returns CSP, possibly with reduced domains\n",
        "    inputs : csp, a binary csp with variables {X_{1}, ..., X_{n}}. \n",
        "    local variables : queue, a queue of arcs, initially all the arcs in csp\n",
        "\n",
        "    while queue not empty : \n",
        "      (X_{i}, X_{j}) = queue.pop()\n",
        "      if REMOVE-INCONSISTENT-VALUES(X_{i}, X_{j}) : \n",
        "        for each X_{k} in (NEIGHBORS[X_{i} - {X_{j}}] : \n",
        "          add (X_{k}, X_{i})\n",
        "}\n",
        "{\n",
        "  def REMOVE-INCONSISTENT-VALUES(X_{i}, X_{j}) : return True iff we removed a value\n",
        "    removed = False\n",
        "    for each x in DOMAIN[X_{i}] : \n",
        "      if no value y in DOMAIN[X_{j}] allows (x,y) to satisfy constaints between X_{i} and X_{j} : \n",
        "        delete x from DOMAIN[X_{i}]\n",
        "        removed = True\n",
        "    return removed\n",
        "\n",
        "\n",
        "}\n",
        "```\n",
        "\n",
        "AC3 Complexity analysis : \n",
        "\n",
        "- $O(n^{2})$, since all nodes can be connected to every other node, so \\\n",
        "$n * (n-1)$\n",
        "\n",
        "- If there are d values, checking arc (i,j) takes $O(d^{2})$ time\n",
        "\n",
        "- Each arc (i,j) can only be inserted into the queue d times\n",
        "\n",
        "- Worst case complexity  = $O(n^{2}d^{3})$\n",
        "\n",
        "  - For planar constraint graphs, ie. no crossing edges, #arcs is linear \\\n",
        "  in N and so time complexity is only $O(nd^{3})$\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP\" : \"problem where states are represented as sets of variables and value\", \n",
        "\"Consistent assignment\" : \"does not violate the constraints\", \n",
        "\"Complete assignment\" : \"every variable is assigned a value. \", \n",
        "\"Unary constraint\" : \"involve a single variable  eg SA != green\",\n",
        "\"Binary constraint\" : \"involve pairs of variables eg. SA != WA\",\n",
        "\"Higher-order constraints\" : \"constraints involving 2+ variables\",\n",
        "\n",
        "\n",
        "}\n"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "a8e8be25-9bf2-47ba-fced-538825a3a5e3"
      },
      "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": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Define CSPs \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \nCSPs take structure of problem into the account. Instead of treating each state as atomic/indivisible, we now represent a state as a set of variables. \n\nProblem is solved when each variable has a value that satisfies all the constraints on the variable. A state is defined as an assignment of values to some or all variables.\n\nCSPs assign values to variables. \n\nCSPs consist of : \n\n- Finite set of variables $X_{1}, ....X_{n}$\n\n- Nonempty domain of possible values for each variable : $D_{1}, ..., D_{n}$ where $D_{i} = {v_1, ...., v_k}$\n\n- Finite set of constraints $C_{1}, ..., C_{m}$ where each constraint limits the values that variables can take, eg. $X_{1} != X_{2}$.\n\n**Solution to a CSP is a consistent, complete assignment. \n\nBenefits of CSPs : \n\n- Can capture many more types of problems, is more generic. \n\n- Since CSP \"knows\" which variables violate a constraint, can prune off all branches that violate. \n\n\nCan represent CSP using a CONSTRAINT graph : \n\n- nodes = variables\n\n- arcs = (binary) constraints, ie. when each constraint relates 2 variables\n\nCSPs can be expressed as a search problem : \n\n- Initial state : {} empty assignment\n\n- Successor f'n : assign value to any unasigned variable provided that there is no constraint conflict (to ensure consistent)\n\n- Goal test : the current assignment is complete\n\n- path cost : constant cost for each step.\n\nNote : Solution always found at depth n, for n variables : use DFS.\n\nSearch and branching factor : \n\n- n variables, domain size d. So branching factor at root is n*d. And branching factor at next level is (n-1) * d. So tree has $n!d^{n}$ leaves.\n\n- Variable assignments are COMMUTATIVE : order in which we assign variables does not matter. Only need to consider assignments to a single variable at each node. So instead of $n!d^{n}$ leaves, b = d so there are just $d^{n}$ leaves. \n\n- Backtracking search : ie. DFS for CSPs. Basic uninformed algo for CSPs.\n\n  - DFS chooses values for one variable at a time, and backtracks when a variable   has no legal values left to assign (ie. this will not lead to complete sol'n)\n\n- How to improve Backtracking search : \n\n  - 1. Next varaible assigned : most CONSTRAINED variable, IE. MRV    (minimum remaining values) heuristic\n  \n    - If ties : most CONSTRAINING variable (choose variable with the most constraints on the    remaining variables.). \n\n  - 2. Order of variable's values : LEAST CONSTRAINING VALUE. (the one that   rules out the fewest values in remaining variables)\n\n  - 3. How to detect inevitable failure early : FORWARD CHECKING. Keep track of   remaining legal values for unassigned variables. Terminate search when any   unassigned variable has no remaining legal values. \n\nBUT issue is that forward checking propagates information from assigned to unassigned variables, but deson't provide early detection for ALL failures. \n\nSo instead of forward checking, need to have CONSTRAINT PROPAGATION : repeatedly enforce constraints locally to eliminate failures early.\n\nLocal consistency means : \n\n- Node consistency : satisfies unary constraints. eg. SA != WA. \n\n- Arc consistency : satisfies binary constraints. \n\n  - $X_{i}$ is arc-consistent w.r.t. $X_{j}$ if for every value v in $D_{i}$,   there is some value w in $D_{j}$ that satisfies the binary constraint on the   arc between $X_{i}$ and $X_{j}$. \n\n  - Graph is arc-consistent if every variable is arc-consistent with every   other variable. \n\n\nAC3 : most popular algo for enforcing arc consistency : \n\n- At each interetion, we only need to examine those $X_{i}$ where at least one neighbor or $X_{i}$ has lost a value in previous iteration. \n\n  - This is because : removing a value from tail can only make head arc-consistent   to the tail. So we only need to check the inverse pair, ie. switch order of   head and tail on next consistency check on next iteration. \n\n  -  If $X_{i}$ loses a value only because of arc inconsistencies with $Y_{j}$, we don't check $Y_{j}$ on the next iteration.\n\n```\nAC3 algo : \n{\n  dev AC3 (csp) : returns CSP, possibly with reduced domains\n    inputs : csp, a binary csp with variables {X_{1}, ..., X_{n}}. \n    local variables : queue, a queue of arcs, initially all the arcs in csp\n\n    while queue not empty : \n      (X_{i}, X_{j}) = queue.pop()\n      if REMOVE-INCONSISTENT-VALUES(X_{i}, X_{j}) : \n        for each X_{k} in (NEIGHBORS[X_{i} - {X_{j}}] : \n          add (X_{k}, X_{i})\n}\n{\n  def REMOVE-INCONSISTENT-VALUES(X_{i}, X_{j}) : return True iff we removed a value\n    removed = False\n    for each x in DOMAIN[X_{i}] : \n      if no value y in DOMAIN[X_{j}] allows (x,y) to satisfy constaints between X_{i} and X_{j} : \n        delete x from DOMAIN[X_{i}]\n        removed = True\n    return removed\n\n\n}\n```\n\nAC3 Complexity analysis : \n\n- $O(n^{2})$, since all nodes can be connected to every other node, so $n * (n-1)$\n\n- If there are d values, checking arc (i,j) takes $O(d^{2})$ time\n\n- Each arc (i,j) can only be inserted into the queue d times\n\n- Worst case complexity  = $O(n^{2}d^{3})$\n\n  - For planar constraint graphs, ie. no crossing edges, #arcs is linear   in N and so time complexity is only $O(nd^{3})$\n \n\n## Module 6 Definitions\n* **Csp** - problem where states are represented as sets of variables and value\n* **Consistent assignment** - does not violate the constraints\n* **Complete assignment** - every variable is assigned a value. \n* **Unary constraint** - involve a single variable  eg SA != green\n* **Binary constraint** - involve pairs of variables eg. SA != WA\n* **Higher-order constraints** - constraints involving 2+ variables\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" KB agents use a process of REASONING over an internal \\\n",
        "representation of knowledge to decide what action to take. \\\n",
        "\n",
        "KB agent can add new information to the KB through observations, and can also \\\n",
        "query the KB and ask it to derive new knowledge in order to select what action \\\n",
        "it should take.\n",
        "\n",
        "Models : \n",
        "\n",
        "- If sentence x is true in model m : \n",
        "\n",
        "  - m satisfies x, or m is a model of x. \n",
        "\n",
        "  - Use notation M(x) to mean the set of al models of x.\n",
        "\n",
        "Logical entailment : ie. setnece follows logically from another sentence\n",
        "\n",
        "- a ⊨ B : a entails sentence B iff M(a) is a subset of M(B). So a is \\\n",
        "more specific sentence than B. Eg. a = cat is feline, B = cat is animal. \\\n",
        "a entails B since if it's a feline, must be a cat.\n",
        "\n",
        "\n",
        "Logical Inference : process of deriving conclusions from entailment\n",
        "\n",
        "- We want to design inference algorithms to enumerate these additional \\\n",
        "sentences that are entailed given the sentences that have been added to the KB\n",
        "\n",
        "- when an inference algo i allows us to conclude that a is true, we write : \n",
        "\n",
        "  - KB ⊢_i a : \"a is derived from KB by i\"\n",
        "\n",
        "- Sound : inference algo should only derive entailed sentences (ie valid sentences)\n",
        "\n",
        "- Complete : inference algo derives all sentences that are entailed (ALL valid)\n",
        "\n",
        "Propositional Logic : \n",
        "\n",
        "- Atomic sentences are represented with a single propositional symbols \\\n",
        "\n",
        "- Propositional symbols stand for a statement that can be T/F. \n",
        "\n",
        "- EG. W_1,3 is a propositional symbol that we choose to stand for \"There is \\\n",
        "a Wampa at location [1,3]\". \n",
        "\n",
        "- Use logical connectives (AND, NOT, OR, IMPLIES, IFF) to form complex sentences\n",
        "\n",
        "Logical equivalence :\n",
        "\n",
        "- Two sentences a and B are logically equivalent if they are true in the same set of \\\n",
        " models. \n",
        "\n",
        "  - a  ≡ B iff a ⊨ B AND B ⊨ a.\n",
        "\n",
        "\n",
        "Monotonicity implies Soundness : \n",
        "\n",
        "- Monotonicity says that the set of entailed sentence can only increase as \\\n",
        "information is added to the KB. \n",
        "\n",
        "  - if KB ⊨ a then KB ∧ B ⊨ a\n",
        "\n",
        "  - if we add additional info to KB, it doesn't invalidate any other info \\\n",
        "  that we've already added\n",
        "\n",
        "  - Therefore if it is sound, it will only derive entailed sentences.\n",
        "\n",
        "\n",
        "  Proof by resolution : \n",
        "\n",
        "  - Resolution is a single inference rule which yields a complete inference \\\n",
        "  algorithm when coupled with any complete search algo. \n",
        "\n",
        "  - If $l_i$ and m are complementary literals (ie. one is the negation \\\n",
        "  of the other), then we can eliminate via unit resolution.)\n",
        "\n",
        "\n",
        "  Conjunctive Normal Form (CNF) : \n",
        "\n",
        "  - Every sentence of propositional logic is logically equivalent to a \\\n",
        "  conjunction of clauses. Clauses are disjunctions of literals. \n",
        "\n",
        "    1. Biconditional elimination : Eliminate ↔ by replacing  \\\n",
        "    a ↔ B with (a → B) ∧ (B → a) \n",
        "\n",
        "    2. Implication elimination : Eliminate → by replacing a → B with ¬a ∨ B\n",
        "\n",
        "    3. DeMorgan's rules : Move ¬ inwards (eliminate double negation and apply\\\n",
        "    deMorgan's rules)\n",
        "\n",
        "    4. Now sentence will contain nested ∧ and ∨ operators applied to literals. \\\n",
        "    Apply distributivity law to distribute ∨ over ∧ wherever possible.\n",
        "\n",
        "\n",
        "Resolution algorithm : \n",
        "\n",
        "- Inference procedures based on resolution work using the principle of proof \\\n",
        "by contradiction. Result is a complete and sound inference method. \n",
        "\n",
        "- To show KB ⊨ a, show that KB ∧ ¬a is UNSATISFIABLE : contradiction.\n",
        "\n",
        "  1. Convert (KB ∧ ¬a) into CNF.\n",
        "\n",
        "  2. Apply resolution rule to the resulting clauses.\n",
        "\n",
        "  3. Resolve every pair that contains complementary literals to produce \\\n",
        "  a new clause.\n",
        "\n",
        "  4. If that new clause isn't already present, then add it to the set.\n",
        "\n",
        "  5. Continue process until EITHER : \n",
        "\n",
        "    1. No new clauses can be added : KB does NOT entail a. \n",
        "\n",
        "    2. Two clauses resolve to yield the empty clause(arising from resolving \\\n",
        "    two contradictory unit clauses eg. P and ¬P) : KB does NOT entail a. \n",
        "\n",
        "\n",
        "Can formulate a KB to be more restrictive (ie. add constraints to KB) \\\n",
        "to enable them to use more efficient inference algos  eg.\n",
        "\n",
        "  1. Definite clause : disjunction of literals where exactly 1 is positive\n",
        "\n",
        "  2. Horn clause : disjunction of literals where at LEAST one is positive \\\n",
        "  (including definite clauses and clauses with no positive literals)\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Axioms\" : \"sentence that is given\",   \n",
        "\"derived sentences\" : \"new sentence that is derived from other sentences\",\n",
        "\"inference\" : \"process of deriving new sentences from old\",\n",
        "\"Knowledge base\" : \"contains a set of sentences that are written in a KB language\",\n",
        "\"Logic\" : \"defines the semantics (true meaning) of the sentences\",\n",
        "\"model\" : \"mathematical abstractions that have a fixed set of truth values which \\\n",
        "are T/F for each sentence\"\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "de8aacf0-afd3-465c-a73a-708249bb8cc6"
      },
      "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": 35,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n KB agents use a process of REASONING over an internal representation of knowledge to decide what action to take. \nKB agent can add new information to the KB through observations, and can also query the KB and ask it to derive new knowledge in order to select what action it should take.\n\nModels : \n\n- If sentence x is true in model m : \n\n  - m satisfies x, or m is a model of x. \n\n  - Use notation M(x) to mean the set of al models of x.\n\nLogical entailment : ie. setnece follows logically from another sentence\n\n- a ⊨ B : a entails sentence B iff M(a) is a subset of M(B). So a is more specific sentence than B. Eg. a = cat is feline, B = cat is animal. a entails B since if it's a feline, must be a cat.\n\n\nLogical Inference : process of deriving conclusions from entailment\n\n- We want to design inference algorithms to enumerate these additional sentences that are entailed given the sentences that have been added to the KB\n\n- when an inference algo i allows us to conclude that a is true, we write : \n\n  - KB ⊢_i a : \"a is derived from KB by i\"\n\n- Sound : inference algo should only derive entailed sentences (ie valid sentences)\n\n- Complete : inference algo derives all sentences that are entailed (ALL valid)\n\nPropositional Logic : \n\n- Atomic sentences are represented with a single propositional symbols \n- Propositional symbols stand for a statement that can be T/F. \n\n- EG. W_1,3 is a propositional symbol that we choose to stand for \"There is a Wampa at location [1,3]\". \n\n- Use logical connectives (AND, NOT, OR, IMPLIES, IFF) to form complex sentences\n\nLogical equivalence :\n\n- Two sentences a and B are logically equivalent if they are true in the same set of  models. \n\n  - a  ≡ B iff a ⊨ B AND B ⊨ a.\n\n\nMonotonicity implies Soundness : \n\n- Monotonicity says that the set of entailed sentence can only increase as information is added to the KB. \n\n  - if KB ⊨ a then KB ∧ B ⊨ a\n\n  - if we add additional info to KB, it doesn't invalidate any other info   that we've already added\n\n  - Therefore if it is sound, it will only derive entailed sentences.\n\n\n  Proof by resolution : \n\n  - Resolution is a single inference rule which yields a complete inference   algorithm when coupled with any complete search algo. \n\n  - If $l_i$ and m are complementary literals (ie. one is the negation   of the other), then we can eliminate via unit resolution.)\n\n\n  Conjunctive Normal Form (CNF) : \n\n  - Every sentence of propositional logic is logically equivalent to a   conjunction of clauses. Clauses are disjunctions of literals. \n\n    1. Biconditional elimination : Eliminate ↔ by replacing      a ↔ B with (a → B) ∧ (B → a) \n\n    2. Implication elimination : Eliminate → by replacing a → B with ¬a ∨ B\n\n    3. DeMorgan's rules : Move ¬ inwards (eliminate double negation and apply    deMorgan's rules)\n\n    4. Now sentence will contain nested ∧ and ∨ operators applied to literals.     Apply distributivity law to distribute ∨ over ∧ wherever possible.\n\n\nResolution algorithm : \n\n- Inference procedures based on resolution work using the principle of proof by contradiction. Result is a complete and sound inference method. \n\n- To show KB ⊨ a, show that KB ∧ ¬a is UNSATISFIABLE : contradiction.\n\n  1. Convert (KB ∧ ¬a) into CNF.\n\n  2. Apply resolution rule to the resulting clauses.\n\n  3. Resolve every pair that contains complementary literals to produce   a new clause.\n\n  4. If that new clause isn't already present, then add it to the set.\n\n  5. Continue process until EITHER : \n\n    1. No new clauses can be added : KB does NOT entail a. \n\n    2. Two clauses resolve to yield the empty clause(arising from resolving     two contradictory unit clauses eg. P and ¬P) : KB does NOT entail a. \n\n\nCan formulate a KB to be more restrictive (ie. add constraints to KB) to enable them to use more efficient inference algos  eg.\n\n  1. Definite clause : disjunction of literals where exactly 1 is positive\n\n  2. Horn clause : disjunction of literals where at LEAST one is positive   (including definite clauses and clauses with no positive literals)\n\n\n\n\n\n\n\n\n\n\n \n\n## Module 7 Definitions\n* **Axioms** - sentence that is given\n* **Derived sentences** - new sentence that is derived from other sentences\n* **Inference** - process of deriving new sentences from old\n* **Knowledge base** - contains a set of sentences that are written in a KB language\n* **Logic** - defines the semantics (true meaning) of the sentences\n* **Model** - mathematical abstractions that have a fixed set of truth values which are T/F for each sentence\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": "a8bdf351-ea4f-4662-bd5c-95f5534a3ae2"
      },
      "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": 36,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Rational agent' is too long!\nWARNING: Your definition of 'Rational agent designer's goal' is too long!\nWARNING: Your definition of 'Types of environment, Deterministic vs Stochastic' is too long!\nWARNING: Your definition of 'Types of environment, fully observable vs partially observable' is too long!\nWARNING: Your definition of 'Types of environment, episodic vs sequential' is too long!\nWARNING: Your definition of 'Types of environment, Static vs dynamic' is too long!\n# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act through actuators in an environment.\n* **Agent (eg)** -  = architecture + program. EG agent : robots, softbots, thermostats, animals \n* **Percept** - agent's perceptual inputs at any given instance\n* **Agent function** - 'f:P ->a' : maps a sequence of percept vectors P to an action a from set A\n* **Agent program** - runs on the physical architecture to produce f\n* **Rational agent** - agent that perceives its environments and behaves rationally, ie. doing the right thing. For each possible percept sequence P, rational agent selects action a to maximize the expected value of its performance measure. NOTE : Rationality is NOT guaranteed success\n* **Performance measure** - objective criterion for success of agent's behaviour, given the evidence provided by percept sequence \n* **Task environment** - problem spec for agent to solve sol'n : PEAS : performance measure, environment, actuators, sensors\n* **Rational agent designer's goal** - Given a PEAS task environment, construct agent f'n f to maximize expected value of performane measure, 2) design agent program that implements f on a particular architecture\n* **Types of environment, deterministic vs stochastic** - DETERMINISTIC : one action has clear consequence; state of world determined by current state and recent choice of agent. Stochastic = probabilistic : many new states can arise from new action, depends on probability\n* **Types of environment, fully observable vs partially observable** - FULLY OBSEVABLE : task agent sensors can detect ALL aspects of environment relevant to agent's choice of actions. PARTIALLY OBSERVABLE : some parts of environment may be obscured (eg self driving cars\n* **Types of environment, episodic vs sequential** - EPISODIC : agent perceives environment, then performs a SINGLE action and the choice each action is NOT dependent on any previous action. SEQUENTIAL : current decision can affect all future actions : imeddiate decision impacts space of possible next choices\n* **Types of environment, static vs dynamic** - STATIC : environment remains unchanged while agent is deliberating about what action to take, eg. crossword puzzle. DYNAMIC : environment changing all the time even while agent is not acting\n* **Types of environment, discrete vs continuous** - DISCRETE = limited number of clearly defined definitions\n* **Types of environment, single vs multi-agent** - can be single agent, or multi agent with single opponent, or multi with multiple opponents\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nObjects and types : \n\n- All data treated as objects. An object is deleted (garbage collection) once unreachable. \n\n- Strong typing : every object has a fixed type interpreter that doesn't allow things incompatible with that type, eg. \"foo\" + 2, str + int not allowed. Can call type(object) or isinstance(object, type) to check.\n\n- Python  has DYNAMIC typing : variables come into existence when first assigned.Type(var) automatically determined. If assigned again, type(var) updated. \n  - Functions have no type signatures, meaning type errors are only caught   at runtime : not caught at compiler time. \n\n- Mutability : something that has the ability to be changed once created.\n\n  - IMMUTABLE : strings, ints, boolean, tuples\n\n  - MUTABLE : lists, sets, dicts\n\n- Slicing : returns a copy of a subsequence : \n  \n  - lst[1:4] :-> returns copy of list from index 1 to index(4-1)\n  \n  - lst[:] :-> returns copy of list\n\n  - lst[1:-1] :-> from index 1 until last item (-1 from end)\n\n\n- Dictionairies : unordered, work by hashing, so keys must be immutable. \n\n  - Constant avg time add, lookup, update\n\n\n- Generators : a kind of iterator object automatically created when keyword \"yield\" is used in code. We dynamically create iterator without having to explicitly create iterator object.\n\n- Functions : are \"first class objects\", meaning that they can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in python have. \n\n\n\n\n\n\n\n\n\n\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n## WARNING: Your definition of 'time/space complexity variables' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n We explore problem-searching agents : computational process is called SEARCH. Assume simple environment : single agent, fully observable, deterministic, static, discrete, known. If environment is Fully Observable, Deterministc, and Known, then solution to any problem is a FIXED SEQUENCE OF ACTIONS. Difference between Tree search and graph search : tree search simply lists all the states that can be reached. Graph search : checks to see if node has already been visited before adding to search queue. Uses more mem since must keep track of all poss states.\n```python\nBFS\n{\n  function BFS(problem) returns solution node or failure\n    node = NODE(problem.INITIAL)\n    if problem.IS_GOAL(node.STATE) : \n      return node\n    frontier = FIFO queue of nodes\n    reached = set of reached states\n    reached.add(problem.INITIAL)\n    while frontier not empty : \n      node = POP(frontier)\n      for child in EXPAND(problem, node) : \n        s = child.STATE\n        if problem.IS-GOAL(s) : \n          return child\n        if s is not in reached : \n          add s to reached\n          add child to frontier\n    return failure //ie. frontier is empty\n}\n{ //node data structure : contains variables like the state, pointer to parent node, action used to create this state, path cost.\n  function EXPAND(problem, node) yields successor nodes\n    s = node.STATE\n    for each action in problem.ACTIONS(s) : \n      s' = problem.RESULT(s, action)\n      cost = node.PATH_COST() + problem.ACTION_COST(s, action, s')\n      yield NODE(STATE = s', PARENT = node, ACTION = action, PATH_COST = cost) \n    \n}\n```\nDFS : expand deepest unexpanded node : Frontier is LIFO, so put successors at the FRONT of frontier successor list\n```python\nDFS\n{ function ITERATIVE_DEEPENING_SEARCH(problem) returns a solution node or failure\n  for depth = 0 to infinity : \n    result = DEPTH_LIMITED_SEARCH(problem, depth)\n    if result != cutoff : \n      return result\n  }\n{\n  function DEPTH_LIMITED_SEARCH(problem, l) returns node or failure or cutoff\n    frontier = LIFO queue (stack) with NODE(problem.INITIAL) as an element\n    result = failure\n    while frontier is not empty :\n      node = POP(frontier)\n      if problem.IS_GOAL(node.STATE) :\n        return node\n      if DEPTH(node) > l : \n        result = cutoff\n      else if not IS_CYCLE(node) : \n        for each child in EXPAND(problem, node) : \n          add child to frontier\n    return result\n}\n```\nDepth vs Breadth first search : use DEPTH-first search if 1) space restricted, 2) there are many poss solutions with long paths and if wrong paths are usually terminated quickly; 3) search can be fine-tuned quickly. Use BREATH-first search if : 1) possibly infinite paths; 2) if some sol'ns have short paths; 3) if you can quickly discard unlikely paths. DFS is not complete since it fails in infinite-depth spaces OR spaces with loops. In order to make DFS complete, we need to limit the depth, so that we avoid the infinite-path problem! If modify to avoid repeated states along path : DFS is complete IF finite spaces. \n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Reflex agent** - selects action based only on the current percept, ie. ignores percept history\n* **Procedure to solve** - 1. GOAL FORMULATION; 2) PROBLEM FORMULATION, 3) SEARCH, 4)EXECUTION\n* **State space** - set S of possible states environment can be in. Includes initial state and goal states\n* **Actions** - set of Actions available to agent given a state s. Action is applicable in s.\n* **Transition model** - describes what each action does. RESULT(s,a) reutrns state that results from doing action a in state s.\n* **Action cost function / path cost** - c(s,a,s') : numeric cost of applying action a in state s to reach state s'. Should reflect agent's performance measure.\n* **Path** - sequence of actions\n* **Solution** - path from s_i to s_g : from inital to goal state\n* **Optimal solution** - lowest path cost among all solutions\n* **Goal test** - s is a goal state if goal test function, 'GOAL(s)', is true\n* **Search tree** - representing the paths that a search algo has explored. Root = initial state, leaves are successor states\n* **Frontier** - states that are available for expanding (ie. applying legal actions to)\n* **Uninformed search** - all non-goal nodes in frontier look equally good\n* **Informed search** - some non-goal nodes can be RANKED above others\n* **Strategy** - order of tree expansion. We evaluate based on 1) Completeness(always find sol), optimality (least cost path), time complexity, space complexity\n* **Time/space complexity variables** - b = maximum branching factor, ie. max set of poss actions between 2 states; d = depth of shallowest goal node; m = max length of any path in state space\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Now we consider INFORMED strategies. \nUniform-cost search : ie Dijkstra's algo : expand node with lowest path cost. Frontier = priority queue ordered by g(n) : path cost. Difference with BFS : test if node is goal state when it is selected for EXPANSION, NOT when it is added to the frontier. The algo updates a node on the frontier if a better path to the same state is found : so always enqueue a node before checking if goal, since there can be 2 ways of reaching that nmode, and the other stil on the queue  would be less costly! \n\n\n\nNow, for informed search, we want to expand nodes based on an ESTIMATE which includes distance to goal. Sort frontier queue by this new f(n).\n\nGreedy Best-First-Search : attempt #1 at integrating heuristic knowledge. \nf(n) is some function that includes the estimate heuristic h(n) of the remaining distance to goal. \nBasic idea : set f(n) = h(n). \nIgnore g(n), ie. the cost to get to n.  Select node for expansion with MINIMAL f(n) : IE. expand node that is estimated  to be closest to goal. \n Properties of Greedy BFS : \n\n Complete : NOT Complete, since can get stuck in loops. \n\n Optimal : NO! Not guaranteed to return the lowest path FIRST.\n\n To guarantee optimality : A* SEARCH : best known form of best-first search. \n \n Key Idea : avoid expanding paths that area already expensive. Expand most promising first.\n\n total cost heuristic $ f(n) = g(n) + h(n)$ : sum of g(n) - actual cost so far to n, + h(n) - estimated cost to get from node to goal. \n\n Implementation : similar to Greedy : Frontier queue is priority queue by  increasing f(n). \n\n Admissible heuristics : $0 <= h(n) <= h*(n)$, where you $h*(n)$ is the true cost from n to goal.\n\n Since $h(n) >= 0$, so h(G) = 0 for any goal G.\n\n THEOREM : If h(n) is admissible, A* using Tree Search is OPTIMAL.\n\n Why?? -> Because admissible heuristics slow down bad plans but never outweigh true costs.  So true best plan will always eventually be expanded.\n\n Inadmissible (pessimistic) heuristics break optimality by trapping good plans  low on frontier = never get explored.\n\n - With an inadmissible heuristic, A* may or may NOT be cost optimal. Algorithm  may also never return solution given infinite search space.\n\n Algorithm : \n\n NOTE : algorithm doesn't end until the goal node is expanded, and so must be at the  top of the Frontier queue to ensure optimality.\n\n To find Admissible Heuristics : \n Cost of an optimal solution to a relaxed problem (fewer restrictions) is an  admissible heuristic for the original problem..\n\n Dominance : metric on which heuristic is better : \n If $h_2(n) >= h_1(n)$ for all n (both admissible) : ie. h2 gives higher remaining  distance\n\n Then $h_2$ dominates $h_1$. h2 is less optimistic but is more accurate than $h_1$ \n\n Note : h*(n) dominates all other heuristics.\n\nCONSISTENCY : \nConsistency is a stronger property to admissibility. \n\nA heuristic h(n) is consistent if, for every node n and every successor n' of n generated by an action a, we have : $$ h(n) <= c(n,a,n') + h(n') $$\n\n- Every consistent heuristic is admissible, but NOT vice versa. \n\n- With a consistent heuristic, A* is thus cost-optimal. \n\n\n## Module 4 Definitions\n* **Informed search strategy** - one that uses domain-specific hints about the location of goals, ie. uses some knowledge about remaining distance to goal\n* **Uniform-cost search** - extension of BFS but now assuming actions have different costs\n* **Heuristic function, h(n)** - estimated cost of the cheapest path from state at node n to goal. EG manhattan (straight line) distance\n* **Greedy best-first search** - expands node with the lowest h(n) (estimated cost to goal) : $f(n) = h(n)$ \n* **A* search** - f(n) = g(n) + h(n) : sum of actual cost so far + estimated cost to goal\n* **Admissible heuristics** - never overestimates cost to reach goal, ie. OPTIMISTIC\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n How to model games with adversaries: model game as game tree \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Optimal decision in games : MINIMAX algorithm and alpha-beta pruning \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic alpha-beta and cutoff search \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games : must evaluate expected value of chance nodes, then conduct minimax the same way. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Principle of maximum expected utility (MEU) : rational agent should choose the action that maximizes the agent's expected utility \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Utility theory \n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions (various) \n\n## Module 5 Lecture Notes\n Introduction of competitive environments : where 2+ agents have conflicting goals = adversarial search.\n\nAssume simplest game environment : multiagent, static, discrete, fully observable, strategic (next state determined by current state and action exectuted by the agent and the actions of one other agent.)\n\nAssume zero-sum : one agent wins = other loses.\n\nMINI-MAX algorithm : \n- All play is computed from MAX's vantage point.\n\n- When MAX moves, MAX attempts to MAXimize MAX's outcomes.\n\n- When MAX's OPPONENT moves, they attempt to MINimize MAX's outcome.\n\n- Root level (ie. level 0)= MAX\n\n- Alternate MAX/MIN labels for each successive ply (tree level) from root.Even levels : MAX. Odd levels : MIN.\n\n- Nodes represent \"board positions\"; edges represent legal moves. \n\n- Evaluation function f(n) : evaluates how \"good\" a board position is. IE. assigns a real-number score to board positions(static features of the  board alone) without reference to path. \n\n - $f(n) > 0 $ if MAX is winning in position n. \n\n - $f(n) = 0 $ if position n is tied\n\n - $f(n) < 0 $ if MIN is winning in position n.\n\n Can count f(n) as 'number of moves available for MAX - number of moves  available for MIN. \n \n OR eg. for chess : f(n) =  (sum of A's piece values) - (sum of B's piece values)\n\n MINIMAX rule : make the best move for MAX assuming that MIN will always reply with the best move for MIN. Can find the backed up value of each node by  determining the values of its children : \n\n - For MAX node, backed-up value is the MAXIMUM of the values of its children  (ie. best for MAX)\n\n - For MIN node, backed-up value is the MINIMUM of the values of its children  (ie. best for MIN)\n\n ```\n MINIMAX IMPLEMENTATION : Recursively call max and min functions until base case\n {\n   def MAX-VALUE(state) : \n     if IS_TERMINAL(state) : \n       return state's utility\n      initialize v = -inf\n      for successor in state.successors() : \n        v = max(v, MIN-VALUE(successor))\n      return v\n }\n {\n   def MIN-VALUE(state) : \n     if IS_TERMINAL(state) : \n       return state's utility\n      initialize v = +inf\n      for successor in state.successors() : \n        v = min(v, MAX-VALUE(successor))\n      return v\n\n }\n ```\n Runtime of MINIMAX : $O(b^m)$, since we essentially implement DFS on  entire game tree. \n\nALPHA - BETA PRUNING : \n\nWe can make this more efficient by pruning, or saving ourselves from exploring  large parts of the tree that would ultimately not affect the outcome.  Conceptually : consider node n on tree, such that Player has a choice of  moving to n. If Player has a better choice either at the same level OR  at any point higher up in the tree, then Player will never move to n. So  we can prune n.\n\n - ALPHA: MAX's current LOWER bound on MAX's outcome. MAX is 'at least' alpha.\n\n - BETA: MIN's current UPPER bound on MIN's outcome. MIN is 'at most' beta.\n\n PRUNE whenever:\n  - for MAX node : whenever value $v >= BETA$ is backed up : MIN will never   select that MAX node since beta is MIN's upper bound. Prune the remaining subtree.\n\n  - for MIN node : whenever value $v <= ALPHA $ is backed up : MAX will never   select that MIN node since alpha is MAX's upper bound. Prune the remaining subtree.\n\nNotes on effectiveness of alpha-beta pruning : \n\n- Effectivenss depends heavily on order in which states are examined. Could prune more or less of tree depending on this order.\n\n- If done perfectly, alpha-beta could only examine $O(b^{(m/2)})$, instead of $O(b^{m})$ for MINIMAX. Ie. effective branching factor becomes $\\sqrt{b}$. \n\nEXPECTIMAX : \n\nFor undertain outcomes controlled by chance, NOT an adversary, eg. dice rolls\n\n- Value should now reflect average-case : EXPECTIMAX, and not worst-case (MINIMAX) outcomes. \n\n- Chance nodes are like min nodes but outcome is uncertain : calculate expected utilities\n\n- Take weighted average (expectation) of children\n\n\n \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Define CSPs \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \nCSPs take structure of problem into the account. Instead of treating each state as atomic/indivisible, we now represent a state as a set of variables. \n\nProblem is solved when each variable has a value that satisfies all the constraints on the variable. A state is defined as an assignment of values to some or all variables.\n\nCSPs assign values to variables. \n\nCSPs consist of : \n\n- Finite set of variables $X_{1}, ....X_{n}$\n\n- Nonempty domain of possible values for each variable : $D_{1}, ..., D_{n}$ where $D_{i} = {v_1, ...., v_k}$\n\n- Finite set of constraints $C_{1}, ..., C_{m}$ where each constraint limits the values that variables can take, eg. $X_{1} != X_{2}$.\n\n**Solution to a CSP is a consistent, complete assignment. \n\nBenefits of CSPs : \n\n- Can capture many more types of problems, is more generic. \n\n- Since CSP \"knows\" which variables violate a constraint, can prune off all branches that violate. \n\n\nCan represent CSP using a CONSTRAINT graph : \n\n- nodes = variables\n\n- arcs = (binary) constraints, ie. when each constraint relates 2 variables\n\nCSPs can be expressed as a search problem : \n\n- Initial state : {} empty assignment\n\n- Successor f'n : assign value to any unasigned variable provided that there is no constraint conflict (to ensure consistent)\n\n- Goal test : the current assignment is complete\n\n- path cost : constant cost for each step.\n\nNote : Solution always found at depth n, for n variables : use DFS.\n\nSearch and branching factor : \n\n- n variables, domain size d. So branching factor at root is n*d. And branching factor at next level is (n-1) * d. So tree has $n!d^{n}$ leaves.\n\n- Variable assignments are COMMUTATIVE : order in which we assign variables does not matter. Only need to consider assignments to a single variable at each node. So instead of $n!d^{n}$ leaves, b = d so there are just $d^{n}$ leaves. \n\n- Backtracking search : ie. DFS for CSPs. Basic uninformed algo for CSPs.\n\n  - DFS chooses values for one variable at a time, and backtracks when a variable   has no legal values left to assign (ie. this will not lead to complete sol'n)\n\n- How to improve Backtracking search : \n\n  - 1. Next varaible assigned : most CONSTRAINED variable, IE. MRV    (minimum remaining values) heuristic\n  \n    - If ties : most CONSTRAINING variable (choose variable with the most constraints on the    remaining variables.). \n\n  - 2. Order of variable's values : LEAST CONSTRAINING VALUE. (the one that   rules out the fewest values in remaining variables)\n\n  - 3. How to detect inevitable failure early : FORWARD CHECKING. Keep track of   remaining legal values for unassigned variables. Terminate search when any   unassigned variable has no remaining legal values. \n\nBUT issue is that forward checking propagates information from assigned to unassigned variables, but deson't provide early detection for ALL failures. \n\nSo instead of forward checking, need to have CONSTRAINT PROPAGATION : repeatedly enforce constraints locally to eliminate failures early.\n\nLocal consistency means : \n\n- Node consistency : satisfies unary constraints. eg. SA != WA. \n\n- Arc consistency : satisfies binary constraints. \n\n  - $X_{i}$ is arc-consistent w.r.t. $X_{j}$ if for every value v in $D_{i}$,   there is some value w in $D_{j}$ that satisfies the binary constraint on the   arc between $X_{i}$ and $X_{j}$. \n\n  - Graph is arc-consistent if every variable is arc-consistent with every   other variable. \n\n\nAC3 : most popular algo for enforcing arc consistency : \n\n- At each interetion, we only need to examine those $X_{i}$ where at least one neighbor or $X_{i}$ has lost a value in previous iteration. \n\n  - This is because : removing a value from tail can only make head arc-consistent   to the tail. So we only need to check the inverse pair, ie. switch order of   head and tail on next consistency check on next iteration. \n\n  -  If $X_{i}$ loses a value only because of arc inconsistencies with $Y_{j}$, we don't check $Y_{j}$ on the next iteration.\n\n```\nAC3 algo : \n{\n  dev AC3 (csp) : returns CSP, possibly with reduced domains\n    inputs : csp, a binary csp with variables {X_{1}, ..., X_{n}}. \n    local variables : queue, a queue of arcs, initially all the arcs in csp\n\n    while queue not empty : \n      (X_{i}, X_{j}) = queue.pop()\n      if REMOVE-INCONSISTENT-VALUES(X_{i}, X_{j}) : \n        for each X_{k} in (NEIGHBORS[X_{i} - {X_{j}}] : \n          add (X_{k}, X_{i})\n}\n{\n  def REMOVE-INCONSISTENT-VALUES(X_{i}, X_{j}) : return True iff we removed a value\n    removed = False\n    for each x in DOMAIN[X_{i}] : \n      if no value y in DOMAIN[X_{j}] allows (x,y) to satisfy constaints between X_{i} and X_{j} : \n        delete x from DOMAIN[X_{i}]\n        removed = True\n    return removed\n\n\n}\n```\n\nAC3 Complexity analysis : \n\n- $O(n^{2})$, since all nodes can be connected to every other node, so $n * (n-1)$\n\n- If there are d values, checking arc (i,j) takes $O(d^{2})$ time\n\n- Each arc (i,j) can only be inserted into the queue d times\n\n- Worst case complexity  = $O(n^{2}d^{3})$\n\n  - For planar constraint graphs, ie. no crossing edges, #arcs is linear   in N and so time complexity is only $O(nd^{3})$\n \n\n## Module 6 Definitions\n* **Csp** - problem where states are represented as sets of variables and value\n* **Consistent assignment** - does not violate the constraints\n* **Complete assignment** - every variable is assigned a value. \n* **Unary constraint** - involve a single variable  eg SA != green\n* **Binary constraint** - involve pairs of variables eg. SA != WA\n* **Higher-order constraints** - constraints involving 2+ variables\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n KB agents use a process of REASONING over an internal representation of knowledge to decide what action to take. \nKB agent can add new information to the KB through observations, and can also query the KB and ask it to derive new knowledge in order to select what action it should take.\n\nModels : \n\n- If sentence x is true in model m : \n\n  - m satisfies x, or m is a model of x. \n\n  - Use notation M(x) to mean the set of al models of x.\n\nLogical entailment : ie. setnece follows logically from another sentence\n\n- a ⊨ B : a entails sentence B iff M(a) is a subset of M(B). So a is more specific sentence than B. Eg. a = cat is feline, B = cat is animal. a entails B since if it's a feline, must be a cat.\n\n\nLogical Inference : process of deriving conclusions from entailment\n\n- We want to design inference algorithms to enumerate these additional sentences that are entailed given the sentences that have been added to the KB\n\n- when an inference algo i allows us to conclude that a is true, we write : \n\n  - KB ⊢_i a : \"a is derived from KB by i\"\n\n- Sound : inference algo should only derive entailed sentences (ie valid sentences)\n\n- Complete : inference algo derives all sentences that are entailed (ALL valid)\n\nPropositional Logic : \n\n- Atomic sentences are represented with a single propositional symbols \n- Propositional symbols stand for a statement that can be T/F. \n\n- EG. W_1,3 is a propositional symbol that we choose to stand for \"There is a Wampa at location [1,3]\". \n\n- Use logical connectives (AND, NOT, OR, IMPLIES, IFF) to form complex sentences\n\nLogical equivalence :\n\n- Two sentences a and B are logically equivalent if they are true in the same set of  models. \n\n  - a  ≡ B iff a ⊨ B AND B ⊨ a.\n\n\nMonotonicity implies Soundness : \n\n- Monotonicity says that the set of entailed sentence can only increase as information is added to the KB. \n\n  - if KB ⊨ a then KB ∧ B ⊨ a\n\n  - if we add additional info to KB, it doesn't invalidate any other info   that we've already added\n\n  - Therefore if it is sound, it will only derive entailed sentences.\n\n\n  Proof by resolution : \n\n  - Resolution is a single inference rule which yields a complete inference   algorithm when coupled with any complete search algo. \n\n  - If $l_i$ and m are complementary literals (ie. one is the negation   of the other), then we can eliminate via unit resolution.)\n\n\n  Conjunctive Normal Form (CNF) : \n\n  - Every sentence of propositional logic is logically equivalent to a   conjunction of clauses. Clauses are disjunctions of literals. \n\n    1. Biconditional elimination : Eliminate ↔ by replacing      a ↔ B with (a → B) ∧ (B → a) \n\n    2. Implication elimination : Eliminate → by replacing a → B with ¬a ∨ B\n\n    3. DeMorgan's rules : Move ¬ inwards (eliminate double negation and apply    deMorgan's rules)\n\n    4. Now sentence will contain nested ∧ and ∨ operators applied to literals.     Apply distributivity law to distribute ∨ over ∧ wherever possible.\n\n\nResolution algorithm : \n\n- Inference procedures based on resolution work using the principle of proof by contradiction. Result is a complete and sound inference method. \n\n- To show KB ⊨ a, show that KB ∧ ¬a is UNSATISFIABLE : contradiction.\n\n  1. Convert (KB ∧ ¬a) into CNF.\n\n  2. Apply resolution rule to the resulting clauses.\n\n  3. Resolve every pair that contains complementary literals to produce   a new clause.\n\n  4. If that new clause isn't already present, then add it to the set.\n\n  5. Continue process until EITHER : \n\n    1. No new clauses can be added : KB does NOT entail a. \n\n    2. Two clauses resolve to yield the empty clause(arising from resolving     two contradictory unit clauses eg. P and ¬P) : KB does NOT entail a. \n\n\nCan formulate a KB to be more restrictive (ie. add constraints to KB) to enable them to use more efficient inference algos  eg.\n\n  1. Definite clause : disjunction of literals where exactly 1 is positive\n\n  2. Horn clause : disjunction of literals where at LEAST one is positive   (including definite clauses and clauses with no positive literals)\n\n\n\n\n\n\n\n\n\n\n \n\n## Module 7 Definitions\n* **Axioms** - sentence that is given\n* **Derived sentences** - new sentence that is derived from other sentences\n* **Inference** - process of deriving new sentences from old\n* **Knowledge base** - contains a set of sentences that are written in a KB language\n* **Logic** - defines the semantics (true meaning) of the sentences\n* **Model** - mathematical abstractions that have a fixed set of truth values which are T/F for each sentence\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}