{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "86YB_ezd_aeM"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9609194b-f351-4659-90ad-d7f1460ebb0a"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e4b12656-bf7c-4a39-c949-332247199031"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0CH4v-Wx_0oO"
      },
      "source": [
        "def parse(s):\n",
        "  ans = ''\n",
        "  for line in s.splitlines():\n",
        "    parts = line.split(':')\n",
        "    if len(parts)<2:\n",
        "      continue\n",
        "    a = '\"'+parts[0]+'\"'\n",
        "    b = '\"'+parts[1]+'\"'\n",
        "    ans += a + ':'+ b + ',' + '\\n' \n",
        "  return ans"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"```\n",
        "- Turing test: need nlp, knowledge representation, automated reasoning, and machine learning to pass\n",
        "- Total turing test: also need computer vision, speech recognition & robotics \n",
        "- Think like a human: introspection, psychological experiments, brain imaging \n",
        "- Rational agent: An agent that perceives its environment & behaves rationally\n",
        "  - For each possible percept sequence P\n",
        "  - A rational agent selects an action a\n",
        "  - To maximize its performance measure\n",
        "- Limited rationality: acting appropriately when there’s not enough time to do all computations one might like\n",
        "- Value alignment problem: values put into machine must be aligned w those of the human\n",
        "- 1st step in designing agent is to specify tasl environment fully\n",
        "- If performance measure is unknown, agent might optimize wrong objective\n",
        "- Through learning, all agents can improve their performance\n",
        "- Percept: 认知对象, the content an agent’s sensors are perceiving \n",
        "- Percept sequence: complete history of everything the agent has ever perceived\n",
        "```\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 = \"\"\"```Limits of AI\n",
        "Strong AI vs. Weak AI\n",
        "Actually thinking vs. merely simulating thinking\n",
        "```\n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\"```\n",
        "Can machines really think?\n",
        "Chinese room \n",
        "An agent’s choice of action at a given instant depends both on its percept sequence and future perceptual inputs.\n",
        "```\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"```\n",
        "Intelligent agents - agents & environments \n",
        "An agent is anything that can be viewed as perceiving its environment through sensors and acting upon it through actuators.\n",
        "An agent’’s choice of action at any given instant can depend on its built-in knowledge & on the entire percept sequence observed to date, but not on anything it hasn’t perceived\n",
        "``` \"\"\"\n",
        "\n",
        "chapter2_2 = \"\"\" Good behavior: concept of rationality \"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\" ```Nature of enviroments \n",
        "Task environments: “problems” to which rational agents are the “solutions”\n",
        "- Performance measure\n",
        "- Environment\n",
        "- Actuators\n",
        "- Sensors \n",
        "If environment is partially observable, it could appear to be nondeterministic\n",
        "```\"\"\"\n",
        "chapter2_4 = \"\"\"```Structure of agents \n",
        "Simple relex agent: select actions on basis of current percept, ignoring history \n",
        "Model based reflex agent: use transition model & sensor to keep track of state of world \n",
        "Goal-based agent: combine goal information w model to choose actions to achieve the goal\n",
        "Utility-based agent: utility function (internalization of performance measure)\n",
        "Maximize its utility \n",
        "Learning agents: allows agent to operate in initially unknown environments\n",
        "```\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"认知对象, the content an agent’s sensors are perceiving\",\n",
        "\"Percept sequence\": \"complete history of everything the agent has ever perceived\",\n",
        "\"Agent function\": \"specifies the action taken by the agent in response to any percept sequence\",\n",
        "\"Performance measure\": \"evaluates behavior of agent in env\",\n",
        "\"Rational agent\": \"acts to max the expected val of performance measure with the info of percept sequence seen\",\n",
        "\"Task environment\": \"includes performance measure, actuators, external enviroment, actuators, and sensors. \",\n",
        "\"Agent program\": \"implements agent function, varies in efficiency, compactness, and flexibility. Depends on nature of the environment\",\n",
        "\"Simple reflex agents\": \"respond directly to percepts\",\n",
        "\"Model-based reflex agents\": \"maintain internal state to track aspects of world not evident in curr percept\",\n",
        "\"Goal based agents\": \"act to achieve goals\",\n",
        "\"Utility based agents\": \"max their own expected happiness\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "c6523d09-83d7-4dc5-801a-31353cb4d4b6"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n```\n- Turing test: need nlp, knowledge representation, automated reasoning, and machine learning to pass\n- Total turing test: also need computer vision, speech recognition & robotics \n- Think like a human: introspection, psychological experiments, brain imaging \n- Rational agent: An agent that perceives its environment & behaves rationally\n  - For each possible percept sequence P\n  - A rational agent selects an action a\n  - To maximize its performance measure\n- Limited rationality: acting appropriately when there’s not enough time to do all computations one might like\n- Value alignment problem: values put into machine must be aligned w those of the human\n- 1st step in designing agent is to specify tasl environment fully\n- If performance measure is unknown, agent might optimize wrong objective\n- Through learning, all agents can improve their performance\n- Percept: 认知对象, the content an agent’s sensors are perceiving \n- Percept sequence: complete history of everything the agent has ever perceived\n```\n\n\n## AIMA Chapter 27.1 The Limits of AI\n```Limits of AI\nStrong AI vs. Weak AI\nActually thinking vs. merely simulating thinking\n```\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n```\nCan machines really think?\nChinese room \nAn agent’s choice of action at a given instant depends both on its percept sequence and future perceptual inputs.\n```\n\n## AIMA 2.1 Agents and Environments\n```\nIntelligent agents - agents & environments \nAn agent is anything that can be viewed as perceiving its environment through sensors and acting upon it through actuators.\nAn agent’’s choice of action at any given instant can depend on its built-in knowledge & on the entire percept sequence observed to date, but not on anything it hasn’t perceived\n``` \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Good behavior: concept of rationality \n\n## AIMA 2.3 The Nature of Environments\n ```Nature of enviroments \nTask environments: “problems” to which rational agents are the “solutions”\n- Performance measure\n- Environment\n- Actuators\n- Sensors \nIf environment is partially observable, it could appear to be nondeterministic\n```\n\n## AIMA 2.4 The Structure of Agents\n```Structure of agents \nSimple relex agent: select actions on basis of current percept, ignoring history \nModel based reflex agent: use transition model & sensor to keep track of state of world \nGoal-based agent: combine goal information w model to choose actions to achieve the goal\nUtility-based agent: utility function (internalization of performance measure)\nMaximize its utility \nLearning agents: allows agent to operate in initially unknown environments\n```\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - 认知对象, the content an agent’s sensors are perceiving\n* **Percept sequence** - complete history of everything the agent has ever perceived\n* **Agent function** - specifies the action taken by the agent in response to any percept sequence\n* **Performance measure** - evaluates behavior of agent in env\n* **Rational agent** - acts to max the expected val of performance measure with the info of percept sequence seen\n* **Task environment** - includes performance measure, actuators, external enviroment, actuators, and sensors. \n* **Agent program** - implements agent function, varies in efficiency, compactness, and flexibility. Depends on nature of the environment\n* **Simple reflex agents** - respond directly to percepts\n* **Model-based reflex agents** - maintain internal state to track aspects of world not evident in curr percept\n* **Goal based agents** - act to achieve goals\n* **Utility based agents** - max their own expected happiness\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",
        "Dynamic typing\n",
        "- Variables come into existence when first assigned \n",
        "type(var) automatically determined\n",
        "If assigned again, type(var) is updated\n",
        "Functions have no type signatures\n",
        "Drawback: type errors are only caught at runtime\n",
        "``` \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 288
        },
        "outputId": "0f32fcc1-6ac9-4451-d3d7-4803e93c3fa7"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n ```\nDynamic typing\n- Variables come into existence when first assigned \ntype(var) automatically determined\nIf assigned again, type(var) is updated\nFunctions have no type signatures\nDrawback: type errors are only caught at runtime\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 = \"\"\" ```\n",
        "Search: the process of looking for a sequence of actions that reaches the goal\n",
        "To fully define a search problem, we need\n",
        "State space\n",
        "- Initial state\n",
        "- Goal states\n",
        "- Actions\n",
        "- Transition model\n",
        "- Action cost function\n",
        "BFS: use with infinite paths\n",
        "DFS: memory efficient\n",
        "\n",
        "``` \"\"\"\n",
        "chapter3_2 = \"\"\" The state space  is the set of possible states of the environment \"\"\"\n",
        "chapter3_3 = \"\"\" ```\n",
        "Graph search is faster than tree search\n",
        "We call a search algorithm a graph search if it checks for redundant paths. Because it does not waste time examining those redundant paths, it runs more quickly\n",
        "Uniform cost search: complete & cost-optimal\n",
        "Guaranteed to find an optimal solution \n",
        "Dijkstra is a similar search without a goal\n",
        "A special case of A* where f(n) is all 0\n",
        "Dfs does NOT has much lower space complexity than iterative deepening \n",
        "``` \"\"\"\n",
        "chapter3_4 = \"\"\" In a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" ```\n",
        "Use depth-first if\n",
        "- Space is restricted\n",
        "- Many possible solutions w long paths\n",
        "- Wrong paths are usually terminated quickly\n",
        "= Search can be fine-tuned quickly\n",
        "Use breadth-first if\n",
        "- Possible infinite paths\n",
        "- Some solutions have short paths\n",
        "Iterative deepening search\n",
        "- Complete: YES \n",
        "- Time complexity: O(bd)\n",
        "- Space complexity: O(bd)\n",
        "- Optimal: YES if step cost is 1\n",
        "\n",
        "d: depth/ num of actions in an optimal solution\n",
        "m: max depth / number of actions in any path\n",
        "b: branching factor or num of successors of a node that need to be considered\n",
        "d: number you put in\n",
        "l: depth limit\n",
        "\n",
        "- An agent can use to select action sequences ina wide variety of environments when they’re episodic, single-agent, fully observable, deterministic, static, discrete, and completely known \n",
        "- Must formulate a problem for an agent to start searching\n",
        "5 parts of problem: \n",
        "1.initial state\n",
        "2.set of actions\n",
        "3. transition model: describe result of those actions \n",
        "4. goal states\n",
        "5. action cost function \n",
        "\n",
        "Iterative deepening search: calls dfs w increasing depth limits until a goal is found. Complete ( when full cycle checking is odne), optimal for unit action cost, O(bd) space, O(b^d) time\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",
        "\"State space graph\":\" represents the enviroment of the problem\",\n",
        "\"Solution\":\" a path through the state space from initial state\",\n",
        "\"Atomic\":\" 原子的, no internal structure/ search algorithms treat states & actions as atomic\",\n",
        "\"Uninformed search\":\" only have access to problem definition. Algorithm build a search tree to find a solution\",\n",
        "\"Best-first search\":\" select nodes for expansion using an evaluation function\",\n",
        "\"Breadth-first search\":\" expands shallowest 最浅的 nodes first. Complete, optimal unit action cost, b^d space & time complexity\",\n",
        "\"Uniform-cost search\":\" expands the node with lowest path cost g(n). Optimal for general action cost\",\n",
        "\"Depth-first search\":\" expands deepest unexpanded node first. Not complete, not optimal, linear O(bm) space, O(b^m)time\",\n",
        "\"Depth-limited search\":\" adds a depth bound, Not complete, not optimal, linear O(bl) space, O(b^l)time\",\n",
        "\"Bidirectional A* search\":\" expands 2 frontiers, one around initial state & one around the goal, stopping when 2 frontiers meet\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "a94ed5a6-6db8-40e4-ee0a-f5aa33f5f9be"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n ```\nSearch: the process of looking for a sequence of actions that reaches the goal\nTo fully define a search problem, we need\nState space\n- Initial state\n- Goal states\n- Actions\n- Transition model\n- Action cost function\nBFS: use with infinite paths\nDFS: memory efficient\n\n``` \n\n## AIMA Chapter 3.2 Example Problems\n The state space  is the set of possible states of the environment \n\n## AIMA Chapter 3.3 Search Algorithms\n ```\nGraph search is faster than tree search\nWe call a search algorithm a graph search if it checks for redundant paths. Because it does not waste time examining those redundant paths, it runs more quickly\nUniform cost search: complete & cost-optimal\nGuaranteed to find an optimal solution \nDijkstra is a similar search without a goal\nA special case of A* where f(n) is all 0\nDfs does NOT has much lower space complexity than iterative deepening \n``` \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n In a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions \n\n## Module 3 Lecture Notes\n ```\nUse depth-first if\n- Space is restricted\n- Many possible solutions w long paths\n- Wrong paths are usually terminated quickly\n= Search can be fine-tuned quickly\nUse breadth-first if\n- Possible infinite paths\n- Some solutions have short paths\nIterative deepening search\n- Complete: YES \n- Time complexity: O(bd)\n- Space complexity: O(bd)\n- Optimal: YES if step cost is 1\n\nd: depth/ num of actions in an optimal solution\nm: max depth / number of actions in any path\nb: branching factor or num of successors of a node that need to be considered\nd: number you put in\nl: depth limit\n\n- An agent can use to select action sequences ina wide variety of environments when they’re episodic, single-agent, fully observable, deterministic, static, discrete, and completely known \n- Must formulate a problem for an agent to start searching\n5 parts of problem: \n1.initial state\n2.set of actions\n3. transition model: describe result of those actions \n4. goal states\n5. action cost function \n\nIterative deepening search: calls dfs w increasing depth limits until a goal is found. Complete ( when full cycle checking is odne), optimal for unit action cost, O(bd) space, O(b^d) time\n``` \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space graph** -  represents the enviroment of the problem\n* **Solution** -  a path through the state space from initial state\n* **Atomic** -  原子的, no internal structure/ search algorithms treat states & actions as atomic\n* **Uninformed search** -  only have access to problem definition. Algorithm build a search tree to find a solution\n* **Best-first search** -  select nodes for expansion using an evaluation function\n* **Breadth-first search** -  expands shallowest 最浅的 nodes first. Complete, optimal unit action cost, b^d space & time complexity\n* **Uniform-cost search** -  expands the node with lowest path cost g(n). Optimal for general action cost\n* **Depth-first search** -  expands deepest unexpanded node first. Not complete, not optimal, linear O(bm) space, O(b^m)time\n* **Depth-limited search** -  adds a depth bound, Not complete, not optimal, linear O(bl) space, O(b^l)time\n* **Bidirectional a* search** -  expands 2 frontiers, one around initial state & one around the goal, stopping when 2 frontiers meet\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" ```\n",
        "Informed search: uses domain specific hints about the location of goals\n",
        "\n",
        "Greedy best first search:\n",
        "\n",
        "- expands first the node with the lowest h(n) value. Eval function f(n) = h(n). \n",
        "- Complete in finite state space, not in infinite\n",
        "- Worst case time & space complexity: O(|V|)\n",
        "- Good heuristic function: reaching O(bm)\n",
        "\n",
        "A* search\n",
        "- expands node with minimal f(n) = g(n) + h(n) = estimated total cost of path from n to goal\n",
        "- g(n): actual cost from start to node\n",
        "- h(n): estimated cost to get from node to goal\n",
        "- Worst case time & space complexity: O(|V|) = O(b^d)\n",
        "- Prunes away some search tree nodes, but worst space stays the same\n",
        "- Complete, cost-optimal (if h(h) is admissible), optimally efficient \n",
        "- Expands many nodes- exponential in length\n",
        "\n",
        "Satisficing solutions: allow A* search to use a inadmissible heuristi (may overestimate) but reduce num of nodes expanded \n",
        "Weighted A* search: weight heuristic value more heavily: f(n) = g(n) +Wxh(n)\n",
        "Bounded suboptimal search: look for solution that’s guaranteed to be within a constant factor W of the optimal cost\n",
        "Bounded-cost search: look for solution whose cost < constant C\n",
        "Unbounded-cost search: accept a solution of any cost, as long as we can find it quickly \n",
        "\n",
        "Memory bounded search\n",
        "Beam search: limits the size of frontier \n",
        "Iterative-deepening A* search: don’t keep all reached states in memory \n",
        "Recursive best-first search: linear space\n",
        "Bidirectional heuristic search: no guarantee that lead to optimal cost or efficient\n",
        "Front to end: distance to goal & distance to start\n",
        "Front-to-front: estimate distance to other frontier\n",
        "\n",
        "An admissible heuristic is one that never overstimates the cost to reach a goal\n",
        "\n",
        "``` \"\"\"\n",
        "chapter3_6 = \"\"\" ```\n",
        "Effective branching factor b*: a uniform tree of depth d would have to have in order to contain N+1 nodes\n",
        "- N+1 = 1 + b* + (b*)^2 + .. + (b*)^d\n",
        "Performance of heuristic search algorithms depends on quality of heuristic function\n",
        "How to construct good heuristic\n",
        "- Relax problem definition\n",
        "- Store precompute dissolution costs for subproblems in pattern database\n",
        "- Define landmarks\n",
        "- Learn from experience w problem class\n",
        "In estimating the travel distance between two locations, Euclidean distance is a consistent and admissible heuristic.\n",
        "```\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" ```\n",
        "Performance of heuristic search depends on quality of heuristic function\n",
        "Can sometimes construct good heuristic by relaxing problem def, store precomputed solution costs for subproblems in pattern database, define landmarks, or learn from experience w problem class\n",
        "Consistency: a heuristic h(n) is consistent if for every node n & every successor n’ of n generated by an action a, we have: \n",
        "- h(n) <= c(n,a,n’) + h(n’)\n",
        "- Every consistent heuristic is admissible (not vice versa)\n",
        "\n",
        "Recursive best-first search: RBFS. optimal search algo that use limited amounts of memory; can solve problems that A* runs out of memory if there’s enough time\n",
        "``` \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Informed search\":\" have access to a heuristic function h(n) & may have additional info like pattern databases w solution costs\",\n",
        "\"Heuristic function\":\" a function  h(n) that estimates cost of n to a solution.\",\n",
        "\"Greedy best-first search\":\" expands nodes w minimal h(n). Not optimal but efficient\",\n",
        "\"A* search\":\" expands nodes w minimal f(n) = g(n) + h(n). g(n)\",\n",
        "\"Admissible\":\" a heuristic is admissible if it never overestimates the cost to reach the goal\",\n",
        "\"Bidirectional A* search\":\" sometimes more efficient than A*\",\n",
        "\"Iterative Deepening A*\":\" Iterative Deepening version of A*, helps w space\",\n",
        "\"Simplified memory-bounded A*\":\" same w RBFS\",\n",
        "\"Beam search\":\" puts limit on size of frontier; incomplete & suboptimal; reasonably good solutions & runs faster \",\n",
        "\"Weighted A*\":\" focus search towards a goal, expending fewer nodes, not optimal\",\n",
        "\"Triangle equality\":\" side of triangle cannot be longer than the sum of other 2 sides\",\n",
        "\"Monotonic\":\" path cost always increase as you go along a path since action costs are always positive\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "08bbd554-482a-4e42-ac93-707004cc267e"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n ```\nInformed search: uses domain specific hints about the location of goals\n\nGreedy best first search:\n\n- expands first the node with the lowest h(n) value. Eval function f(n) = h(n). \n- Complete in finite state space, not in infinite\n- Worst case time & space complexity: O(|V|)\n- Good heuristic function: reaching O(bm)\n\nA* search\n- expands node with minimal f(n) = g(n) + h(n) = estimated total cost of path from n to goal\n- g(n): actual cost from start to node\n- h(n): estimated cost to get from node to goal\n- Worst case time & space complexity: O(|V|) = O(b^d)\n- Prunes away some search tree nodes, but worst space stays the same\n- Complete, cost-optimal (if h(h) is admissible), optimally efficient \n- Expands many nodes- exponential in length\n\nSatisficing solutions: allow A* search to use a inadmissible heuristi (may overestimate) but reduce num of nodes expanded \nWeighted A* search: weight heuristic value more heavily: f(n) = g(n) +Wxh(n)\nBounded suboptimal search: look for solution that’s guaranteed to be within a constant factor W of the optimal cost\nBounded-cost search: look for solution whose cost < constant C\nUnbounded-cost search: accept a solution of any cost, as long as we can find it quickly \n\nMemory bounded search\nBeam search: limits the size of frontier \nIterative-deepening A* search: don’t keep all reached states in memory \nRecursive best-first search: linear space\nBidirectional heuristic search: no guarantee that lead to optimal cost or efficient\nFront to end: distance to goal & distance to start\nFront-to-front: estimate distance to other frontier\n\nAn admissible heuristic is one that never overstimates the cost to reach a goal\n\n``` \n\n## AIMA Chapter 3.6 Heuristic Functions\n ```\nEffective branching factor b*: a uniform tree of depth d would have to have in order to contain N+1 nodes\n- N+1 = 1 + b* + (b*)^2 + .. + (b*)^d\nPerformance of heuristic search algorithms depends on quality of heuristic function\nHow to construct good heuristic\n- Relax problem definition\n- Store precompute dissolution costs for subproblems in pattern database\n- Define landmarks\n- Learn from experience w problem class\nIn estimating the travel distance between two locations, Euclidean distance is a consistent and admissible heuristic.\n```\n\n## Module 4 Lecture Notes\n ```\nPerformance of heuristic search depends on quality of heuristic function\nCan sometimes construct good heuristic by relaxing problem def, store precomputed solution costs for subproblems in pattern database, define landmarks, or learn from experience w problem class\nConsistency: a heuristic h(n) is consistent if for every node n & every successor n’ of n generated by an action a, we have: \n- h(n) <= c(n,a,n’) + h(n’)\n- Every consistent heuristic is admissible (not vice versa)\n\nRecursive best-first search: RBFS. optimal search algo that use limited amounts of memory; can solve problems that A* runs out of memory if there’s enough time\n``` \n\n## Module 4 Definitions\n* **Informed search** -  have access to a heuristic function h(n) & may have additional info like pattern databases w solution costs\n* **Heuristic function** -  a function  h(n) that estimates cost of n to a solution.\n* **Greedy best-first search** -  expands nodes w minimal h(n). Not optimal but efficient\n* **A* search** -  expands nodes w minimal f(n) = g(n) + h(n). g(n)\n* **Admissible** -  a heuristic is admissible if it never overestimates the cost to reach the goal\n* **Bidirectional a* search** -  sometimes more efficient than A*\n* **Iterative deepening a*** -  Iterative Deepening version of A*, helps w space\n* **Simplified memory-bounded a*** -  same w RBFS\n* **Beam search** -  puts limit on size of frontier; incomplete & suboptimal; reasonably good solutions & runs faster \n* **Weighted a*** -  focus search towards a goal, expending fewer nodes, not optimal\n* **Triangle equality** -  side of triangle cannot be longer than the sum of other 2 sides\n* **Monotonic** -  path cost always increase as you go along a path since action costs are always positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" ```\n",
        "Minimax search: solves perfect information, zero-sum games\n",
        "- Evaluates nodes in same order as dfs\n",
        "- The value at that node is the value of the best terminal state reach by both player playing optimally. That means that the current player tries to maximize the score and the other player tries to minimize it\n",
        "- Time: O(b^m) \n",
        "  - b: # of legal moves at each node\n",
        "  - m: max depth of tree\n",
        "Perfect information = fully observable\n",
        "Zero sum = what is good for one player is just as bad for the other, no win-win\n",
        "Move = action\n",
        "Position = state\n",
        "Pruning: makes the search more efficient by ignoring parts that’s not in optimal move\n",
        "Define a game with: initial state, actions, result/transition model,terminal test, utility function\n",
        " \n",
        "Games have multiple agents while search problems do not\n",
        "Utility function gives the payoff for each player in terminal state s\n",
        "``` \"\"\"\n",
        "chapter5_2 = \"\"\" ```\n",
        "Minimax value: utility of being in that state assuming both players play optimally from there to the end of the game\n",
        "Minimax search algorithm solves perfect information, zero-sum games\n",
        "In minimax search, the value of a node is the optimal value of its children \n",
        "- For the MAX player, that's the highest value. For MIN, that's the lowest value. This is because minimax assumes both players play optimally.\n",
        "The minimax decision maximizes the utility under the assumption that the opponent plays perfectly\n",
        "Alpha-beta search computes the same optimal moves as minimax.\n",
        "``` \"\"\"\n",
        "chapter5_3 = \"\"\" ```\n",
        "Heuristic evaluation function returns an estimate of expected utility of state s to player p\n",
        "The effectiveness of Alpha-Beta pruning DEPEND on the order in which successor nodes are examined.\n",
        "``` \"\"\"\n",
        "\n",
        "chapter5_4 = \"\"\" ```\n",
        "MCT strategy: value of a state is estimated as the avg utility over a num of simulation(or playout/rollout) of complete games starting from the state\n",
        "4 steps: selection, expansion, simulation, back-propagation\n",
        "``` \"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\" ```\n",
        "Chance nodes: denote possible dice roles w possibility\n",
        "Stochastic game: unpredictability, include random elements\n",
        "For stochastic? Games, chance nodes denoting the probabilities associated with each action as well as expecti-minimax values are included in the minimax tree.\n",
        "```\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Maximum expected utility MEU: a rational agent should choos ethe action that maximizes agent’s expected utility  \"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "```Monte carlo tree search MCTs: evaluate states not by applying a heuristic function, but by playing out the game all the way to the end & using rules of game to see who won\n",
        "Expectiminimax: games of chance, evaluates a chance node by taking avg utility of all its children, weighted by probability of each child\n",
        "```\"\"\"\n",
        "chapter16_3 = \"\"\" Expected monetary value (EMV): sum of pr[getting the value] * value \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Alpha-beta search\":\" computes same optimal move as minimax, but achieve greater efficiency by eliminating irrelevant subtrees\",\n",
        "\"Monte carlo tree search MCTs\":\" evaluate states not by applying heuristic function, but by playing out the game all the way to the end\",\n",
        "\"Expectiminimax\":\" games of chance, evaluates a chance node by taking avg utility of all its children\",\n",
        "\"Imperfect information games\":\" need to reason about belief states of each player& avg value\",\n",
        "\"Probability theory\":\" what an agent should believe on basis of evidence\",\n",
        "\"Utility theorey\":\" describes what an agent wants \",\n",
        "\"Rational agent\":\" makes decisions by considering all possible actions & choosing the one that leads to the best expected outcome\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "db596ae4-6f88-4d22-d344-9651cf8a5784"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n ```\nMinimax search: solves perfect information, zero-sum games\n- Evaluates nodes in same order as dfs\n- The value at that node is the value of the best terminal state reach by both player playing optimally. That means that the current player tries to maximize the score and the other player tries to minimize it\n- Time: O(b^m) \n  - b: # of legal moves at each node\n  - m: max depth of tree\nPerfect information = fully observable\nZero sum = what is good for one player is just as bad for the other, no win-win\nMove = action\nPosition = state\nPruning: makes the search more efficient by ignoring parts that’s not in optimal move\nDefine a game with: initial state, actions, result/transition model,terminal test, utility function\n \nGames have multiple agents while search problems do not\nUtility function gives the payoff for each player in terminal state s\n``` \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n ```\nMinimax value: utility of being in that state assuming both players play optimally from there to the end of the game\nMinimax search algorithm solves perfect information, zero-sum games\nIn minimax search, the value of a node is the optimal value of its children \n- For the MAX player, that's the highest value. For MIN, that's the lowest value. This is because minimax assumes both players play optimally.\nThe minimax decision maximizes the utility under the assumption that the opponent plays perfectly\nAlpha-beta search computes the same optimal moves as minimax.\n``` \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n ```\nHeuristic evaluation function returns an estimate of expected utility of state s to player p\nThe effectiveness of Alpha-Beta pruning DEPEND on the order in which successor nodes are examined.\n``` \n\n## AIMA Chapter 5.5 Stochastic Games\n ```\nChance nodes: denote possible dice roles w possibility\nStochastic game: unpredictability, include random elements\nFor stochastic? Games, chance nodes denoting the probabilities associated with each action as well as expecti-minimax values are included in the minimax tree.\n```\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Maximum expected utility MEU: a rational agent should choos ethe action that maximizes agent’s expected utility  \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n```Monte carlo tree search MCTs: evaluate states not by applying a heuristic function, but by playing out the game all the way to the end & using rules of game to see who won\nExpectiminimax: games of chance, evaluates a chance node by taking avg utility of all its children, weighted by probability of each child\n```\n\n## AIMA Chapter 16.3 Utility Functions\n Expected monetary value (EMV): sum of pr[getting the value] * value \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Alpha-beta search** -  computes same optimal move as minimax, but achieve greater efficiency by eliminating irrelevant subtrees\n* **Monte carlo tree search mcts** -  evaluate states not by applying heuristic function, but by playing out the game all the way to the end\n* **Expectiminimax** -  games of chance, evaluates a chance node by taking avg utility of all its children\n* **Imperfect information games** -  need to reason about belief states of each player& avg value\n* **Probability theory** -  what an agent should believe on basis of evidence\n* **Utility theorey** -  describes what an agent wants \n* **Rational agent** -  makes decisions by considering all possible actions & choosing the one that leads to the best expected outcome\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" ```\n",
        "`constraint propagation: using the constraints to reduce the number of legal values for a variable, \n",
        "CSPs represent a state with a set of variable/value pairs\n",
        "CSPs represent the conditions for a solution with a set of constraints on the variables\n",
        "In search problems, states are black boxes with a transition model to move between boxes. In CSPs, the agent can see inside the states and move between states accordingly.\n",
        "```\"\"\"\n",
        "chapter6_2 = \"\"\"```\n",
        "CSP have 2 ways of ruling out variable assignments: search & inference\n",
        "Constraint propagation: using the constraints to reduce the number of legal values for a variable, \n",
        "- Can reduce legal values for another variable\n",
        "In CSP solvers, inference techniques use constriants to rule out variable assignment\n",
        "- Key idea behind inference: enforcing k-consistency\n",
        "\n",
        "A single var is node-consistent if all values in variable’s domain satisfy the variable’s unary constraint\n",
        "Arc consistency: if every value in its domain asatisfies the variable’s binary constraints \n",
        "- Tightens down domains using arcs\n",
        "Ac-3: algorithm that enforces arc consistency\n",
        "- Algorithm: Place all the arcs in a queue. Pop arcs. For each arc, remove inconsistent values. If we change the values of a node, add its arcs to the queue. Terminate when the queue is empty.\n",
        "- maintains a queue of arcs to consider\n",
        "- Initially: contain all arcs in CSP\n",
        "- Pops off arbitrary arc from queue & makes Xi arc-consistent w respect to xj. \n",
        "- If changes Di (makes domain smaller), add queue all argos (Xk,Xi) where Xk is a neighbor of Xi \n",
        "- If D revised down to nothing, CSP has no consistent solution → AC-3 return false \n",
        "- Checking consistency of an arc: O(d2) time, d being the domain size \n",
        "- O(cd3) total worst case time\n",
        "Path consistency \n",
        "- Tightens binary constraints by using implicit constraints inferred by looking at triples of variables \n",
        "K-consistency \n",
        "- If for any set of k-1 variables & for any consistent assignment to those var, a consistent val can always be assigned to any kth variable \n",
        "Global constraints\n",
        "- One involving an arbitrary num of variables\n",
        "```\"\"\"\n",
        "chapter6_3 = \"\"\"```\n",
        "Back tracking search \n",
        "MRV(minimum remaining value) heuristic\n",
        "- chooses variable w fewest legal values\n",
        "Degree heuristic\n",
        "- Chooses variable w largest num of constraints \n",
        "Least constraining value heuristic\n",
        "- chooses the value that rules out the fewest values for neighboring variables\n",
        "Constraint learning\n",
        "- records the conflicts as they are encountered in the search in order to avoid the same conflict later\n",
        "Forward checking\n",
        "- Whenever a variable X is assigned, we establish arc consistency for X\n",
        "MAC: maintaining Arc Consistency\n",
        "- Detects inconsistencies that doesn’t satisfy the constraint\n",
        "Chronological backtracking\n",
        "- Back up to the preceding variable & try a different value for it\n",
        "- Most recent decision point is revisited\n",
        "difference between MAC and forward checking\n",
        "- MAC recursively propogrates constraints, whereas forward checking does not. If we assign X, forward checking makes all the arcs incident on X consistent. MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...) \n",
        "Diff btw MAC & AC-3\n",
        "- MAC is a way of interleaving search and inference. AC-3 is pure inference. MAC runs while assigning variables in backtracking search. Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3\n",
        "```\"\"\"\n",
        "chapter6_4 = \"\"\"```\n",
        "```\"\"\"\n",
        "chapter6_5 = \"\"\"```\n",
        "Solving Arbitrary CSP takes exponential time\n",
        "Tree-structured CSP: linear time\n",
        "Cutset conditioning: \n",
        "- reduce a general CSP to a tree structured one\n",
        "- Can be executed in linear memory \n",
        "- Efficient if a small cutset can be found\n",
        "- No more efficient than solving a CSP directly \n",
        "- Most space efficient\n",
        "Tree decomposition\n",
        "- transform the CSP into a tree of subproblems \n",
        "- are efficient if the tree width of the constraint graph is small\n",
        "- Most time efficient\n",
        "```\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CSP:rep a state w set of var/val pairs & rep conditions for a solution by a set of constraints on variables\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Inference techniques\":\" node, arc, k-consistency\",\n",
        "\"Backtracking search\":\" a form of dfs. Occurs when no legal assignment can be found for a var\",\n",
        "\"Minimum-remaining-values and degree heuristics\":\" domain-independent methods for deciding which variable to choose next in backtracking search\",\n",
        "\"Least-constraining-value heuristics\":\" helps to divide which value to try first for a given var\",\n",
        "\"Conflict-directed backjumping\":\" backtracks directly to source of problem\",\n",
        "\"Constraint learning\":\" records conflicts as encountered during search to avoid same conflict later\",\n",
        "\"Mini-conflicts heuristic\":\" local search use this \",\n",
        "\"Cutset conditioning\":\" reduce a general CSP to a tree-structured one & efficient if a small cutset can be found\",\n",
        "\"Tree decomposition\":\" transform CSP into a tree of subproblems & are efficient if tree width of constraint graph is small\",\n",
        "  \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "2d5f6498-1210-4453-fbb6-45026e3308ee"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n ```\n`constraint propagation: using the constraints to reduce the number of legal values for a variable, \nCSPs represent a state with a set of variable/value pairs\nCSPs represent the conditions for a solution with a set of constraints on the variables\nIn search problems, states are black boxes with a transition model to move between boxes. In CSPs, the agent can see inside the states and move between states accordingly.\n```\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n```\nCSP have 2 ways of ruling out variable assignments: search & inference\nConstraint propagation: using the constraints to reduce the number of legal values for a variable, \n- Can reduce legal values for another variable\nIn CSP solvers, inference techniques use constriants to rule out variable assignment\n- Key idea behind inference: enforcing k-consistency\n\nA single var is node-consistent if all values in variable’s domain satisfy the variable’s unary constraint\nArc consistency: if every value in its domain asatisfies the variable’s binary constraints \n- Tightens down domains using arcs\nAc-3: algorithm that enforces arc consistency\n- Algorithm: Place all the arcs in a queue. Pop arcs. For each arc, remove inconsistent values. If we change the values of a node, add its arcs to the queue. Terminate when the queue is empty.\n- maintains a queue of arcs to consider\n- Initially: contain all arcs in CSP\n- Pops off arbitrary arc from queue & makes Xi arc-consistent w respect to xj. \n- If changes Di (makes domain smaller), add queue all argos (Xk,Xi) where Xk is a neighbor of Xi \n- If D revised down to nothing, CSP has no consistent solution → AC-3 return false \n- Checking consistency of an arc: O(d2) time, d being the domain size \n- O(cd3) total worst case time\nPath consistency \n- Tightens binary constraints by using implicit constraints inferred by looking at triples of variables \nK-consistency \n- If for any set of k-1 variables & for any consistent assignment to those var, a consistent val can always be assigned to any kth variable \nGlobal constraints\n- One involving an arbitrary num of variables\n```\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n```\nBack tracking search \nMRV(minimum remaining value) heuristic\n- chooses variable w fewest legal values\nDegree heuristic\n- Chooses variable w largest num of constraints \nLeast constraining value heuristic\n- chooses the value that rules out the fewest values for neighboring variables\nConstraint learning\n- records the conflicts as they are encountered in the search in order to avoid the same conflict later\nForward checking\n- Whenever a variable X is assigned, we establish arc consistency for X\nMAC: maintaining Arc Consistency\n- Detects inconsistencies that doesn’t satisfy the constraint\nChronological backtracking\n- Back up to the preceding variable & try a different value for it\n- Most recent decision point is revisited\ndifference between MAC and forward checking\n- MAC recursively propogrates constraints, whereas forward checking does not. If we assign X, forward checking makes all the arcs incident on X consistent. MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...) \nDiff btw MAC & AC-3\n- MAC is a way of interleaving search and inference. AC-3 is pure inference. MAC runs while assigning variables in backtracking search. Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3\n```\n\n## AIMA Chapter 6.4 Local Search for CSPs\n```\n```\n\n## AIMA Chapter 6.5 The Structure of Problems\n```\nSolving Arbitrary CSP takes exponential time\nTree-structured CSP: linear time\nCutset conditioning: \n- reduce a general CSP to a tree structured one\n- Can be executed in linear memory \n- Efficient if a small cutset can be found\n- No more efficient than solving a CSP directly \n- Most space efficient\nTree decomposition\n- transform the CSP into a tree of subproblems \n- are efficient if the tree width of the constraint graph is small\n- Most time efficient\n```\n\n## Module 6 Lecture Notes\n CSP:rep a state w set of var/val pairs & rep conditions for a solution by a set of constraints on variables\n \n\n## Module 6 Definitions\n* **Inference techniques** -  node, arc, k-consistency\n* **Backtracking search** -  a form of dfs. Occurs when no legal assignment can be found for a var\n* **Minimum-remaining-values and degree heuristics** -  domain-independent methods for deciding which variable to choose next in backtracking search\n* **Least-constraining-value heuristics** -  helps to divide which value to try first for a given var\n* **Conflict-directed backjumping** -  backtracks directly to source of problem\n* **Constraint learning** -  records conflicts as encountered during search to avoid same conflict later\n* **Mini-conflicts heuristic** -  local search use this \n* **Cutset conditioning** -  reduce a general CSP to a tree-structured one & efficient if a small cutset can be found\n* **Tree decomposition** -  transform CSP into a tree of subproblems & are efficient if tree width of constraint graph is small\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" ```\n",
        "Intelligent agents need knowledge about the world in order to reach good decisions\n",
        "Knowledge is contained in agents in form of sentences in a knowledge rep language, stored in knowledge base\n",
        "``` \"\"\"\n",
        "chapter7_2 = \"\"\" ```\n",
        "Representation language is defined by syntax\n",
        "Syntax specifies structures of sentences & its semantics\n",
        "Semantics defines the truth of each sentences in each possible world/model\n",
        "``` \"\"\"\n",
        "chapter7_3 = \"\"\" ```\n",
        "Entailment between sentences\n",
        "Validity of sentence\n",
        "Unsatisfiability of sentence\n",
        "``` \"\"\"\n",
        "chapter7_4 = \"\"\" ```\n",
        "Propositional logic: simple language consisting of proposition symbols & logical connectives; can handle propositions taht are known to be true, false, or unknown\n",
        "``` \"\"\"\n",
        "chapter7_5 = \"\"\" ```\n",
        "CNF: conjunctive normal form \n",
        "- Biconditional elimination\n",
        "- Implication elimination\n",
        "- Demorgan \n",
        "``` \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Propositional logic: simple language consisting of proposition symbols & logical connectives; can handle propositions taht are known to be true, false, or unknown \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Inference\":\" process of deriving new sentences from old ones\",\n",
        "\"Sound inference\":\" derive only sentences that are entailed\",\n",
        "\"Complete algorithms\":\" derive all sentences that are entailed\",\n",
        "\"Inference rules\":\" patterns of sound inference that can be used to find proofs\",\n",
        "\"Resolution rule\":\" yields a complete inference algorithm from knowledge base expressed in CNF\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 762
        },
        "outputId": "84ee65f6-1f54-4105-ca67-c03ddf9672bd"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n ```\nIntelligent agents need knowledge about the world in order to reach good decisions\nKnowledge is contained in agents in form of sentences in a knowledge rep language, stored in knowledge base\n``` \n\n## AIMA Chapter 7.2 The Wumpus World\n ```\nRepresentation language is defined by syntax\nSyntax specifies structures of sentences & its semantics\nSemantics defines the truth of each sentences in each possible world/model\n``` \n\n## AIMA Chapter 7.3 Logic\n ```\nEntailment between sentences\nValidity of sentence\nUnsatisfiability of sentence\n``` \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n ```\nPropositional logic: simple language consisting of proposition symbols & logical connectives; can handle propositions taht are known to be true, false, or unknown\n``` \n\n## AIMA 7.5 Propositional Theorem Proving\n ```\nCNF: conjunctive normal form \n- Biconditional elimination\n- Implication elimination\n- Demorgan \n``` \n\n## Module 7 Lecture Notes\n Propositional logic: simple language consisting of proposition symbols & logical connectives; can handle propositions taht are known to be true, false, or unknown \n\n## Module 7 Definitions\n* **Inference** -  process of deriving new sentences from old ones\n* **Sound inference** -  derive only sentences that are entailed\n* **Complete algorithms** -  derive all sentences that are entailed\n* **Inference rules** -  patterns of sound inference that can be used to find proofs\n* **Resolution rule** -  yields a complete inference algorithm from knowledge base expressed in CNF\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": "c3615481-bcb6-4dfb-e069-facd9db06152"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n```\n- Turing test: need nlp, knowledge representation, automated reasoning, and machine learning to pass\n- Total turing test: also need computer vision, speech recognition & robotics \n- Think like a human: introspection, psychological experiments, brain imaging \n- Rational agent: An agent that perceives its environment & behaves rationally\n  - For each possible percept sequence P\n  - A rational agent selects an action a\n  - To maximize its performance measure\n- Limited rationality: acting appropriately when there’s not enough time to do all computations one might like\n- Value alignment problem: values put into machine must be aligned w those of the human\n- 1st step in designing agent is to specify tasl environment fully\n- If performance measure is unknown, agent might optimize wrong objective\n- Through learning, all agents can improve their performance\n- Percept: 认知对象, the content an agent’s sensors are perceiving \n- Percept sequence: complete history of everything the agent has ever perceived\n```\n\n\n## AIMA Chapter 27.1 The Limits of AI\n```Limits of AI\nStrong AI vs. Weak AI\nActually thinking vs. merely simulating thinking\n```\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n```\nCan machines really think?\nChinese room \nAn agent’s choice of action at a given instant depends both on its percept sequence and future perceptual inputs.\n```\n\n## AIMA 2.1 Agents and Environments\n```\nIntelligent agents - agents & environments \nAn agent is anything that can be viewed as perceiving its environment through sensors and acting upon it through actuators.\nAn agent’’s choice of action at any given instant can depend on its built-in knowledge & on the entire percept sequence observed to date, but not on anything it hasn’t perceived\n``` \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Good behavior: concept of rationality \n\n## AIMA 2.3 The Nature of Environments\n ```Nature of enviroments \nTask environments: “problems” to which rational agents are the “solutions”\n- Performance measure\n- Environment\n- Actuators\n- Sensors \nIf environment is partially observable, it could appear to be nondeterministic\n```\n\n## AIMA 2.4 The Structure of Agents\n```Structure of agents \nSimple relex agent: select actions on basis of current percept, ignoring history \nModel based reflex agent: use transition model & sensor to keep track of state of world \nGoal-based agent: combine goal information w model to choose actions to achieve the goal\nUtility-based agent: utility function (internalization of performance measure)\nMaximize its utility \nLearning agents: allows agent to operate in initially unknown environments\n```\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - 认知对象, the content an agent’s sensors are perceiving\n* **Percept sequence** - complete history of everything the agent has ever perceived\n* **Agent function** - specifies the action taken by the agent in response to any percept sequence\n* **Performance measure** - evaluates behavior of agent in env\n* **Rational agent** - acts to max the expected val of performance measure with the info of percept sequence seen\n* **Task environment** - includes performance measure, actuators, external enviroment, actuators, and sensors. \n* **Agent program** - implements agent function, varies in efficiency, compactness, and flexibility. Depends on nature of the environment\n* **Simple reflex agents** - respond directly to percepts\n* **Model-based reflex agents** - maintain internal state to track aspects of world not evident in curr percept\n* **Goal based agents** - act to achieve goals\n* **Utility based agents** - max their own expected happiness\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n ```\nDynamic typing\n- Variables come into existence when first assigned \ntype(var) automatically determined\nIf assigned again, type(var) is updated\nFunctions have no type signatures\nDrawback: type errors are only caught at runtime\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 ```\nSearch: the process of looking for a sequence of actions that reaches the goal\nTo fully define a search problem, we need\nState space\n- Initial state\n- Goal states\n- Actions\n- Transition model\n- Action cost function\nBFS: use with infinite paths\nDFS: memory efficient\n\n``` \n\n## AIMA Chapter 3.2 Example Problems\n The state space  is the set of possible states of the environment \n\n## AIMA Chapter 3.3 Search Algorithms\n ```\nGraph search is faster than tree search\nWe call a search algorithm a graph search if it checks for redundant paths. Because it does not waste time examining those redundant paths, it runs more quickly\nUniform cost search: complete & cost-optimal\nGuaranteed to find an optimal solution \nDijkstra is a similar search without a goal\nA special case of A* where f(n) is all 0\nDfs does NOT has much lower space complexity than iterative deepening \n``` \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n In a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions \n\n## Module 3 Lecture Notes\n ```\nUse depth-first if\n- Space is restricted\n- Many possible solutions w long paths\n- Wrong paths are usually terminated quickly\n= Search can be fine-tuned quickly\nUse breadth-first if\n- Possible infinite paths\n- Some solutions have short paths\nIterative deepening search\n- Complete: YES \n- Time complexity: O(bd)\n- Space complexity: O(bd)\n- Optimal: YES if step cost is 1\n\nd: depth/ num of actions in an optimal solution\nm: max depth / number of actions in any path\nb: branching factor or num of successors of a node that need to be considered\nd: number you put in\nl: depth limit\n\n- An agent can use to select action sequences ina wide variety of environments when they’re episodic, single-agent, fully observable, deterministic, static, discrete, and completely known \n- Must formulate a problem for an agent to start searching\n5 parts of problem: \n1.initial state\n2.set of actions\n3. transition model: describe result of those actions \n4. goal states\n5. action cost function \n\nIterative deepening search: calls dfs w increasing depth limits until a goal is found. Complete ( when full cycle checking is odne), optimal for unit action cost, O(bd) space, O(b^d) time\n``` \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space graph** -  represents the enviroment of the problem\n* **Solution** -  a path through the state space from initial state\n* **Atomic** -  原子的, no internal structure/ search algorithms treat states & actions as atomic\n* **Uninformed search** -  only have access to problem definition. Algorithm build a search tree to find a solution\n* **Best-first search** -  select nodes for expansion using an evaluation function\n* **Breadth-first search** -  expands shallowest 最浅的 nodes first. Complete, optimal unit action cost, b^d space & time complexity\n* **Uniform-cost search** -  expands the node with lowest path cost g(n). Optimal for general action cost\n* **Depth-first search** -  expands deepest unexpanded node first. Not complete, not optimal, linear O(bm) space, O(b^m)time\n* **Depth-limited search** -  adds a depth bound, Not complete, not optimal, linear O(bl) space, O(b^l)time\n* **Bidirectional a* search** -  expands 2 frontiers, one around initial state & one around the goal, stopping when 2 frontiers meet\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n ```\nInformed search: uses domain specific hints about the location of goals\n\nGreedy best first search:\n\n- expands first the node with the lowest h(n) value. Eval function f(n) = h(n). \n- Complete in finite state space, not in infinite\n- Worst case time & space complexity: O(|V|)\n- Good heuristic function: reaching O(bm)\n\nA* search\n- expands node with minimal f(n) = g(n) + h(n) = estimated total cost of path from n to goal\n- g(n): actual cost from start to node\n- h(n): estimated cost to get from node to goal\n- Worst case time & space complexity: O(|V|) = O(b^d)\n- Prunes away some search tree nodes, but worst space stays the same\n- Complete, cost-optimal (if h(h) is admissible), optimally efficient \n- Expands many nodes- exponential in length\n\nSatisficing solutions: allow A* search to use a inadmissible heuristi (may overestimate) but reduce num of nodes expanded \nWeighted A* search: weight heuristic value more heavily: f(n) = g(n) +Wxh(n)\nBounded suboptimal search: look for solution that’s guaranteed to be within a constant factor W of the optimal cost\nBounded-cost search: look for solution whose cost < constant C\nUnbounded-cost search: accept a solution of any cost, as long as we can find it quickly \n\nMemory bounded search\nBeam search: limits the size of frontier \nIterative-deepening A* search: don’t keep all reached states in memory \nRecursive best-first search: linear space\nBidirectional heuristic search: no guarantee that lead to optimal cost or efficient\nFront to end: distance to goal & distance to start\nFront-to-front: estimate distance to other frontier\n\nAn admissible heuristic is one that never overstimates the cost to reach a goal\n\n``` \n\n## AIMA Chapter 3.6 Heuristic Functions\n ```\nEffective branching factor b*: a uniform tree of depth d would have to have in order to contain N+1 nodes\n- N+1 = 1 + b* + (b*)^2 + .. + (b*)^d\nPerformance of heuristic search algorithms depends on quality of heuristic function\nHow to construct good heuristic\n- Relax problem definition\n- Store precompute dissolution costs for subproblems in pattern database\n- Define landmarks\n- Learn from experience w problem class\nIn estimating the travel distance between two locations, Euclidean distance is a consistent and admissible heuristic.\n```\n\n## Module 4 Lecture Notes\n ```\nPerformance of heuristic search depends on quality of heuristic function\nCan sometimes construct good heuristic by relaxing problem def, store precomputed solution costs for subproblems in pattern database, define landmarks, or learn from experience w problem class\nConsistency: a heuristic h(n) is consistent if for every node n & every successor n’ of n generated by an action a, we have: \n- h(n) <= c(n,a,n’) + h(n’)\n- Every consistent heuristic is admissible (not vice versa)\n\nRecursive best-first search: RBFS. optimal search algo that use limited amounts of memory; can solve problems that A* runs out of memory if there’s enough time\n``` \n\n## Module 4 Definitions\n* **Informed search** -  have access to a heuristic function h(n) & may have additional info like pattern databases w solution costs\n* **Heuristic function** -  a function  h(n) that estimates cost of n to a solution.\n* **Greedy best-first search** -  expands nodes w minimal h(n). Not optimal but efficient\n* **A* search** -  expands nodes w minimal f(n) = g(n) + h(n). g(n)\n* **Admissible** -  a heuristic is admissible if it never overestimates the cost to reach the goal\n* **Bidirectional a* search** -  sometimes more efficient than A*\n* **Iterative deepening a*** -  Iterative Deepening version of A*, helps w space\n* **Simplified memory-bounded a*** -  same w RBFS\n* **Beam search** -  puts limit on size of frontier; incomplete & suboptimal; reasonably good solutions & runs faster \n* **Weighted a*** -  focus search towards a goal, expending fewer nodes, not optimal\n* **Triangle equality** -  side of triangle cannot be longer than the sum of other 2 sides\n* **Monotonic** -  path cost always increase as you go along a path since action costs are always positive\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n ```\nMinimax search: solves perfect information, zero-sum games\n- Evaluates nodes in same order as dfs\n- The value at that node is the value of the best terminal state reach by both player playing optimally. That means that the current player tries to maximize the score and the other player tries to minimize it\n- Time: O(b^m) \n  - b: # of legal moves at each node\n  - m: max depth of tree\nPerfect information = fully observable\nZero sum = what is good for one player is just as bad for the other, no win-win\nMove = action\nPosition = state\nPruning: makes the search more efficient by ignoring parts that’s not in optimal move\nDefine a game with: initial state, actions, result/transition model,terminal test, utility function\n \nGames have multiple agents while search problems do not\nUtility function gives the payoff for each player in terminal state s\n``` \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n ```\nMinimax value: utility of being in that state assuming both players play optimally from there to the end of the game\nMinimax search algorithm solves perfect information, zero-sum games\nIn minimax search, the value of a node is the optimal value of its children \n- For the MAX player, that's the highest value. For MIN, that's the lowest value. This is because minimax assumes both players play optimally.\nThe minimax decision maximizes the utility under the assumption that the opponent plays perfectly\nAlpha-beta search computes the same optimal moves as minimax.\n``` \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n ```\nHeuristic evaluation function returns an estimate of expected utility of state s to player p\nThe effectiveness of Alpha-Beta pruning DEPEND on the order in which successor nodes are examined.\n``` \n\n## AIMA Chapter 5.5 Stochastic Games\n ```\nChance nodes: denote possible dice roles w possibility\nStochastic game: unpredictability, include random elements\nFor stochastic? Games, chance nodes denoting the probabilities associated with each action as well as expecti-minimax values are included in the minimax tree.\n```\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Maximum expected utility MEU: a rational agent should choos ethe action that maximizes agent’s expected utility  \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n```Monte carlo tree search MCTs: evaluate states not by applying a heuristic function, but by playing out the game all the way to the end & using rules of game to see who won\nExpectiminimax: games of chance, evaluates a chance node by taking avg utility of all its children, weighted by probability of each child\n```\n\n## AIMA Chapter 16.3 Utility Functions\n Expected monetary value (EMV): sum of pr[getting the value] * value \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Alpha-beta search** -  computes same optimal move as minimax, but achieve greater efficiency by eliminating irrelevant subtrees\n* **Monte carlo tree search mcts** -  evaluate states not by applying heuristic function, but by playing out the game all the way to the end\n* **Expectiminimax** -  games of chance, evaluates a chance node by taking avg utility of all its children\n* **Imperfect information games** -  need to reason about belief states of each player& avg value\n* **Probability theory** -  what an agent should believe on basis of evidence\n* **Utility theorey** -  describes what an agent wants \n* **Rational agent** -  makes decisions by considering all possible actions & choosing the one that leads to the best expected outcome\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n ```\n`constraint propagation: using the constraints to reduce the number of legal values for a variable, \nCSPs represent a state with a set of variable/value pairs\nCSPs represent the conditions for a solution with a set of constraints on the variables\nIn search problems, states are black boxes with a transition model to move between boxes. In CSPs, the agent can see inside the states and move between states accordingly.\n```\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n```\nCSP have 2 ways of ruling out variable assignments: search & inference\nConstraint propagation: using the constraints to reduce the number of legal values for a variable, \n- Can reduce legal values for another variable\nIn CSP solvers, inference techniques use constriants to rule out variable assignment\n- Key idea behind inference: enforcing k-consistency\n\nA single var is node-consistent if all values in variable’s domain satisfy the variable’s unary constraint\nArc consistency: if every value in its domain asatisfies the variable’s binary constraints \n- Tightens down domains using arcs\nAc-3: algorithm that enforces arc consistency\n- Algorithm: Place all the arcs in a queue. Pop arcs. For each arc, remove inconsistent values. If we change the values of a node, add its arcs to the queue. Terminate when the queue is empty.\n- maintains a queue of arcs to consider\n- Initially: contain all arcs in CSP\n- Pops off arbitrary arc from queue & makes Xi arc-consistent w respect to xj. \n- If changes Di (makes domain smaller), add queue all argos (Xk,Xi) where Xk is a neighbor of Xi \n- If D revised down to nothing, CSP has no consistent solution → AC-3 return false \n- Checking consistency of an arc: O(d2) time, d being the domain size \n- O(cd3) total worst case time\nPath consistency \n- Tightens binary constraints by using implicit constraints inferred by looking at triples of variables \nK-consistency \n- If for any set of k-1 variables & for any consistent assignment to those var, a consistent val can always be assigned to any kth variable \nGlobal constraints\n- One involving an arbitrary num of variables\n```\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n```\nBack tracking search \nMRV(minimum remaining value) heuristic\n- chooses variable w fewest legal values\nDegree heuristic\n- Chooses variable w largest num of constraints \nLeast constraining value heuristic\n- chooses the value that rules out the fewest values for neighboring variables\nConstraint learning\n- records the conflicts as they are encountered in the search in order to avoid the same conflict later\nForward checking\n- Whenever a variable X is assigned, we establish arc consistency for X\nMAC: maintaining Arc Consistency\n- Detects inconsistencies that doesn’t satisfy the constraint\nChronological backtracking\n- Back up to the preceding variable & try a different value for it\n- Most recent decision point is revisited\ndifference between MAC and forward checking\n- MAC recursively propogrates constraints, whereas forward checking does not. If we assign X, forward checking makes all the arcs incident on X consistent. MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...) \nDiff btw MAC & AC-3\n- MAC is a way of interleaving search and inference. AC-3 is pure inference. MAC runs while assigning variables in backtracking search. Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3\n```\n\n## AIMA Chapter 6.4 Local Search for CSPs\n```\n```\n\n## AIMA Chapter 6.5 The Structure of Problems\n```\nSolving Arbitrary CSP takes exponential time\nTree-structured CSP: linear time\nCutset conditioning: \n- reduce a general CSP to a tree structured one\n- Can be executed in linear memory \n- Efficient if a small cutset can be found\n- No more efficient than solving a CSP directly \n- Most space efficient\nTree decomposition\n- transform the CSP into a tree of subproblems \n- are efficient if the tree width of the constraint graph is small\n- Most time efficient\n```\n\n## Module 6 Lecture Notes\n CSP:rep a state w set of var/val pairs & rep conditions for a solution by a set of constraints on variables\n \n\n## Module 6 Definitions\n* **Inference techniques** -  node, arc, k-consistency\n* **Backtracking search** -  a form of dfs. Occurs when no legal assignment can be found for a var\n* **Minimum-remaining-values and degree heuristics** -  domain-independent methods for deciding which variable to choose next in backtracking search\n* **Least-constraining-value heuristics** -  helps to divide which value to try first for a given var\n* **Conflict-directed backjumping** -  backtracks directly to source of problem\n* **Constraint learning** -  records conflicts as encountered during search to avoid same conflict later\n* **Mini-conflicts heuristic** -  local search use this \n* **Cutset conditioning** -  reduce a general CSP to a tree-structured one & efficient if a small cutset can be found\n* **Tree decomposition** -  transform CSP into a tree of subproblems & are efficient if tree width of constraint graph is small\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n ```\nIntelligent agents need knowledge about the world in order to reach good decisions\nKnowledge is contained in agents in form of sentences in a knowledge rep language, stored in knowledge base\n``` \n\n## AIMA Chapter 7.2 The Wumpus World\n ```\nRepresentation language is defined by syntax\nSyntax specifies structures of sentences & its semantics\nSemantics defines the truth of each sentences in each possible world/model\n``` \n\n## AIMA Chapter 7.3 Logic\n ```\nEntailment between sentences\nValidity of sentence\nUnsatisfiability of sentence\n``` \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n ```\nPropositional logic: simple language consisting of proposition symbols & logical connectives; can handle propositions taht are known to be true, false, or unknown\n``` \n\n## AIMA 7.5 Propositional Theorem Proving\n ```\nCNF: conjunctive normal form \n- Biconditional elimination\n- Implication elimination\n- Demorgan \n``` \n\n## Module 7 Lecture Notes\n Propositional logic: simple language consisting of proposition symbols & logical connectives; can handle propositions taht are known to be true, false, or unknown \n\n## Module 7 Definitions\n* **Inference** -  process of deriving new sentences from old ones\n* **Sound inference** -  derive only sentences that are entailed\n* **Complete algorithms** -  derive all sentences that are entailed\n* **Inference rules** -  patterns of sound inference that can be used to find proofs\n* **Resolution rule** -  yields a complete inference algorithm from knowledge base expressed in CNF\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}