{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "“DRAFT Template_for CIS521_midterm notes.ipynb”的副本",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "0cbf15b5-820b-4b09-c3dc-3d59ff5c1454"
      },
      "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": 46,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "42e97b5e-87bd-4a45-870c-eb5ccc5bd10a"
      },
      "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": 47,
      "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": 48,
      "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 =  \"\"\" $$\\alpha \\implies \\beta$$\"\"\"\n",
        "chapter1_1 =  \"\"\"\n",
        "Your summary here\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "###Rantional Agents:\n",
        "**Agents:** \n",
        "- An agent is anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\n",
        "- A percept is the agent's perceptual inputs at any given instance.\n",
        "- An agent is specified by an **agent function** $$f:P\\longrightarrow a$$ that maps a sequence of percept vectors P to an action a from a set A.\n",
        "- Agent function & program: The **agent program** runs on physical **architecture** to produce f\n",
        "- **Agents** An agent is anything that can be viewd as:\n",
        "    - Perceiving its environment through sensors and\n",
        "    - Acting upon that environment through actuators\n",
        "\n",
        "###Rational Behavior & Expected Value:\n",
        "**Rational Agent**: A rational agent is an agent that perceives its environment and behaves rationally. Rational behavior: doing the right thing.\n",
        "- For each possible percept sequence P\n",
        "- a rational agents selects an action a\n",
        "- to maximize the **expected value** of its performance measure\n",
        "- Computational limitations make complete rationality unachievable - not omniscience\n",
        "\n",
        "**Performance measure**\n",
        "- An objective criterion for success of an agent's behavior\n",
        "- Given the evidence provided by the percept sequence\n",
        "- We want the performance measure: describe what you want to be achieved in the environment, rather than how you think the agent should behave.\n",
        "\n",
        "### Task Environments: **PEAS**\n",
        "To design a rational agents we need to specify a task environment: a problem specification for which the agent is a solution\n",
        "- P: Performance measure\n",
        "- E: Environment\n",
        "- A: Actuators\n",
        "- S: Sensors\n",
        "\n",
        "Goal of AI practitioner who designs rational agents:\n",
        "**Given a PEAS task environment,**\n",
        "- Cioonstruct agent function **f** that maximizes the expected value of the performance measure,\n",
        "- Design an agent program that implements **f** on a particular architecture\n",
        "\n",
        "### Problem Solving Agents & Problem Formulation\n",
        "Example: 8-puzzle\n",
        "Formulate goal\n",
        "- Pieces to end up in order as shown…\n",
        "- Formulate search problem\n",
        "    - States: configurations of the puzzle (9! configurations)\n",
        "    - Actions: Move one of the movable pieces (≤4 possible)\n",
        "    - Performance measure: minimize total moves \n",
        "- Find solution\n",
        "    - Sequence of pieces moved:  3,1,6,3,1,\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\",\n",
        "\"percept\" : \"the agent's perceptual inputs at any given instance.\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 49,
      "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": 1523
        },
        "cellView": "form",
        "outputId": "53a7a8ee-b1bf-409b-caf5-f4aa406e2550"
      },
      "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": 50,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nYour summary here\n\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 \n###Rantional Agents:\n**Agents:** \n- An agent is anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\n- A percept is the agent's perceptual inputs at any given instance.\n- An agent is specified by an **agent function** $$f:P\\longrightarrow a$$ that maps a sequence of percept vectors P to an action a from a set A.\n- Agent function & program: The **agent program** runs on physical **architecture** to produce f\n- **Agents** An agent is anything that can be viewd as:\n    - Perceiving its environment through sensors and\n    - Acting upon that environment through actuators\n\n###Rational Behavior & Expected Value:\n**Rational Agent**: A rational agent is an agent that perceives its environment and behaves rationally. Rational behavior: doing the right thing.\n- For each possible percept sequence P\n- a rational agents selects an action a\n- to maximize the **expected value** of its performance measure\n- Computational limitations make complete rationality unachievable - not omniscience\n\n**Performance measure**\n- An objective criterion for success of an agent's behavior\n- Given the evidence provided by the percept sequence\n- We want the performance measure: describe what you want to be achieved in the environment, rather than how you think the agent should behave.\n\n### Task Environments: **PEAS**\nTo design a rational agents we need to specify a task environment: a problem specification for which the agent is a solution\n- P: Performance measure\n- E: Environment\n- A: Actuators\n- S: Sensors\n\nGoal of AI practitioner who designs rational agents:\n**Given a PEAS task environment,**\n- Cioonstruct agent function **f** that maximizes the expected value of the performance measure,\n- Design an agent program that implements **f** on a particular architecture\n\n### Problem Solving Agents & Problem Formulation\nExample: 8-puzzle\nFormulate goal\n- Pieces to end up in order as shown…\n- Formulate search problem\n    - States: configurations of the puzzle (9! configurations)\n    - Actions: Move one of the movable pieces (≤4 possible)\n    - Performance measure: minimize total moves \n- Find solution\n    - Sequence of pieces moved:  3,1,6,3,1,\n \n\n## Module 1 Definitions\n* **Agent** - anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\n* **Percept** - the agent's perceptual inputs at any given instance.\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "###Python: Developed by Guido van Rossum in 1989\n",
        "- Fast development\n",
        "- Portable\n",
        "- Various built-in types: lists, dictionaries, sets\n",
        "- Large collection of support libraries: NumPy for Matlab like programming, Pandas for data analysis, Sklearn for machine learning, Pytorch and TensorFlow for deep learning\n",
        "\n",
        "###Objects and Types\n",
        "- All data treated as objects\n",
        "- Strong Typing: every object has a fixed type, interpreter doesn't allow things incompatible with that type (eg. \"foo\"+2)\n",
        "- Examples of Types: int, float; str, tuple, dict, list; bool: True, False; None, generator, function\n",
        "\n",
        "###Static vs. Dynamic Typing: Python is dynamic typing.\n",
        "\n",
        "###Strings:\n",
        "- Creation: \n",
        "    - Can use either single or double quotes Triple quote for multiline string and docstring\n",
        "- Concatenating strings:\n",
        "    - By separating string literals with whitespace Special use of ‘+’\n",
        "- Prefixing with r means raw. \n",
        "    - No need to escape special characters: r’\\n’ \n",
        "- String formatting\n",
        "    - Special use of ‘%’ (as in printf in C) print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\n",
        "- Immutable\n",
        "\n",
        "###References and Mutability\n",
        "- strings are immutable\n",
        "- == checks whether variables point to objects of the same value \n",
        "- is checks whether variables point to the same object\n",
        "- lists are mutable \n",
        "- use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value\n",
        "\n",
        "###Sequence Types: Tuples, Lists, and Strings\n",
        "- Tuple\n",
        "    - A simple immutable ordered sequence of items Immutable: a tuple cannot be modified once created Items can be of mixed types, including collection types\n",
        "- Strings\n",
        "    - Immutable Regular strings are Unicode and use 2-byte characters (Regular strings in Python 2 use 8-bit characters)\n",
        "- List\n",
        "    - Mutable ordered sequence of items of mixed types\n",
        "- Slicing\n",
        "- Operaitons on Lists\n",
        "    - a.append()\n",
        "    - a.insert(2,'i')\n",
        "    - a.index('b') #index of first occurrence\n",
        "    - a.count('b') #number of occurrences\n",
        "    - a.remove('b') #remove first occurrence\n",
        "    - a.revers() #reverse the list\n",
        "    - a.sort() #sort\n",
        "    - sorted(a) #return a *copy* sorted.\n",
        "- Operation on Strings\n",
        "    - s = \"Pretend this sentence makes sense.\" >>> words = s.split(\" \") \n",
        "    - words ['Pretend', 'this', 'sentence', 'makes', 'sense.'] \n",
        "    - \"_\".join(words) #join method of obj \"_\" 'Pretend_this_sentence_makes_sense.'\n",
        "    - s = 'dog' >>> s.capitalize() 'Dog'; >>> s.upper() 'DOG’; >>> ' hi --'.strip(' –') 'hi’ \n",
        "\n",
        "### Dictionaries: A mapping collection type\n",
        "- Dictionaries are unordered & work by hashing, so keys must be immutable\n",
        "- Constant average time add, lookup, update \n",
        "\n",
        "- Dict: Useful Methods\n",
        "    - d = {'user':'R2D2', 'p':1234, 'i':34} >>> d.keys() # List of current keys\n",
        "    - dict_keys(['user', 'p', 'i’])\n",
        "    - d.values() # List of current values. dict_values(['R2D2', 1234, 34])\n",
        "    - d.items() # List of item tuples. dict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)])\n",
        "- Defualt Dictionaries and Counters\n",
        "    - defaultdict automatically initializes nonexistent dictionary values \n",
        "    - d = defualtdict(str) #automatically give string key types \"\" value\n",
        "    - d = Counter() # automatically give key \"0\" value\n",
        "    - otherwise, retrieving any key that doesn't exist in the dict will raise a KeyError\n",
        "\n",
        "### Functions\n",
        "- When returning multiple values, it returns a tuple\n",
        "- Does not support overloading\n",
        "- Non-default argument should always precede default arguments; otherwise, it reports SyntaxError\n",
        "- *arg: Suppose you want to accept a variable number of non-keyword arguments to your\n",
        "function\n",
        "- **kwargs: Suppose you want to accept a variable number of keyword arguments to your\n",
        "function\n",
        "- Example: \\\\\n",
        "def myfun(positional, *args, **kwargs):\n",
        "    print(positional) \n",
        "    if args:\n",
        "        print(args) \n",
        "    if kwargs:\n",
        "        print(kwargs)\n",
        "myfun(\"hi\", \"the\", \"best\", \"food\", \"is\", \"tacos\", shell=\"soft\", meat=\"beef\")\\\\\n",
        "    hi \\\\\n",
        "    ('the', 'best', 'food', 'is', 'tacos’) \\\\\n",
        "    {'shell': 'soft', 'meat': 'beef'}\n",
        "- Functions are “first-class” objects\n",
        "    - First class object: An entity that can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have\n",
        "    - Functions are “first-class citizens”: Pass functions as arguments to other functions Return functions as the values from other functions Assign functions to variables or store them in data structures\n",
        "\n",
        "### Classes and Inheritance\n",
        "- To redefine a method of the parent class, include a new definition using the same\n",
        "name in the subclass.\n",
        "-  To execute the method in the parent class in addition to new code for some\n",
        "method, explicitly call the parent’s version of the method.\\\\\n",
        "parentClass.methodName(self, a, b, c)\\\\\n",
        "    The only time you ever explicitly pass self as an argument is when\n",
        "calling a method of an ancestor.\\\\\n",
        "    So use myOwnSubClass.methodName(a,b,c)\n",
        "\n",
        "### Duck Typing\n",
        "__init__: The constructor for the class.\n",
        "__len__ : Define how  len( obj ) works. \n",
        "__copy__: Define how to copy a class.\n",
        "__cmp__ : Define how == works for class. \n",
        "__add__ : Define how + works for class \n",
        "__neg__ : Define how unary negation works for class\n",
        "\n",
        "class Duck:\\\\\n",
        "    def fly(self):\\\\\n",
        "        print(\"Duck flying\")\\\\\n",
        "class Airplane:\\\\\n",
        "    def fly(self):\\\\\n",
        "        print(\"Airplane flying\")\\\\\n",
        "class Whale:\\\\\n",
        "    def swim(self):\\\\\n",
        "        print(\"Whale swimming\")\\\\\n",
        "def lift_off(entity)\\\\\n",
        "    entity.fly()\\\\\n",
        "\n",
        "duck = Duck()\\\\\n",
        "plane = Airplane()\\\\\n",
        "whale = Whale()\\\\\n",
        "lift_off(duck) Duck flying\\\\\n",
        "lift_off(plane) Airplane flying\\\\\n",
        "lift_off(whale) AttributeError: 'Whale' objecthas no attribute 'fly'\\\\\n",
        "\n",
        "\n",
        "### List Comprehensions\n",
        "[ **expression** for **name** in list if **filter** ]\n",
        "### Iterators:\n",
        "Iterable objects can be used in a  for loop because they have an __iter__ magic method, which converts them to iterator objects:\n",
        "### Generators: using yield\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": 51,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2556
        },
        "outputId": "9d981199-4b14-447a-d915-354f2520d09c"
      },
      "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": 52,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\n###Python: Developed by Guido van Rossum in 1989\n- Fast development\n- Portable\n- Various built-in types: lists, dictionaries, sets\n- Large collection of support libraries: NumPy for Matlab like programming, Pandas for data analysis, Sklearn for machine learning, Pytorch and TensorFlow for deep learning\n\n###Objects and Types\n- All data treated as objects\n- Strong Typing: every object has a fixed type, interpreter doesn't allow things incompatible with that type (eg. \"foo\"+2)\n- Examples of Types: int, float; str, tuple, dict, list; bool: True, False; None, generator, function\n\n###Static vs. Dynamic Typing: Python is dynamic typing.\n\n###Strings:\n- Creation: \n    - Can use either single or double quotes Triple quote for multiline string and docstring\n- Concatenating strings:\n    - By separating string literals with whitespace Special use of ‘+’\n- Prefixing with r means raw. \n    - No need to escape special characters: r’\n’ \n- String formatting\n    - Special use of ‘%’ (as in printf in C) print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\n- Immutable\n\n###References and Mutability\n- strings are immutable\n- == checks whether variables point to objects of the same value \n- is checks whether variables point to the same object\n- lists are mutable \n- use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value\n\n###Sequence Types: Tuples, Lists, and Strings\n- Tuple\n    - A simple immutable ordered sequence of items Immutable: a tuple cannot be modified once created Items can be of mixed types, including collection types\n- Strings\n    - Immutable Regular strings are Unicode and use 2-byte characters (Regular strings in Python 2 use 8-bit characters)\n- List\n    - Mutable ordered sequence of items of mixed types\n- Slicing\n- Operaitons on Lists\n    - a.append()\n    - a.insert(2,'i')\n    - a.index('b') #index of first occurrence\n    - a.count('b') #number of occurrences\n    - a.remove('b') #remove first occurrence\n    - a.revers() #reverse the list\n    - a.sort() #sort\n    - sorted(a) #return a *copy* sorted.\n- Operation on Strings\n    - s = \"Pretend this sentence makes sense.\" >>> words = s.split(\" \") \n    - words ['Pretend', 'this', 'sentence', 'makes', 'sense.'] \n    - \"_\".join(words) #join method of obj \"_\" 'Pretend_this_sentence_makes_sense.'\n    - s = 'dog' >>> s.capitalize() 'Dog'; >>> s.upper() 'DOG’; >>> ' hi --'.strip(' –') 'hi’ \n\n### Dictionaries: A mapping collection type\n- Dictionaries are unordered & work by hashing, so keys must be immutable\n- Constant average time add, lookup, update \n\n- Dict: Useful Methods\n    - d = {'user':'R2D2', 'p':1234, 'i':34} >>> d.keys() # List of current keys\n    - dict_keys(['user', 'p', 'i’])\n    - d.values() # List of current values. dict_values(['R2D2', 1234, 34])\n    - d.items() # List of item tuples. dict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)])\n- Defualt Dictionaries and Counters\n    - defaultdict automatically initializes nonexistent dictionary values \n    - d = defualtdict(str) #automatically give string key types \"\" value\n    - d = Counter() # automatically give key \"0\" value\n    - otherwise, retrieving any key that doesn't exist in the dict will raise a KeyError\n\n### Functions\n- When returning multiple values, it returns a tuple\n- Does not support overloading\n- Non-default argument should always precede default arguments; otherwise, it reports SyntaxError\n- *arg: Suppose you want to accept a variable number of non-keyword arguments to your\nfunction\n- **kwargs: Suppose you want to accept a variable number of keyword arguments to your\nfunction\n- Example: \\\ndef myfun(positional, *args, **kwargs):\n    print(positional) \n    if args:\n        print(args) \n    if kwargs:\n        print(kwargs)\nmyfun(\"hi\", \"the\", \"best\", \"food\", \"is\", \"tacos\", shell=\"soft\", meat=\"beef\")\\\n    hi \\\n    ('the', 'best', 'food', 'is', 'tacos’) \\\n    {'shell': 'soft', 'meat': 'beef'}\n- Functions are “first-class” objects\n    - First class object: An entity that can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have\n    - Functions are “first-class citizens”: Pass functions as arguments to other functions Return functions as the values from other functions Assign functions to variables or store them in data structures\n\n### Classes and Inheritance\n- To redefine a method of the parent class, include a new definition using the same\nname in the subclass.\n-  To execute the method in the parent class in addition to new code for some\nmethod, explicitly call the parent’s version of the method.\\\nparentClass.methodName(self, a, b, c)\\\n    The only time you ever explicitly pass self as an argument is when\ncalling a method of an ancestor.\\\n    So use myOwnSubClass.methodName(a,b,c)\n\n### Duck Typing\n__init__: The constructor for the class.\n__len__ : Define how  len( obj ) works. \n__copy__: Define how to copy a class.\n__cmp__ : Define how == works for class. \n__add__ : Define how + works for class \n__neg__ : Define how unary negation works for class\n\nclass Duck:\\\n    def fly(self):\\\n        print(\"Duck flying\")\\\nclass Airplane:\\\n    def fly(self):\\\n        print(\"Airplane flying\")\\\nclass Whale:\\\n    def swim(self):\\\n        print(\"Whale swimming\")\\\ndef lift_off(entity)\\\n    entity.fly()\\\n\nduck = Duck()\\\nplane = Airplane()\\\nwhale = Whale()\\\nlift_off(duck) Duck flying\\\nlift_off(plane) Airplane flying\\\nlift_off(whale) AttributeError: 'Whale' objecthas no attribute 'fly'\\\n\n\n### List Comprehensions\n[ **expression** for **name** in list if **filter** ]\n### Iterators:\nIterable objects can be used in a  for loop because they have an __iter__ magic method, which converts them to iterator objects:\n### Generators: using yield\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 = \"\"\" \n",
        "##Search Problems:\n",
        "###Problem Solving Agents & Problem Formulation\n",
        "- Reflex Agents:\n",
        "    - A simple reflex agent is one that selects an action based on the current percept\n",
        "    - It ignores the rest of the percept history\n",
        "- Problem_Solving Agent\n",
        "    - A problem-solving agent must plan ahead.\n",
        "    - The computational process that it undertakes is called search\n",
        "    - It will considdr **a sequence of actions** that form a path to a goal state\n",
        "    - Such a sequence is called a solution\n",
        "- Task environment and solution types:\n",
        "    - If the environment is:\n",
        "        - Fully observable\n",
        "        - Deterministic\n",
        "        - Known environment\\\\\n",
        "        The soluciont is a fixed sequence of actions\n",
        "    - If the environment is:\n",
        "        - Partially observable or\n",
        "        - Nondeterministic\\\\\n",
        "        The solution recommend different future actions, which is a branching strategy\n",
        "\n",
        "###A Formal Definition of a Problem:\n",
        "1. States: a set S\n",
        "2. An initial state s_i in S\n",
        "3. Actions: a set A, Actions(s) = the set of actions that can be executed for all s\n",
        "4. Transition Model: s_r is called a successor of s, if {s_i} 并 Successors(s_i)* = state space \n",
        "5. Path Cost(Performance Measure): must be additive\n",
        "6. Goal Test: Goal(s); s is a goal if Goal(s) is true\n",
        "\n",
        "###Solutions & Optimal Solutions:\n",
        "- A solution is a sequence of actions from the initial state to a goal state\n",
        "- Optimal Solution: A solution is optimal if it has the lowest path cost among all other solutions\n",
        "\n",
        "###Useful Concepts:\n",
        "- State space: the set of all states reachable from the initial state by any sequence of actions:\n",
        "    - When several operators can apply to each state, this gets large very quickly\n",
        "    - Might be a proper subset of the set of configurations\n",
        "- Path: a sequence of actions leading from one state s_j to another state s_k \n",
        "- Frontier: those states that are available for expanding (for applying legal actions to) \n",
        "- Solution: a path from the initial state si to a state sf that satisfies the goal test\n",
        "\n",
        "###Basic search algorithms: Tree Search\n",
        "- Generalized algorithm to solve search problems \n",
        "- Enumerate in some order all possible paths from the initial state\n",
        "    - Here: search through explicit tree generation\n",
        "    - ROOT= initial state. \n",
        "    - Nodes in search tree generated through transition model \n",
        "    - Tree search treats different paths to the same node as distinct\n",
        "\n",
        "##Uninformed Search Strategies\n",
        "###Search Strategies\n",
        "**IMPORTANT**\n",
        "Review: Strategy = order of tree expansion\n",
        "- Implemented by different queue structures (LIFO, FIFO, priority)\\\\\n",
        "Dimensions for evaluation\n",
        "- Completeness: always find the solution?\n",
        "- Optimality: finds a least cost solution (lowest path cost) first?\n",
        "- Time complexity: # of nodes generated (worst case)\n",
        "- Space complexity: # of nodes simultaneously in memory (worst case)\n",
        "Time/space complexity variables\n",
        "- b, maximum branching factor of search tree\n",
        "- d, depth of the shallowest goal node\n",
        "- m, maximum length of any path in the state space (potentially infinity)\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\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",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 53,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1701
        },
        "outputId": "f7b4c1e6-0fff-4911-ef8f-1c85e5cfbec7"
      },
      "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": 54,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n \n##Search Problems:\n###Problem Solving Agents & Problem Formulation\n- Reflex Agents:\n    - A simple reflex agent is one that selects an action based on the current percept\n    - It ignores the rest of the percept history\n- Problem_Solving Agent\n    - A problem-solving agent must plan ahead.\n    - The computational process that it undertakes is called search\n    - It will considdr **a sequence of actions** that form a path to a goal state\n    - Such a sequence is called a solution\n- Task environment and solution types:\n    - If the environment is:\n        - Fully observable\n        - Deterministic\n        - Known environment\\\n        The soluciont is a fixed sequence of actions\n    - If the environment is:\n        - Partially observable or\n        - Nondeterministic\\\n        The solution recommend different future actions, which is a branching strategy\n\n###A Formal Definition of a Problem:\n1. States: a set S\n2. An initial state s_i in S\n3. Actions: a set A, Actions(s) = the set of actions that can be executed for all s\n4. Transition Model: s_r is called a successor of s, if {s_i} 并 Successors(s_i)* = state space \n5. Path Cost(Performance Measure): must be additive\n6. Goal Test: Goal(s); s is a goal if Goal(s) is true\n\n###Solutions & Optimal Solutions:\n- A solution is a sequence of actions from the initial state to a goal state\n- Optimal Solution: A solution is optimal if it has the lowest path cost among all other solutions\n\n###Useful Concepts:\n- State space: the set of all states reachable from the initial state by any sequence of actions:\n    - When several operators can apply to each state, this gets large very quickly\n    - Might be a proper subset of the set of configurations\n- Path: a sequence of actions leading from one state s_j to another state s_k \n- Frontier: those states that are available for expanding (for applying legal actions to) \n- Solution: a path from the initial state si to a state sf that satisfies the goal test\n\n###Basic search algorithms: Tree Search\n- Generalized algorithm to solve search problems \n- Enumerate in some order all possible paths from the initial state\n    - Here: search through explicit tree generation\n    - ROOT= initial state. \n    - Nodes in search tree generated through transition model \n    - Tree search treats different paths to the same node as distinct\n\n##Uninformed Search Strategies\n###Search Strategies\n**IMPORTANT**\nReview: Strategy = order of tree expansion\n- Implemented by different queue structures (LIFO, FIFO, priority)\\\nDimensions for evaluation\n- Completeness: always find the solution?\n- Optimality: finds a least cost solution (lowest path cost) first?\n- Time complexity: # of nodes generated (worst case)\n- Space complexity: # of nodes simultaneously in memory (worst case)\nTime/space complexity variables\n- b, maximum branching factor of search tree\n- d, depth of the shallowest goal node\n- m, maximum length of any path in the state space (potentially infinity)\n\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\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",
            "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 = \"\"\" \n",
        "##\"Uniformed Cost\" Search\n",
        "In computer science, uniform-cost search is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph.\n",
        "## g(N): the path cost function\n",
        "- Assumption so far: All moves equal in cost\n",
        "    - Cost = # of nodes in path-1\n",
        "    - g(N) = depth(N) in the search tree\n",
        "\n",
        "##Uniform-cost Search (=Best-first Search+path cost)\n",
        "- Extension of BFS\n",
        "    - Expand node with lowest path cost\n",
        "- Implementation:\n",
        "    - frontier = priority queue ordered by g(n)\n",
        "- Subtle but significant difference from BFS:\n",
        "    - Tests if a node is a goal state when it is selected for expansion, not when it is added to the frontier.\n",
        "    - Updates a node on the frontier if a better path to the same state is found.\n",
        "    - So always enqueues a node before checking whether it is a goal\n",
        "\n",
        "##Greedy Best-First Search\n",
        "###Recap of Best-first Search:\n",
        "Basic idea: select node for expansion with minimal evaluation function f(n)\n",
        "- where f(n) is some function that included estimate heuristic h(n) of the remaining distance to goal\n",
        "- Implement using priority queue\n",
        "- Exactly UCS with f(n) replacing g(n)\\\\\n",
        "\n",
        "##Greedy Best-First Search: f(n) = h(n)\n",
        "Expandes the node that is estimated to be closest to goal\\\\\n",
        "Completely ignores g(n): the cost to get to n\\\\\n",
        "- Manhattan distance:\\\\\n",
        "def heuristic(a, b):\\\\\n",
        "return abs(a.x - b.x) + abs(a.y - b.y)\n",
        "\n",
        "##A* search\n",
        "Best-known form of best-first search.\\\\\n",
        "Key Idea: avoid expanding paths that are already expensive, but expand most promising first.\\\\\n",
        "Simple idea: f(n)=g(n)+h(n)\n",
        "- g(n): the actual cost(so far) to reach the node\n",
        "- h(n): estimated cost to get from the node to the goal\n",
        "- f(n): estimated total cost of path through n to goal\n",
        "Implementation: Frontier queue as priority queue by increasing f(n)\n",
        "\n",
        "###Key concept: admissible heuristics\n",
        "A heuristic h(n) is admissible if it never overestimates the cost to reach the goal(optimistic).\\\\\n",
        "For all n, n is a node:\n",
        "- h(n) <= h*(n), h*(n) is the true cost to a nearest goal\n",
        "- h(n) >= 0\n",
        "- If h(n) is admissible, A* using Tree Search is optimal\n",
        "\n",
        "###Relaxed problems:\n",
        "A problem with fewer restrictions on the actions than the original is called a relaxed problem\\\\\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the\n",
        "original problem\\\\\n",
        "If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h_oop(n)\n",
        "gives the shortest solution\\\\\n",
        "If the rules are relaxed so that a tile can move to any adjacent square, then h_md(n)\n",
        "gives the shortest solution\n",
        "\n",
        "###Defining Heuristics: h(n)\n",
        "Cost of an exact solution to a relaxed problem\\\\\n",
        "Constraints on Full Problem:\\\\\n",
        "A tile can move from square A to square B if A is adjacent to B and B is blank.\\\\\n",
        "Constraints on relaxed problems:\n",
        "- A tile can move from square A to square B if A is adjacent to B. (h_md) \n",
        "- A tile can move from square A to square B if B is blank.\n",
        "- A tile can move from square A to square B. (h_oop)\n",
        "\n",
        "###Dominance: A measure of better heuristics\n",
        "If h_2(n) >= h_1(n) for all n (both admissible), then h_2 dominates h_1.\\\\\n",
        "h_2 is optimistic, but more accurate than h_1\n",
        "- h_2 is therefore better for search\n",
        "- h_md dominates h_oop\n",
        "####The best and worst admissible heuristics\n",
        "BEST: h*(n): the (unachievable) Oracle heuristic\n",
        "- h*(n) = the true distance from the n to goal. (Dominates all other heuristics)\n",
        "WORST: h_teleportation(n)=0. (Dominated by all heuristics)\n",
        "\n",
        "##A* search is optimal\n",
        "Admissible (optimistic) heuristics slow down bad plans but never outweigh true costs. That means that the true best plan will always be expanded.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 55,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1808
        },
        "outputId": "4bfe6895-a4ce-4f17-a2b1-961d463058af"
      },
      "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": 56,
      "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 \n##\"Uniformed Cost\" Search\nIn computer science, uniform-cost search is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph.\n## g(N): the path cost function\n- Assumption so far: All moves equal in cost\n    - Cost = # of nodes in path-1\n    - g(N) = depth(N) in the search tree\n\n##Uniform-cost Search (=Best-first Search+path cost)\n- Extension of BFS\n    - Expand node with lowest path cost\n- Implementation:\n    - frontier = priority queue ordered by g(n)\n- Subtle but significant difference from BFS:\n    - Tests if a node is a goal state when it is selected for expansion, not when it is added to the frontier.\n    - Updates a node on the frontier if a better path to the same state is found.\n    - So always enqueues a node before checking whether it is a goal\n\n##Greedy Best-First Search\n###Recap of Best-first Search:\nBasic idea: select node for expansion with minimal evaluation function f(n)\n- where f(n) is some function that included estimate heuristic h(n) of the remaining distance to goal\n- Implement using priority queue\n- Exactly UCS with f(n) replacing g(n)\\\n\n##Greedy Best-First Search: f(n) = h(n)\nExpandes the node that is estimated to be closest to goal\\\nCompletely ignores g(n): the cost to get to n\\\n- Manhattan distance:\\\ndef heuristic(a, b):\\\nreturn abs(a.x - b.x) + abs(a.y - b.y)\n\n##A* search\nBest-known form of best-first search.\\\nKey Idea: avoid expanding paths that are already expensive, but expand most promising first.\\\nSimple idea: f(n)=g(n)+h(n)\n- g(n): the actual cost(so far) to reach the node\n- h(n): estimated cost to get from the node to the goal\n- f(n): estimated total cost of path through n to goal\nImplementation: Frontier queue as priority queue by increasing f(n)\n\n###Key concept: admissible heuristics\nA heuristic h(n) is admissible if it never overestimates the cost to reach the goal(optimistic).\\\nFor all n, n is a node:\n- h(n) <= h*(n), h*(n) is the true cost to a nearest goal\n- h(n) >= 0\n- If h(n) is admissible, A* using Tree Search is optimal\n\n###Relaxed problems:\nA problem with fewer restrictions on the actions than the original is called a relaxed problem\\\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the\noriginal problem\\\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h_oop(n)\ngives the shortest solution\\\nIf the rules are relaxed so that a tile can move to any adjacent square, then h_md(n)\ngives the shortest solution\n\n###Defining Heuristics: h(n)\nCost of an exact solution to a relaxed problem\\\nConstraints on Full Problem:\\\nA tile can move from square A to square B if A is adjacent to B and B is blank.\\\nConstraints on relaxed problems:\n- A tile can move from square A to square B if A is adjacent to B. (h_md) \n- A tile can move from square A to square B if B is blank.\n- A tile can move from square A to square B. (h_oop)\n\n###Dominance: A measure of better heuristics\nIf h_2(n) >= h_1(n) for all n (both admissible), then h_2 dominates h_1.\\\nh_2 is optimistic, but more accurate than h_1\n- h_2 is therefore better for search\n- h_md dominates h_oop\n####The best and worst admissible heuristics\nBEST: h*(n): the (unachievable) Oracle heuristic\n- h*(n) = the true distance from the n to goal. (Dominates all other heuristics)\nWORST: h_teleportation(n)=0. (Dominated by all heuristics)\n\n##A* search is optimal\nAdmissible (optimistic) heuristics slow down bad plans but never outweigh true costs. That means that the true best plan will always be expanded.\n\n\n\n\n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "####The Simplest Game Environment\n",
        "- Multiagent\n",
        "- Static: No change while an agent is deliberating\n",
        "- Discrete: A finite set of percepts and actions\n",
        "- Fully observable: An agent's sensors give it the complete state of the environment\n",
        "- Strategic: The next state is determined by the current state and the action executed by the agent and the actions of one other agent\n",
        "\n",
        "###Key properties of our games\n",
        "1. Two plaers alternate moves\n",
        "2. Zero-sum: one player's loss is another's gain\n",
        "3. Clear set of legal moves\n",
        "4. Well-defined outcomes\n",
        "\n",
        "####How to play a game by searching\n",
        "General Scheme\n",
        "1. Consider all legal successors to the current state (‘board position’)\n",
        "2. Evaluate each successor board position\n",
        "3. Pick the move which leads to the best board position.\n",
        "4. After your opponent moves, repeat. \n",
        "\n",
        "###Game Trees\n",
        "Represent the game problem space by a tree:\\\\\n",
        "Nodes represent 'board positions'; edges represent legal moves.\\\\\n",
        "Root node is the first position in which a decision must be made\n",
        "- Evaluation function f assigns real-number scores to 'board positions' without reference to path\n",
        "\n",
        "###Evaluation functions: f(n)\n",
        "Evaluates how good a 'board position' is\n",
        "- Zero-sum assumption lets us use one function to describe goodness for both players.\n",
        "    - f(n)>0 if MAX is winning in position n\n",
        "    - f(n)=0 if position n is tied \n",
        "    - f(n)<0 if MIN is winning in position n\n",
        "- Build using expert knowledge,\n",
        "Tic-tac-toe: f(n)=(# of 3 lengths open for MAX)-(# open for MIN)\n",
        "\n",
        "##Minimax and Alpha-Beta Pruning\n",
        "**The Minimax Rule**: “Don’t play hope chess”\n",
        "- Idea : Make the best move for MAX assuming that MIN always replies with the best\n",
        "move for MIN o Easily computed by a recursive process\n",
        "- The backed-up value of each node in the tree is determined by the values of its\n",
        "children:\n",
        "    - For a MAX node, the backed-up value is the maximum of the values of its\n",
        "children (i.e. the best for MAX)\n",
        "    - For a MIN node, the backed-up value is the minimum of the values of its\n",
        "children (i.e. the best for MIN)\\\\\n",
        "\n",
        "**Minimax Procedure**\n",
        "1. Start with the current position as a MAX node. \n",
        "2. Expand the game tree a fixed number of ply. \n",
        "3. Apply the evaluation function to the leaf positions. \n",
        "4. Calculate back-up values bottom-up. \n",
        "5. Pick the move assigned to MAX at the root \n",
        "6. Wait for MIN to respon\n",
        "\n",
        "Minimax search: \n",
        "A state-space search tree\\\\\n",
        "Players alternate turns\\\\\n",
        "Compute each node’s minimax value: the best achievable utility against a rational (optimal) adversary\n",
        "\n",
        "###What if MIN does not play optimally?\n",
        "- Definition of optimal play for MAX assumes MIN plays optimally:\n",
        "    - Maximizes worst-case outcome for MAX. (Classic game theoretic strategy)\n",
        "- But if MIN does not play optimally, MAX will do even better.\n",
        "    - his theorem is not hard to prove\n",
        "\n",
        "##Alpha-Beta Pruning\n",
        "- During Minimax, keep track of two additional values:\n",
        "    - α: MAX’s current lowerbound on MAX’s outcome \n",
        "    - β: MIN’s current upperbound on MIN’s outcome\n",
        "- MAX will never allow a move that could lead to a worse score (for MAX) than α \n",
        "- MIN will never allow a move that could lead to a better score (for MAX) than β\n",
        "- Therefore, stop evaluating a branch whenever:\n",
        "    - When evaluating a MAX node: a value  ≥ is backed-up\n",
        "    - MIN will never select that MAX node When evaluating a MIN node: a value  ≤ is found\n",
        "    - MAX will never select that MIN node\n",
        "\n",
        "##Expectimax and Utilities\n",
        "- Expectimax search: compute the average score under optimal play\n",
        "    - Max nodes as in minimax search \n",
        "    - Chance nodes are like min nodes but the outcome is uncertain \n",
        "    - Calculate their expected utilities \n",
        "    - I.e. take weighted average (expectation) of children\n",
        "\n",
        "##Probabilities\n",
        "- A random variable represents an event whose outcome is unknown \n",
        "- A probability distribution is an assignment of weights to outcome\n",
        "- Objectivist / frequentist answer:\n",
        "    - Averages over repeated experiments \n",
        "    - E.g. empirically estimating P(rain) from historical observation \n",
        "    - Assertion about how future experiments will go (in the limit) \n",
        "    - New evidence changes the reference class \n",
        "    - Makes one think of inherently random events, like rolling dic\n",
        "- Subjectivist / Bayesian answer:\n",
        "    - Degrees of belief about unobserved variables \n",
        "    - E.g. an agent’s belief that it’s raining, given the temperature \n",
        "    - E.g. agent’s belief how an opponent will behave, given the state \n",
        "    - Often learn probabilities from past experiences (more later) \n",
        "    - New evidence updates beliefs (more later)\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "\"minimax value\": \"the best achievable utility against a rational (optimal) adversary\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 57,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e67e3126-d6f1-438d-fbb0-c96ac86df468"
      },
      "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": 58,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n\n####The Simplest Game Environment\n- Multiagent\n- Static: No change while an agent is deliberating\n- Discrete: A finite set of percepts and actions\n- Fully observable: An agent's sensors give it the complete state of the environment\n- Strategic: The next state is determined by the current state and the action executed by the agent and the actions of one other agent\n\n###Key properties of our games\n1. Two plaers alternate moves\n2. Zero-sum: one player's loss is another's gain\n3. Clear set of legal moves\n4. Well-defined outcomes\n\n####How to play a game by searching\nGeneral Scheme\n1. Consider all legal successors to the current state (‘board position’)\n2. Evaluate each successor board position\n3. Pick the move which leads to the best board position.\n4. After your opponent moves, repeat. \n\n###Game Trees\nRepresent the game problem space by a tree:\\\nNodes represent 'board positions'; edges represent legal moves.\\\nRoot node is the first position in which a decision must be made\n- Evaluation function f assigns real-number scores to 'board positions' without reference to path\n\n###Evaluation functions: f(n)\nEvaluates how good a 'board position' is\n- Zero-sum assumption lets us use one function to describe goodness for both players.\n    - f(n)>0 if MAX is winning in position n\n    - f(n)=0 if position n is tied \n    - f(n)<0 if MIN is winning in position n\n- Build using expert knowledge,\nTic-tac-toe: f(n)=(# of 3 lengths open for MAX)-(# open for MIN)\n\n##Minimax and Alpha-Beta Pruning\n**The Minimax Rule**: “Don’t play hope chess”\n- Idea : Make the best move for MAX assuming that MIN always replies with the best\nmove for MIN o Easily computed by a recursive process\n- The backed-up value of each node in the tree is determined by the values of its\nchildren:\n    - For a MAX node, the backed-up value is the maximum of the values of its\nchildren (i.e. the best for MAX)\n    - For a MIN node, the backed-up value is the minimum of the values of its\nchildren (i.e. the best for MIN)\\\n\n**Minimax Procedure**\n1. Start with the current position as a MAX node. \n2. Expand the game tree a fixed number of ply. \n3. Apply the evaluation function to the leaf positions. \n4. Calculate back-up values bottom-up. \n5. Pick the move assigned to MAX at the root \n6. Wait for MIN to respon\n\nMinimax search: \nA state-space search tree\\\nPlayers alternate turns\\\nCompute each node’s minimax value: the best achievable utility against a rational (optimal) adversary\n\n###What if MIN does not play optimally?\n- Definition of optimal play for MAX assumes MIN plays optimally:\n    - Maximizes worst-case outcome for MAX. (Classic game theoretic strategy)\n- But if MIN does not play optimally, MAX will do even better.\n    - his theorem is not hard to prove\n\n##Alpha-Beta Pruning\n- During Minimax, keep track of two additional values:\n    - α: MAX’s current lowerbound on MAX’s outcome \n    - β: MIN’s current upperbound on MIN’s outcome\n- MAX will never allow a move that could lead to a worse score (for MAX) than α \n- MIN will never allow a move that could lead to a better score (for MAX) than β\n- Therefore, stop evaluating a branch whenever:\n    - When evaluating a MAX node: a value  ≥ is backed-up\n    - MIN will never select that MAX node When evaluating a MIN node: a value  ≤ is found\n    - MAX will never select that MIN node\n\n##Expectimax and Utilities\n- Expectimax search: compute the average score under optimal play\n    - Max nodes as in minimax search \n    - Chance nodes are like min nodes but the outcome is uncertain \n    - Calculate their expected utilities \n    - I.e. take weighted average (expectation) of children\n\n##Probabilities\n- A random variable represents an event whose outcome is unknown \n- A probability distribution is an assignment of weights to outcome\n- Objectivist / frequentist answer:\n    - Averages over repeated experiments \n    - E.g. empirically estimating P(rain) from historical observation \n    - Assertion about how future experiments will go (in the limit) \n    - New evidence changes the reference class \n    - Makes one think of inherently random events, like rolling dic\n- Subjectivist / Bayesian answer:\n    - Degrees of belief about unobserved variables \n    - E.g. an agent’s belief that it’s raining, given the temperature \n    - E.g. agent’s belief how an opponent will behave, given the state \n    - Often learn probabilities from past experiences (more later) \n    - New evidence updates beliefs (more later)\n\n\n\n\n\n## Module 5 Definitions\n* **Concept** - definition\n* **Minimax value** - the best achievable utility against a rational (optimal) adversary\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 = \"\"\" Your summary here \"\"\"\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",
        "##Big Idea\n",
        "- Represent the constraintsthat solutions must satisfy in a uniform declarative language \n",
        "- Find solutions by GENERAL PURPOSE search algorithmswith no changes from problem to problem\n",
        "    - No hand-built transition functions \n",
        "    - No hand-built heuristics\n",
        "- Just specify the problem in a formal declarative language, and a general-purpose algorithm does everything else!\n",
        "\n",
        "##Constraint Satisfaction Problems\n",
        "- A CSP consists of:\n",
        "    - Finite set of variables X1, X2, ..., Xn\n",
        "    - Nonempty **domain** of possible values for each variable D1, D2, ... Dn, where Di = {v1, ..., vk} \n",
        "    - Finite set of constraints C1, C2, ..., Cm\n",
        "        - Each constraint Ci limits the values that variables can take. E.g., X1 != X2\n",
        "        - A **state** is defined as an assignment of values to some or all variables\n",
        "- A **consistent** assignment does not violate the constraints.\n",
        "- An assignment is **complete** when every variable is assigned a value.\n",
        "- A **solution** to a CSP is a **complete, consistent** assignment\n",
        "- Solutions to CSPs can be found by a completely **general purpost** algorithm, given only the formal specification of the CSP.\n",
        "- CSPs that require a solution that maximizes an **objective function**.\n",
        "\n",
        "##Benefits of CPS\n",
        "- Clean specification of many problems, generic goal,successor function & heuristics\n",
        "    - Just represent problem as a CSP & solve with general package\n",
        "- CSP “knows” which variables violate a constraint\n",
        "    - And hence where to focus the search\n",
        "- CSPs: Automatically prune off all branches that violate constraints\n",
        "(State space search could do this only by hand-building constraints\n",
        "into the successor function)\n",
        "\n",
        "##CSP Representations\n",
        "- Constraint graph:\n",
        "    - nodes are variables\n",
        "    - arcs are (binary) constraints\n",
        "- Standard representation pattern:\n",
        "    - variables with values\n",
        "- Constraint graph simplifies search (some node might not need check)\n",
        "\n",
        "Varieties of constraints\n",
        "- Unary constraints involve a single variable,\n",
        "    - e.g., SA  ≠ green \n",
        "- Binary constraints involve pairs of variables,\n",
        "    - e.g., SA ≠ WA \n",
        "- Higher-order constraints involve 3 or more variables\n",
        "    - e.g., crypt-arithmetic column constraint\n",
        "- Preference (soft constraints) e.g. redis better than greencan be represented by a cost for each variable assignment\n",
        "    - Constrained optimization problems.\n",
        "\n",
        "\n",
        "##Idea 1: CSP as a search problem\n",
        "- A CSP can easily be expressed as a search problem\n",
        "    - Initial State: the empty assignment {}.\n",
        "    - Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict.\n",
        "    - Goal test: the current assignment is complete.\n",
        "    - Path cost: a constant cost for every step. \n",
        "- Solution is always found at depth n, for nvariables\n",
        "    - Hence Depth First Search can be used\n",
        "\n",
        "###Search and branching factor\n",
        "- n variables of domain size d \n",
        "- Branching factor at the root is n*d \n",
        "- Branching factor at next level is (n-1)*d \n",
        "- Tree has n!*d n leave\n",
        "- The variable assignments are commutatibe, thus it is a tree search, not a graph search\n",
        "- Only need to consider assignments to a single variable at each node\n",
        "    - b = d and there are d^n leaves (n variables, domain size d)\n",
        "- Search and **backtracking**\n",
        "    - Depth-first search for CSPs with single-variable assignments is called backtracking search\n",
        "    - The term backtracking search is used for a depth-first search that chooses values for  one variable at a time and backtracks when a variable has no legal values left to assign. \n",
        "    - Backtracking search is the basic __uninformed algorithm__ for CSPs\n",
        "\n",
        "##Idea 2: Improving backtracking efficiency\n",
        "- General-purpose methods & general-purpose heuristics can give huge gains in speed, on average\n",
        "- Heuristics:\n",
        "    - Q: Which variable should be assigned next?\n",
        "    - 1. Most constrainedvariable \n",
        "      2. (if ties:) Most constraining variable\n",
        "    - Q: In what order should that variable’s values be tried? \n",
        "      3. Least constraining value\n",
        "    - Q: Can we detect inevitable failure early?\n",
        "    - 4. Forward checking\n",
        "- Heuristic 1: Most constrained variable\n",
        "    - Choose a variable with the fewest legal values\n",
        "    - a.k.a. minimum remaining values (MRV) heuristic\n",
        "- Heuristic 2: Most constraining variable\n",
        "    - Tie-breaker among most constrained variables\n",
        "    - Choose the variable with the most constraints on remaining variables\n",
        "- Heuristic 3: Least constraining value\n",
        "    - Given a variable, choose the least constraining value: the one that rules out the fewest values in the remaining variable\n",
        "- Heuristic 4: Forward checking\n",
        "    - Idea: Keep track of remaining legal values for unassigned variables Terminate search when any unassigned variable has no remaining legal value\n",
        "\n",
        "###Towards Constranit propagation:\n",
        "- Forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures:\n",
        "- NEED CONSTRAINT PROPAGATION: goes beyond forward checking & repeatedly enforces constraints locally\n",
        "\n",
        "#Arc Consistency, Constraint Propagation & AC-3\n",
        "##Idea 3(big idea): **Inference** in CSPs\n",
        "- CSP solvers combine search and inference\n",
        "    - Search\n",
        "        - assigning a value to a variable \n",
        "    - Constraint propagation (inference)\n",
        "        - Eliminates possible values for a variable if the value would violate local consistency \n",
        "        Can do inference first, or intertwine it with search\n",
        "- Local consistency\n",
        "    - Node consistency: satisfies unary constraints\n",
        "        - This is trivial! \n",
        "    - Arc consistency: satisfies binary constraints\n",
        "        - Xi is arc-consistent w.r.t. Xj\\\\\n",
        "        if for every value v in Di, there is some value w in Dj \\\\\n",
        "        that satisfies the binary constraint on the arc between Xi and Xj\n",
        "\n",
        "- Edges to Arcs: From Constraint Graph to Directed Graph\n",
        "    - Given a pair of nodes Xi and Xj connected by a constraint edge, we represent this not by a single undirected edge, but a pair of directed arcs.\n",
        "- Arc consistency:\n",
        "    - Simplest form of propagation makes each arc consistent \n",
        "    - X to Y is consistent iff \\\\\n",
        "    for every value x of X there is some allowed y\n",
        "    - If Xloses a value, recheck neighbors of X\n",
        "    - If Xloses a value, we need to recheck neighbors of X \n",
        "    - Detects failure earlier than forward checking \n",
        "    - Can be run as a preprocessor or after each assignment\n",
        "    - **An arc (i,j) is arc consistent if and only if every value v on Xiis consistent with some label on Yj.**\\\\\n",
        "    To make an arc (i,j) arc consistent, for each value von Xi, if there is no label on Yj consistent with v then remove v from Xi\n",
        "    - Given d values, checking arc (i,j) takes O(d^2)time worst case\n",
        "\n",
        "###Replacing Search:\n",
        "\n",
        "The Waltz/Mackworth Constraint Propagation Algorithm \n",
        "1. Assign every node in the constraint graph a set of all\n",
        "possible values \n",
        "2. Repeat until there is no change in the set of values\n",
        "associated with any node:\n",
        "3. For each node i:\n",
        "4. For each neighboring node j in the picture:\n",
        "5. Remove any value from i which is not arc consistent with j.\n",
        "\n",
        "###Inefficiencies: Towards AC-3 \n",
        "1. At each iteration, we only need to examine those  Xi\n",
        "where at least one neighbor of Xi  has lost a value in the\n",
        "previous iteration. \n",
        "2. If Xi loses a value only because of arc inconsistencies\n",
        "with Yj, we don’t need to check Yj on the next iteration. \n",
        "3. Removing a value on Xi can only make Yj arc-\n",
        "inconsistent with respect to Xi  itself. Thus, we only\n",
        "need to check that (j,i) is still arc-consistent. \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 59,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "13cacba0-f9f7-4433-a6de-764626fc1176"
      },
      "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": 60,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n\n##Big Idea\n- Represent the constraintsthat solutions must satisfy in a uniform declarative language \n- Find solutions by GENERAL PURPOSE search algorithmswith no changes from problem to problem\n    - No hand-built transition functions \n    - No hand-built heuristics\n- Just specify the problem in a formal declarative language, and a general-purpose algorithm does everything else!\n\n##Constraint Satisfaction Problems\n- A CSP consists of:\n    - Finite set of variables X1, X2, ..., Xn\n    - Nonempty **domain** of possible values for each variable D1, D2, ... Dn, where Di = {v1, ..., vk} \n    - Finite set of constraints C1, C2, ..., Cm\n        - Each constraint Ci limits the values that variables can take. E.g., X1 != X2\n        - A **state** is defined as an assignment of values to some or all variables\n- A **consistent** assignment does not violate the constraints.\n- An assignment is **complete** when every variable is assigned a value.\n- A **solution** to a CSP is a **complete, consistent** assignment\n- Solutions to CSPs can be found by a completely **general purpost** algorithm, given only the formal specification of the CSP.\n- CSPs that require a solution that maximizes an **objective function**.\n\n##Benefits of CPS\n- Clean specification of many problems, generic goal,successor function & heuristics\n    - Just represent problem as a CSP & solve with general package\n- CSP “knows” which variables violate a constraint\n    - And hence where to focus the search\n- CSPs: Automatically prune off all branches that violate constraints\n(State space search could do this only by hand-building constraints\ninto the successor function)\n\n##CSP Representations\n- Constraint graph:\n    - nodes are variables\n    - arcs are (binary) constraints\n- Standard representation pattern:\n    - variables with values\n- Constraint graph simplifies search (some node might not need check)\n\nVarieties of constraints\n- Unary constraints involve a single variable,\n    - e.g., SA  ≠ green \n- Binary constraints involve pairs of variables,\n    - e.g., SA ≠ WA \n- Higher-order constraints involve 3 or more variables\n    - e.g., crypt-arithmetic column constraint\n- Preference (soft constraints) e.g. redis better than greencan be represented by a cost for each variable assignment\n    - Constrained optimization problems.\n\n\n##Idea 1: CSP as a search problem\n- A CSP can easily be expressed as a search problem\n    - Initial State: the empty assignment {}.\n    - Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict.\n    - Goal test: the current assignment is complete.\n    - Path cost: a constant cost for every step. \n- Solution is always found at depth n, for nvariables\n    - Hence Depth First Search can be used\n\n###Search and branching factor\n- n variables of domain size d \n- Branching factor at the root is n*d \n- Branching factor at next level is (n-1)*d \n- Tree has n!*d n leave\n- The variable assignments are commutatibe, thus it is a tree search, not a graph search\n- Only need to consider assignments to a single variable at each node\n    - b = d and there are d^n leaves (n variables, domain size d)\n- Search and **backtracking**\n    - Depth-first search for CSPs with single-variable assignments is called backtracking search\n    - The term backtracking search is used for a depth-first search that chooses values for  one variable at a time and backtracks when a variable has no legal values left to assign. \n    - Backtracking search is the basic __uninformed algorithm__ for CSPs\n\n##Idea 2: Improving backtracking efficiency\n- General-purpose methods & general-purpose heuristics can give huge gains in speed, on average\n- Heuristics:\n    - Q: Which variable should be assigned next?\n    - 1. Most constrainedvariable \n      2. (if ties:) Most constraining variable\n    - Q: In what order should that variable’s values be tried? \n      3. Least constraining value\n    - Q: Can we detect inevitable failure early?\n    - 4. Forward checking\n- Heuristic 1: Most constrained variable\n    - Choose a variable with the fewest legal values\n    - a.k.a. minimum remaining values (MRV) heuristic\n- Heuristic 2: Most constraining variable\n    - Tie-breaker among most constrained variables\n    - Choose the variable with the most constraints on remaining variables\n- Heuristic 3: Least constraining value\n    - Given a variable, choose the least constraining value: the one that rules out the fewest values in the remaining variable\n- Heuristic 4: Forward checking\n    - Idea: Keep track of remaining legal values for unassigned variables Terminate search when any unassigned variable has no remaining legal value\n\n###Towards Constranit propagation:\n- Forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures:\n- NEED CONSTRAINT PROPAGATION: goes beyond forward checking & repeatedly enforces constraints locally\n\n#Arc Consistency, Constraint Propagation & AC-3\n##Idea 3(big idea): **Inference** in CSPs\n- CSP solvers combine search and inference\n    - Search\n        - assigning a value to a variable \n    - Constraint propagation (inference)\n        - Eliminates possible values for a variable if the value would violate local consistency \n        Can do inference first, or intertwine it with search\n- Local consistency\n    - Node consistency: satisfies unary constraints\n        - This is trivial! \n    - Arc consistency: satisfies binary constraints\n        - Xi is arc-consistent w.r.t. Xj\\\n        if for every value v in Di, there is some value w in Dj \\\n        that satisfies the binary constraint on the arc between Xi and Xj\n\n- Edges to Arcs: From Constraint Graph to Directed Graph\n    - Given a pair of nodes Xi and Xj connected by a constraint edge, we represent this not by a single undirected edge, but a pair of directed arcs.\n- Arc consistency:\n    - Simplest form of propagation makes each arc consistent \n    - X to Y is consistent iff \\\n    for every value x of X there is some allowed y\n    - If Xloses a value, recheck neighbors of X\n    - If Xloses a value, we need to recheck neighbors of X \n    - Detects failure earlier than forward checking \n    - Can be run as a preprocessor or after each assignment\n    - **An arc (i,j) is arc consistent if and only if every value v on Xiis consistent with some label on Yj.**\\\n    To make an arc (i,j) arc consistent, for each value von Xi, if there is no label on Yj consistent with v then remove v from Xi\n    - Given d values, checking arc (i,j) takes O(d^2)time worst case\n\n###Replacing Search:\n\nThe Waltz/Mackworth Constraint Propagation Algorithm \n1. Assign every node in the constraint graph a set of all\npossible values \n2. Repeat until there is no change in the set of values\nassociated with any node:\n3. For each node i:\n4. For each neighboring node j in the picture:\n5. Remove any value from i which is not arc consistent with j.\n\n###Inefficiencies: Towards AC-3 \n1. At each iteration, we only need to examine those  Xi\nwhere at least one neighbor of Xi  has lost a value in the\nprevious iteration. \n2. If Xi loses a value only because of arc inconsistencies\nwith Yj, we don’t need to check Yj on the next iteration. \n3. Removing a value on Xi can only make Yj arc-\ninconsistent with respect to Xi  itself. Thus, we only\nneed to check that (j,i) is still arc-consistent. \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "##Knowledge-based Agents\n",
        "- Knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what action to take\n",
        "- A central component of a knowledge-based agent is a knowledge base or KB\n",
        "- AKB contains a set of **sentence** that are written in a **knowledge representation language**. The sentence contains some assertion about the world\n",
        "- Two kinds of sentences:\n",
        "    - Axioms: a sentence that is given\n",
        "    - Derived sentences: a new sentence that is derived from other sentences, this process is called **inference**\n",
        "- A KB can initially contain some **background information** about the world, and a knowledge-based agent can add to the information in the KB through its observations of the world.1\n",
        "- Logical Entailment and Inference: on reference paper\n",
        "\n",
        "##Knowledge Bases\n",
        "Sound: the inference algorithm should only derive entailed sentences. \n",
        "Complete: an inference algorithm is complete if it can derive all sentences that are entailed\n",
        "\n",
        "###Resolution\n",
        "There is a single inference rule, resolution, which yields a complete inference algorithm when coupled with any complete search algorithm.\n",
        "\n",
        "\n",
        "###Forward Chaining and Backward Chaining\n",
        "Forward Chaining is a kind of data-driven reasoning. \\\\\n",
        "An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions.  It doesn’t have to have a specific query in mind to do so.\\\\\n",
        "Backward chaining works backwards from a query.  \\\\\n",
        "If the query is known to be true, then no work is needed.  Otherwise, the algorithm finds implications in the KB whose conclusions is the query.  If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\\\\\n",
        "Backward chaining is a form of goal-directed reasoning.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 61,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "58da7a13-c854-49a3-eb0a-c9096178c2dd"
      },
      "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": 62,
      "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 \n##Knowledge-based Agents\n- Knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what action to take\n- A central component of a knowledge-based agent is a knowledge base or KB\n- AKB contains a set of **sentence** that are written in a **knowledge representation language**. The sentence contains some assertion about the world\n- Two kinds of sentences:\n    - Axioms: a sentence that is given\n    - Derived sentences: a new sentence that is derived from other sentences, this process is called **inference**\n- A KB can initially contain some **background information** about the world, and a knowledge-based agent can add to the information in the KB through its observations of the world.1\n- Logical Entailment and Inference: on reference paper\n\n##Knowledge Bases\nSound: the inference algorithm should only derive entailed sentences. \nComplete: an inference algorithm is complete if it can derive all sentences that are entailed\n\n###Resolution\nThere is a single inference rule, resolution, which yields a complete inference algorithm when coupled with any complete search algorithm.\n\n\n###Forward Chaining and Backward Chaining\nForward Chaining is a kind of data-driven reasoning. \\\nAn agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions.  It doesn’t have to have a specific query in mind to do so.\\\nBackward chaining works backwards from a query.  \\\nIf the query is known to be true, then no work is needed.  Otherwise, the algorithm finds implications in the KB whose conclusions is the query.  If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\\\nBackward chaining is a form of goal-directed reasoning.\n\n\n\n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "eae5b2ee-f4ab-4e5b-8e40-1dec23d0fb0c"
      },
      "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",
        "                             module1_markdown,\n",
        "                             module1_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 63,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nYour summary here\n\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 \n###Rantional Agents:\n**Agents:** \n- An agent is anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\n- A percept is the agent's perceptual inputs at any given instance.\n- An agent is specified by an **agent function** $$f:P\\longrightarrow a$$ that maps a sequence of percept vectors P to an action a from a set A.\n- Agent function & program: The **agent program** runs on physical **architecture** to produce f\n- **Agents** An agent is anything that can be viewd as:\n    - Perceiving its environment through sensors and\n    - Acting upon that environment through actuators\n\n###Rational Behavior & Expected Value:\n**Rational Agent**: A rational agent is an agent that perceives its environment and behaves rationally. Rational behavior: doing the right thing.\n- For each possible percept sequence P\n- a rational agents selects an action a\n- to maximize the **expected value** of its performance measure\n- Computational limitations make complete rationality unachievable - not omniscience\n\n**Performance measure**\n- An objective criterion for success of an agent's behavior\n- Given the evidence provided by the percept sequence\n- We want the performance measure: describe what you want to be achieved in the environment, rather than how you think the agent should behave.\n\n### Task Environments: **PEAS**\nTo design a rational agents we need to specify a task environment: a problem specification for which the agent is a solution\n- P: Performance measure\n- E: Environment\n- A: Actuators\n- S: Sensors\n\nGoal of AI practitioner who designs rational agents:\n**Given a PEAS task environment,**\n- Cioonstruct agent function **f** that maximizes the expected value of the performance measure,\n- Design an agent program that implements **f** on a particular architecture\n\n### Problem Solving Agents & Problem Formulation\nExample: 8-puzzle\nFormulate goal\n- Pieces to end up in order as shown…\n- Formulate search problem\n    - States: configurations of the puzzle (9! configurations)\n    - Actions: Move one of the movable pieces (≤4 possible)\n    - Performance measure: minimize total moves \n- Find solution\n    - Sequence of pieces moved:  3,1,6,3,1,\n \n\n## Module 1 Definitions\n* **Agent** - anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\n* **Percept** - the agent's perceptual inputs at any given instance.\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\n###Python: Developed by Guido van Rossum in 1989\n- Fast development\n- Portable\n- Various built-in types: lists, dictionaries, sets\n- Large collection of support libraries: NumPy for Matlab like programming, Pandas for data analysis, Sklearn for machine learning, Pytorch and TensorFlow for deep learning\n\n###Objects and Types\n- All data treated as objects\n- Strong Typing: every object has a fixed type, interpreter doesn't allow things incompatible with that type (eg. \"foo\"+2)\n- Examples of Types: int, float; str, tuple, dict, list; bool: True, False; None, generator, function\n\n###Static vs. Dynamic Typing: Python is dynamic typing.\n\n###Strings:\n- Creation: \n    - Can use either single or double quotes Triple quote for multiline string and docstring\n- Concatenating strings:\n    - By separating string literals with whitespace Special use of ‘+’\n- Prefixing with r means raw. \n    - No need to escape special characters: r’\n’ \n- String formatting\n    - Special use of ‘%’ (as in printf in C) print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\n- Immutable\n\n###References and Mutability\n- strings are immutable\n- == checks whether variables point to objects of the same value \n- is checks whether variables point to the same object\n- lists are mutable \n- use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value\n\n###Sequence Types: Tuples, Lists, and Strings\n- Tuple\n    - A simple immutable ordered sequence of items Immutable: a tuple cannot be modified once created Items can be of mixed types, including collection types\n- Strings\n    - Immutable Regular strings are Unicode and use 2-byte characters (Regular strings in Python 2 use 8-bit characters)\n- List\n    - Mutable ordered sequence of items of mixed types\n- Slicing\n- Operaitons on Lists\n    - a.append()\n    - a.insert(2,'i')\n    - a.index('b') #index of first occurrence\n    - a.count('b') #number of occurrences\n    - a.remove('b') #remove first occurrence\n    - a.revers() #reverse the list\n    - a.sort() #sort\n    - sorted(a) #return a *copy* sorted.\n- Operation on Strings\n    - s = \"Pretend this sentence makes sense.\" >>> words = s.split(\" \") \n    - words ['Pretend', 'this', 'sentence', 'makes', 'sense.'] \n    - \"_\".join(words) #join method of obj \"_\" 'Pretend_this_sentence_makes_sense.'\n    - s = 'dog' >>> s.capitalize() 'Dog'; >>> s.upper() 'DOG’; >>> ' hi --'.strip(' –') 'hi’ \n\n### Dictionaries: A mapping collection type\n- Dictionaries are unordered & work by hashing, so keys must be immutable\n- Constant average time add, lookup, update \n\n- Dict: Useful Methods\n    - d = {'user':'R2D2', 'p':1234, 'i':34} >>> d.keys() # List of current keys\n    - dict_keys(['user', 'p', 'i’])\n    - d.values() # List of current values. dict_values(['R2D2', 1234, 34])\n    - d.items() # List of item tuples. dict_items([('user', 'R2D2'), ('p', 1234), ('i', 34)])\n- Defualt Dictionaries and Counters\n    - defaultdict automatically initializes nonexistent dictionary values \n    - d = defualtdict(str) #automatically give string key types \"\" value\n    - d = Counter() # automatically give key \"0\" value\n    - otherwise, retrieving any key that doesn't exist in the dict will raise a KeyError\n\n### Functions\n- When returning multiple values, it returns a tuple\n- Does not support overloading\n- Non-default argument should always precede default arguments; otherwise, it reports SyntaxError\n- *arg: Suppose you want to accept a variable number of non-keyword arguments to your\nfunction\n- **kwargs: Suppose you want to accept a variable number of keyword arguments to your\nfunction\n- Example: \\\ndef myfun(positional, *args, **kwargs):\n    print(positional) \n    if args:\n        print(args) \n    if kwargs:\n        print(kwargs)\nmyfun(\"hi\", \"the\", \"best\", \"food\", \"is\", \"tacos\", shell=\"soft\", meat=\"beef\")\\\n    hi \\\n    ('the', 'best', 'food', 'is', 'tacos’) \\\n    {'shell': 'soft', 'meat': 'beef'}\n- Functions are “first-class” objects\n    - First class object: An entity that can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have\n    - Functions are “first-class citizens”: Pass functions as arguments to other functions Return functions as the values from other functions Assign functions to variables or store them in data structures\n\n### Classes and Inheritance\n- To redefine a method of the parent class, include a new definition using the same\nname in the subclass.\n-  To execute the method in the parent class in addition to new code for some\nmethod, explicitly call the parent’s version of the method.\\\nparentClass.methodName(self, a, b, c)\\\n    The only time you ever explicitly pass self as an argument is when\ncalling a method of an ancestor.\\\n    So use myOwnSubClass.methodName(a,b,c)\n\n### Duck Typing\n__init__: The constructor for the class.\n__len__ : Define how  len( obj ) works. \n__copy__: Define how to copy a class.\n__cmp__ : Define how == works for class. \n__add__ : Define how + works for class \n__neg__ : Define how unary negation works for class\n\nclass Duck:\\\n    def fly(self):\\\n        print(\"Duck flying\")\\\nclass Airplane:\\\n    def fly(self):\\\n        print(\"Airplane flying\")\\\nclass Whale:\\\n    def swim(self):\\\n        print(\"Whale swimming\")\\\ndef lift_off(entity)\\\n    entity.fly()\\\n\nduck = Duck()\\\nplane = Airplane()\\\nwhale = Whale()\\\nlift_off(duck) Duck flying\\\nlift_off(plane) Airplane flying\\\nlift_off(whale) AttributeError: 'Whale' objecthas no attribute 'fly'\\\n\n\n### List Comprehensions\n[ **expression** for **name** in list if **filter** ]\n### Iterators:\nIterable objects can be used in a  for loop because they have an __iter__ magic method, which converts them to iterator objects:\n### Generators: using yield\n\n\n\n\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n \n##Search Problems:\n###Problem Solving Agents & Problem Formulation\n- Reflex Agents:\n    - A simple reflex agent is one that selects an action based on the current percept\n    - It ignores the rest of the percept history\n- Problem_Solving Agent\n    - A problem-solving agent must plan ahead.\n    - The computational process that it undertakes is called search\n    - It will considdr **a sequence of actions** that form a path to a goal state\n    - Such a sequence is called a solution\n- Task environment and solution types:\n    - If the environment is:\n        - Fully observable\n        - Deterministic\n        - Known environment\\\n        The soluciont is a fixed sequence of actions\n    - If the environment is:\n        - Partially observable or\n        - Nondeterministic\\\n        The solution recommend different future actions, which is a branching strategy\n\n###A Formal Definition of a Problem:\n1. States: a set S\n2. An initial state s_i in S\n3. Actions: a set A, Actions(s) = the set of actions that can be executed for all s\n4. Transition Model: s_r is called a successor of s, if {s_i} 并 Successors(s_i)* = state space \n5. Path Cost(Performance Measure): must be additive\n6. Goal Test: Goal(s); s is a goal if Goal(s) is true\n\n###Solutions & Optimal Solutions:\n- A solution is a sequence of actions from the initial state to a goal state\n- Optimal Solution: A solution is optimal if it has the lowest path cost among all other solutions\n\n###Useful Concepts:\n- State space: the set of all states reachable from the initial state by any sequence of actions:\n    - When several operators can apply to each state, this gets large very quickly\n    - Might be a proper subset of the set of configurations\n- Path: a sequence of actions leading from one state s_j to another state s_k \n- Frontier: those states that are available for expanding (for applying legal actions to) \n- Solution: a path from the initial state si to a state sf that satisfies the goal test\n\n###Basic search algorithms: Tree Search\n- Generalized algorithm to solve search problems \n- Enumerate in some order all possible paths from the initial state\n    - Here: search through explicit tree generation\n    - ROOT= initial state. \n    - Nodes in search tree generated through transition model \n    - Tree search treats different paths to the same node as distinct\n\n##Uninformed Search Strategies\n###Search Strategies\n**IMPORTANT**\nReview: Strategy = order of tree expansion\n- Implemented by different queue structures (LIFO, FIFO, priority)\\\nDimensions for evaluation\n- Completeness: always find the solution?\n- Optimality: finds a least cost solution (lowest path cost) first?\n- Time complexity: # of nodes generated (worst case)\n- Space complexity: # of nodes simultaneously in memory (worst case)\nTime/space complexity variables\n- b, maximum branching factor of search tree\n- d, depth of the shallowest goal node\n- m, maximum length of any path in the state space (potentially infinity)\n\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\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\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 \n##\"Uniformed Cost\" Search\nIn computer science, uniform-cost search is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph.\n## g(N): the path cost function\n- Assumption so far: All moves equal in cost\n    - Cost = # of nodes in path-1\n    - g(N) = depth(N) in the search tree\n\n##Uniform-cost Search (=Best-first Search+path cost)\n- Extension of BFS\n    - Expand node with lowest path cost\n- Implementation:\n    - frontier = priority queue ordered by g(n)\n- Subtle but significant difference from BFS:\n    - Tests if a node is a goal state when it is selected for expansion, not when it is added to the frontier.\n    - Updates a node on the frontier if a better path to the same state is found.\n    - So always enqueues a node before checking whether it is a goal\n\n##Greedy Best-First Search\n###Recap of Best-first Search:\nBasic idea: select node for expansion with minimal evaluation function f(n)\n- where f(n) is some function that included estimate heuristic h(n) of the remaining distance to goal\n- Implement using priority queue\n- Exactly UCS with f(n) replacing g(n)\\\n\n##Greedy Best-First Search: f(n) = h(n)\nExpandes the node that is estimated to be closest to goal\\\nCompletely ignores g(n): the cost to get to n\\\n- Manhattan distance:\\\ndef heuristic(a, b):\\\nreturn abs(a.x - b.x) + abs(a.y - b.y)\n\n##A* search\nBest-known form of best-first search.\\\nKey Idea: avoid expanding paths that are already expensive, but expand most promising first.\\\nSimple idea: f(n)=g(n)+h(n)\n- g(n): the actual cost(so far) to reach the node\n- h(n): estimated cost to get from the node to the goal\n- f(n): estimated total cost of path through n to goal\nImplementation: Frontier queue as priority queue by increasing f(n)\n\n###Key concept: admissible heuristics\nA heuristic h(n) is admissible if it never overestimates the cost to reach the goal(optimistic).\\\nFor all n, n is a node:\n- h(n) <= h*(n), h*(n) is the true cost to a nearest goal\n- h(n) >= 0\n- If h(n) is admissible, A* using Tree Search is optimal\n\n###Relaxed problems:\nA problem with fewer restrictions on the actions than the original is called a relaxed problem\\\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the\noriginal problem\\\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h_oop(n)\ngives the shortest solution\\\nIf the rules are relaxed so that a tile can move to any adjacent square, then h_md(n)\ngives the shortest solution\n\n###Defining Heuristics: h(n)\nCost of an exact solution to a relaxed problem\\\nConstraints on Full Problem:\\\nA tile can move from square A to square B if A is adjacent to B and B is blank.\\\nConstraints on relaxed problems:\n- A tile can move from square A to square B if A is adjacent to B. (h_md) \n- A tile can move from square A to square B if B is blank.\n- A tile can move from square A to square B. (h_oop)\n\n###Dominance: A measure of better heuristics\nIf h_2(n) >= h_1(n) for all n (both admissible), then h_2 dominates h_1.\\\nh_2 is optimistic, but more accurate than h_1\n- h_2 is therefore better for search\n- h_md dominates h_oop\n####The best and worst admissible heuristics\nBEST: h*(n): the (unachievable) Oracle heuristic\n- h*(n) = the true distance from the n to goal. (Dominates all other heuristics)\nWORST: h_teleportation(n)=0. (Dominated by all heuristics)\n\n##A* search is optimal\nAdmissible (optimistic) heuristics slow down bad plans but never outweigh true costs. That means that the true best plan will always be expanded.\n\n\n\n\n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n\n####The Simplest Game Environment\n- Multiagent\n- Static: No change while an agent is deliberating\n- Discrete: A finite set of percepts and actions\n- Fully observable: An agent's sensors give it the complete state of the environment\n- Strategic: The next state is determined by the current state and the action executed by the agent and the actions of one other agent\n\n###Key properties of our games\n1. Two plaers alternate moves\n2. Zero-sum: one player's loss is another's gain\n3. Clear set of legal moves\n4. Well-defined outcomes\n\n####How to play a game by searching\nGeneral Scheme\n1. Consider all legal successors to the current state (‘board position’)\n2. Evaluate each successor board position\n3. Pick the move which leads to the best board position.\n4. After your opponent moves, repeat. \n\n###Game Trees\nRepresent the game problem space by a tree:\\\nNodes represent 'board positions'; edges represent legal moves.\\\nRoot node is the first position in which a decision must be made\n- Evaluation function f assigns real-number scores to 'board positions' without reference to path\n\n###Evaluation functions: f(n)\nEvaluates how good a 'board position' is\n- Zero-sum assumption lets us use one function to describe goodness for both players.\n    - f(n)>0 if MAX is winning in position n\n    - f(n)=0 if position n is tied \n    - f(n)<0 if MIN is winning in position n\n- Build using expert knowledge,\nTic-tac-toe: f(n)=(# of 3 lengths open for MAX)-(# open for MIN)\n\n##Minimax and Alpha-Beta Pruning\n**The Minimax Rule**: “Don’t play hope chess”\n- Idea : Make the best move for MAX assuming that MIN always replies with the best\nmove for MIN o Easily computed by a recursive process\n- The backed-up value of each node in the tree is determined by the values of its\nchildren:\n    - For a MAX node, the backed-up value is the maximum of the values of its\nchildren (i.e. the best for MAX)\n    - For a MIN node, the backed-up value is the minimum of the values of its\nchildren (i.e. the best for MIN)\\\n\n**Minimax Procedure**\n1. Start with the current position as a MAX node. \n2. Expand the game tree a fixed number of ply. \n3. Apply the evaluation function to the leaf positions. \n4. Calculate back-up values bottom-up. \n5. Pick the move assigned to MAX at the root \n6. Wait for MIN to respon\n\nMinimax search: \nA state-space search tree\\\nPlayers alternate turns\\\nCompute each node’s minimax value: the best achievable utility against a rational (optimal) adversary\n\n###What if MIN does not play optimally?\n- Definition of optimal play for MAX assumes MIN plays optimally:\n    - Maximizes worst-case outcome for MAX. (Classic game theoretic strategy)\n- But if MIN does not play optimally, MAX will do even better.\n    - his theorem is not hard to prove\n\n##Alpha-Beta Pruning\n- During Minimax, keep track of two additional values:\n    - α: MAX’s current lowerbound on MAX’s outcome \n    - β: MIN’s current upperbound on MIN’s outcome\n- MAX will never allow a move that could lead to a worse score (for MAX) than α \n- MIN will never allow a move that could lead to a better score (for MAX) than β\n- Therefore, stop evaluating a branch whenever:\n    - When evaluating a MAX node: a value  ≥ is backed-up\n    - MIN will never select that MAX node When evaluating a MIN node: a value  ≤ is found\n    - MAX will never select that MIN node\n\n##Expectimax and Utilities\n- Expectimax search: compute the average score under optimal play\n    - Max nodes as in minimax search \n    - Chance nodes are like min nodes but the outcome is uncertain \n    - Calculate their expected utilities \n    - I.e. take weighted average (expectation) of children\n\n##Probabilities\n- A random variable represents an event whose outcome is unknown \n- A probability distribution is an assignment of weights to outcome\n- Objectivist / frequentist answer:\n    - Averages over repeated experiments \n    - E.g. empirically estimating P(rain) from historical observation \n    - Assertion about how future experiments will go (in the limit) \n    - New evidence changes the reference class \n    - Makes one think of inherently random events, like rolling dic\n- Subjectivist / Bayesian answer:\n    - Degrees of belief about unobserved variables \n    - E.g. an agent’s belief that it’s raining, given the temperature \n    - E.g. agent’s belief how an opponent will behave, given the state \n    - Often learn probabilities from past experiences (more later) \n    - New evidence updates beliefs (more later)\n\n\n\n\n\n## Module 5 Definitions\n* **Concept** - definition\n* **Minimax value** - the best achievable utility against a rational (optimal) adversary\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n\n##Big Idea\n- Represent the constraintsthat solutions must satisfy in a uniform declarative language \n- Find solutions by GENERAL PURPOSE search algorithmswith no changes from problem to problem\n    - No hand-built transition functions \n    - No hand-built heuristics\n- Just specify the problem in a formal declarative language, and a general-purpose algorithm does everything else!\n\n##Constraint Satisfaction Problems\n- A CSP consists of:\n    - Finite set of variables X1, X2, ..., Xn\n    - Nonempty **domain** of possible values for each variable D1, D2, ... Dn, where Di = {v1, ..., vk} \n    - Finite set of constraints C1, C2, ..., Cm\n        - Each constraint Ci limits the values that variables can take. E.g., X1 != X2\n        - A **state** is defined as an assignment of values to some or all variables\n- A **consistent** assignment does not violate the constraints.\n- An assignment is **complete** when every variable is assigned a value.\n- A **solution** to a CSP is a **complete, consistent** assignment\n- Solutions to CSPs can be found by a completely **general purpost** algorithm, given only the formal specification of the CSP.\n- CSPs that require a solution that maximizes an **objective function**.\n\n##Benefits of CPS\n- Clean specification of many problems, generic goal,successor function & heuristics\n    - Just represent problem as a CSP & solve with general package\n- CSP “knows” which variables violate a constraint\n    - And hence where to focus the search\n- CSPs: Automatically prune off all branches that violate constraints\n(State space search could do this only by hand-building constraints\ninto the successor function)\n\n##CSP Representations\n- Constraint graph:\n    - nodes are variables\n    - arcs are (binary) constraints\n- Standard representation pattern:\n    - variables with values\n- Constraint graph simplifies search (some node might not need check)\n\nVarieties of constraints\n- Unary constraints involve a single variable,\n    - e.g., SA  ≠ green \n- Binary constraints involve pairs of variables,\n    - e.g., SA ≠ WA \n- Higher-order constraints involve 3 or more variables\n    - e.g., crypt-arithmetic column constraint\n- Preference (soft constraints) e.g. redis better than greencan be represented by a cost for each variable assignment\n    - Constrained optimization problems.\n\n\n##Idea 1: CSP as a search problem\n- A CSP can easily be expressed as a search problem\n    - Initial State: the empty assignment {}.\n    - Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict.\n    - Goal test: the current assignment is complete.\n    - Path cost: a constant cost for every step. \n- Solution is always found at depth n, for nvariables\n    - Hence Depth First Search can be used\n\n###Search and branching factor\n- n variables of domain size d \n- Branching factor at the root is n*d \n- Branching factor at next level is (n-1)*d \n- Tree has n!*d n leave\n- The variable assignments are commutatibe, thus it is a tree search, not a graph search\n- Only need to consider assignments to a single variable at each node\n    - b = d and there are d^n leaves (n variables, domain size d)\n- Search and **backtracking**\n    - Depth-first search for CSPs with single-variable assignments is called backtracking search\n    - The term backtracking search is used for a depth-first search that chooses values for  one variable at a time and backtracks when a variable has no legal values left to assign. \n    - Backtracking search is the basic __uninformed algorithm__ for CSPs\n\n##Idea 2: Improving backtracking efficiency\n- General-purpose methods & general-purpose heuristics can give huge gains in speed, on average\n- Heuristics:\n    - Q: Which variable should be assigned next?\n    - 1. Most constrainedvariable \n      2. (if ties:) Most constraining variable\n    - Q: In what order should that variable’s values be tried? \n      3. Least constraining value\n    - Q: Can we detect inevitable failure early?\n    - 4. Forward checking\n- Heuristic 1: Most constrained variable\n    - Choose a variable with the fewest legal values\n    - a.k.a. minimum remaining values (MRV) heuristic\n- Heuristic 2: Most constraining variable\n    - Tie-breaker among most constrained variables\n    - Choose the variable with the most constraints on remaining variables\n- Heuristic 3: Least constraining value\n    - Given a variable, choose the least constraining value: the one that rules out the fewest values in the remaining variable\n- Heuristic 4: Forward checking\n    - Idea: Keep track of remaining legal values for unassigned variables Terminate search when any unassigned variable has no remaining legal value\n\n###Towards Constranit propagation:\n- Forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures:\n- NEED CONSTRAINT PROPAGATION: goes beyond forward checking & repeatedly enforces constraints locally\n\n#Arc Consistency, Constraint Propagation & AC-3\n##Idea 3(big idea): **Inference** in CSPs\n- CSP solvers combine search and inference\n    - Search\n        - assigning a value to a variable \n    - Constraint propagation (inference)\n        - Eliminates possible values for a variable if the value would violate local consistency \n        Can do inference first, or intertwine it with search\n- Local consistency\n    - Node consistency: satisfies unary constraints\n        - This is trivial! \n    - Arc consistency: satisfies binary constraints\n        - Xi is arc-consistent w.r.t. Xj\\\n        if for every value v in Di, there is some value w in Dj \\\n        that satisfies the binary constraint on the arc between Xi and Xj\n\n- Edges to Arcs: From Constraint Graph to Directed Graph\n    - Given a pair of nodes Xi and Xj connected by a constraint edge, we represent this not by a single undirected edge, but a pair of directed arcs.\n- Arc consistency:\n    - Simplest form of propagation makes each arc consistent \n    - X to Y is consistent iff \\\n    for every value x of X there is some allowed y\n    - If Xloses a value, recheck neighbors of X\n    - If Xloses a value, we need to recheck neighbors of X \n    - Detects failure earlier than forward checking \n    - Can be run as a preprocessor or after each assignment\n    - **An arc (i,j) is arc consistent if and only if every value v on Xiis consistent with some label on Yj.**\\\n    To make an arc (i,j) arc consistent, for each value von Xi, if there is no label on Yj consistent with v then remove v from Xi\n    - Given d values, checking arc (i,j) takes O(d^2)time worst case\n\n###Replacing Search:\n\nThe Waltz/Mackworth Constraint Propagation Algorithm \n1. Assign every node in the constraint graph a set of all\npossible values \n2. Repeat until there is no change in the set of values\nassociated with any node:\n3. For each node i:\n4. For each neighboring node j in the picture:\n5. Remove any value from i which is not arc consistent with j.\n\n###Inefficiencies: Towards AC-3 \n1. At each iteration, we only need to examine those  Xi\nwhere at least one neighbor of Xi  has lost a value in the\nprevious iteration. \n2. If Xi loses a value only because of arc inconsistencies\nwith Yj, we don’t need to check Yj on the next iteration. \n3. Removing a value on Xi can only make Yj arc-\ninconsistent with respect to Xi  itself. Thus, we only\nneed to check that (j,i) is still arc-consistent. \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n \n##Knowledge-based Agents\n- Knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what action to take\n- A central component of a knowledge-based agent is a knowledge base or KB\n- AKB contains a set of **sentence** that are written in a **knowledge representation language**. The sentence contains some assertion about the world\n- Two kinds of sentences:\n    - Axioms: a sentence that is given\n    - Derived sentences: a new sentence that is derived from other sentences, this process is called **inference**\n- A KB can initially contain some **background information** about the world, and a knowledge-based agent can add to the information in the KB through its observations of the world.1\n- Logical Entailment and Inference: on reference paper\n\n##Knowledge Bases\nSound: the inference algorithm should only derive entailed sentences. \nComplete: an inference algorithm is complete if it can derive all sentences that are entailed\n\n###Resolution\nThere is a single inference rule, resolution, which yields a complete inference algorithm when coupled with any complete search algorithm.\n\n\n###Forward Chaining and Backward Chaining\nForward Chaining is a kind of data-driven reasoning. \\\nAn agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions.  It doesn’t have to have a specific query in mind to do so.\\\nBackward chaining works backwards from a query.  \\\nIf the query is known to be true, then no work is needed.  Otherwise, the algorithm finds implications in the KB whose conclusions is the query.  If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\\\nBackward chaining is a form of goal-directed reasoning.\n\n\n\n\n## Module 7 Definitions\n* **Concept** - definition\n\n\n# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nYour summary here\n\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 \n###Rantional Agents:\n**Agents:** \n- An agent is anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\n- A percept is the agent's perceptual inputs at any given instance.\n- An agent is specified by an **agent function** $$f:P\\longrightarrow a$$ that maps a sequence of percept vectors P to an action a from a set A.\n- Agent function & program: The **agent program** runs on physical **architecture** to produce f\n- **Agents** An agent is anything that can be viewd as:\n    - Perceiving its environment through sensors and\n    - Acting upon that environment through actuators\n\n###Rational Behavior & Expected Value:\n**Rational Agent**: A rational agent is an agent that perceives its environment and behaves rationally. Rational behavior: doing the right thing.\n- For each possible percept sequence P\n- a rational agents selects an action a\n- to maximize the **expected value** of its performance measure\n- Computational limitations make complete rationality unachievable - not omniscience\n\n**Performance measure**\n- An objective criterion for success of an agent's behavior\n- Given the evidence provided by the percept sequence\n- We want the performance measure: describe what you want to be achieved in the environment, rather than how you think the agent should behave.\n\n### Task Environments: **PEAS**\nTo design a rational agents we need to specify a task environment: a problem specification for which the agent is a solution\n- P: Performance measure\n- E: Environment\n- A: Actuators\n- S: Sensors\n\nGoal of AI practitioner who designs rational agents:\n**Given a PEAS task environment,**\n- Cioonstruct agent function **f** that maximizes the expected value of the performance measure,\n- Design an agent program that implements **f** on a particular architecture\n\n### Problem Solving Agents & Problem Formulation\nExample: 8-puzzle\nFormulate goal\n- Pieces to end up in order as shown…\n- Formulate search problem\n    - States: configurations of the puzzle (9! configurations)\n    - Actions: Move one of the movable pieces (≤4 possible)\n    - Performance measure: minimize total moves \n- Find solution\n    - Sequence of pieces moved:  3,1,6,3,1,\n \n\n## Module 1 Definitions\n* **Agent** - anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\n* **Percept** - the agent's perceptual inputs at any given instance.\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nYour summary here\n\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 \n###Rantional Agents:\n**Agents:** \n- An agent is anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\n- A percept is the agent's perceptual inputs at any given instance.\n- An agent is specified by an **agent function** $$f:P\\longrightarrow a$$ that maps a sequence of percept vectors P to an action a from a set A.\n- Agent function & program: The **agent program** runs on physical **architecture** to produce f\n- **Agents** An agent is anything that can be viewd as:\n    - Perceiving its environment through sensors and\n    - Acting upon that environment through actuators\n\n###Rational Behavior & Expected Value:\n**Rational Agent**: A rational agent is an agent that perceives its environment and behaves rationally. Rational behavior: doing the right thing.\n- For each possible percept sequence P\n- a rational agents selects an action a\n- to maximize the **expected value** of its performance measure\n- Computational limitations make complete rationality unachievable - not omniscience\n\n**Performance measure**\n- An objective criterion for success of an agent's behavior\n- Given the evidence provided by the percept sequence\n- We want the performance measure: describe what you want to be achieved in the environment, rather than how you think the agent should behave.\n\n### Task Environments: **PEAS**\nTo design a rational agents we need to specify a task environment: a problem specification for which the agent is a solution\n- P: Performance measure\n- E: Environment\n- A: Actuators\n- S: Sensors\n\nGoal of AI practitioner who designs rational agents:\n**Given a PEAS task environment,**\n- Cioonstruct agent function **f** that maximizes the expected value of the performance measure,\n- Design an agent program that implements **f** on a particular architecture\n\n### Problem Solving Agents & Problem Formulation\nExample: 8-puzzle\nFormulate goal\n- Pieces to end up in order as shown…\n- Formulate search problem\n    - States: configurations of the puzzle (9! configurations)\n    - Actions: Move one of the movable pieces (≤4 possible)\n    - Performance measure: minimize total moves \n- Find solution\n    - Sequence of pieces moved:  3,1,6,3,1,\n \n\n## Module 1 Definitions\n* **Agent** - anything that perceives its environment through perceives its environment through sensors and can act on its environment through actuators.\n* **Percept** - the agent's perceptual inputs at any given instance.\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}