{
  "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/",
          "height": 0
        },
        "outputId": "4bad47d6-76d8-49fd-c5b8-643f21605bc9"
      },
      "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": 75,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "77f87638-c644-489a-c4c7-1b8fef985ea6"
      },
      "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": 76,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 77,
      "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 = \"\"\" What is AI \\n\n",
        "There're various definitions about what an AI is. For example, in terms of fidelity\\\n",
        "to human performance, or rationality.\\n\n",
        "There're several tests for computers to pass, like nlp, knowledge representation \\\n",
        "automated reasoning, machine learning,  (possibly) plus computer vision, robotics.\\n\n",
        "\n",
        "There're also ways that can be considered as rational but without any inference.\\\n",
        "For example, recoiling from a hot stove. \\n\n",
        "\n",
        "We do not want the agent that created by human does not pursue our objective. So,\\\n",
        " here comes a term - Value alignment problem. We want them to be provably beneficial. \\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 = \"\"\" The Limits of AI\\n\n",
        "We have two types of AI - weak AI (acts as if they were intelligent) and strong \\\n",
        "AI (do actually has conscious thinking). We also encontered many problems that \\\n",
        "when we evaluating what an AI is, such as qualification problem and embodied cognition. \\\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" Can Machines Really Think\\n\n",
        "Some philosophers say that a machine that acts intelligently is just mimicing. \\\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Agents and Environment\\n\n",
        "We talked about the difference between agent function, agent program. Also \\\n",
        "with some crucial definition regarding environment, sensors, actuators. \"\"\"\n",
        "chapter2_2 = \"\"\" The Concept of Rationality \\n\n",
        "\n",
        "We have key four things to describe the rationality of an agent. That are, \\\n",
        "performance measure, prior knowledge of environment, actions, percept sequence to date \\\n",
        "Note that, an rational agent are expected to maximize the performance measure(given \\\n",
        "a sequence of percepts and built'in knowldge). \\n\n",
        "\n",
        "Omniscience, learning and autonomy. We need to pay attention to the definition \\\n",
        "of Omniscience, which is different from rationality. See definition\\n\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" The Nature of Environments \\n\n",
        "There're several pairs of evaluation standards regarding how to define an environment.\\\n",
        " Fully observable - Partially observable, single-agent - multiagent, Deterministic - \\\n",
        " nondeterministic, Episodic - Sequential, Static - Dynamic, Discrete - Continuous.\"\"\"\n",
        "chapter2_4 = \"\"\" The structure of Agent /n\n",
        "We need to note that agent = architecture + program. We may devide the type of \\\n",
        "agents into Simple reflex agents, Model-based reflex agents, Goal-based agents and\\\n",
        " Utility-based agents. To be more details, simple reflex agent's decision is based \\\n",
        "on the percept of current state's percept, no history considered. A model based \\\n",
        "agent need to maintain some sort of internal state. The potential models include \\\n",
        "transition model, sensor model. Goal based agents, have some information that \\\n",
        "describe situations which are desired by us. Search and planning are crucial \\\n",
        "steps in reaching the goals. A Utility based agent has a utility function. And \\\n",
        "it tries to maximize the expected utility. \\n\n",
        "\n",
        "Learning agent is a special case, it has a advantage that it allows the agent \\\n",
        "to start from scratch, operating in initially unknown environment, and become \\\n",
        "more competent. The learning element absorb feedbacks from critic, then figure out \\\n",
        "how to improve next time. It also has a property called problem generator, which \\\n",
        "suggests actions leading to new and informative experience. \\n\n",
        "\n",
        "As for how the components of agent programs work, we can split the topic into many parts. \\\n",
        "atomic representation, factored representation, structured representation, localist \\\n",
        "representation, distributed representation .. \"\"\"\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 which aims to do the right thing (achieve the best (expected) outcome)\",\n",
        "\"percept\" : \"the content that the agent collected using sensors\",\n",
        "\"Value alignment problem\" : \"values that the machine holds need to be aligned with human\",\n",
        "\"agent function\": \"map percept sequence to action\",\n",
        "\"agent program\" : \"concrete implementation, actually running physically in system.\",\n",
        "\"consequentialism\" : \"an agent's behaviors' consequences are standards\",\n",
        "\"Omniscience\" : \"knows the actual outcome of actions, impossible for most cases\",\n",
        "\"Deterministic\" : \"true if current state and action determine the next state's environment\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 78,
      "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": 1305
        },
        "cellView": "form",
        "outputId": "0602393b-3d64-4102-e6da-250753a16425"
      },
      "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": 79,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n What is AI \n\nThere're various definitions about what an AI is. For example, in terms of fidelityto human performance, or rationality.\n\nThere're several tests for computers to pass, like nlp, knowledge representation automated reasoning, machine learning,  (possibly) plus computer vision, robotics.\n\n\nThere're also ways that can be considered as rational but without any inference.For example, recoiling from a hot stove. \n\n\nWe do not want the agent that created by human does not pursue our objective. So, here comes a term - Value alignment problem. We want them to be provably beneficial. \n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n The Limits of AI\n\nWe have two types of AI - weak AI (acts as if they were intelligent) and strong AI (do actually has conscious thinking). We also encontered many problems that when we evaluating what an AI is, such as qualification problem and embodied cognition. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Can Machines Really Think\n\nSome philosophers say that a machine that acts intelligently is just mimicing.  \n\n## AIMA 2.1 Agents and Environments\n Agents and Environment\n\nWe talked about the difference between agent function, agent program. Also with some crucial definition regarding environment, sensors, actuators. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n The Concept of Rationality \n\n\nWe have key four things to describe the rationality of an agent. That are, performance measure, prior knowledge of environment, actions, percept sequence to date Note that, an rational agent are expected to maximize the performance measure(given a sequence of percepts and built'in knowldge). \n\n\nOmniscience, learning and autonomy. We need to pay attention to the definition of Omniscience, which is different from rationality. See definition\n\n \n\n## AIMA 2.3 The Nature of Environments\n The Nature of Environments \n\nThere're several pairs of evaluation standards regarding how to define an environment. Fully observable - Partially observable, single-agent - multiagent, Deterministic -  nondeterministic, Episodic - Sequential, Static - Dynamic, Discrete - Continuous.\n\n## AIMA 2.4 The Structure of Agents\n The structure of Agent /n\nWe need to note that agent = architecture + program. We may devide the type of agents into Simple reflex agents, Model-based reflex agents, Goal-based agents and Utility-based agents. To be more details, simple reflex agent's decision is based on the percept of current state's percept, no history considered. A model based agent need to maintain some sort of internal state. The potential models include transition model, sensor model. Goal based agents, have some information that describe situations which are desired by us. Search and planning are crucial steps in reaching the goals. A Utility based agent has a utility function. And it tries to maximize the expected utility. \n\n\nLearning agent is a special case, it has a advantage that it allows the agent to start from scratch, operating in initially unknown environment, and become more competent. The learning element absorb feedbacks from critic, then figure out how to improve next time. It also has a property called problem generator, which suggests actions leading to new and informative experience. \n\n\nAs for how the components of agent programs work, we can split the topic into many parts. atomic representation, factored representation, structured representation, localist representation, distributed representation .. \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 which aims to do the right thing (achieve the best (expected) outcome)\n* **Percept** - the content that the agent collected using sensors\n* **Value alignment problem** - values that the machine holds need to be aligned with human\n* **Agent function** - map percept sequence to action\n* **Agent program** - concrete implementation, actually running physically in system.\n* **Consequentialism** - an agent's behaviors' consequences are standards\n* **Omniscience** - knows the actual outcome of actions, impossible for most cases\n* **Deterministic** - true if current state and action determine the next state's environment\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 = \"\"\" Homework1\\n\n",
        "`def concatenate(seqs):\n",
        "    return [y for x in seqs for y in x]`\n",
        "\n",
        "\n",
        "`def transpose(matrix):\n",
        "    return [[row[i] for row in matrix] for i in range(len(matrix[0]))]` \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 80,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 257
        },
        "outputId": "64d2b9d4-c10e-4232-f79b-cc6061763dc0"
      },
      "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": 81,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Homework1\n\n`def concatenate(seqs):\n    return [y for x in seqs for y in x]`\n\n\n`def transpose(matrix):\n    return [[row[i] for row in matrix] for i in range(len(matrix[0]))]` \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 = \"\"\" Solving Problems by Searching \\n\n",
        "The key factors used to defind a problem is as follows, \\\n",
        "state space, initial state, goal satets, actions, transition model, action \\\n",
        "cost function. During which process, we extract a model (mathematical description).\\\n",
        "\\n\n",
        "We have several standard search algorithm, such as best-first search which \n",
        "always expand nodes with minimum f(n) value. \\n\n",
        "We have several standards of measuring problem-solving performance, such as, \\\n",
        "completeness, cost optimality, time complexity, space complexity.\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" \"\"\"\n",
        "chapter3_3 = \"\"\" Search Algorithm \\n\n",
        "\n",
        "  \"\"\"\n",
        "chapter3_4 = \"\"\" Uninformed Search Strategies \\n \n",
        "We have breadth-first search, dijkstra's algorithm or uniform-cost search, \\\n",
        "Depth-first search, Interative deepening search, Bidirectional search. \\\n",
        "We can then summary the features of each strategies as follows, \\n\n",
        "The order is Complete? Optimal Cost? Time and Space complexity.\\n\n",
        "Breadth-first (Yes, Yes, O(b^d), O(b^d)) / Uniform-Cost (Yes, Yes, O(b^(1+[C*/e])), \n",
        "O(b^(1+[C*/e]))) / Depth-First (No, No, O(b^m), O(bm)) / Depth-Limited (No, \\\n",
        "No, O(b^l), O(bl)) / Iterative Deepening (Yes, Yes, O(b^d), O(bd)) / Bidirectional \\\n",
        "(Yes, Yes, O(b^d/2), O(b^d/2)) \\n\n",
        "Where b is the branching factor, m is the maximum depth of the search tree, d is \\\n",
        "the depth of the shallowest solution, or is m when there is no solution, l is \\\n",
        "the depth limit.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\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",
        "}\n",
        "\n"
      ],
      "execution_count": 82,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 687
        },
        "outputId": "06a1c250-ae1c-42ac-fe44-715488f0f5b3"
      },
      "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": 83,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Solving Problems by Searching \n\nThe key factors used to defind a problem is as follows, state space, initial state, goal satets, actions, transition model, action cost function. During which process, we extract a model (mathematical description).\n\nWe have several standard search algorithm, such as best-first search which \nalways expand nodes with minimum f(n) value. \n\nWe have several standards of measuring problem-solving performance, such as, completeness, cost optimality, time complexity, space complexity.\n \n\n## AIMA Chapter 3.2 Example Problems\n \n\n## AIMA Chapter 3.3 Search Algorithms\n Search Algorithm \n\n\n  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed Search Strategies \n \nWe have breadth-first search, dijkstra's algorithm or uniform-cost search, Depth-first search, Interative deepening search, Bidirectional search. We can then summary the features of each strategies as follows, \n\nThe order is Complete? Optimal Cost? Time and Space complexity.\n\nBreadth-first (Yes, Yes, O(b^d), O(b^d)) / Uniform-Cost (Yes, Yes, O(b^(1+[C*/e])), \nO(b^(1+[C*/e]))) / Depth-First (No, No, O(b^m), O(bm)) / Depth-Limited (No, No, O(b^l), O(bl)) / Iterative Deepening (Yes, Yes, O(b^d), O(bd)) / Bidirectional (Yes, Yes, O(b^d/2), O(b^d/2)) \n\nWhere b is the branching factor, m is the maximum depth of the search tree, d is the depth of the shallowest solution, or is m when there is no solution, l is the depth limit.\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\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 = \"\"\" Informed (Heuristic) search strategies \\n\n",
        "Common strategies: greedy best-first search, A* search. In which, the greedy \\\n",
        "best-first search always first expand nodes with lowest h(n) value, so the \n",
        "evaluation function is f(n) = h(n). A* search is a best-first search uses the \\\n",
        "evaluation function f(n) = g(n) + h(n). Note that, there's a stronger property \\\n",
        "- consistency. If A* applies a consistency heuristic function, we are guaranteed \\\n",
        "that we never re-add a state to the frontier, costing both time and space. \\n\n",
        "So, if h(n) = 0, then the A* would become Uniform-cost search, we can change the \\\n",
        "coeff of h(n) to adjust our A* search to be a weighted one. \\n\n",
        "\n",
        "There are several examples for memory-bounded search. Such as, beam search, \\\n",
        "iterative-deepening A* search, Recursive best-first search.\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" Heuristic Functions \\n\n",
        "\n",
        "The heuristic function has a major effect on the practical performance of A* \\\n",
        "search, since a good heuristic allows A* to prune away many of the bd nodes that\\\n",
        "an uninformed search would expand. Its quality can be expressed in terms of the\\\n",
        "effective branching factor b*, which can be determined empirically for a \\\n",
        "problem instance by measuring the number of nodes generated by expansion, \\\n",
        "N, and the depth of the solution, then solving\\\n",
        "\n",
        "Good heuristics are those with low effective branching factor (the optimal being b* = 1).\\\n",
        "\n",
        "The time complexity is polynomial when the search space is a tree, there is a \\\n",
        "single goal state, and the heuristic function h meets the following condition:\n",
        "\n",
        "|h(x)-h^{*}(x)|=O(\\log h^{*}(x))|h(x) - h^*(x)| = O(\\log h^*(x))\\\n",
        "where h* is the optimal heuristic, the exact cost to get from x to the goal.\\\n",
        "In other words, the error of h will not grow faster than the logarithm of the\\\n",
        "perfect heuristic\" h* that returns the true distance from x to the goal.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 84,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 582
        },
        "cellView": "form",
        "outputId": "5a82e0b2-a51d-49a3-d5ff-6d7526134d71"
      },
      "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": 85,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed (Heuristic) search strategies \n\nCommon strategies: greedy best-first search, A* search. In which, the greedy best-first search always first expand nodes with lowest h(n) value, so the \nevaluation function is f(n) = h(n). A* search is a best-first search uses the evaluation function f(n) = g(n) + h(n). Note that, there's a stronger property - consistency. If A* applies a consistency heuristic function, we are guaranteed that we never re-add a state to the frontier, costing both time and space. \n\nSo, if h(n) = 0, then the A* would become Uniform-cost search, we can change the coeff of h(n) to adjust our A* search to be a weighted one. \n\n\nThere are several examples for memory-bounded search. Such as, beam search, iterative-deepening A* search, Recursive best-first search.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Heuristic Functions \n\n\nThe heuristic function has a major effect on the practical performance of A* search, since a good heuristic allows A* to prune away many of the bd nodes thatan uninformed search would expand. Its quality can be expressed in terms of theeffective branching factor b*, which can be determined empirically for a problem instance by measuring the number of nodes generated by expansion, N, and the depth of the solution, then solving\nGood heuristics are those with low effective branching factor (the optimal being b* = 1).\nThe time complexity is polynomial when the search space is a tree, there is a single goal state, and the heuristic function h meets the following condition:\n\n|h(x)-h^{*}(x)|=O(\\log h^{*}(x))|h(x) - h^*(x)| = O(\\log h^*(x))where h* is the optimal heuristic, the exact cost to get from x to the goal.In other words, the error of h will not grow faster than the logarithm of theperfect heuristic\" h* that returns the true distance from x to the goal.\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Game Theory\\n\n",
        "We most focus on deterministic, two-player, turn-taking, perfect information, \\\n",
        "zero-sum games within the field of AI. We talked in this section about the elements \\\n",
        "used to define the game - Initial state, To-Move, Actions, result (transition model) \\\n",
        "terminal test / terminal states, Utility function.\"\"\"\n",
        "chapter5_2 = \"\"\" Optimal Decisions in Games \\n\n",
        "We most focus on the analysis of minimax algorithm (with or without alpha-beta pruning) \\\n",
        "Suppose we have m maximum depth, and b legal moves (expanding factor). Then the \\\n",
        "time complexity of minimax is O(b^m). The space complexity is O(bm) or O(m), depending \\\n",
        "on generating all solution at once or not. \\n\n",
        "As for alpha-beta pruning, we may think alpha as 'at least' and beta as 'at most'. \\\n",
        "To be more specific, alpha is the best or highest-value chocie we have found so \\\n",
        "far at any choice point along the way for MAX. Beta is the best or lowest-value \\\n",
        "choice we have found so far at any choice point along the path for MIN. \\n\n",
        "Alpha-beta pruning in theory, can reduce the time to O(b^m/2).\"\"\"\n",
        "chapter5_3 = \"\"\" Heuristic Alpha-Beta Three Search \\n\n",
        "Key idea - treating nonterminal as if they were. There are several guidelines \\\n",
        "to choose the evaluation function - util(loss) <= eval <= util(win) / util(t)=eval(t) \\\n",
        "and the evaluation should be strongly possible correlated with actual chance of \\\n",
        "winning. \\n\n",
        "\n",
        "There're also some crucial concepts regarding foreard pruning. Such as beam \\\n",
        "search, late move reduction.\"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic Games \\n\n",
        "It has chance nodes, however, we can just calculate the expected value \\\n",
        "for a position without knowing the exact definite value. So, this leads to the \\\n",
        "concept of expectiminimax value, which is a generalization of the minimax value \\\n",
        "for deterministic games. The worst running time is O(b^m n^m) \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Combining Beliefs and Desires under uncertainty, we \\\n",
        "encountered the concepts like utility function, expected utility given the \\\n",
        "evidance,which is just the average utility of the outcomes times the \\\n",
        "probability of which the outcome could happen, the maximum expected utility, \\\n",
        "which is basically a guidenline(formalize) that a rational agent should follow.\\\n",
        "But it does not operationalize that advice.\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" six constraints that needed to be obeyed by any resonable preference relation:\n",
        "Orderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability. \"\"\"\n",
        "chapter16_3 = \"\"\" Utility functions \\n\n",
        "Utility function under the restriction of six axioms and maps from lotteries to \\\n",
        "real numbers.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"zero-sum games\" : \"no 'win,win situation\",\n",
        "\"quiescene\" : \"just consider certain types of moves\",\n",
        "\"horizon effect\" : \"when the opponent's behavior ultimately cause serious damages\",\n",
        "\"lottery\" : \"it describes the set of outcomes for a given action with possibility\",\n",
        "\"preference elicitation\" : \"present choice to human, use preference to create utility funcs\",\n",
        "\"framing effect\" : \"wording of a decision problem influence agent's choices\",\n",
        "\"anchoring effect\" : \"prefer relative utility judgements to abosolute judgements, first important\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 86,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1142
        },
        "outputId": "4efd31c6-875b-4ebe-e072-12bf3ebfdb5d"
      },
      "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": 87,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Game Theory\n\nWe most focus on deterministic, two-player, turn-taking, perfect information, zero-sum games within the field of AI. We talked in this section about the elements used to define the game - Initial state, To-Move, Actions, result (transition model) terminal test / terminal states, Utility function.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Optimal Decisions in Games \n\nWe most focus on the analysis of minimax algorithm (with or without alpha-beta pruning) Suppose we have m maximum depth, and b legal moves (expanding factor). Then the time complexity of minimax is O(b^m). The space complexity is O(bm) or O(m), depending on generating all solution at once or not. \n\nAs for alpha-beta pruning, we may think alpha as 'at least' and beta as 'at most'. To be more specific, alpha is the best or highest-value chocie we have found so far at any choice point along the way for MAX. Beta is the best or lowest-value choice we have found so far at any choice point along the path for MIN. \n\nAlpha-beta pruning in theory, can reduce the time to O(b^m/2).\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic Alpha-Beta Three Search \n\nKey idea - treating nonterminal as if they were. There are several guidelines to choose the evaluation function - util(loss) <= eval <= util(win) / util(t)=eval(t) and the evaluation should be strongly possible correlated with actual chance of winning. \n\n\nThere're also some crucial concepts regarding foreard pruning. Such as beam search, late move reduction.\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic Games \n\nIt has chance nodes, however, we can just calculate the expected value for a position without knowing the exact definite value. So, this leads to the concept of expectiminimax value, which is a generalization of the minimax value for deterministic games. The worst running time is O(b^m n^m) \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Combining Beliefs and Desires under uncertainty, we encountered the concepts like utility function, expected utility given the evidance,which is just the average utility of the outcomes times the probability of which the outcome could happen, the maximum expected utility, which is basically a guidenline(formalize) that a rational agent should follow.But it does not operationalize that advice.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n six constraints that needed to be obeyed by any resonable preference relation:\nOrderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability. \n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions \n\nUtility function under the restriction of six axioms and maps from lotteries to real numbers.\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Zero-sum games** - no 'win,win situation\n* **Quiescene** - just consider certain types of moves\n* **Horizon effect** - when the opponent's behavior ultimately cause serious damages\n* **Lottery** - it describes the set of outcomes for a given action with possibility\n* **Preference elicitation** - present choice to human, use preference to create utility funcs\n* **Framing effect** - wording of a decision problem influence agent's choices\n* **Anchoring effect** - prefer relative utility judgements to abosolute judgements, first important\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 = \"\"\" Defining Constraint Satisfaction Problems\\n\n",
        "CSP is problem sets in which we see how treating states as more than just \\\n",
        "little black boxex leads to new search methods and a deeper undestanding of the \\\n",
        "problem structure. \\n\n",
        "The reason in which we may turn to CSPs, is that once we find a partial solution \\\n",
        "that violates the constraints, we can immediately stop going any further, in such way, \\\n",
        "we can pay attention to those variables really matter. \\n\n",
        "The simplest kind of CSP has discrete, finite domains. We may have simplest type \\\n",
        "of constraints be unary constraint, which restrics the value of a single variable. \\\n",
        "Binary ones relates two variables. We may also have global constraint, but does not \\\n",
        "necessarily involve all the variables。 \"\"\"\n",
        "chapter6_2 = \"\"\" Constraint Propagation: Inference in CSPs \\n\n",
        "The key idea of this process is to force local consistency. We have different \\\n",
        "types of consistency, such as node-consistent, arc consistency, Path consistency \\\n",
        ", K consistency and strongly k consistency. \\n\n",
        "Note that for AC-3, checking consistency of an arc can be done in O(d^2), total \\\n",
        "worst-case time is O(cd^3). For building a strong n-consistent needs O(n^2d) time.\\\n",
        "However, this is one of the NP-complete problem, so estabilishing n-consistency \\\n",
        "have both exponential time and space complexity.\"\"\"\n",
        "chapter6_3 = \"\"\" Backstracking Search for CSPs \\n\n",
        "We could have n! * d^n leaves, since the branching factor at first layer is nd, \\\n",
        "next is (n-1)d. \\n \n",
        "Intuitively, we have one approach to reduce the possible branching factor, that is, \\\n",
        "expand variable with fewest legal values, to say, most constrained variable, \\\n",
        "or fail-first heuristic. We may also choose another approach, which is the opposite \\\n",
        "of the MRV, say, value that rules out the fewest choices for the neighboring, which \\\n",
        "is called, least-constraining-value, via which, we can look for most likely values first.\\\n",
        "Selection should be variable - fail-first, value - fail-last. \\n\n",
        "\n",
        "Another well-known algorithm is called MAC, (maintaining arc consistency). It \\\n",
        "differs with forward checking in that, it recursively propagate constraints when \\\n",
        "changes are made to the domains of variables. \\n\n",
        "\n",
        "backjumping does exactly what farward checking does. So, we may use conflict \\\n",
        "directed backjumping to further improve the algorithm. We can summarize how to \\\n",
        "build a direct conflict set in the following way: Let Xj be the current variable, \\\n",
        "conf(Xj) be its confilict set. If every possible value for Xj fails, backjump to \\\n",
        "the most recent variable Xi in conf(Xj) and recompute the confilict set for Xi:\n",
        "conf(Xi) = conf(Xi) or conf(Xj) - Xi\\\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" Local Search for CSPs\\n\n",
        "Note that a amazing heuristic is introduced in this chapter, that is, min-conflicts \\\n",
        "heuristic, which select the value that results in the minimum number of conflicts \\\n",
        "with other variables. It is roughly indepent of what the size of a problem is, \\\n",
        "it can even solve million-queens in 50 steps on average.\"\"\"\n",
        "chapter6_5 = \"\"\" The structure of problems\\n\n",
        "Two main topics - Cutset conditioning and Tree decomposition. \\n\n",
        "The key idea for cutset conditioning is to assign part of the values to certain \\\n",
        "variables in order to make the left variables able to form a tree. And the key idea \\\n",
        "for tree decomposition is different. \\n\n",
        "The comparison: the time complexity for both is O(d^c (n-c)d^2) and O(nd^w+1) \\\n",
        "respectively. Tree decomposition is faster in time, but requires memory exp in w. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"assignments\" : \"<X1 = v1>\",\n",
        "\"consistent\" : \"does not violate any constraints\",\n",
        "\"complete\" : \"every variable is assigned a value\",\n",
        "\"solution\" : \"a complete and consistent assignment\",\n",
        "\"COP\" : \"constrained optimization problem\",\n",
        "\"constraint propogation\" : \"reduce the number of legal values using constriants\", \n",
        "\"minimum-remaining-values (MRV)\" : \"choose variables with least legal values.\",\n",
        "\"least-constraining-value\" : \"choose values that rules out least possibility for nei.\",\n",
        "\"forward checking\" : \"We establish arc consistency after assigning value for X\",\n",
        "\"chronological backtracking\" : \"revisit the most recent decision point\",\n",
        "\"conflict set\" : \"a set which conflict with a certain variable (say SA)\",\n",
        "\"backjumping\" : \"jump back to the assigenment in the conflict set that is most recent\",\n",
        "\"conflict-directed backjumping\" : \"differs with pure backjumping, \",\n",
        "\"Constraint learning\" : \"to find a minimum set of variable that cause a problem\",\n",
        "\"no-good\" : \"variables and values of above set\",\n",
        "\"constraint weighting\" : \"focus on the search of important constraints\",\n",
        "\"symmetry-breaking constraint\" : \"ordinal variable\"\n",
        "\n",
        "}\n"
      ],
      "execution_count": 88,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1369
        },
        "outputId": "3f0c7175-86cd-410d-87df-dcacd4b116bb"
      },
      "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": 89,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Defining Constraint Satisfaction Problems\n\nCSP is problem sets in which we see how treating states as more than just little black boxex leads to new search methods and a deeper undestanding of the problem structure. \n\nThe reason in which we may turn to CSPs, is that once we find a partial solution that violates the constraints, we can immediately stop going any further, in such way, we can pay attention to those variables really matter. \n\nThe simplest kind of CSP has discrete, finite domains. We may have simplest type of constraints be unary constraint, which restrics the value of a single variable. Binary ones relates two variables. We may also have global constraint, but does not necessarily involve all the variables。 \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint Propagation: Inference in CSPs \n\nThe key idea of this process is to force local consistency. We have different types of consistency, such as node-consistent, arc consistency, Path consistency , K consistency and strongly k consistency. \n\nNote that for AC-3, checking consistency of an arc can be done in O(d^2), total worst-case time is O(cd^3). For building a strong n-consistent needs O(n^2d) time.However, this is one of the NP-complete problem, so estabilishing n-consistency have both exponential time and space complexity.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backstracking Search for CSPs \n\nWe could have n! * d^n leaves, since the branching factor at first layer is nd, next is (n-1)d. \n \nIntuitively, we have one approach to reduce the possible branching factor, that is, expand variable with fewest legal values, to say, most constrained variable, or fail-first heuristic. We may also choose another approach, which is the opposite of the MRV, say, value that rules out the fewest choices for the neighboring, which is called, least-constraining-value, via which, we can look for most likely values first.Selection should be variable - fail-first, value - fail-last. \n\n\nAnother well-known algorithm is called MAC, (maintaining arc consistency). It differs with forward checking in that, it recursively propagate constraints when changes are made to the domains of variables. \n\n\nbackjumping does exactly what farward checking does. So, we may use conflict directed backjumping to further improve the algorithm. We can summarize how to build a direct conflict set in the following way: Let Xj be the current variable, conf(Xj) be its confilict set. If every possible value for Xj fails, backjump to the most recent variable Xi in conf(Xj) and recompute the confilict set for Xi:\nconf(Xi) = conf(Xi) or conf(Xj) - Xi\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local Search for CSPs\n\nNote that a amazing heuristic is introduced in this chapter, that is, min-conflicts heuristic, which select the value that results in the minimum number of conflicts with other variables. It is roughly indepent of what the size of a problem is, it can even solve million-queens in 50 steps on average.\n\n## AIMA Chapter 6.5 The Structure of Problems\n The structure of problems\n\nTwo main topics - Cutset conditioning and Tree decomposition. \n\nThe key idea for cutset conditioning is to assign part of the values to certain variables in order to make the left variables able to form a tree. And the key idea for tree decomposition is different. \n\nThe comparison: the time complexity for both is O(d^c (n-c)d^2) and O(nd^w+1) respectively. Tree decomposition is faster in time, but requires memory exp in w. \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Assignments** - <X1 = v1>\n* **Consistent** - does not violate any constraints\n* **Complete** - every variable is assigned a value\n* **Solution** - a complete and consistent assignment\n* **Cop** - constrained optimization problem\n* **Constraint propogation** - reduce the number of legal values using constriants\n* **Minimum-remaining-values (mrv)** - choose variables with least legal values.\n* **Least-constraining-value** - choose values that rules out least possibility for nei.\n* **Forward checking** - We establish arc consistency after assigning value for X\n* **Chronological backtracking** - revisit the most recent decision point\n* **Conflict set** - a set which conflict with a certain variable (say SA)\n* **Backjumping** - jump back to the assigenment in the conflict set that is most recent\n* **Conflict-directed backjumping** - differs with pure backjumping, \n* **Constraint learning** - to find a minimum set of variable that cause a problem\n* **No-good** - variables and values of above set\n* **Constraint weighting** - focus on the search of important constraints\n* **Symmetry-breaking constraint** - ordinal variable\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 = \"\"\" Knowledge-Based Agents. \\n\n",
        "The key concept of the knowledge based agents it the KB, which comprise of a set\\\n",
        "of sentences. (knowledge representation language). \"\"\"\n",
        "chapter7_2 = \"\"\" The Wumpus World. \\n\n",
        "We need to notice that in the wampus world example, we still need to pay attention \\\n",
        "to PEAS, that are, Performance measure, Envoronment, Actuators, Sensors. \\\n",
        "\\n\n",
        "Moreover, it is clearly a deterministic, discrete, static and single angent model.\\\n",
        "It is also, sequential, partial observable. \"\"\"\n",
        "chapter7_3 = \"\"\" Logic. \\n\n",
        "Logic is a way to express some assertion. Using sentences with concrete 'syntax'\\\n",
        "We may also need semantic which in turn defines the truth of each sentence \\\n",
        "corresponding to each possible world (more specific term will be model). \\\n",
        "\\n\n",
        "We may also need to pay attention to entaiment. So we need to introduce the \\\n",
        "concept of satisfaction, that is, we may use notation M(alpha) to denote the set \\\n",
        "of all models of alpha. We say a model m satisfies alpha when alpha is true in model m\\\n",
        "\\n\n",
        "We say A entails B, when the idea that a sentence follows logicaaly from another\n",
        "sentence. In this manner, we say A entails B is true, iff in every model A is \\\n",
        "true, B is also true. So, A is a stronger assertion, since it rules out more \\\n",
        "possibilities than B.\\\n",
        "\\n\n",
        "Deriving conclusion is to carry out logical inference. We may have 'A is \\\n",
        "derived from KB by i.' Here, the searching process is no more than sounds like \\\n",
        "searching a needle A in the haystack KB. \\\n",
        "\\n\n",
        "To be noted, Soundess is a highly demandding property. Since we need to assert \\\n",
        "True, in the very end. Completeness is also desired. There's luckly procedure \\\n",
        "that can handle many knowledge base that is an complete algorithm. Another issue\\\n",
        "is grounding, see definition below./\"\"\"\n",
        "chapter7_4 = \"\"\" Propositional Logic \\n\n",
        "We have several key syntax: negation, conjunction, disjunction, implication, \\\n",
        "biconditional. In a more systematic way of the constructure is, \\\n",
        "1) Sentence can be formed with an Atomic or a complex sentence. 2) An \n",
        "AotomicSentence is either true, false, P. 3) A complexSentence is either a sentence\\\n",
        " neg sentence, or any combination with boolean algebra conjs.\\\n",
        " \\n\n",
        " TT-Entails performs a recursive enumeration of a finite space of assignments to\\\n",
        " symbols, with the time complexity being O(2^n) and space complextity is the same \\\n",
        " as depth-first search. Every algorithm known to inference propositional logic is\\\n",
        " co-NP-complete.\"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",  \n",
        "\"axiom\" : \"given without derived. (Base condition)\",\n",
        "\"declarative approach\" : \"agents are told one by one\",\n",
        "\"procedural approach\" : \"all be encodeded\",\n",
        "\"grounding\" : \"the bridge which connects the logical reasoning(Theory) and real envorinment.\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 90,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1003
        },
        "outputId": "083b09d4-0d6d-4ee3-d53c-5184ec465629"
      },
      "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": 91,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge-Based Agents. \n\nThe key concept of the knowledge based agents it the KB, which comprise of a setof sentences. (knowledge representation language). \n\n## AIMA Chapter 7.2 The Wumpus World\n The Wumpus World. \n\nWe need to notice that in the wampus world example, we still need to pay attention to PEAS, that are, Performance measure, Envoronment, Actuators, Sensors. \n\nMoreover, it is clearly a deterministic, discrete, static and single angent model.It is also, sequential, partial observable. \n\n## AIMA Chapter 7.3 Logic\n Logic. \n\nLogic is a way to express some assertion. Using sentences with concrete 'syntax'We may also need semantic which in turn defines the truth of each sentence corresponding to each possible world (more specific term will be model). \n\nWe may also need to pay attention to entaiment. So we need to introduce the concept of satisfaction, that is, we may use notation M(alpha) to denote the set of all models of alpha. We say a model m satisfies alpha when alpha is true in model m\n\nWe say A entails B, when the idea that a sentence follows logicaaly from another\nsentence. In this manner, we say A entails B is true, iff in every model A is true, B is also true. So, A is a stronger assertion, since it rules out more possibilities than B.\n\nDeriving conclusion is to carry out logical inference. We may have 'A is derived from KB by i.' Here, the searching process is no more than sounds like searching a needle A in the haystack KB. \n\nTo be noted, Soundess is a highly demandding property. Since we need to assert True, in the very end. Completeness is also desired. There's luckly procedure that can handle many knowledge base that is an complete algorithm. Another issueis grounding, see definition below./\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Propositional Logic \n\nWe have several key syntax: negation, conjunction, disjunction, implication, biconditional. In a more systematic way of the constructure is, 1) Sentence can be formed with an Atomic or a complex sentence. 2) An \nAotomicSentence is either true, false, P. 3) A complexSentence is either a sentence neg sentence, or any combination with boolean algebra conjs. \n\n TT-Entails performs a recursive enumeration of a finite space of assignments to symbols, with the time complexity being O(2^n) and space complextity is the same  as depth-first search. Every algorithm known to inference propositional logic is co-NP-complete.\n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n* **Axiom** - given without derived. (Base condition)\n* **Declarative approach** - agents are told one by one\n* **Procedural approach** - all be encodeded\n* **Grounding** - the bridge which connects the logical reasoning(Theory) and real envorinment.\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": 6208
        },
        "id": "T3cm1WV542_a",
        "outputId": "a3ff18d7-93a4-48a3-8f85-e7be73f28f6c"
      },
      "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": 94,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n What is AI \n\nThere're various definitions about what an AI is. For example, in terms of fidelityto human performance, or rationality.\n\nThere're several tests for computers to pass, like nlp, knowledge representation automated reasoning, machine learning,  (possibly) plus computer vision, robotics.\n\n\nThere're also ways that can be considered as rational but without any inference.For example, recoiling from a hot stove. \n\n\nWe do not want the agent that created by human does not pursue our objective. So, here comes a term - Value alignment problem. We want them to be provably beneficial. \n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n The Limits of AI\n\nWe have two types of AI - weak AI (acts as if they were intelligent) and strong AI (do actually has conscious thinking). We also encontered many problems that when we evaluating what an AI is, such as qualification problem and embodied cognition. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Can Machines Really Think\n\nSome philosophers say that a machine that acts intelligently is just mimicing.  \n\n## AIMA 2.1 Agents and Environments\n Agents and Environment\n\nWe talked about the difference between agent function, agent program. Also with some crucial definition regarding environment, sensors, actuators. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n The Concept of Rationality \n\n\nWe have key four things to describe the rationality of an agent. That are, performance measure, prior knowledge of environment, actions, percept sequence to date Note that, an rational agent are expected to maximize the performance measure(given a sequence of percepts and built'in knowldge). \n\n\nOmniscience, learning and autonomy. We need to pay attention to the definition of Omniscience, which is different from rationality. See definition\n\n \n\n## AIMA 2.3 The Nature of Environments\n The Nature of Environments \n\nThere're several pairs of evaluation standards regarding how to define an environment. Fully observable - Partially observable, single-agent - multiagent, Deterministic -  nondeterministic, Episodic - Sequential, Static - Dynamic, Discrete - Continuous.\n\n## AIMA 2.4 The Structure of Agents\n The structure of Agent /n\nWe need to note that agent = architecture + program. We may devide the type of agents into Simple reflex agents, Model-based reflex agents, Goal-based agents and Utility-based agents. To be more details, simple reflex agent's decision is based on the percept of current state's percept, no history considered. A model based agent need to maintain some sort of internal state. The potential models include transition model, sensor model. Goal based agents, have some information that describe situations which are desired by us. Search and planning are crucial steps in reaching the goals. A Utility based agent has a utility function. And it tries to maximize the expected utility. \n\n\nLearning agent is a special case, it has a advantage that it allows the agent to start from scratch, operating in initially unknown environment, and become more competent. The learning element absorb feedbacks from critic, then figure out how to improve next time. It also has a property called problem generator, which suggests actions leading to new and informative experience. \n\n\nAs for how the components of agent programs work, we can split the topic into many parts. atomic representation, factored representation, structured representation, localist representation, distributed representation .. \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 which aims to do the right thing (achieve the best (expected) outcome)\n* **Percept** - the content that the agent collected using sensors\n* **Value alignment problem** - values that the machine holds need to be aligned with human\n* **Agent function** - map percept sequence to action\n* **Agent program** - concrete implementation, actually running physically in system.\n* **Consequentialism** - an agent's behaviors' consequences are standards\n* **Omniscience** - knows the actual outcome of actions, impossible for most cases\n* **Deterministic** - true if current state and action determine the next state's environment\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Homework1\n\n`def concatenate(seqs):\n    return [y for x in seqs for y in x]`\n\n\n`def transpose(matrix):\n    return [[row[i] for row in matrix] for i in range(len(matrix[0]))]` \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 Solving Problems by Searching \n\nThe key factors used to defind a problem is as follows, state space, initial state, goal satets, actions, transition model, action cost function. During which process, we extract a model (mathematical description).\n\nWe have several standard search algorithm, such as best-first search which \nalways expand nodes with minimum f(n) value. \n\nWe have several standards of measuring problem-solving performance, such as, completeness, cost optimality, time complexity, space complexity.\n \n\n## AIMA Chapter 3.2 Example Problems\n \n\n## AIMA Chapter 3.3 Search Algorithms\n Search Algorithm \n\n\n  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed Search Strategies \n \nWe have breadth-first search, dijkstra's algorithm or uniform-cost search, Depth-first search, Interative deepening search, Bidirectional search. We can then summary the features of each strategies as follows, \n\nThe order is Complete? Optimal Cost? Time and Space complexity.\n\nBreadth-first (Yes, Yes, O(b^d), O(b^d)) / Uniform-Cost (Yes, Yes, O(b^(1+[C*/e])), \nO(b^(1+[C*/e]))) / Depth-First (No, No, O(b^m), O(bm)) / Depth-Limited (No, No, O(b^l), O(bl)) / Iterative Deepening (Yes, Yes, O(b^d), O(bd)) / Bidirectional (Yes, Yes, O(b^d/2), O(b^d/2)) \n\nWhere b is the branching factor, m is the maximum depth of the search tree, d is the depth of the shallowest solution, or is m when there is no solution, l is the depth limit.\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed (Heuristic) search strategies \n\nCommon strategies: greedy best-first search, A* search. In which, the greedy best-first search always first expand nodes with lowest h(n) value, so the \nevaluation function is f(n) = h(n). A* search is a best-first search uses the evaluation function f(n) = g(n) + h(n). Note that, there's a stronger property - consistency. If A* applies a consistency heuristic function, we are guaranteed that we never re-add a state to the frontier, costing both time and space. \n\nSo, if h(n) = 0, then the A* would become Uniform-cost search, we can change the coeff of h(n) to adjust our A* search to be a weighted one. \n\n\nThere are several examples for memory-bounded search. Such as, beam search, iterative-deepening A* search, Recursive best-first search.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Heuristic Functions \n\n\nThe heuristic function has a major effect on the practical performance of A* search, since a good heuristic allows A* to prune away many of the bd nodes thatan uninformed search would expand. Its quality can be expressed in terms of theeffective branching factor b*, which can be determined empirically for a problem instance by measuring the number of nodes generated by expansion, N, and the depth of the solution, then solving\nGood heuristics are those with low effective branching factor (the optimal being b* = 1).\nThe time complexity is polynomial when the search space is a tree, there is a single goal state, and the heuristic function h meets the following condition:\n\n|h(x)-h^{*}(x)|=O(\\log h^{*}(x))|h(x) - h^*(x)| = O(\\log h^*(x))where h* is the optimal heuristic, the exact cost to get from x to the goal.In other words, the error of h will not grow faster than the logarithm of theperfect heuristic\" h* that returns the true distance from x to the goal.\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Game Theory\n\nWe most focus on deterministic, two-player, turn-taking, perfect information, zero-sum games within the field of AI. We talked in this section about the elements used to define the game - Initial state, To-Move, Actions, result (transition model) terminal test / terminal states, Utility function.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Optimal Decisions in Games \n\nWe most focus on the analysis of minimax algorithm (with or without alpha-beta pruning) Suppose we have m maximum depth, and b legal moves (expanding factor). Then the time complexity of minimax is O(b^m). The space complexity is O(bm) or O(m), depending on generating all solution at once or not. \n\nAs for alpha-beta pruning, we may think alpha as 'at least' and beta as 'at most'. To be more specific, alpha is the best or highest-value chocie we have found so far at any choice point along the way for MAX. Beta is the best or lowest-value choice we have found so far at any choice point along the path for MIN. \n\nAlpha-beta pruning in theory, can reduce the time to O(b^m/2).\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic Alpha-Beta Three Search \n\nKey idea - treating nonterminal as if they were. There are several guidelines to choose the evaluation function - util(loss) <= eval <= util(win) / util(t)=eval(t) and the evaluation should be strongly possible correlated with actual chance of winning. \n\n\nThere're also some crucial concepts regarding foreard pruning. Such as beam search, late move reduction.\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic Games \n\nIt has chance nodes, however, we can just calculate the expected value for a position without knowing the exact definite value. So, this leads to the concept of expectiminimax value, which is a generalization of the minimax value for deterministic games. The worst running time is O(b^m n^m) \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Combining Beliefs and Desires under uncertainty, we encountered the concepts like utility function, expected utility given the evidance,which is just the average utility of the outcomes times the probability of which the outcome could happen, the maximum expected utility, which is basically a guidenline(formalize) that a rational agent should follow.But it does not operationalize that advice.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n six constraints that needed to be obeyed by any resonable preference relation:\nOrderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability. \n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions \n\nUtility function under the restriction of six axioms and maps from lotteries to real numbers.\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Zero-sum games** - no 'win,win situation\n* **Quiescene** - just consider certain types of moves\n* **Horizon effect** - when the opponent's behavior ultimately cause serious damages\n* **Lottery** - it describes the set of outcomes for a given action with possibility\n* **Preference elicitation** - present choice to human, use preference to create utility funcs\n* **Framing effect** - wording of a decision problem influence agent's choices\n* **Anchoring effect** - prefer relative utility judgements to abosolute judgements, first important\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Defining Constraint Satisfaction Problems\n\nCSP is problem sets in which we see how treating states as more than just little black boxex leads to new search methods and a deeper undestanding of the problem structure. \n\nThe reason in which we may turn to CSPs, is that once we find a partial solution that violates the constraints, we can immediately stop going any further, in such way, we can pay attention to those variables really matter. \n\nThe simplest kind of CSP has discrete, finite domains. We may have simplest type of constraints be unary constraint, which restrics the value of a single variable. Binary ones relates two variables. We may also have global constraint, but does not necessarily involve all the variables。 \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint Propagation: Inference in CSPs \n\nThe key idea of this process is to force local consistency. We have different types of consistency, such as node-consistent, arc consistency, Path consistency , K consistency and strongly k consistency. \n\nNote that for AC-3, checking consistency of an arc can be done in O(d^2), total worst-case time is O(cd^3). For building a strong n-consistent needs O(n^2d) time.However, this is one of the NP-complete problem, so estabilishing n-consistency have both exponential time and space complexity.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backstracking Search for CSPs \n\nWe could have n! * d^n leaves, since the branching factor at first layer is nd, next is (n-1)d. \n \nIntuitively, we have one approach to reduce the possible branching factor, that is, expand variable with fewest legal values, to say, most constrained variable, or fail-first heuristic. We may also choose another approach, which is the opposite of the MRV, say, value that rules out the fewest choices for the neighboring, which is called, least-constraining-value, via which, we can look for most likely values first.Selection should be variable - fail-first, value - fail-last. \n\n\nAnother well-known algorithm is called MAC, (maintaining arc consistency). It differs with forward checking in that, it recursively propagate constraints when changes are made to the domains of variables. \n\n\nbackjumping does exactly what farward checking does. So, we may use conflict directed backjumping to further improve the algorithm. We can summarize how to build a direct conflict set in the following way: Let Xj be the current variable, conf(Xj) be its confilict set. If every possible value for Xj fails, backjump to the most recent variable Xi in conf(Xj) and recompute the confilict set for Xi:\nconf(Xi) = conf(Xi) or conf(Xj) - Xi\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local Search for CSPs\n\nNote that a amazing heuristic is introduced in this chapter, that is, min-conflicts heuristic, which select the value that results in the minimum number of conflicts with other variables. It is roughly indepent of what the size of a problem is, it can even solve million-queens in 50 steps on average.\n\n## AIMA Chapter 6.5 The Structure of Problems\n The structure of problems\n\nTwo main topics - Cutset conditioning and Tree decomposition. \n\nThe key idea for cutset conditioning is to assign part of the values to certain variables in order to make the left variables able to form a tree. And the key idea for tree decomposition is different. \n\nThe comparison: the time complexity for both is O(d^c (n-c)d^2) and O(nd^w+1) respectively. Tree decomposition is faster in time, but requires memory exp in w. \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Assignments** - <X1 = v1>\n* **Consistent** - does not violate any constraints\n* **Complete** - every variable is assigned a value\n* **Solution** - a complete and consistent assignment\n* **Cop** - constrained optimization problem\n* **Constraint propogation** - reduce the number of legal values using constriants\n* **Minimum-remaining-values (mrv)** - choose variables with least legal values.\n* **Least-constraining-value** - choose values that rules out least possibility for nei.\n* **Forward checking** - We establish arc consistency after assigning value for X\n* **Chronological backtracking** - revisit the most recent decision point\n* **Conflict set** - a set which conflict with a certain variable (say SA)\n* **Backjumping** - jump back to the assigenment in the conflict set that is most recent\n* **Conflict-directed backjumping** - differs with pure backjumping, \n* **Constraint learning** - to find a minimum set of variable that cause a problem\n* **No-good** - variables and values of above set\n* **Constraint weighting** - focus on the search of important constraints\n* **Symmetry-breaking constraint** - ordinal variable\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge-Based Agents. \n\nThe key concept of the knowledge based agents it the KB, which comprise of a setof sentences. (knowledge representation language). \n\n## AIMA Chapter 7.2 The Wumpus World\n The Wumpus World. \n\nWe need to notice that in the wampus world example, we still need to pay attention to PEAS, that are, Performance measure, Envoronment, Actuators, Sensors. \n\nMoreover, it is clearly a deterministic, discrete, static and single angent model.It is also, sequential, partial observable. \n\n## AIMA Chapter 7.3 Logic\n Logic. \n\nLogic is a way to express some assertion. Using sentences with concrete 'syntax'We may also need semantic which in turn defines the truth of each sentence corresponding to each possible world (more specific term will be model). \n\nWe may also need to pay attention to entaiment. So we need to introduce the concept of satisfaction, that is, we may use notation M(alpha) to denote the set of all models of alpha. We say a model m satisfies alpha when alpha is true in model m\n\nWe say A entails B, when the idea that a sentence follows logicaaly from another\nsentence. In this manner, we say A entails B is true, iff in every model A is true, B is also true. So, A is a stronger assertion, since it rules out more possibilities than B.\n\nDeriving conclusion is to carry out logical inference. We may have 'A is derived from KB by i.' Here, the searching process is no more than sounds like searching a needle A in the haystack KB. \n\nTo be noted, Soundess is a highly demandding property. Since we need to assert True, in the very end. Completeness is also desired. There's luckly procedure that can handle many knowledge base that is an complete algorithm. Another issueis grounding, see definition below./\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Propositional Logic \n\nWe have several key syntax: negation, conjunction, disjunction, implication, biconditional. In a more systematic way of the constructure is, 1) Sentence can be formed with an Atomic or a complex sentence. 2) An \nAotomicSentence is either true, false, P. 3) A complexSentence is either a sentence neg sentence, or any combination with boolean algebra conjs. \n\n TT-Entails performs a recursive enumeration of a finite space of assignments to symbols, with the time complexity being O(2^n) and space complextity is the same  as depth-first search. Every algorithm known to inference propositional logic is co-NP-complete.\n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n* **Axiom** - given without derived. (Base condition)\n* **Declarative approach** - agents are told one by one\n* **Procedural approach** - all be encodeded\n* **Grounding** - the bridge which connects the logical reasoning(Theory) and real envorinment.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VQuxzhDv2rOg"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}