{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "“FINAL Template_for CIS521_midterm notes.ipynb”",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6abdd868-b89f-4e6b-b120-5d141309062b"
      },
      "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": "b35855b2-b4c2-4966-c44e-9951d76cd240"
      },
      "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": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" There are four combinations from two dimensions: human vs. rational, thought vs. behavior, \\n\n",
        "1.Acting humanly(The Turing test): The computer would need NLP, knowledge representation, automated reasoning, ML; CV, robotics \\n\n",
        "2.Thinking humanly(The cognitive modeling approach): we learn about human thought through introspection, psychological experiments, brain imaging; interdiscipline with cognitive science. \\n\n",
        "3.Thinking rationally: logic, probability \\n\n",
        "4.Acting rationally(The rational agent approach): standard model\n",
        "Beneficial machines:pursue people's benift rather than solely apply standard model\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 = \"\"\" weak AI: machines could act as if they were intelligent \\n\n",
        "strong AI: actually consciously thinking (not just simulating thinking) \\n\n",
        "Good Old-Fashioned AI: logical agent for qualification problem \\n\n",
        "embodied cognition: cognition takes place within a body, which is embedded in an environment \\n\n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\" humans have a clear advantage over machines,\n",
        "because they can use their own subjective to appreciate the subjective experience of others\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" percept sequence is the complete history of everything the agent has ever perceived \\n\n",
        "The agent function is an Agent program abstract mathematical description; the agent program is a concrete implementation, running within some physical system \\n\n",
        "Agents interact with environments through sensors and actuators\"\"\"\n",
        "chapter2_2 = \"\"\" For each possible \"percept sequence\", a rational agent should select an \"action\" that is expected\n",
        "to maximize its \"performance measure\", given the evidence provided by the \"percept sequence\" and whatever \"prior knowledge\" the agent has \"\"\"\n",
        "chapter2_3 = \"\"\" task environment: PEAS (Performance, Environment, Actuators, Sensors) description. \\n\n",
        "the environment: fully observable vs. partially observable \\n\n",
        "single-agent vs. multiagent(competitive or cooperative) \\n\n",
        "the next state of the environment: deterministic vs. nondeterministic \\n\n",
        "the behavior: episodic vs. sequential(whether action can have long-term effect) \\n\n",
        "static, semidynamic (environment itself does not change, but the performance measurement changes) or dynamic \\n\n",
        "time: discrete or continuous \\n\n",
        "prior knowledge: known vs. unknown \\n\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" agent = architecture + program \\n\n",
        "\"Simple reflex agents\" respond directly to percepts; \"model-based reflex agents\" maintain internal state to track aspects of the world that are not evident in the current \n",
        "percept; \"Goal-based agents\" act to achieve their goals, and \"utility-based agents\" try to\n",
        "maximize their own expected “happiness. \\n\n",
        "Agents need internal state, transition model and sensor model and choose action according to the utility to achieve the goal. \\n\n",
        "Learning agents require the reward and penalty.\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",
        "\"rational agent\": \"agent that act to achieve the maximum (expected) performance measure\",\n",
        "\"percept\" : \"gathering information from an environment\",\n",
        "\"autonomy\" : \"learn to compensate for inadequate prior knowledge\",\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
        },
        "outputId": "80c14924-358b-4d95-840a-eb600c6f07f8"
      },
      "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 There are four combinations from two dimensions: human vs. rational, thought vs. behavior, \n\n1.Acting humanly(The Turing test): The computer would need NLP, knowledge representation, automated reasoning, ML; CV, robotics \n\n2.Thinking humanly(The cognitive modeling approach): we learn about human thought through introspection, psychological experiments, brain imaging; interdiscipline with cognitive science. \n\n3.Thinking rationally: logic, probability \n\n4.Acting rationally(The rational agent approach): standard model\nBeneficial machines:pursue people's benift rather than solely apply standard model\n \n\n## AIMA Chapter 27.1 The Limits of AI\n weak AI: machines could act as if they were intelligent \n\nstrong AI: actually consciously thinking (not just simulating thinking) \n\nGood Old-Fashioned AI: logical agent for qualification problem \n\nembodied cognition: cognition takes place within a body, which is embedded in an environment \n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n humans have a clear advantage over machines,\nbecause they can use their own subjective to appreciate the subjective experience of others\n\n## AIMA 2.1 Agents and Environments\n percept sequence is the complete history of everything the agent has ever perceived \n\nThe agent function is an Agent program abstract mathematical description; the agent program is a concrete implementation, running within some physical system \n\nAgents interact with environments through sensors and actuators\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n For each possible \"percept sequence\", a rational agent should select an \"action\" that is expected\nto maximize its \"performance measure\", given the evidence provided by the \"percept sequence\" and whatever \"prior knowledge\" the agent has \n\n## AIMA 2.3 The Nature of Environments\n task environment: PEAS (Performance, Environment, Actuators, Sensors) description. \n\nthe environment: fully observable vs. partially observable \n\nsingle-agent vs. multiagent(competitive or cooperative) \n\nthe next state of the environment: deterministic vs. nondeterministic \n\nthe behavior: episodic vs. sequential(whether action can have long-term effect) \n\nstatic, semidynamic (environment itself does not change, but the performance measurement changes) or dynamic \n\ntime: discrete or continuous \n\nprior knowledge: known vs. unknown \n\n\n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program \n\n\"Simple reflex agents\" respond directly to percepts; \"model-based reflex agents\" maintain internal state to track aspects of the world that are not evident in the current \npercept; \"Goal-based agents\" act to achieve their goals, and \"utility-based agents\" try to\nmaximize their own expected “happiness. \n\nAgents need internal state, transition model and sensor model and choose action according to the utility to achieve the goal. \n\nLearning agents require the reward and penalty.\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* **Rational agent** - agent that act to achieve the maximum (expected) performance measure\n* **Percept** - gathering information from an environment\n* **Autonomy** - learn to compensate for inadequate prior knowledge\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",
        "strongly and dynamically typed: Strong typing means that variables do have a type. eg. We can use x = 1 instead of\n",
        "int x = 1; Dynamic typing means that the variable type is determined only while running. \n",
        "eg. formula def add(x, y): return x+y  works for both int and float type \\n\n",
        "Objects of built-in types like (int, float, bool, str, tuple, unicode) are immutable and hashable. Mutable object cannot be the key of a dict (eg. list) \\n\\n\n",
        "list methods: li.append('a'), li.insert(pos, 'i'), li.index('b')#index of first occur, li.count('b') # number of occurrences, li.remove('b') # remove first occurrence, li.reverse(), li.sort() \\n\n",
        "string methods: s.split(\" \")# return list, \"_\".join(words), s.capitalize()#'Dog', s.upper()#'DOG', 'hi--'.strip('–')#'hi'remove'_' at beginning and end \\n\n",
        "list methods: d.keys() # List of current keys, d.values() # List of current values, d.items() # List of item tuples \\n\n",
        "iterator: i = iter(k) next(i), \\n\n",
        "generator: yield keyword automatically return a generator when called\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"If an object is mutable, its state can be changed after declared.\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 385
        },
        "outputId": "cd30b0e5-2f12-43f5-e6cd-274a777449aa"
      },
      "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 \nstrongly and dynamically typed: Strong typing means that variables do have a type. eg. We can use x = 1 instead of\nint x = 1; Dynamic typing means that the variable type is determined only while running. \neg. formula def add(x, y): return x+y  works for both int and float type \n\nObjects of built-in types like (int, float, bool, str, tuple, unicode) are immutable and hashable. Mutable object cannot be the key of a dict (eg. list) \n\n\nlist methods: li.append('a'), li.insert(pos, 'i'), li.index('b')#index of first occur, li.count('b') # number of occurrences, li.remove('b') # remove first occurrence, li.reverse(), li.sort() \n\nstring methods: s.split(\" \")# return list, \"_\".join(words), s.capitalize()#'Dog', s.upper()#'DOG', 'hi--'.strip('–')#'hi'remove'_' at beginning and end \n\nlist methods: d.keys() # List of current keys, d.values() # List of current values, d.items() # List of item tuples \n\niterator: i = iter(k) next(i), \n\ngenerator: yield keyword automatically return a generator when called\n\n\n## Module 2 Definitions\n* **Mutability** - If an object is mutable, its state can be changed after declared.\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 = \"\"\"search problem: state space, initial state, goal states, actions available to the agent, transition model, action cost function \\n\"\"\"\n",
        "chapter3_2 = \"\"\" The state space can be infinite. State space must be abstracted for problem solving\"\"\"\n",
        "chapter3_3 = \"\"\" the search tree describes paths between states, reaching towards the goal.  \\n\n",
        "```\n",
        "def Best_First_Search():\n",
        "    frontier = PriorityQueue()\n",
        "    frontier.add(initial_state)\n",
        "    reached = []\n",
        "    while frontier:\n",
        "        cur = frontier.pop()\n",
        "        if isGoal(cur): \n",
        "            return True \n",
        "        for s in cur.successors: \n",
        "            if s.state is not in reached or s.cost < reached[s.state]: ### cost = history_path + action cost\n",
        "              reached[s.state] = s \n",
        "              frontier.add(s) \n",
        "    return False \n",
        "```\n",
        "best-first search: priority queue \\n\n",
        "breadth-first search: FIFO queue \\n\n",
        "depth-first search: LIFO queue (stack) \\n\n",
        "graph search: check for redundant path vs. tree seach: not check for redundant path.\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" Use depth-first if： Space is restricted \\n\n",
        "Use breadth-first if: Possible infinite paths, Some solutions have short paths \\n\n",
        "uniform-cost search (UCS) is a tree search\n",
        "algorithm used for searching a weighted tree or graph \\n\n",
        "Dijkstra’s algorithm or uniform-cost search: implemented as a call to BEST-FIRST-SEARCH with PATH-COST as the evaluation function，\n",
        "Dijkstra’s algorithm is a Uniform-cost Search without a goal \\n\n",
        "Tests if a node is a goal state when it is selected for expansion, not when it is added to the frontier \\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"  \"\"\"\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",
        "\"path\" :  \"A sequence of actions\",\n",
        "\"solution\" : \"a path from the initial state to a goal path state\",\n",
        "\"optimal solution\" : \"the solution that has lowest path cost\",\n",
        "\"frontier\" : \"unexpanded nodes\",\n",
        "\"Completeness\": \"Is the algorithm guaranteed to find a solution and to report failure when there is no solution\",\n",
        "\"optimality/admissibility\" : \"whether the algorithm can find the solution with lowest cost\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 993
        },
        "outputId": "519b23d2-4911-4865-f0e9-5ee71b8ffada"
      },
      "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\nsearch problem: state space, initial state, goal states, actions available to the agent, transition model, action cost function \n\n\n## AIMA Chapter 3.2 Example Problems\n The state space can be infinite. State space must be abstracted for problem solving\n\n## AIMA Chapter 3.3 Search Algorithms\n the search tree describes paths between states, reaching towards the goal.  \n\n```\ndef Best_First_Search():\n    frontier = PriorityQueue()\n    frontier.add(initial_state)\n    reached = []\n    while frontier:\n        cur = frontier.pop()\n        if isGoal(cur): \n            return True \n        for s in cur.successors: \n            if s.state is not in reached or s.cost < reached[s.state]: ### cost = history_path + action cost\n              reached[s.state] = s \n              frontier.add(s) \n    return False \n```\nbest-first search: priority queue \n\nbreadth-first search: FIFO queue \n\ndepth-first search: LIFO queue (stack) \n\ngraph search: check for redundant path vs. tree seach: not check for redundant path.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Use depth-first if： Space is restricted \n\nUse breadth-first if: Possible infinite paths, Some solutions have short paths \n\nuniform-cost search (UCS) is a tree search\nalgorithm used for searching a weighted tree or graph \n\nDijkstra’s algorithm or uniform-cost search: implemented as a call to BEST-FIRST-SEARCH with PATH-COST as the evaluation function，\nDijkstra’s algorithm is a Uniform-cost Search without a goal \n\nTests if a node is a goal state when it is selected for expansion, not when it is added to the frontier \n\n\n\n## Module 3 Lecture Notes\n  \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** - A sequence of actions\n* **Solution** - a path from the initial state to a goal path state\n* **Optimal solution** - the solution that has lowest path cost\n* **Frontier** - unexpanded nodes\n* **Completeness** - Is the algorithm guaranteed to find a solution and to report failure when there is no solution\n* **Optimality/admissibility** - whether the algorithm can find the solution with lowest cost\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 = \"\"\" Uninformed search can only access problem definition. \\n \n",
        "h(n) = estimated cost of the cheapest path from the state at node n to a goal state \\n\n",
        "Greedy best-first search expand nodes with the lowest h(n) value, evaluation function f(n)=h(n), exactly UCS with f(n) replacing g(n) \\n\n",
        "is not complete.\n",
        "A* search: f (n) = g(n)+h(n) \\n\n",
        "g(n) = the path cost from the initial state to node n \\n\n",
        "h(n) = the estimated cost of the shortest path from n to a goal state \\n\n",
        "is complete and cost-optimal if the heuristic is admissible( $h(n) \\le h^*(n) $ \\n where $h^*(n)$ is the real cost to the goal state), also called optimistic \\n\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem \\n\n",
        "dominates: If h2(n) ≥ h1(n) for all n (both admissible), So h2 is optimistic, but more accurate than h1 \\n\n",
        "The proof of optimal: \\n\n",
        "Assume all action costs are $\\\\ge \\\\epsilon > 0$\n",
        "Suppose the optimal path has cost $C^*$, but A* returns $C>C^*$ \\n\n",
        "There must be some node $n$ which is on the real optimal path and is unexpanded. \\n\n",
        "$f(n) > C > C^*$ (otherwise $n$ would have been expanded) \\n\n",
        "$f(n) = g(n) + h(n) \\le g(n) + h^*(n)$ (admissibility) \\n\n",
        "$f(n) \\le C^*$ \\n (contradiction) \\n\n",
        "\n",
        "Weighted A* enforce the algorithm to be greedy \\n\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" eg heuristic fuctions: \\n\n",
        "8-puzzle: the number of misplaced tiles; Manhattan distance \\n\n",
        "\n",
        "effective branching factor b*: N +1 = $1+b∗+(b∗)^2+...+(b∗)^d$ \\n\n",
        "(with fixed d of optimal solution, a better h(n) lead to less N, A well-designed heuristic would have a value of b∗ close to 1)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Another proof: \\n\n",
        "Claim that $n$ which is an ancestor of optimal $A$ will be expanded before sub-optimal $B$ \\n\n",
        "$f(n) \\le f(A)$ (admissibility) \\n\n",
        "$f(A) \\le f(B)$ (B is sub-optimal) \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"relaxed problem\" : \"A problem with fewer restrictions on the actions than the original\",  \n",
        "\"consistency\" :  \"$h(n) \\le c(n, a, n') + h(n')$(stronger property)\",  \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 895
        },
        "cellView": "form",
        "outputId": "8771aa21-4334-4dd2-d331-e3b1006d3305"
      },
      "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 Uninformed search can only access problem definition. \n \nh(n) = estimated cost of the cheapest path from the state at node n to a goal state \n\nGreedy best-first search expand nodes with the lowest h(n) value, evaluation function f(n)=h(n), exactly UCS with f(n) replacing g(n) \n\nis not complete.\nA* search: f (n) = g(n)+h(n) \n\ng(n) = the path cost from the initial state to node n \n\nh(n) = the estimated cost of the shortest path from n to a goal state \n\nis complete and cost-optimal if the heuristic is admissible( $h(n) \\le h^*(n) $ \n where $h^*(n)$ is the real cost to the goal state), also called optimistic \n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem \n\ndominates: If h2(n) ≥ h1(n) for all n (both admissible), So h2 is optimistic, but more accurate than h1 \n\nThe proof of optimal: \n\nAssume all action costs are $\\ge \\epsilon > 0$\nSuppose the optimal path has cost $C^*$, but A* returns $C>C^*$ \n\nThere must be some node $n$ which is on the real optimal path and is unexpanded. \n\n$f(n) > C > C^*$ (otherwise $n$ would have been expanded) \n\n$f(n) = g(n) + h(n) \\le g(n) + h^*(n)$ (admissibility) \n\n$f(n) \\le C^*$ \n (contradiction) \n\n\nWeighted A* enforce the algorithm to be greedy \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n eg heuristic fuctions: \n\n8-puzzle: the number of misplaced tiles; Manhattan distance \n\n\neffective branching factor b*: N +1 = $1+b∗+(b∗)^2+...+(b∗)^d$ \n\n(with fixed d of optimal solution, a better h(n) lead to less N, A well-designed heuristic would have a value of b∗ close to 1)\n\n\n## Module 4 Lecture Notes\n Another proof: \n\nClaim that $n$ which is an ancestor of optimal $A$ will be expanded before sub-optimal $B$ \n\n$f(n) \\le f(A)$ (admissibility) \n\n$f(A) \\le f(B)$ (B is sub-optimal) \n\n\n\n## Module 4 Definitions\n* **Relaxed problem** - A problem with fewer restrictions on the actions than the original\n* **Consistency** - $h(n) \\le c(n, a, n') + h(n')$(stronger property)\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 = \"\"\" deterministic, two-player, turn-taking, perfect information(fully observable), zero-sum games \\n\n",
        "initial state, transition mode, terminal states, utility function \\n\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" alpha–beta pruning \\n\n",
        "Alpha: MAX's current lower bound on MAX's outcome \\n\n",
        "Beta: MIN's current upper bound on MIN's outcome \\n\n",
        "MAX will never allow a move that could lead to a worse score (for MAX) than $\\\\alpha$ \\n\n",
        "MIN will never allow a move that could lead to a better score (for MAX) than $\\\\beta$ \\n\n",
        "Therefore, stop evaluating a branch whenever: \\n\n",
        "When evaluating a MAX node: a value $v \\\\ge \\\\beta$ is backed-up (MIN will never select that MAX node) \\n\n",
        "When evaluating a MIN node: a value $v \\\\le \\\\alpha$ (Max will never select that MIN node) \\n\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" Heuristic Alpha–Beta Tree Search: we replace the UTILITY function with EVAL, which estimates a\n",
        "state’s utility; replace the terminal test by a cutoff test, which Cutoff test must return true for\n",
        "terminal states, also free to decide when to cut off the search, based on the search depth and any property \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic games (such as the throwing of dice) \\n\n",
        "Expectimax search: compute the average score under optimal play \\n\n",
        "A game tree in backgammon must include chance nodes in addition to MAX and MIN nodes. \\n\n",
        "for chance node: calculate expectation of Expect-min-max() \\n\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" $P(s'|a) = \\\\sum_{s} P(s)P(s'|s,a)$ \\n\n",
        "Expected utility of action $a$: $ EU(a) = \\\\sum_{s'}P(s'|a)U(s') $ \\n\n",
        "action = $\\\\argmax_a EU(a)$ \\n\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" omit \"\"\"\n",
        "chapter16_3 = \"\"\" omit \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" game trees: Nodes represent ‘board positions’; edges represent legal moves. \\n\n",
        "Root node is the first position in which a decision must be made \\n  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {   \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": "654486fa-9faa-4310-d94d-8691b587d1dd"
      },
      "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 deterministic, two-player, turn-taking, perfect information(fully observable), zero-sum games \n\ninitial state, transition mode, terminal states, utility function \n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n alpha–beta pruning \n\nAlpha: MAX's current lower bound on MAX's outcome \n\nBeta: MIN's current upper bound on MIN's outcome \n\nMAX will never allow a move that could lead to a worse score (for MAX) than $\\alpha$ \n\nMIN will never allow a move that could lead to a better score (for MAX) than $\\beta$ \n\nTherefore, stop evaluating a branch whenever: \n\nWhen evaluating a MAX node: a value $v \\ge \\beta$ is backed-up (MIN will never select that MAX node) \n\nWhen evaluating a MIN node: a value $v \\le \\alpha$ (Max will never select that MIN node) \n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic Alpha–Beta Tree Search: we replace the UTILITY function with EVAL, which estimates a\nstate’s utility; replace the terminal test by a cutoff test, which Cutoff test must return true for\nterminal states, also free to decide when to cut off the search, based on the search depth and any property \n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games (such as the throwing of dice) \n\nExpectimax search: compute the average score under optimal play \n\nA game tree in backgammon must include chance nodes in addition to MAX and MIN nodes. \n\nfor chance node: calculate expectation of Expect-min-max() \n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n $P(s'|a) = \\sum_{s} P(s)P(s'|s,a)$ \n\nExpected utility of action $a$: $ EU(a) = \\sum_{s'}P(s'|a)U(s') $ \n\naction = $\\argmax_a EU(a)$ \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n omit \n\n## AIMA Chapter 16.3 Utility Functions\n omit \n\n## Module 5 Lecture Notes\n game trees: Nodes represent ‘board positions’; edges represent legal moves. \n\nRoot node is the first position in which a decision must be made \n  \n\n## Module 5 Definitions\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 = \"\"\" CSP consists of $X$, $D$ and $C$. $X$ is set of variables, $D$ is set of domains for variables, $C$ is set of constraints. \\n\n",
        "The simplest kind of CSP involves variables that have discrete, finite domains \\n\n",
        "\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" node consistent: all the values in the variable’s domain satisfy the variable’s unary constraints \\n\n",
        "arc-consistent: if every value in its domain satisfies the variable’s binary constraints \\n\n",
        "path consistency: tightens the binary constraints by using Path consistency implicit constraints that are inferred by looking at triples of variables \\n\n",
        "K-consistency: A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any the kth variable \\n\n",
        "strongly k-consistent: it is k-consistent and is also (k−1)-consistent, (k−2)-k-consistent ... 1-consistenct \\n\n",
        "AC-3 can be used to enforce arc consistency. \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" Backtracking Search for CSPs: is a form of depth first search \\n\n",
        "forward checking: Whenever a variable X is assigned, the forward-checking process establishes arc consistency, for each unassigned\n",
        "variable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for X \\n\n",
        "MAC recursively propogrates constraints, whereas forward checking does not: If we assign X, forward checking makes all the arcs incident on X consistent. \n",
        "MAC does this, and if the domain of a variable Y changes, does the same for Y \\n\n",
        "MAC runs while assigning variables in backtracking search. \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "min-conflicts heuristic: Randomly choose the min-conflicted variable and modift its value to satisfy the constraints \\n\n",
        "constraint weighting: concentrate Constraint weighting the search on the important constraints \\n \"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "Cutset conditioning: to reduce a general CSP to a tree structured one (which can be linear time complexity). \\n\n",
        "Tree decomposition: transform the CSP into a tree of subproblems. (efficient if the tree width of the constraint graph is small)\\n\n",
        "Cutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width \\n\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "Idea 1: CSP as a search problem\n",
        "Improving backtracking efficiency:\n",
        "Heuristic 1: Most constrained variable: Choose a variable with the fewest legal values \\n\n",
        "Heuristic 2: Most constraining variable: with most remaining neighbors \\n\n",
        "Heuristic 3: Least constraining value: choose value that rules out the fewest values in the remaining variables \\n\n",
        "Heuristic 4: Forward checking (Arc consistency & AC-3) \\n \n",
        "CSP differ from search problems: In search problems, states are black boxes with transition model to move between. In CSPs, the agent can see inside states and move accordingly. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"MAC\": \"Maintaining Arc Consistency\",   \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "67612bda-813b-42a4-826a-40edeafd778c"
      },
      "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 CSP consists of $X$, $D$ and $C$. $X$ is set of variables, $D$ is set of domains for variables, $C$ is set of constraints. \n\nThe simplest kind of CSP involves variables that have discrete, finite domains \n\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n node consistent: all the values in the variable’s domain satisfy the variable’s unary constraints \n\narc-consistent: if every value in its domain satisfies the variable’s binary constraints \n\npath consistency: tightens the binary constraints by using Path consistency implicit constraints that are inferred by looking at triples of variables \n\nK-consistency: A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any the kth variable \n\nstrongly k-consistent: it is k-consistent and is also (k−1)-consistent, (k−2)-k-consistent ... 1-consistenct \n\nAC-3 can be used to enforce arc consistency. \n\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking Search for CSPs: is a form of depth first search \n\nforward checking: Whenever a variable X is assigned, the forward-checking process establishes arc consistency, for each unassigned\nvariable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for X \n\nMAC recursively propogrates constraints, whereas forward checking does not: If we assign X, forward checking makes all the arcs incident on X consistent. \nMAC does this, and if the domain of a variable Y changes, does the same for Y \n\nMAC runs while assigning variables in backtracking search. \n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nmin-conflicts heuristic: Randomly choose the min-conflicted variable and modift its value to satisfy the constraints \n\nconstraint weighting: concentrate Constraint weighting the search on the important constraints \n \n\n## AIMA Chapter 6.5 The Structure of Problems\n\nCutset conditioning: to reduce a general CSP to a tree structured one (which can be linear time complexity). \n\nTree decomposition: transform the CSP into a tree of subproblems. (efficient if the tree width of the constraint graph is small)\n\nCutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width \n\n \n\n## Module 6 Lecture Notes\n \nIdea 1: CSP as a search problem\nImproving backtracking efficiency:\nHeuristic 1: Most constrained variable: Choose a variable with the fewest legal values \n\nHeuristic 2: Most constraining variable: with most remaining neighbors \n\nHeuristic 3: Least constraining value: choose value that rules out the fewest values in the remaining variables \n\nHeuristic 4: Forward checking (Arc consistency & AC-3) \n \nCSP differ from search problems: In search problems, states are black boxes with transition model to move between. In CSPs, the agent can see inside states and move accordingly. \n\n\n\n## Module 6 Definitions\n* **Mac** - Maintaining Arc Consistency\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 = \"\"\" A Knowledge base is a set of sentences \\n\n",
        "The agent maintains a knowledge base, KB, which may initially contain some background knowledge \\n\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" PEAS description: Performance measurement, Environment, Actuator, Sensor \\n \"\"\"\n",
        "chapter7_3 = \"\"\" Entailment: $\\\\alpha \\\\models \\\\beta$ if in every model where $\\\\alpha$ is true, $\\\\beta$ is also true \n",
        "$\\\\alpha \\\\models \\\\beta$ if and only if ($M(\\\\alpha) \\\\subset M(\\\\beta)$)\\n\n",
        "If an algorithm $i$ can derive $\\\\alpha$ from $KB$, we write $KB \\\\vdash_i \\\\alpha$\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "not : $\\\\neg$ (negation) \\n\n",
        "and : $\\\\wedge$  $P \\\\wedge Q$ is called a conjunction. \\n\n",
        "or ： $\\\\vee$ $P \\\\vee Q$ is called a disjunction. \\n\n",
        "imply : $\\\\Rightarrow$ \\n\n",
        "if and only if: $\\\\Leftrightarrow$ \\n\n",
        "$\\\\neg P$ is true iff P is false in m.\n",
        "$P \\\\wedge Q$ is true iff both P and Q are true in m.\n",
        "$P \\\\vee Q$ is true iff either P or Q is true in m.\n",
        "$P \\\\Rightarrow Q$ is true unless P is true and Q is false in m.\n",
        "$P \\\\Leftrightarrow Q$ is true iff P and Q are both true or both false in m.\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "logical equivalence: $\\\\alpha \\\\equiv \\\\beta$ iff $\\\\alpha \\\\models \\\\beta$ and $\\\\beta \\\\models \\\\alpha$ \\n\n",
        "Inference and proofs: \\n\n",
        "logical systems is monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base \\n\n",
        "if $KB \\\\models \\\\alpha$ then $KB \\\\wedge \\\\beta \\\\models \\\\alpha$ \\n \n",
        "Proof by resolution: yields a complete inference algorithm when coupled with any complete search algorithm \\n\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "CNF (Conjunctive Normal Form): Every sentence of propositional logic is logically equivalent to a conjunction of clauses which are disjunctions of literals.\n",
        "1. Eliminate $\\\\Leftrightarrow$ by $(\\\\alpha \\\\Leftrightarrow \\\\beta) \\\\equiv ((\\\\alpha \\\\Rightarrow \\\\beta) \\\\wedge (\\\\beta \\\\Leftrightarrow \\\\alpha))$ \\n\n",
        "2. Eliminate $\\\\Rightarrow$ by $(\\\\alpha \\\\Rightarrow \\\\beta) \\\\equiv (\\\\neg \\\\alpha \\\\vee \\\\beta)$ \\n\n",
        "3. Move $\\\\neg$ inwards (only before literals) by De Morgan and double-negation. \\n\n",
        "4. Distribute $\\\\vee$ over $\\wedge$ wherever possible. \n",
        "Resolution Algorithm: \\n\n",
        "Inference procedures based on resolution work using the principle of proof by contradiction \\n\n",
        "To show $KB \\\\models \\\\alpha$, we can show that $KB \\\\wedge \\\\neg\\\\alpha$ is unsatisfiable. \\n\n",
        "1. Convert $KB \\\\wedge \\\\neg\\\\alpha$ into CNF. \\n\n",
        "2. apply the resolution rule to the resulting clauses\n",
        "3. Resolve every pair that contains complementary literals to produce a new clause, add unalready presented clause to the set. \\n\n",
        "4. Repeat resolution for each pairs of disjunctions until one of two things happens: \\n\n",
        "a) There are no new clauses that can be added. In this case, the KB does not entail $\\\\alpha$ \\n\n",
        "b) Two clauses resolve to yield the empty clause (comes from contradiction), in which case the KB does entail $\\\\alpha$\n",
        "Resolution is sound and complete. \\n\n",
        "\\n\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Soundness\" : \"the inference algorithm should only derive entailed sentences\", \n",
        "\"Completeness\" : \"An inference algorithm is complete if it can derive all sentences that are entailed.\",   \n",
        "\"Validity\" : \"A sentence is valid if it is true in all models.\",\n",
        "\"Satisfiability\" : \"A sentence is satisfiable if it is true in, or satisfied by some models.\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7232bd86-a83a-490c-a675-92be815907b6"
      },
      "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 A Knowledge base is a set of sentences \n\nThe agent maintains a knowledge base, KB, which may initially contain some background knowledge \n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n PEAS description: Performance measurement, Environment, Actuator, Sensor \n \n\n## AIMA Chapter 7.3 Logic\n Entailment: $\\alpha \\models \\beta$ if in every model where $\\alpha$ is true, $\\beta$ is also true \n$\\alpha \\models \\beta$ if and only if ($M(\\alpha) \\subset M(\\beta)$)\n\nIf an algorithm $i$ can derive $\\alpha$ from $KB$, we write $KB \\vdash_i \\alpha$\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nnot : $\\neg$ (negation) \n\nand : $\\wedge$  $P \\wedge Q$ is called a conjunction. \n\nor ： $\\vee$ $P \\vee Q$ is called a disjunction. \n\nimply : $\\Rightarrow$ \n\nif and only if: $\\Leftrightarrow$ \n\n$\\neg P$ is true iff P is false in m.\n$P \\wedge Q$ is true iff both P and Q are true in m.\n$P \\vee Q$ is true iff either P or Q is true in m.\n$P \\Rightarrow Q$ is true unless P is true and Q is false in m.\n$P \\Leftrightarrow Q$ is true iff P and Q are both true or both false in m.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \nlogical equivalence: $\\alpha \\equiv \\beta$ iff $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$ \n\nInference and proofs: \n\nlogical systems is monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base \n\nif $KB \\models \\alpha$ then $KB \\wedge \\beta \\models \\alpha$ \n \nProof by resolution: yields a complete inference algorithm when coupled with any complete search algorithm \n\n \n\n## Module 7 Lecture Notes\n \nCNF (Conjunctive Normal Form): Every sentence of propositional logic is logically equivalent to a conjunction of clauses which are disjunctions of literals.\n1. Eliminate $\\Leftrightarrow$ by $(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n2. Eliminate $\\Rightarrow$ by $(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n3. Move $\\neg$ inwards (only before literals) by De Morgan and double-negation. \n\n4. Distribute $\\vee$ over $\\wedge$ wherever possible. \nResolution Algorithm: \n\nInference procedures based on resolution work using the principle of proof by contradiction \n\nTo show $KB \\models \\alpha$, we can show that $KB \\wedge \\neg\\alpha$ is unsatisfiable. \n\n1. Convert $KB \\wedge \\neg\\alpha$ into CNF. \n\n2. apply the resolution rule to the resulting clauses\n3. Resolve every pair that contains complementary literals to produce a new clause, add unalready presented clause to the set. \n\n4. Repeat resolution for each pairs of disjunctions until one of two things happens: \n\na) There are no new clauses that can be added. In this case, the KB does not entail $\\alpha$ \n\nb) Two clauses resolve to yield the empty clause (comes from contradiction), in which case the KB does entail $\\alpha$\nResolution is sound and complete. \n\n\n\n\n## Module 7 Definitions\n* **Soundness** - the inference algorithm should only derive entailed sentences\n* **Completeness** - An inference algorithm is complete if it can derive all sentences that are entailed.\n* **Validity** - A sentence is valid if it is true in all models.\n* **Satisfiability** - A sentence is satisfiable if it is true in, or satisfied by some models.\n* **Oy** - .\n* **Fogr** - .\n* **Oe** - .\n* **Ogrr** - .\n* **Obtd** - .\n* **Ofse** - .\n* **Oew5** - .\n* **Ohdd** - .\n* **Ogrs** - .\n* **Ogrw** - .\n* **Oegg** - .\n* **Ose4** - .\n* **Oetf** - .\n* **Osew** - .\n* **Ohtd** - .\n* **Obre** - .\n* **Osht** - .\n* **Vhro** - .\n* **Osdb** - .\n* **Odju** - .\n* **Otrf** - .\n* **Otjh** - .\n* **Ofre** - .\n* **Odtu** - .\n* **Omug5** - .\n* **O4esf** - .\n* **Ory5e** - .\n* **Oesgy** - .\n* **Os4t** - .\n* **Ords** - .\n* **Orty** - .\n* **Ods4w** - .\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": "9c48646b-6736-4482-ff7a-25ad851a2f08"
      },
      "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 There are four combinations from two dimensions: human vs. rational, thought vs. behavior, \n\n1.Acting humanly(The Turing test): The computer would need NLP, knowledge representation, automated reasoning, ML; CV, robotics \n\n2.Thinking humanly(The cognitive modeling approach): we learn about human thought through introspection, psychological experiments, brain imaging; interdiscipline with cognitive science. \n\n3.Thinking rationally: logic, probability \n\n4.Acting rationally(The rational agent approach): standard model\nBeneficial machines:pursue people's benift rather than solely apply standard model\n \n\n## AIMA Chapter 27.1 The Limits of AI\n weak AI: machines could act as if they were intelligent \n\nstrong AI: actually consciously thinking (not just simulating thinking) \n\nGood Old-Fashioned AI: logical agent for qualification problem \n\nembodied cognition: cognition takes place within a body, which is embedded in an environment \n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n humans have a clear advantage over machines,\nbecause they can use their own subjective to appreciate the subjective experience of others\n\n## AIMA 2.1 Agents and Environments\n percept sequence is the complete history of everything the agent has ever perceived \n\nThe agent function is an Agent program abstract mathematical description; the agent program is a concrete implementation, running within some physical system \n\nAgents interact with environments through sensors and actuators\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n For each possible \"percept sequence\", a rational agent should select an \"action\" that is expected\nto maximize its \"performance measure\", given the evidence provided by the \"percept sequence\" and whatever \"prior knowledge\" the agent has \n\n## AIMA 2.3 The Nature of Environments\n task environment: PEAS (Performance, Environment, Actuators, Sensors) description. \n\nthe environment: fully observable vs. partially observable \n\nsingle-agent vs. multiagent(competitive or cooperative) \n\nthe next state of the environment: deterministic vs. nondeterministic \n\nthe behavior: episodic vs. sequential(whether action can have long-term effect) \n\nstatic, semidynamic (environment itself does not change, but the performance measurement changes) or dynamic \n\ntime: discrete or continuous \n\nprior knowledge: known vs. unknown \n\n\n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program \n\n\"Simple reflex agents\" respond directly to percepts; \"model-based reflex agents\" maintain internal state to track aspects of the world that are not evident in the current \npercept; \"Goal-based agents\" act to achieve their goals, and \"utility-based agents\" try to\nmaximize their own expected “happiness. \n\nAgents need internal state, transition model and sensor model and choose action according to the utility to achieve the goal. \n\nLearning agents require the reward and penalty.\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* **Rational agent** - agent that act to achieve the maximum (expected) performance measure\n* **Percept** - gathering information from an environment\n* **Autonomy** - learn to compensate for inadequate prior knowledge\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nstrongly and dynamically typed: Strong typing means that variables do have a type. eg. We can use x = 1 instead of\nint x = 1; Dynamic typing means that the variable type is determined only while running. \neg. formula def add(x, y): return x+y  works for both int and float type \n\nObjects of built-in types like (int, float, bool, str, tuple, unicode) are immutable and hashable. Mutable object cannot be the key of a dict (eg. list) \n\n\nlist methods: li.append('a'), li.insert(pos, 'i'), li.index('b')#index of first occur, li.count('b') # number of occurrences, li.remove('b') # remove first occurrence, li.reverse(), li.sort() \n\nstring methods: s.split(\" \")# return list, \"_\".join(words), s.capitalize()#'Dog', s.upper()#'DOG', 'hi--'.strip('–')#'hi'remove'_' at beginning and end \n\nlist methods: d.keys() # List of current keys, d.values() # List of current values, d.items() # List of item tuples \n\niterator: i = iter(k) next(i), \n\ngenerator: yield keyword automatically return a generator when called\n\n\n## Module 2 Definitions\n* **Mutability** - If an object is mutable, its state can be changed after declared.\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nsearch problem: state space, initial state, goal states, actions available to the agent, transition model, action cost function \n\n\n## AIMA Chapter 3.2 Example Problems\n The state space can be infinite. State space must be abstracted for problem solving\n\n## AIMA Chapter 3.3 Search Algorithms\n the search tree describes paths between states, reaching towards the goal.  \n\n```\ndef Best_First_Search():\n    frontier = PriorityQueue()\n    frontier.add(initial_state)\n    reached = []\n    while frontier:\n        cur = frontier.pop()\n        if isGoal(cur): \n            return True \n        for s in cur.successors: \n            if s.state is not in reached or s.cost < reached[s.state]: ### cost = history_path + action cost\n              reached[s.state] = s \n              frontier.add(s) \n    return False \n```\nbest-first search: priority queue \n\nbreadth-first search: FIFO queue \n\ndepth-first search: LIFO queue (stack) \n\ngraph search: check for redundant path vs. tree seach: not check for redundant path.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Use depth-first if： Space is restricted \n\nUse breadth-first if: Possible infinite paths, Some solutions have short paths \n\nuniform-cost search (UCS) is a tree search\nalgorithm used for searching a weighted tree or graph \n\nDijkstra’s algorithm or uniform-cost search: implemented as a call to BEST-FIRST-SEARCH with PATH-COST as the evaluation function，\nDijkstra’s algorithm is a Uniform-cost Search without a goal \n\nTests if a node is a goal state when it is selected for expansion, not when it is added to the frontier \n\n\n\n## Module 3 Lecture Notes\n  \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** - A sequence of actions\n* **Solution** - a path from the initial state to a goal path state\n* **Optimal solution** - the solution that has lowest path cost\n* **Frontier** - unexpanded nodes\n* **Completeness** - Is the algorithm guaranteed to find a solution and to report failure when there is no solution\n* **Optimality/admissibility** - whether the algorithm can find the solution with lowest cost\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Uninformed search can only access problem definition. \n \nh(n) = estimated cost of the cheapest path from the state at node n to a goal state \n\nGreedy best-first search expand nodes with the lowest h(n) value, evaluation function f(n)=h(n), exactly UCS with f(n) replacing g(n) \n\nis not complete.\nA* search: f (n) = g(n)+h(n) \n\ng(n) = the path cost from the initial state to node n \n\nh(n) = the estimated cost of the shortest path from n to a goal state \n\nis complete and cost-optimal if the heuristic is admissible( $h(n) \\le h^*(n) $ \n where $h^*(n)$ is the real cost to the goal state), also called optimistic \n\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem \n\ndominates: If h2(n) ≥ h1(n) for all n (both admissible), So h2 is optimistic, but more accurate than h1 \n\nThe proof of optimal: \n\nAssume all action costs are $\\ge \\epsilon > 0$\nSuppose the optimal path has cost $C^*$, but A* returns $C>C^*$ \n\nThere must be some node $n$ which is on the real optimal path and is unexpanded. \n\n$f(n) > C > C^*$ (otherwise $n$ would have been expanded) \n\n$f(n) = g(n) + h(n) \\le g(n) + h^*(n)$ (admissibility) \n\n$f(n) \\le C^*$ \n (contradiction) \n\n\nWeighted A* enforce the algorithm to be greedy \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n eg heuristic fuctions: \n\n8-puzzle: the number of misplaced tiles; Manhattan distance \n\n\neffective branching factor b*: N +1 = $1+b∗+(b∗)^2+...+(b∗)^d$ \n\n(with fixed d of optimal solution, a better h(n) lead to less N, A well-designed heuristic would have a value of b∗ close to 1)\n\n\n## Module 4 Lecture Notes\n Another proof: \n\nClaim that $n$ which is an ancestor of optimal $A$ will be expanded before sub-optimal $B$ \n\n$f(n) \\le f(A)$ (admissibility) \n\n$f(A) \\le f(B)$ (B is sub-optimal) \n\n\n\n## Module 4 Definitions\n* **Relaxed problem** - A problem with fewer restrictions on the actions than the original\n* **Consistency** - $h(n) \\le c(n, a, n') + h(n')$(stronger property)\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n deterministic, two-player, turn-taking, perfect information(fully observable), zero-sum games \n\ninitial state, transition mode, terminal states, utility function \n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n alpha–beta pruning \n\nAlpha: MAX's current lower bound on MAX's outcome \n\nBeta: MIN's current upper bound on MIN's outcome \n\nMAX will never allow a move that could lead to a worse score (for MAX) than $\\alpha$ \n\nMIN will never allow a move that could lead to a better score (for MAX) than $\\beta$ \n\nTherefore, stop evaluating a branch whenever: \n\nWhen evaluating a MAX node: a value $v \\ge \\beta$ is backed-up (MIN will never select that MAX node) \n\nWhen evaluating a MIN node: a value $v \\le \\alpha$ (Max will never select that MIN node) \n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic Alpha–Beta Tree Search: we replace the UTILITY function with EVAL, which estimates a\nstate’s utility; replace the terminal test by a cutoff test, which Cutoff test must return true for\nterminal states, also free to decide when to cut off the search, based on the search depth and any property \n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games (such as the throwing of dice) \n\nExpectimax search: compute the average score under optimal play \n\nA game tree in backgammon must include chance nodes in addition to MAX and MIN nodes. \n\nfor chance node: calculate expectation of Expect-min-max() \n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n $P(s'|a) = \\sum_{s} P(s)P(s'|s,a)$ \n\nExpected utility of action $a$: $ EU(a) = \\sum_{s'}P(s'|a)U(s') $ \n\naction = $\\argmax_a EU(a)$ \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n omit \n\n## AIMA Chapter 16.3 Utility Functions\n omit \n\n## Module 5 Lecture Notes\n game trees: Nodes represent ‘board positions’; edges represent legal moves. \n\nRoot node is the first position in which a decision must be made \n  \n\n## Module 5 Definitions\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP consists of $X$, $D$ and $C$. $X$ is set of variables, $D$ is set of domains for variables, $C$ is set of constraints. \n\nThe simplest kind of CSP involves variables that have discrete, finite domains \n\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n node consistent: all the values in the variable’s domain satisfy the variable’s unary constraints \n\narc-consistent: if every value in its domain satisfies the variable’s binary constraints \n\npath consistency: tightens the binary constraints by using Path consistency implicit constraints that are inferred by looking at triples of variables \n\nK-consistency: A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any the kth variable \n\nstrongly k-consistent: it is k-consistent and is also (k−1)-consistent, (k−2)-k-consistent ... 1-consistenct \n\nAC-3 can be used to enforce arc consistency. \n\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking Search for CSPs: is a form of depth first search \n\nforward checking: Whenever a variable X is assigned, the forward-checking process establishes arc consistency, for each unassigned\nvariable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent with the value chosen for X \n\nMAC recursively propogrates constraints, whereas forward checking does not: If we assign X, forward checking makes all the arcs incident on X consistent. \nMAC does this, and if the domain of a variable Y changes, does the same for Y \n\nMAC runs while assigning variables in backtracking search. \n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nmin-conflicts heuristic: Randomly choose the min-conflicted variable and modift its value to satisfy the constraints \n\nconstraint weighting: concentrate Constraint weighting the search on the important constraints \n \n\n## AIMA Chapter 6.5 The Structure of Problems\n\nCutset conditioning: to reduce a general CSP to a tree structured one (which can be linear time complexity). \n\nTree decomposition: transform the CSP into a tree of subproblems. (efficient if the tree width of the constraint graph is small)\n\nCutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width \n\n \n\n## Module 6 Lecture Notes\n \nIdea 1: CSP as a search problem\nImproving backtracking efficiency:\nHeuristic 1: Most constrained variable: Choose a variable with the fewest legal values \n\nHeuristic 2: Most constraining variable: with most remaining neighbors \n\nHeuristic 3: Least constraining value: choose value that rules out the fewest values in the remaining variables \n\nHeuristic 4: Forward checking (Arc consistency & AC-3) \n \nCSP differ from search problems: In search problems, states are black boxes with transition model to move between. In CSPs, the agent can see inside states and move accordingly. \n\n\n\n## Module 6 Definitions\n* **Mac** - Maintaining Arc Consistency\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n A Knowledge base is a set of sentences \n\nThe agent maintains a knowledge base, KB, which may initially contain some background knowledge \n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n PEAS description: Performance measurement, Environment, Actuator, Sensor \n \n\n## AIMA Chapter 7.3 Logic\n Entailment: $\\alpha \\models \\beta$ if in every model where $\\alpha$ is true, $\\beta$ is also true \n$\\alpha \\models \\beta$ if and only if ($M(\\alpha) \\subset M(\\beta)$)\n\nIf an algorithm $i$ can derive $\\alpha$ from $KB$, we write $KB \\vdash_i \\alpha$\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nnot : $\\neg$ (negation) \n\nand : $\\wedge$  $P \\wedge Q$ is called a conjunction. \n\nor ： $\\vee$ $P \\vee Q$ is called a disjunction. \n\nimply : $\\Rightarrow$ \n\nif and only if: $\\Leftrightarrow$ \n\n$\\neg P$ is true iff P is false in m.\n$P \\wedge Q$ is true iff both P and Q are true in m.\n$P \\vee Q$ is true iff either P or Q is true in m.\n$P \\Rightarrow Q$ is true unless P is true and Q is false in m.\n$P \\Leftrightarrow Q$ is true iff P and Q are both true or both false in m.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \nlogical equivalence: $\\alpha \\equiv \\beta$ iff $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$ \n\nInference and proofs: \n\nlogical systems is monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base \n\nif $KB \\models \\alpha$ then $KB \\wedge \\beta \\models \\alpha$ \n \nProof by resolution: yields a complete inference algorithm when coupled with any complete search algorithm \n\n \n\n## Module 7 Lecture Notes\n \nCNF (Conjunctive Normal Form): Every sentence of propositional logic is logically equivalent to a conjunction of clauses which are disjunctions of literals.\n1. Eliminate $\\Leftrightarrow$ by $(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Leftrightarrow \\alpha))$ \n\n2. Eliminate $\\Rightarrow$ by $(\\alpha \\Rightarrow \\beta) \\equiv (\\neg \\alpha \\vee \\beta)$ \n\n3. Move $\\neg$ inwards (only before literals) by De Morgan and double-negation. \n\n4. Distribute $\\vee$ over $\\wedge$ wherever possible. \nResolution Algorithm: \n\nInference procedures based on resolution work using the principle of proof by contradiction \n\nTo show $KB \\models \\alpha$, we can show that $KB \\wedge \\neg\\alpha$ is unsatisfiable. \n\n1. Convert $KB \\wedge \\neg\\alpha$ into CNF. \n\n2. apply the resolution rule to the resulting clauses\n3. Resolve every pair that contains complementary literals to produce a new clause, add unalready presented clause to the set. \n\n4. Repeat resolution for each pairs of disjunctions until one of two things happens: \n\na) There are no new clauses that can be added. In this case, the KB does not entail $\\alpha$ \n\nb) Two clauses resolve to yield the empty clause (comes from contradiction), in which case the KB does entail $\\alpha$\nResolution is sound and complete. \n\n\n\n\n## Module 7 Definitions\n* **Soundness** - the inference algorithm should only derive entailed sentences\n* **Completeness** - An inference algorithm is complete if it can derive all sentences that are entailed.\n* **Validity** - A sentence is valid if it is true in all models.\n* **Satisfiability** - A sentence is satisfiable if it is true in, or satisfied by some models.\n* **Oy** - .\n* **Fogr** - .\n* **Oe** - .\n* **Ogrr** - .\n* **Obtd** - .\n* **Ofse** - .\n* **Oew5** - .\n* **Ohdd** - .\n* **Ogrs** - .\n* **Ogrw** - .\n* **Oegg** - .\n* **Ose4** - .\n* **Oetf** - .\n* **Osew** - .\n* **Ohtd** - .\n* **Obre** - .\n* **Osht** - .\n* **Vhro** - .\n* **Osdb** - .\n* **Odju** - .\n* **Otrf** - .\n* **Otjh** - .\n* **Ofre** - .\n* **Odtu** - .\n* **Omug5** - .\n* **O4esf** - .\n* **Ory5e** - .\n* **Oesgy** - .\n* **Os4t** - .\n* **Ords** - .\n* **Orty** - .\n* **Ods4w** - .\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}