{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "“FINAL Template_for CIS521_midterm notes.ipynb”的副本",
      "provenance": [],
      "collapsed_sections": [
        "cw5IpDLCZa4W",
        "5yG3-YncJfTB",
        "GZZXyrV-xuAp"
      ]
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "51f83f1d-15b1-4b40-e3b1-db3bce753e33"
      },
      "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": 69,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b4d2064f-235a-47a8-f1bb-ba2b9a3b6b93"
      },
      "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": 70,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 71,
      "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 = \"\"\" Turing Test: whether it is acting humanly, a computer passes it  if a human cannot tell the response \\\n",
        "come from a person or from a computer. Computer needs to do \n",
        "1. NLP to communicate in human language \n",
        "2. knowledge representation to store what it knows or hears\n",
        "3. automtaed reasoning to answer questions and make conclusions \n",
        "4. ML to adapt to new circumstances and to detect and extrapolate patterns. \n",
        "5. CV and speech recoginition to perceive the world \n",
        "6. robotics to manipulate objects and move about for total Turing test (iteraction with objects and people in the real world)\"\"\" \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",
        "chapter27_2 = \"\"\" Can machines really think \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" agents and environment \"\"\"\n",
        "chapter2_2 = \"\"\" the concept of rationality \"\"\"\n",
        "chapter2_3 = \"\"\" Properties of task environments: \n",
        "1. Fully observable vs partially observable \n",
        "2. single-agent vs multiagent\n",
        "3. copetitive vs cooperative\n",
        "4. Deterministic vs Nondeterministic (chances without actual number, if with actual probability \n",
        "then it is stochastic) \n",
        "5. episodic vs sequential \n",
        "6. static vs dynamic (can change while an agent is deliberating) \n",
        "7. discrete vs continuous \n",
        "8. known vs unknown\"\"\"\n",
        "chapter2_4 = \"\"\" agent = architecture + program. \n",
        "1. Simple reflex agent: (selects on the current percept, ignoring the rest of percept history) respond directly to percepts\n",
        "2. Model-based reflex agents (handle partial observability, keep track of the part of the world it can't \n",
        "see now - internal state, transition model, sensor model, maintain internal state to track aspects of the world that are not\n",
        "evident in the current percept\n",
        "3. Goal-based agents: goal, search, and planning to find the action sequence that achieves the agent's goals\n",
        "4. Utility-based agents: \"the quaklity of being useful\", maximize their own expected \"happiness\"\n",
        "5. Learning agents: Leraning element, performace element, critic, problem generator, reward, penalty. All agents can improve their\n",
        "performance through learning \\n\n",
        "How the components work a)atomic, b)factoered, c) structured\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive through sensors and act in an environment through actuators\",\n",
        "\"agent_examples\" : \"humans, robots, softbots, thermostats (automatically)\",\n",
        "\"percept\" : \"the agent's perceptual inputs at any given instance (P)\",\n",
        "\"percept_sequence\" : \"the complete history of everything the agent has ever perceived\",\n",
        "\"agent function\" : \"f:P->a that maps a sequence of percept vectors P to an action a\",\n",
        "\"agent function\" : \"from a set A: P = [p0,..pt], A={a0,..ak}\",\n",
        "\"agent program\": \"runs on the physical architecture to produce f -> agent = architecture + program\",\n",
        "\"function vs program\": \"abstract mathematical description vs concerete implementation\",\n",
        "\"rational agent\": \"agent perceives its environment and behaves rationally\",\n",
        "\"rational agent\": \"for each possible P, the agent selects an action a to maximize the expected value of its performace measure\",\n",
        "\"goal of rational agent design\" : \"given a PEAS task environment, construct function f that maximizes the expected value\",\n",
        "\"goal of rational agent design\" : \"design an agent program that implements f on a particular architecture\",\n",
        "\"rationality\" : \"doing the right thing\",\n",
        "\"performance measure\" : \"an objective criterion for success of an agent's behavior given the evidence by the percept sequence\",\n",
        "\"performance measure\" : \"evaluates the behavior of the agent in an environment\",\n",
        "\"task environment\" : \"PEAS: Performance measure, Envrionment, Actuators, Sensors\",\n",
        "\"hardest environment\" : \"continuous, partially observable, stochastic, multiagent\",\n",
        "\"condition-action rule\" : \"if car-in-front-is-braking then initiate-braking\",\n",
        "\"utility function\" : \"an internalization of the performace measure\",\n",
        "\"expected utility\" : \"the utility the agent expect to derive on average gievn the prob and utilities of each outcome\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 72,
      "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": 0
        },
        "cellView": "form",
        "outputId": "ae763265-6c54-4564-e993-07047b1c1652"
      },
      "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": 73,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Turing Test: whether it is acting humanly, a computer passes it  if a human cannot tell the response come from a person or from a computer. Computer needs to do \n1. NLP to communicate in human language \n2. knowledge representation to store what it knows or hears\n3. automtaed reasoning to answer questions and make conclusions \n4. ML to adapt to new circumstances and to detect and extrapolate patterns. \n5. CV and speech recoginition to perceive the world \n6. robotics to manipulate objects and move about for total Turing test (iteraction with objects and people in the real world)\n\n## AIMA Chapter 27.1 The Limits of AI\n The limits of AI \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Can machines really think \n\n## AIMA 2.1 Agents and Environments\n agents and environment \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n the concept of rationality \n\n## AIMA 2.3 The Nature of Environments\n Properties of task environments: \n1. Fully observable vs partially observable \n2. single-agent vs multiagent\n3. copetitive vs cooperative\n4. Deterministic vs Nondeterministic (chances without actual number, if with actual probability \nthen it is stochastic) \n5. episodic vs sequential \n6. static vs dynamic (can change while an agent is deliberating) \n7. discrete vs continuous \n8. known vs unknown\n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program. \n1. Simple reflex agent: (selects on the current percept, ignoring the rest of percept history) respond directly to percepts\n2. Model-based reflex agents (handle partial observability, keep track of the part of the world it can't \nsee now - internal state, transition model, sensor model, maintain internal state to track aspects of the world that are not\nevident in the current percept\n3. Goal-based agents: goal, search, and planning to find the action sequence that achieves the agent's goals\n4. Utility-based agents: \"the quaklity of being useful\", maximize their own expected \"happiness\"\n5. Learning agents: Leraning element, performace element, critic, problem generator, reward, penalty. All agents can improve their\nperformance through learning \n\nHow the components work a)atomic, b)factoered, c) structured\n\n## Module 1 Lecture Notes\n\n```\ndef function():\n      print('hello world')\n```\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act in an environment through actuators\n* **Agent_examples** - humans, robots, softbots, thermostats (automatically)\n* **Percept** - the agent's perceptual inputs at any given instance (P)\n* **Percept_sequence** - the complete history of everything the agent has ever perceived\n* **Agent function** - from a set A: P = [p0,..pt], A={a0,..ak}\n* **Agent program** - runs on the physical architecture to produce f -> agent = architecture + program\n* **Function vs program** - abstract mathematical description vs concerete implementation\n* **Rational agent** - for each possible P, the agent selects an action a to maximize the expected value of its performace measure\n* **Goal of rational agent design** - design an agent program that implements f on a particular architecture\n* **Rationality** - doing the right thing\n* **Performance measure** - evaluates the behavior of the agent in an environment\n* **Task environment** - PEAS: Performance measure, Envrionment, Actuators, Sensors\n* **Hardest environment** - continuous, partially observable, stochastic, multiagent\n* **Condition-action rule** - if car-in-front-is-braking then initiate-braking\n* **Utility function** - an internalization of the performace measure\n* **Expected utility** - the utility the agent expect to derive on average gievn the prob and utilities of each outcome\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "Python Advantages: \\n\n",
        "1. fast development (intuitive, garbage collection: an object is deleted once unreachable) \n",
        "2. portable (runs on different platforms)\n",
        "3. various built-in types \n",
        "4. large collection of support libraries \\n\n",
        "Objects and types: \\n\n",
        "1. all data treated as objects \n",
        "2. strong typing: every object has a fixed type, interpreter does not allow thing \n",
        "incompatible with that type (no \"foo\" + 2)   \n",
        "3. dynamic typing: variables come into existence when first assigned (type(var) auto\n",
        "matically determined, type error only caught at runtime) - vs static typing:\n",
        "variables can only refer to objects of a declared type, that methods using (string[] args) signatures to enforce contracts \\n\n",
        "Syntax: \\n\n",
        "1. Literals: True/False, 1.0, 2e9 \n",
        "2. Operations: **(power), and, or, not (不用字符)3)+= (没有++、--) \\n\n",
        "Sequence types: (闭区间，开区间） [-1] 倒数第一个 可以用+\\n\n",
        "*String: \\n\n",
        "1. 用单双三引号create \n",
        "2. 用+合并 \n",
        "3. prefix r means raw \n",
        "4. immutable \n",
        "5. == checks if the same value \n",
        "6. is check if the same object\n",
        "7. x.strip() new object \n",
        "8. regular strings are unicode and use 2-byte characters\\n\n",
        "9. words=s.split(), \"_\".join(words) # join method of object \"_\"每个词都用下划线连接 \n",
        "10. immutable, cannot perform mathematical operations\n",
        "*Lists: []\n",
        "\\n\n",
        "1. Mutable ordered sequence of items of mixed types \n",
        "2. y=x[:] get a shallow copy /new object of the same value \n",
        "3. x.append() same object \n",
        "4. insert(2,'i') index2=i \n",
        "5. index('b') index of first occurence \n",
        "6. count('b) number of occurence\n",
        "7. remove('b') same \n",
        "8. li.reverse()/sort() inplace, sorted(li) returns a copy sorted\n",
        "\\n\n",
        "*Tuple: () \\n\n",
        "1. simple immutable ordered sequence of items \n",
        "2. items can be mixed types including collection \n",
        "3. can be created without parentheses (using tuple())\n",
        "\\n\n",
        "Slicing: return copy of a subsequence, [1:4]前三个, [1:-1]除了最后一个, [1:-1:2]每两个选一个, [:2]前两个\n",
        "\\n\n",
        "Collection Types: \\n\n",
        "*Dict: {} 不能用+， no duplicate keys, key immutable (can't be lists)\\n\n",
        "1. unordered, work by hashing, keys must be immutable, dict mutable\n",
        "2. constant average time add, look up, update\n",
        "3. use key to get value, but cannot use value to get key\n",
        "4. .keys()/values()/items - list of current keys\n",
        "\\n\n",
        "Functions:\n",
        "\\n\n",
        "1. return multiple values in a tuple \n",
        "2. specified by name alone, no overloading不能重名\n",
        "3. can provide default values for arguments to be optional\n",
        "4. functions can be called with arguments out of order （但要在所有其他arguments后call)\n",
        "5. dynamic scope: function sess the most current value of variables\n",
        "6. first class object, can be passed/returned/assigned to other variables, higher order functions take functions as input\n",
        "\\n\n",
        "Class:\n",
        "\\n\n",
        "1. student1.print() 等同于 Student.print(student1)\n",
        "2. subclass allow use of methods and attribute already defined in the previous, support multiple inheritance\n",
        "\\n\n",
        "Magic Methods:\n",
        "\\n\n",
        "1) _str_/_init_/_len_/_copy_/_cmp_/_add_/_neg_\n",
        "\\n\n",
        "For loops:\n",
        "\\n\n",
        "0. for <item> in <collection>: <statements>\n",
        "1. list(range(5)) - [0,1,2,3,4]\n",
        "2. list comprehensions - squares = [x*x for x in nums] # nums is a list\n",
        "2.1. li=[('a',1),('b',2),('c',7)], [n*3 for (x, n) in li if n < 7 ]=[3,6] [ expression for name in list if filter ]\n",
        "Iterators:\n",
        "\\\n",
        "1. use memory efficiently, for <item> in <iterable>: <statements>\n",
        "2. _iter_ #to be iterable, _next_ to be iterator, for char in Reverse('spam'): print(char)\n",
        "\\n\n",
        "Generators:\n",
        "\\n\n",
        "1. are iterators(with_next()_ method), using yield (automaically return a generator when called)\n",
        "2. each time we call the next method of the generator, the method run untils it encounters a yield statement, and then stops\n",
        "and returns the values that was yielded. Next time ,it resumes where it left off\n",
        "3. values are computed one at a time as they are needed, avoid storing the entire sequence in memory, \n",
        "crucial for infinite sequences, bad if individual value inspection needed\n",
        "\\n\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"can be modified or not once created\",\n",
        "}"
      ],
      "execution_count": 74,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "905e98eb-dd3d-41cb-d6fd-fd4252f5c867"
      },
      "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": 75,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nPython Advantages: \n\n1. fast development (intuitive, garbage collection: an object is deleted once unreachable) \n2. portable (runs on different platforms)\n3. various built-in types \n4. large collection of support libraries \n\nObjects and types: \n\n1. all data treated as objects \n2. strong typing: every object has a fixed type, interpreter does not allow thing \nincompatible with that type (no \"foo\" + 2)   \n3. dynamic typing: variables come into existence when first assigned (type(var) auto\nmatically determined, type error only caught at runtime) - vs static typing:\nvariables can only refer to objects of a declared type, that methods using (string[] args) signatures to enforce contracts \n\nSyntax: \n\n1. Literals: True/False, 1.0, 2e9 \n2. Operations: **(power), and, or, not (不用字符)3)+= (没有++、--) \n\nSequence types: (闭区间，开区间） [-1] 倒数第一个 可以用+\n\n*String: \n\n1. 用单双三引号create \n2. 用+合并 \n3. prefix r means raw \n4. immutable \n5. == checks if the same value \n6. is check if the same object\n7. x.strip() new object \n8. regular strings are unicode and use 2-byte characters\n\n9. words=s.split(), \"_\".join(words) # join method of object \"_\"每个词都用下划线连接 \n10. immutable, cannot perform mathematical operations\n*Lists: []\n\n\n1. Mutable ordered sequence of items of mixed types \n2. y=x[:] get a shallow copy /new object of the same value \n3. x.append() same object \n4. insert(2,'i') index2=i \n5. index('b') index of first occurence \n6. count('b) number of occurence\n7. remove('b') same \n8. li.reverse()/sort() inplace, sorted(li) returns a copy sorted\n\n\n*Tuple: () \n\n1. simple immutable ordered sequence of items \n2. items can be mixed types including collection \n3. can be created without parentheses (using tuple())\n\n\nSlicing: return copy of a subsequence, [1:4]前三个, [1:-1]除了最后一个, [1:-1:2]每两个选一个, [:2]前两个\n\n\nCollection Types: \n\n*Dict: {} 不能用+， no duplicate keys, key immutable (can't be lists)\n\n1. unordered, work by hashing, keys must be immutable, dict mutable\n2. constant average time add, look up, update\n3. use key to get value, but cannot use value to get key\n4. .keys()/values()/items - list of current keys\n\n\nFunctions:\n\n\n1. return multiple values in a tuple \n2. specified by name alone, no overloading不能重名\n3. can provide default values for arguments to be optional\n4. functions can be called with arguments out of order （但要在所有其他arguments后call)\n5. dynamic scope: function sess the most current value of variables\n6. first class object, can be passed/returned/assigned to other variables, higher order functions take functions as input\n\n\nClass:\n\n\n1. student1.print() 等同于 Student.print(student1)\n2. subclass allow use of methods and attribute already defined in the previous, support multiple inheritance\n\n\nMagic Methods:\n\n\n1) _str_/_init_/_len_/_copy_/_cmp_/_add_/_neg_\n\n\nFor loops:\n\n\n0. for <item> in <collection>: <statements>\n1. list(range(5)) - [0,1,2,3,4]\n2. list comprehensions - squares = [x*x for x in nums] # nums is a list\n2.1. li=[('a',1),('b',2),('c',7)], [n*3 for (x, n) in li if n < 7 ]=[3,6] [ expression for name in list if filter ]\nIterators:\n1. use memory efficiently, for <item> in <iterable>: <statements>\n2. _iter_ #to be iterable, _next_ to be iterator, for char in Reverse('spam'): print(char)\n\n\nGenerators:\n\n\n1. are iterators(with_next()_ method), using yield (automaically return a generator when called)\n2. each time we call the next method of the generator, the method run untils it encounters a yield statement, and then stops\nand returns the values that was yielded. Next time ,it resumes where it left off\n3. values are computed one at a time as they are needed, avoid storing the entire sequence in memory, \ncrucial for infinite sequences, bad if individual value inspection needed\n\n\n \n\n## Module 2 Definitions\n* **Mutability** - can be modified or not once created\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 = \"\"\" goal formulation, problem formulation, search, solution, execution, search problems\n",
        " ```\n",
        "function Best-FIRST-Search(problem f) returns a solution node or failure:\n",
        "  node = Node(State = problem.initial)\n",
        "  frontier = a priority queue ordered by f, whith node as an element\n",
        "  reached = a loopup table, with one entry with key problem.Initial and value node\n",
        "  while not Is-Empty(frontier):\n",
        "    node = frontier.pop()\n",
        "    if problem.is-goal(node.state) return node\n",
        "    for each child in expand (problem, node):\n",
        "      s = child.state\n",
        "      if s is not in reached or child.path-cost < reached[s].path_cost\"\n",
        "        reached[s] = child\n",
        "        add child to frontier\n",
        "  return failure\n",
        "\n",
        "function expand(problem, node) yields nodes\n",
        "  s = node.state\n",
        "  for each action in problem.actions(s):\n",
        "    s' = problem.result(s, action)\n",
        "    cost = node.path_cost + problem.action_cost(s, action, s')\n",
        "    yield Node(state = s', parent = node, action = action, path_cost = cost)\n",
        "```\n",
        "- node.action: the action that was applied to the parent’s state to generate this node; \\n\n",
        "- node.path_cost: the total cost of the path from the initial state to this node. g(n)  \\n\n",
        "- frontier: thoses states that are available for expanding(for applying legal actions to), priority queue for best-first/uniform cost search, FIFO queue for BFS, LIFO(stack) for DFS \\n\n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        " ```\n",
        "function Breadth-FIRST-Search(problem) returns a solution node or failure:\n",
        "  node = Node(problem.initial)\n",
        "  if problem.is-goal(node.state) than return node\n",
        "  frontier = a FIFO queue, with node as an element\n",
        "  reached = {problem.initial}\n",
        "  while not Is-Empty(frontier):\n",
        "    node = frontier.pop()\n",
        "    for each child in expand (problem, node):\n",
        "      s = child.state\n",
        "      if problem.is-goal(s) then return child\n",
        "      if s is not in reached then\n",
        "        add s to reached\n",
        "        add child to frontier\n",
        "  return failure\n",
        "\n",
        "function uniform-cost-search(problem) returns a solution node or failure\n",
        "  return Best-First-Search(problem, path-cost)\n",
        "```\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\" \n",
        " ```\n",
        "function Iterative-Deepening-Search(problem) returns a solution node or failure: \n",
        "  for depth = 0 to infinite:\n",
        "    result = depth-limited-search(problem, depth)\n",
        "    if result not equal to cutoff\n",
        "      return result\n",
        "function Depth-limited-search(problem, l) returns a solution node or failure:\n",
        "  frontier = a LIFO queue, with node(state.initial) as an element\n",
        "  result = failure\n",
        "  while not Is-Empty(frontier):\n",
        "    node = frontier.pop()\n",
        "    if problem.is-goal(node.state) then return node\n",
        "    if depth(node) > l then:\n",
        "        result = cutoff\n",
        "    else if not is-cycle(node):\n",
        "      for each child in expand(problem, node):\n",
        "        add child to frontier\n",
        "  return result\n",
        "```\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "Uninformed:\\n\n",
        "Best-First Search \n",
        "\\n\n",
        "selects node for expansion using an evaluation function\n",
        "\\n\n",
        "Breadth-First search:\n",
        "\\n\n",
        "BFS, expands the shallowest node first. is a best-first-search where f(n) is the depth of the node \\n\n",
        "use if possible infinite paths / some solutions have short paths / can quickly discard unlikely paths \\n\n",
        "1. complete \\n\n",
        "2. optimal for unit action costs\\n\n",
        "3. exponential space complexity (bad), O(b^d) for searching a uniform tree where every state has b successors and at depth d\\n\n",
        "4. time complexity: O(b^d)\\n\n",
        "\\n\n",
        "Uniform-cost search:\n",
        "\\n\n",
        "expands node with lowest path cost g(n) - the cost of the path from the root to the current node.\\n\n",
        "Dijkstra is an uniform-cost search without a goal \\n\n",
        "test for goals only when it expands a node, not when it generates a node \\n\n",
        "a tree search algorithm used for traversing or searching a weighted tree, tree stucture, or graph \\n\n",
        "1. complete \\n\n",
        "2. optimal for general action costs \\n\n",
        "3. O(b^ 1+C*/) \\n\n",
        "4. difference from BFS: test if a node is a goal state when it is selected for expansion, not when it is added to the frontier,\n",
        "updates a node on the frontier if a better path to the same state is found, always enqueues a node before checking if it is a goal.\n",
        "Instead of exploring all possible paths equally, it favors lower cost paths. Prioritize which paths to explore\n",
        "\\n\n",
        "Depth-first Search:\n",
        "\\n\n",
        "expands the deepest unexpanded node first, \\n\n",
        "use with restricted memory / many possible solutions with long and wrong paths are usually terminated quickly / search can be fine-tuned quickly\n",
        "1. not complete unless m is bounded\n",
        "2. not optimal\n",
        "3. linear space complexity (depth-limited search adds a depth bound), O(b*m) space\n",
        "4. time complexity: O(b^m); terrible if m >> d \\n\n",
        "Depth-Limit Search: \\n\n",
        "DFS with depth limit l, node at depth l have no successors, no infinite-path probem\n",
        "1. if l = d by luck, then optimal. if l<d then incomplete, if l>d then not optimal (not complete nor optimal)\n",
        "2. time: O(b^l)\n",
        "3. space: O(bl) (good)\n",
        "\\n\n",
        "Iterative Deepening Search:\n",
        "\\n\n",
        "calls dfs with increasing depth limit until reach the goal\n",
        "1. complete when full cycle checking (no infinite paths) is done, goal is always found at depth d, the depth of the shallowest goal-node\n",
        "2. optimal for unit action costs (step cost is 1) good\n",
        "3. BFS comparable time complexity, O(b^d) \n",
        "4. linear space complexity, O(bd) (good)\n",
        "\\n\n",
        "Bidirectional Search:\n",
        "\\n\n",
        "expands two frontiers, one around the initial state and goal state. stop when the two meets\n",
        "1. complete\n",
        "2. optimal\n",
        "3. O(b^d/2) for time and space\n",
        "\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {   \n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",  \n",
        "\"solution\": \"a sequence of actions that reaches the goal\",  \n",
        "\"Search\": \"finding a solution\",\n",
        "\"strategy\":\"order of tree expansion\",\n",
        "\"Search algorithm\": \"takes a search problem as input and returns a solution, or an indication of failure\",\n",
        "\"node\": \"corresponding to a state in the state space\",\n",
        "\"edge\": \"actions\",\n",
        "\"root\": \"initial states\",\n",
        "\"execution\": \"execute the actions in the solution one at a time\",\n",
        "\"search problems\": \"5 parts below\",\n",
        "\"the initial state\": \"\",\n",
        "\"a set of actions\": \"5 parts below\",\n",
        "\"a transition model\": \"describing the results of those actions\",\n",
        "\"a set of goal states\": \"5 parts below\",\n",
        "\"an action cost function\": \"5 parts below\",\n",
        "\"state space graph\": \"environment of the problem\",\n",
        "\"path\": \"a sequence of actions\",\n",
        "\"cycle\": \"a special case of redudant path, has a repeated state in the search tree\",\n",
        "\"graph search\" : \"checks for redudant path\",\n",
        "\"tree-like search\": \"does not check for redudant paths, save memory space\",\n",
        "\"solution\": \"a path through the state space from the initial to the goal\",\n",
        "\"search algorithm\": \"judged by completeness, cost optimality, time complexity, and space complexity\",\n",
        "\"completeness\":\"guaranteed to find a solution when there is one, and to correctly report failure when there is not\",\n",
        "\"optimality\":\" find a solution with the lowest path cost of all solutions\",\n",
        "\"time complexity\":\"How long does it take to find a solution, number of states and actions considered\",\n",
        "\"space complexity\":\"memory needed to perform\",\n",
        "\"systematic\":\"make sure it can eventually reach any state that is connetced to the initial in an infinite state space\",\n",
        "\"|V|\":\"the number of vertices (state nodes)\",\n",
        "\"|E|\":\"the number of edges (distinct state\\action pairs)\",\n",
        "\"d, depth\":\"number of actions in an optimal solution/depth of the solution/shallowest goal node\",\n",
        "\"m\":\"maximum number of actions in any path/maximum depth of the search tree\",\n",
        "\"b, branching factor\":\"number of successors of a node that needed to be considered\",\n",
        "\"Uninformed search\": \"have access only to the problem definition\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 76,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "09b2023e-582e-495d-d72b-f76a24cdf6b5"
      },
      "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": 77,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n goal formulation, problem formulation, search, solution, execution, search problems\n ```\nfunction Best-FIRST-Search(problem f) returns a solution node or failure:\n  node = Node(State = problem.initial)\n  frontier = a priority queue ordered by f, whith node as an element\n  reached = a loopup table, with one entry with key problem.Initial and value node\n  while not Is-Empty(frontier):\n    node = frontier.pop()\n    if problem.is-goal(node.state) return node\n    for each child in expand (problem, node):\n      s = child.state\n      if s is not in reached or child.path-cost < reached[s].path_cost\"\n        reached[s] = child\n        add child to frontier\n  return failure\n\nfunction expand(problem, node) yields nodes\n  s = node.state\n  for each action in problem.actions(s):\n    s' = problem.result(s, action)\n    cost = node.path_cost + problem.action_cost(s, action, s')\n    yield Node(state = s', parent = node, action = action, path_cost = cost)\n```\n- node.action: the action that was applied to the parent’s state to generate this node; \n\n- node.path_cost: the total cost of the path from the initial state to this node. g(n)  \n\n- frontier: thoses states that are available for expanding(for applying legal actions to), priority queue for best-first/uniform cost search, FIFO queue for BFS, LIFO(stack) for DFS \n\n \n\n## AIMA Chapter 3.2 Example Problems\n\n ```\nfunction Breadth-FIRST-Search(problem) returns a solution node or failure:\n  node = Node(problem.initial)\n  if problem.is-goal(node.state) than return node\n  frontier = a FIFO queue, with node as an element\n  reached = {problem.initial}\n  while not Is-Empty(frontier):\n    node = frontier.pop()\n    for each child in expand (problem, node):\n      s = child.state\n      if problem.is-goal(s) then return child\n      if s is not in reached then\n        add s to reached\n        add child to frontier\n  return failure\n\nfunction uniform-cost-search(problem) returns a solution node or failure\n  return Best-First-Search(problem, path-cost)\n```\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \n ```\nfunction Iterative-Deepening-Search(problem) returns a solution node or failure: \n  for depth = 0 to infinite:\n    result = depth-limited-search(problem, depth)\n    if result not equal to cutoff\n      return result\nfunction Depth-limited-search(problem, l) returns a solution node or failure:\n  frontier = a LIFO queue, with node(state.initial) as an element\n  result = failure\n  while not Is-Empty(frontier):\n    node = frontier.pop()\n    if problem.is-goal(node.state) then return node\n    if depth(node) > l then:\n        result = cutoff\n    else if not is-cycle(node):\n      for each child in expand(problem, node):\n        add child to frontier\n  return result\n```\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n\n\n\n## Module 3 Lecture Notes\n \nUninformed:\n\nBest-First Search \n\n\nselects node for expansion using an evaluation function\n\n\nBreadth-First search:\n\n\nBFS, expands the shallowest node first. is a best-first-search where f(n) is the depth of the node \n\nuse if possible infinite paths / some solutions have short paths / can quickly discard unlikely paths \n\n1. complete \n\n2. optimal for unit action costs\n\n3. exponential space complexity (bad), O(b^d) for searching a uniform tree where every state has b successors and at depth d\n\n4. time complexity: O(b^d)\n\n\n\nUniform-cost search:\n\n\nexpands node with lowest path cost g(n) - the cost of the path from the root to the current node.\n\nDijkstra is an uniform-cost search without a goal \n\ntest for goals only when it expands a node, not when it generates a node \n\na tree search algorithm used for traversing or searching a weighted tree, tree stucture, or graph \n\n1. complete \n\n2. optimal for general action costs \n\n3. O(b^ 1+C*/) \n\n4. difference from BFS: test if a node is a goal state when it is selected for expansion, not when it is added to the frontier,\nupdates a node on the frontier if a better path to the same state is found, always enqueues a node before checking if it is a goal.\nInstead of exploring all possible paths equally, it favors lower cost paths. Prioritize which paths to explore\n\n\nDepth-first Search:\n\n\nexpands the deepest unexpanded node first, \n\nuse with restricted memory / many possible solutions with long and wrong paths are usually terminated quickly / search can be fine-tuned quickly\n1. not complete unless m is bounded\n2. not optimal\n3. linear space complexity (depth-limited search adds a depth bound), O(b*m) space\n4. time complexity: O(b^m); terrible if m >> d \n\nDepth-Limit Search: \n\nDFS with depth limit l, node at depth l have no successors, no infinite-path probem\n1. if l = d by luck, then optimal. if l<d then incomplete, if l>d then not optimal (not complete nor optimal)\n2. time: O(b^l)\n3. space: O(bl) (good)\n\n\nIterative Deepening Search:\n\n\ncalls dfs with increasing depth limit until reach the goal\n1. complete when full cycle checking (no infinite paths) is done, goal is always found at depth d, the depth of the shallowest goal-node\n2. optimal for unit action costs (step cost is 1) good\n3. BFS comparable time complexity, O(b^d) \n4. linear space complexity, O(bd) (good)\n\n\nBidirectional Search:\n\n\nexpands two frontiers, one around the initial state and goal state. stop when the two meets\n1. complete\n2. optimal\n3. O(b^d/2) for time and space\n\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Solution** - a path through the state space from the initial to the goal\n* **Search** - finding a solution\n* **Strategy** - order of tree expansion\n* **Search algorithm** - takes a search problem as input and returns a solution, or an indication of failure\n* **Node** - corresponding to a state in the state space\n* **Edge** - actions\n* **Root** - initial states\n* **Execution** - execute the actions in the solution one at a time\n* **Search problems** - 5 parts below\n* **The initial state** - \n* **A set of actions** - 5 parts below\n* **A transition model** - describing the results of those actions\n* **A set of goal states** - 5 parts below\n* **An action cost function** - 5 parts below\n* **State space graph** - environment of the problem\n* **Path** - a sequence of actions\n* **Cycle** - a special case of redudant path, has a repeated state in the search tree\n* **Graph search** - checks for redudant path\n* **Tree-like search** - does not check for redudant paths, save memory space\n* **Search algorithm** - judged by completeness, cost optimality, time complexity, and space complexity\n* **Completeness** - guaranteed to find a solution when there is one, and to correctly report failure when there is not\n* **Optimality** -  find a solution with the lowest path cost of all solutions\n* **Time complexity** - How long does it take to find a solution, number of states and actions considered\n* **Space complexity** - memory needed to perform\n* **Systematic** - make sure it can eventually reach any state that is connetced to the initial in an infinite state space\n* **|v|** - the number of vertices (state nodes)\n* **|e|** - the number of edges (distinct state\u0007ction pairs)\n* **D, depth** - number of actions in an optimal solution/depth of the solution/shallowest goal node\n* **M** - maximum number of actions in any path/maximum depth of the search tree\n* **B, branching factor** - number of successors of a node that needed to be considered\n* **Uninformed search** - have access only to the problem definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        " ```\n",
        "function Greedy-Best-FIRST-Search:\n",
        "  frontier = PQ()\n",
        "  frontier.put(start, 0)\n",
        "  came_from = {}\n",
        "  came_from[start] = None\n",
        "  while not frontier.empty():\n",
        "    current = frontie.get()\n",
        "    if current == goal:\n",
        "        break\n",
        "      for next in graph.neighbors(current):\n",
        "        if next not in came_from:\n",
        "          priority = heuristic(goal, next)\n",
        "          frontier.put(next, priority)\n",
        "          came_from[next] = current\n",
        "```\n",
        " ```\n",
        "BFS in 10 lines:\n",
        "  frontier = Queue()\n",
        "  frontier.put(start, 0)\n",
        "  visited = {}\n",
        "  visited[start] = True\n",
        "  while not frontier.empty():\n",
        "    current = frontie.get()\n",
        "    for next in graph.neighbors(current):\n",
        "      if next not in visited:\n",
        "          frontier.put(next)\n",
        "          visited[next] = True\n",
        "```\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        " ```\n",
        "Finding the shortest path:\n",
        "  frontier = Queue()\n",
        "  frontier.put(start, 0)\n",
        "  came_from = {}\n",
        "  came_from[start] = None\n",
        "  while not frontier.empty():\n",
        "    current = frontie.get()\n",
        "    for next in graph.neighbors(current):\n",
        "      if next not in came_from:\n",
        "          frontier.put(next)\n",
        "          came_from[next] = current\n",
        "# Backtrack\n",
        "  current = goal\n",
        "  path = []\n",
        "  while current != start:\n",
        "    path.append(current)\n",
        "    current = came_from[current]\n",
        "  path.append(start)\n",
        "  path.reverse()\n",
        " ```\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "Informed: \\n\n",
        "Greedy best-first search:\n",
        "\\n\n",
        " expands nodes with minimal h(n), f(n) = h(n), completely ignores g(n) \\n\n",
        " Manhattan distance: 两点之间的距离\n",
        " 1. not complete, can get stuck in loops\n",
        " 2. not optimal, often efficient\n",
        "\\n\n",
        "A* search:\n",
        "\\n\n",
        "best known form of best-first search, expands node with minimal f(n) = g(n) + h(n)\n",
        "1. complete\n",
        "2. optimal when h(n) is admissible\n",
        "3. space complexity still an issue O(b^d)\n",
        "4. expands mainly towards the goal, but does hedge its bets to ensure optimality, while uniform-cost expands equally in all \"directions\"\n",
        "\\n\n",
        "Bidirectional A* search:\n",
        "\\n\n",
        "sometimes more efficient than A*\n",
        "\\n\n",
        "IDA* iterative deepening A* search:\n",
        "\\n\n",
        "better the space complexity\n",
        "\\n\n",
        "RBFS (recursive best-first search) & SMA*(simplified memory-bounded A*):\n",
        "\\n\n",
        "1. robust\n",
        "2. optimal\n",
        "3. use limited amounts of memory, can solve A* run out of memory with enough time (space efficient)\n",
        "\\n\n",
        "Beam Search:\n",
        "\\n\n",
        "puts a limit on the size of the frontier\n",
        "1. incomplete\n",
        "2. suboptimal\n",
        "3. but reasonably good solutions and run faster than complete searches\n",
        "\\n\n",
        "Weighted A* search:\n",
        "\\n\n",
        "focuses the search towards a goal, expanding fewer nodes (expands for nodes which minimizes f(n) = g(n) + W*h(n))\n",
        "1. complete\n",
        "2. not optimal\n",
        "\\n\n",
        "Heuuristics function:\n",
        "h2 dominates h1: if h2(n) >= h1(n) for all n (both admissble) => \\n\n",
        "h2 more accurate, therefore better for search. \\n\n",
        "Domination translates directly into efficiency: A* using h2 will never expand more nodes than A* using h1 \\n\n",
        "In 8 puzzle, hmd dominates hoop. \\n\n",
        "A heuristic h is admissible if: 0 <= h(n) <= h*(n) where h*(n) is the true cost to a nearest goal \\n\n",
        "heuristic function with branching factor (b): the less b is, the better as the branching fatocr denots how many\n",
        "new nodes are added for each node as we increases depth by one. b*=1.5 at four means we only need to explore 1.5^4 = 5 nodes\n",
        "\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Informed search\": \"have access to the problem definition and heuristic function h(n)\",\n",
        "\"h(n)\":\"estimates the cost of the cheapest path from the state at the current node n to a goal node\",\n",
        "\"h*(n)\":\"the unachievable Oracle heuristic, the true distance from n to goal\",\n",
        "\"admiisible/optimistic h(n)\":\"never overestimate the cost to reach the goal\",\n",
        "\"relax problem\" : \"a problem with fewer restrictions on the actions than the original\", \n",
        "\"admissible heuristic\" : \"the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\",     \n",
        "\"hoop(n) for 8 puzzle\": \"number of out of place tiles, gives shorest solution if tile can move anywhere\",\n",
        "\"hmd(n) for 8 puzzle\": \"number of moves from desired location of each tile, shortest if tile can move to any adjacent square\",\n",
        "\"h2 dominates h1\":\"if h2(n) >= h1(n) for all n (both admissble), h2 more accurate\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 78,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "36669bb8-3158-4538-fac8-c8b539eee6b2"
      },
      "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": 79,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n ```\nfunction Greedy-Best-FIRST-Search:\n  frontier = PQ()\n  frontier.put(start, 0)\n  came_from = {}\n  came_from[start] = None\n  while not frontier.empty():\n    current = frontie.get()\n    if current == goal:\n        break\n      for next in graph.neighbors(current):\n        if next not in came_from:\n          priority = heuristic(goal, next)\n          frontier.put(next, priority)\n          came_from[next] = current\n```\n ```\nBFS in 10 lines:\n  frontier = Queue()\n  frontier.put(start, 0)\n  visited = {}\n  visited[start] = True\n  while not frontier.empty():\n    current = frontie.get()\n    for next in graph.neighbors(current):\n      if next not in visited:\n          frontier.put(next)\n          visited[next] = True\n```\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \n ```\nFinding the shortest path:\n  frontier = Queue()\n  frontier.put(start, 0)\n  came_from = {}\n  came_from[start] = None\n  while not frontier.empty():\n    current = frontie.get()\n    for next in graph.neighbors(current):\n      if next not in came_from:\n          frontier.put(next)\n          came_from[next] = current\n# Backtrack\n  current = goal\n  path = []\n  while current != start:\n    path.append(current)\n    current = came_from[current]\n  path.append(start)\n  path.reverse()\n ```\n\n\n\n## Module 4 Lecture Notes\n \nInformed: \n\nGreedy best-first search:\n\n\n expands nodes with minimal h(n), f(n) = h(n), completely ignores g(n) \n\n Manhattan distance: 两点之间的距离\n 1. not complete, can get stuck in loops\n 2. not optimal, often efficient\n\n\nA* search:\n\n\nbest known form of best-first search, expands node with minimal f(n) = g(n) + h(n)\n1. complete\n2. optimal when h(n) is admissible\n3. space complexity still an issue O(b^d)\n4. expands mainly towards the goal, but does hedge its bets to ensure optimality, while uniform-cost expands equally in all \"directions\"\n\n\nBidirectional A* search:\n\n\nsometimes more efficient than A*\n\n\nIDA* iterative deepening A* search:\n\n\nbetter the space complexity\n\n\nRBFS (recursive best-first search) & SMA*(simplified memory-bounded A*):\n\n\n1. robust\n2. optimal\n3. use limited amounts of memory, can solve A* run out of memory with enough time (space efficient)\n\n\nBeam Search:\n\n\nputs a limit on the size of the frontier\n1. incomplete\n2. suboptimal\n3. but reasonably good solutions and run faster than complete searches\n\n\nWeighted A* search:\n\n\nfocuses the search towards a goal, expanding fewer nodes (expands for nodes which minimizes f(n) = g(n) + W*h(n))\n1. complete\n2. not optimal\n\n\nHeuuristics function:\nh2 dominates h1: if h2(n) >= h1(n) for all n (both admissble) => \n\nh2 more accurate, therefore better for search. \n\nDomination translates directly into efficiency: A* using h2 will never expand more nodes than A* using h1 \n\nIn 8 puzzle, hmd dominates hoop. \n\nA heuristic h is admissible if: 0 <= h(n) <= h*(n) where h*(n) is the true cost to a nearest goal \n\nheuristic function with branching factor (b): the less b is, the better as the branching fatocr denots how many\nnew nodes are added for each node as we increases depth by one. b*=1.5 at four means we only need to explore 1.5^4 = 5 nodes\n\n\n\n\n## Module 4 Definitions\n* **Informed search** - have access to the problem definition and heuristic function h(n)\n* **H(n)** - estimates the cost of the cheapest path from the state at the current node n to a goal node\n* **H*(n)** - the unachievable Oracle heuristic, the true distance from n to goal\n* **Admiisible/optimistic h(n)** - never overestimate the cost to reach the goal\n* **Relax problem** - a problem with fewer restrictions on the actions than the original\n* **Admissible heuristic** - the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n* **Hoop(n) for 8 puzzle** - number of out of place tiles, gives shorest solution if tile can move anywhere\n* **Hmd(n) for 8 puzzle** - number of moves from desired location of each tile, shortest if tile can move to any adjacent square\n* **H2 dominates h1** - if h2(n) >= h1(n) for all n (both admissble), h2 more accurate\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "stochastic & no perfect information games: 卡牌游戏 \\n\n",
        "continuous & no turn games: real time strategy games \\n\n",
        "GAME setup \\n\n",
        "Two players MAX and MIN, MAX moves first \\n\n",
        "takes turns until the game is over \\n\n",
        "MAX uses search tree to determine next move\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "\n",
        "- Heuristic Alpha-Beta:\n",
        "  - evaluation function : \n",
        "    - replaces the utility function \n",
        "    - estimates the value(the utility) of non-terminal nodes\n",
        "    - the evaluation function should be applied only to positions that are quiescent\n",
        "      - the eval(s, p) in a non-terminal state given an adversarial game \n",
        "        - returns n estimate of the expected utility of some state s, for player p. \n",
        "        - For terminal states, the evaluation function is exactly equal to the utility.\n",
        "    - a move is quiescent if: \n",
        "      - there is no pending move that would wildly swing the valuation. \n",
        "      - For example, if a move in chess would allow your queen to be eaten in the next turn, it would not be quiescent.\n",
        "    - horizon effect：\n",
        "      - when an agent try to erroneously delay the inevitable\n",
        "      - mitigate the horizon effect\n",
        "        - allow signular extensions, moves that are clearly better than all other moves in a given position\n",
        "      \n",
        "  - replaces the terminal test with a cutoff test (which decides when to cut off the search)\n",
        "  - forward pruning: prunes moves that appear to be bad moves\n",
        "    - E.g. Beam Search\n",
        "- MCTS:\n",
        "  - evaluates states not by applying a heuristic function\n",
        "  - but by playing out the game all the way to the end and using the rules of the game to see who won\n",
        "  - Since the moves chosen during the playout may not have been optimal moves, \n",
        "    - the process is repeated multiple times and the evaluation is an average of the results.\n",
        "  - evaluating an action:\n",
        "    - Repeatedly play the game from that state and take the average of the results\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "- Given a game where the outcome of a player making a move is deterministic, \n",
        "inimax and Expectiminimax will always produce the same solutions.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Adversarial Search: \n",
        "\\n\n",
        "All play is computed from MAX's vantage point: \\n\n",
        "When MAX moves, MAX attempts to MAXIMIZE MAX's outcome \\n\n",
        "When MIN moves, MIN attempts to MINIMIZE MAX's outcome \\n\n",
        "Typically assume MAX moves first (label root level 0 MAX), even levels for MAX, odd levels for MIN \\n\n",
        "Evaluation function f(n): \\n\n",
        "- evaluates how good a board position is (represeneted as a node in search tree)\\n\n",
        "- f(n) > 0 if MAX is winning in position n \\n\n",
        "- f(n) = 0 if posistion n is tied \\n\n",
        "- f(n) < 0 if MIN is winning in position n \\n\n",
        "- f(b) = (sum of A's piece values) - (sum of B's piece values) for chess games -> f(n) can be a weighted linear function\n",
        "\\n\n",
        "Minimax Rule: \\n\n",
        "1. make the best move for MAX assuming that Min always replies with the best moves for MIN \n",
        "2. Easily computer by a recursive process such that \n",
        "- The backend-up value of each node in the tree is determined by the values of its children\n",
        "- For a MAX node, the backed-up value is the maximum of the values of its children (i.e. the best for MAX)\n",
        "- For a MIN node, the backed-up value is the minimum of the values of its children (i.e. the best for MIN) \\n\n",
        "Minimax Procedure:\n",
        "- start with the current position as a MAX node\n",
        "- expand the game tree a fixed number of ply\n",
        "- apply the evaluation function to the leaf positions\n",
        "- calculate back-up values bottom-up\n",
        "- pick the moves assigned to MAX at the root\n",
        "- wait for MIN to respond\n",
        "\\n\n",
        "MiniMax algorithm:\n",
        "- the value of a node is the optimal value of its children. (highest value for max, lowest for min)\n",
        "- time complexity: O(b^m), where b is the number of legal moves at each node, m is the maximum depth of the tree \\n\n",
        "```\n",
        "def max-value(state):\n",
        "   if the state is a terminal state:\n",
        "        return the state’s utility\n",
        "   initialize v = -∞\n",
        "   for each successor of state:\n",
        "     v = max(v, min-value(successor))\n",
        "   return v\n",
        "```\n",
        "```\n",
        "def min-value(state):\n",
        "   if the state is a terminal state:\n",
        "        return the state’s utility\n",
        "   initialize v = +∞\n",
        "   for each successor of state:\n",
        "     v = min(v, max-value(successor))\n",
        "   return v\n",
        "```\n",
        "\\n\n",
        "Alpha-Beta Pruning: \\n\n",
        "- computes the same optimal moves as minimax, but achieves much greater efficiency by eliminating subtrees that are provably irrelevant.\n",
        "- α: MAX’s current lower bound on MAX’s outcome: Max's best option along path to root\n",
        "  - -infinite at first\n",
        "  - MAX will never allow a move that could lead to a worse case than α\n",
        "    - When evaluating a MIN Node, a value 𝑣 ≤ 𝛼 is found 剪枝不update alpha和beta\n",
        "      - MAX will never select that MIN node\n",
        "- β: MIN’s current upper bound on MIN’s outcome: MIN's best option along path to root\n",
        "  - +infinite at first\n",
        "  - MIN will never allow a move that could lead to a better score (for MAX) than β\n",
        "    - When evaluating a MAX node: a value 𝑣 ≥ 𝛽 is backed-up 剪枝不update alpha和beta\n",
        "      - MIN will never select that MAX node\n",
        "- Alpha-beta search computes the same optimal moves as minimax\n",
        "  - if we generates the worst successors first, than we don't get to prune anything: the efficiency is highly dependent on the order \n",
        "  in which the states are exmained\n",
        "  - if we evaluate nodes in the optimal order, the running time of Alpha-Beta pruning is O(b^m/2)\n",
        "    - with random move ordering and moderate b, the total number of nodes examined will be roughly O(b^3m/4)\n",
        "- Type A & Type B\n",
        "  - For games with a large search space, it is not feasible to search the whole tree. \n",
        "  As such, we have to make tradeoffs about what part of the tree to search\n",
        "\\n\n",
        "Expectimax Search:\n",
        "- an extension to the minimax algorithm that \n",
        "  - evaluates a chance node by taking the average utility of all its children, weighted by the probability of each child.\n",
        "- values now reflect average-case (Expectimax) outcomes\n",
        "- handle game of chances\n",
        "- uses expected value at chance nodes\n",
        "\\n\n",
        "```\n",
        "def value(state):\n",
        "  if the state is a terminal state: return the state’s utility if the next agent is MAX: return max-value(state)\n",
        "  if the next agent is EXP: return exp-value(state)\n",
        "```\n",
        "```\n",
        "def max-value(state):\n",
        "  initialize v = -∞\n",
        "  for each successor of state:\n",
        "     v = max(v, value(successor))\n",
        "  return v\n",
        "```\n",
        "```\n",
        "def exp-value(state):\n",
        "  initialize v = 0\n",
        "  for each successor of state:\n",
        "    p = probability(successor)\n",
        "    v += p * value(successor)\n",
        "  return v\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"game\" : \"initial state, the legal actions in each state, the result of each action +\",   \n",
        "\"game\":\"a terminal test, a utility function that applies to terminal state for winner and final score\",\n",
        "\"game differ from search problems\": \"games have multiple agents\",\n",
        "\"perfect information\" :\"a synonym for fully observable\",\n",
        "\"zero-sum\":\"what is good for one player is just as bad for the other\",\n",
        "\"utility function U(s)\":\"gives the payoff for each player in terminal state s\",\n",
        "\"game environment static\": \"no change while an agent is deliberating\",\n",
        "\"discrete\": \"a finite set of percepts and actions\",\n",
        "\"fully observable/perfect information\":\"an agent's sensors give it the complete state of the environment\",\n",
        "\"strategic\": \"The next state is determined by the current state and the\",\n",
        "\"strategic\" :\" action executed by the agent and the actions of one other agent.\",\n",
        "\"minmax search algorithms solves by DFS\": \"two-player, discrete, deterministic(vs stochastic), turn-making zero-sum games with perfect information\",\n",
        "\"ply\":\"Alternate MAX/MIN labels at each successive tree level (ply)\",\n",
        "\"evaluation function f\": \"assigns real-number scores to `board positions’ without reference to path (based on static features)\",\n",
        "\"each node's minimax value\": \"the best achievable utility against a rational(optimal) adversary\",\n",
        "\"random value\":\"an event whose outcome is unknown\",\n",
        "\"probability distribution\":\"assignment of weights to outcomes\",\n",
        "\"expected value of a function of a random variable\": \"average, weighted by the probability distribution over outcomes\",\n",
        "\"Type A strategy\": \"considers all possible moves to a certain depth in the search tree, then use h(n) to estimate the utility of state at depth\",\n",
        "\"Type A strategy\": \"explores a wide but shallow portion of the tree\",\n",
        "\"Type B strategy\": \"ignores moves that look bad, follows promisiing lines as far as possible\",\n",
        "\"Type B strategy\": \"deep but narrow portion of the trees\",\n",
        "\"MCTS\":\"Monte Carlo tree search\",\n",
        "\"MCTS\":\"playing the game to the end while randomly selecting moves\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 80,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4aa887f8-c097-4fd4-c7ca-468d0e370e3c"
      },
      "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": 81,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nstochastic & no perfect information games: 卡牌游戏 \n\ncontinuous & no turn games: real time strategy games \n\nGAME setup \n\nTwo players MAX and MIN, MAX moves first \n\ntakes turns until the game is over \n\nMAX uses search tree to determine next move\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n\n- Heuristic Alpha-Beta:\n  - evaluation function : \n    - replaces the utility function \n    - estimates the value(the utility) of non-terminal nodes\n    - the evaluation function should be applied only to positions that are quiescent\n      - the eval(s, p) in a non-terminal state given an adversarial game \n        - returns n estimate of the expected utility of some state s, for player p. \n        - For terminal states, the evaluation function is exactly equal to the utility.\n    - a move is quiescent if: \n      - there is no pending move that would wildly swing the valuation. \n      - For example, if a move in chess would allow your queen to be eaten in the next turn, it would not be quiescent.\n    - horizon effect：\n      - when an agent try to erroneously delay the inevitable\n      - mitigate the horizon effect\n        - allow signular extensions, moves that are clearly better than all other moves in a given position\n      \n  - replaces the terminal test with a cutoff test (which decides when to cut off the search)\n  - forward pruning: prunes moves that appear to be bad moves\n    - E.g. Beam Search\n- MCTS:\n  - evaluates states not by applying a heuristic function\n  - but by playing out the game all the way to the end and using the rules of the game to see who won\n  - Since the moves chosen during the playout may not have been optimal moves, \n    - the process is repeated multiple times and the evaluation is an average of the results.\n  - evaluating an action:\n    - Repeatedly play the game from that state and take the average of the results\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n- Given a game where the outcome of a player making a move is deterministic, \ninimax and Expectiminimax will always produce the same solutions.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n\nAdversarial Search: \n\n\nAll play is computed from MAX's vantage point: \n\nWhen MAX moves, MAX attempts to MAXIMIZE MAX's outcome \n\nWhen MIN moves, MIN attempts to MINIMIZE MAX's outcome \n\nTypically assume MAX moves first (label root level 0 MAX), even levels for MAX, odd levels for MIN \n\nEvaluation function f(n): \n\n- evaluates how good a board position is (represeneted as a node in search tree)\n\n- f(n) > 0 if MAX is winning in position n \n\n- f(n) = 0 if posistion n is tied \n\n- f(n) < 0 if MIN is winning in position n \n\n- f(b) = (sum of A's piece values) - (sum of B's piece values) for chess games -> f(n) can be a weighted linear function\n\n\nMinimax Rule: \n\n1. make the best move for MAX assuming that Min always replies with the best moves for MIN \n2. Easily computer by a recursive process such that \n- The backend-up value of each node in the tree is determined by the values of its children\n- For a MAX node, the backed-up value is the maximum of the values of its children (i.e. the best for MAX)\n- For a MIN node, the backed-up value is the minimum of the values of its children (i.e. the best for MIN) \n\nMinimax Procedure:\n- start with the current position as a MAX node\n- expand the game tree a fixed number of ply\n- apply the evaluation function to the leaf positions\n- calculate back-up values bottom-up\n- pick the moves assigned to MAX at the root\n- wait for MIN to respond\n\n\nMiniMax algorithm:\n- the value of a node is the optimal value of its children. (highest value for max, lowest for min)\n- time complexity: O(b^m), where b is the number of legal moves at each node, m is the maximum depth of the tree \n\n```\ndef max-value(state):\n   if the state is a terminal state:\n        return the state’s utility\n   initialize v = -∞\n   for each successor of state:\n     v = max(v, min-value(successor))\n   return v\n```\n```\ndef min-value(state):\n   if the state is a terminal state:\n        return the state’s utility\n   initialize v = +∞\n   for each successor of state:\n     v = min(v, max-value(successor))\n   return v\n```\n\n\nAlpha-Beta Pruning: \n\n- computes the same optimal moves as minimax, but achieves much greater efficiency by eliminating subtrees that are provably irrelevant.\n- α: MAX’s current lower bound on MAX’s outcome: Max's best option along path to root\n  - -infinite at first\n  - MAX will never allow a move that could lead to a worse case than α\n    - When evaluating a MIN Node, a value 𝑣 ≤ 𝛼 is found 剪枝不update alpha和beta\n      - MAX will never select that MIN node\n- β: MIN’s current upper bound on MIN’s outcome: MIN's best option along path to root\n  - +infinite at first\n  - MIN will never allow a move that could lead to a better score (for MAX) than β\n    - When evaluating a MAX node: a value 𝑣 ≥ 𝛽 is backed-up 剪枝不update alpha和beta\n      - MIN will never select that MAX node\n- Alpha-beta search computes the same optimal moves as minimax\n  - if we generates the worst successors first, than we don't get to prune anything: the efficiency is highly dependent on the order \n  in which the states are exmained\n  - if we evaluate nodes in the optimal order, the running time of Alpha-Beta pruning is O(b^m/2)\n    - with random move ordering and moderate b, the total number of nodes examined will be roughly O(b^3m/4)\n- Type A & Type B\n  - For games with a large search space, it is not feasible to search the whole tree. \n  As such, we have to make tradeoffs about what part of the tree to search\n\n\nExpectimax Search:\n- an extension to the minimax algorithm that \n  - evaluates a chance node by taking the average utility of all its children, weighted by the probability of each child.\n- values now reflect average-case (Expectimax) outcomes\n- handle game of chances\n- uses expected value at chance nodes\n\n\n```\ndef value(state):\n  if the state is a terminal state: return the state’s utility if the next agent is MAX: return max-value(state)\n  if the next agent is EXP: return exp-value(state)\n```\n```\ndef max-value(state):\n  initialize v = -∞\n  for each successor of state:\n     v = max(v, value(successor))\n  return v\n```\n```\ndef exp-value(state):\n  initialize v = 0\n  for each successor of state:\n    p = probability(successor)\n    v += p * value(successor)\n  return v\n```\n\n\n## Module 5 Definitions\n* **Game** - a terminal test, a utility function that applies to terminal state for winner and final score\n* **Game differ from search problems** - games have multiple agents\n* **Perfect information** - a synonym for fully observable\n* **Zero-sum** - what is good for one player is just as bad for the other\n* **Utility function u(s)** - gives the payoff for each player in terminal state s\n* **Game environment static** - no change while an agent is deliberating\n* **Discrete** - a finite set of percepts and actions\n* **Fully observable/perfect information** - an agent's sensors give it the complete state of the environment\n* **Strategic** -  action executed by the agent and the actions of one other agent.\n* **Minmax search algorithms solves by dfs** - two-player, discrete, deterministic(vs stochastic), turn-making zero-sum games with perfect information\n* **Ply** - Alternate MAX/MIN labels at each successive tree level (ply)\n* **Evaluation function f** - assigns real-number scores to `board positions’ without reference to path (based on static features)\n* **Each node's minimax value** - the best achievable utility against a rational(optimal) adversary\n* **Random value** - an event whose outcome is unknown\n* **Probability distribution** - assignment of weights to outcomes\n* **Expected value of a function of a random variable** - average, weighted by the probability distribution over outcomes\n* **Type a strategy** - explores a wide but shallow portion of the tree\n* **Type b strategy** - deep but narrow portion of the trees\n* **Mcts** - playing the game to the end while randomly selecting moves\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "CSP\n",
        "- represent a state: with a set of variable/value pairs\n",
        "- represent the conditions for a solution: by a set of constraints on the variables\n",
        "- difference with search problems:\n",
        "  - the agent can see the inside states and move between states accordingly\n",
        "  - while search problems: states are black boxes with a transition model to move between boxes\n",
        "- examples using CSP:\n",
        "  - sudoku, map coloring, scheduling problems, floor planning for VLSI\n",
        "- definition\n",
        "  - consiste of X, D, C\n",
        "    - X is a set of variables {X1..Xn} (state in map coloring), 2 ways of ruling out variable assignments (search or inference)\n",
        "    - D is a set of domains {D1, ..Dn} for each variable (color in map coloring)\n",
        "    - C is a set of constraints that specify allowable combinations of values\n",
        "      - Cj (scope, rel)\n",
        "      - SA <> WA => {(red, green), (red, blue), ....}\n",
        "- Constraint gaph:\n",
        "  - node: variables of the problem (state in map coloring)\n",
        "  - edges: connects any two variables that participate in a constraint\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "- Constraint Propagation:\n",
        "  - using the constraints to reduce the number of legal values for a variable,\n",
        "   which in turn can reduce the legal values for another variable, and so on\n",
        "  - leave fewer choices to consider when we make the next choice of a variable assignment\n",
        "  - can be a preprocess step before search start, or can be used together\n",
        "  - inference: enforcing k-consistency\n",
        "- Node consistency\n",
        "  - a single variable (a node in CSP graph) is consistent if all the values in its domain\n",
        "  satisfy the variable's unary constraint\n",
        "- Arc consistency\n",
        "  - if every value in a variable's domain satisfies the variable's binary constraints\n",
        "  - graph is arc-consistent if every variable is arc-consistent with every other\n",
        "  - AC3: enforcing arc-consistency\n",
        "    - O(cd^3) for CSP with n variables each with domain size d, with c binary constraints(arcs)\n",
        "    - no consistent solution if Di is nothing, get solution if every domain size is 1\n",
        "\\n\n",
        "```\n",
        "function AC-3(csp) returns false if an inconsistency is found and true otherwise\n",
        "  queue = a queue of arcs, initially all the arcs in csp\n",
        "  while queue is not empty:\n",
        "    (Xi,Xj) = pop(queue)\n",
        "    if revise(csp, Xi, Xj) then\n",
        "      if size of Di = 0 then return false\n",
        "      for each Xk in Xi.neighbors-{Xj}:\n",
        "        add(Xk, Xi) to queue # since we modify Di then it may enable further reduction in Dk\n",
        "  return true\n",
        "```\n",
        "```\n",
        "function revise(csp, Xi, Xj) returns true iff we revise the domain of Xi\n",
        "  revised = false\n",
        "  for each x in Di:\n",
        "    if no value y in Dj allows(x,y) sastifing the constraint between Xi and Xj then:\n",
        "      delete x from Di\n",
        "      revised = true\n",
        "  return revised \n",
        "```\n",
        "\\n\n",
        "- Path consistency\n",
        "  - tightens the binary constraints by using implicit constraints that are inferred by looking at triples variables\n",
        "- K-consistency\n",
        "  - is k-consistent \n",
        "    - for any set of variables and for any consistent assignment to those variables, a consistent value can always be assigned to any th variable.\n",
        "  - is strongly k-consistent\n",
        "    - if k, k-1, k-2 ...1 consistent\n",
        "- global constraints\n",
        "\"\"\"\n",
        "\n",
        "chapter6_3 = \"\"\" \n",
        "- After propagation(inference) we still have variables with possible solutions\n",
        "  - so we have to search \n",
        "- Backtracking search for partial assignment\n",
        "  - is a form of DFS with limit\n",
        "  - basic uninformed algorithm for CSP\n",
        "  - repeatedly chooses an unassigned variable\n",
        "    - tries all values in its domain\n",
        "      - try to extend to a solution, \n",
        "        - if succeed, return\n",
        "        - if fail, restored the assignment to the previous state, try next value\n",
        "\\n\n",
        "```\n",
        "function Backtrack(csp, assignment) returns a solution or failure\n",
        "  if assignment is complete return assignment\n",
        "  var = select-unassigned-variable(csp, assignment)\n",
        "  for each value in order-domain-values(csp, var, assignment)\n",
        "    if value is consitent with assignment:\n",
        "        add {var=value} to assignment\n",
        "        inferences = inference (csp, var, assignment)\n",
        "        if inferences <> failure\n",
        "          add inferences to csp\n",
        "          result = backtrack(csp, assignment)\n",
        "          if result <> failure then return result\n",
        "          remove inferences from csp\n",
        "        remove {var = value} from assignment\n",
        "  return failure \n",
        "```\n",
        "- Heuristic:\n",
        "  - choose variable (fail first cuz every var has to be assigned ultimately, we will have fewer assignments to backtrack over)\n",
        "    - in order / randomly both not optimal\n",
        "    - minimum-remaining-values (MRV) heuristic\n",
        "      - Most constrained variable\n",
        "      - picks a variable with the fewest legal values \n",
        "      - powerful guide\n",
        "    - degree heuristic:\n",
        "      - most constraining variable\n",
        "      - select the variable involved in the largest number of contsraints on other unassigned variables\n",
        "      - tie breaker\n",
        "  - choose values:\n",
        "    - least constraint value (fail last cuz we only need one)\n",
        "      - prefer value that rules out the fewest choices for the neighboring variables in the constraint graph\n",
        "      - trying to leave the maximum flexibility for subsequent variable assignments\n",
        "- Forward checking:\n",
        "  - whenever a variable X is assigned\n",
        "    - for each unassigned variable Y that is connected to X by a constraint\n",
        "      - delete from Y's domain any value that is inconsistent with the value chosen for X\n",
        "- Constraint Learing:\n",
        "  - records the conflict as they are encountered in the search in order to avoid the same conflict later\n",
        "\"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\"\n",
        "- loacal search for complete assignments\n",
        "\"\"\"\n",
        "\n",
        "chapter6_5 = \"\"\" \n",
        "- Solving an arbitrary CSP:\n",
        "  - takes exponential time in the number of variables\n",
        "- Solving a tree-structured CSP:\n",
        "  - takes linear tine in the number of variables\n",
        "- Cutset Conditioning\n",
        "  - reduce a general CSP to a tree structured one\n",
        "  - efficient if a small cutset can be found. \n",
        "  However, in general, it is no more efficient than solving a CSP directly. There is no free-lunch in solving CSPs indirectly.\n",
        "  - space efficient\n",
        "    - can be executed in linear memory, while tree decomposition requries memory exponential in the tree width ww\n",
        "- Tree decomposition techniques:\n",
        "  - transform the CSP into a tree of subproblems.\n",
        "  - efficient if the tree width of the constraint graph is small\n",
        "    - more efficient than cutset conditioning\n",
        "      - Whenever you have a cycle-cutset of size cc, there is also a tree of width w<c+1, and it may be far smaller in some cases.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "- Map coloring\n",
        "  - n variables of domain size d\n",
        "  - branching factor at root is n*d, at next level is (n-1)*d\n",
        "  - Tree has n!d^n leaves\n",
        "- Forward checking:\n",
        "  - keep track of remaining legal values for unassigned variables\n",
        "  - terminate search when any unassigned variables has no remaining legal values\n",
        "- Arc Consistency\n",
        "  - an arc(i,j) is consistent if nd only if every value v on Xi is consistent with some label on Yj.\n",
        "  - To make an arc (i,j) arc consistent,\n",
        "    - for each value v on Xi ,\n",
        "     - if there is no label on Yj consistent with v,\n",
        "      - then remove v from Xi\n",
        "  - Given d values, checking arc (i,j) takes O(d2) time worst case\n",
        "- Backtracking occurs when no legal assignments can be found for a variable\n",
        "- AC3\n",
        "  - An arc (i,j) is arc consistent if and only if every value v on Xi is consistent with some label on Yj.\n",
        "  - To make an arc (i,j) arc consistent,\n",
        "    - for each value v on Xi ,\n",
        "      - if there is no label on Yj consistent with v\n",
        "      - then remove v from Xi\n",
        "  - Given d values, checking arc (i,j) takes O(d2) time worst case\n",
        "- MAC: Maintaining Arc Consistency\n",
        "  - detects inconsistencies after forward checking calls AC3\n",
        "  - MAC vs forward checking\n",
        "    - MAC recursively propogrates constraints, whereas forward checking does not\n",
        "      - If we assign X, forward checking makes all the arcs incident on X consistent. \n",
        "      - MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...) \n",
        "  - MAC vs AC3\n",
        "    - MaC is a way of interleaving search and inference\n",
        "    - whereas AC3 is pure inference\n",
        "    - MAC runs while assigning variables in backtracking search. \n",
        "    - Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3.\n",
        "  - more powerful than forward checking because forward checking does the same thing as MAC on the initial arcs in MAC’s queue; \n",
        "  - unlike MAC, forward checking does not recursively propagate constraints when changes are made to the domains of variables.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP\" : \" Constraint satisfaction problems\",\n",
        "\"scope\": \"a tuple of variables that participate in the constraint\",\n",
        "\"rel\": \"a relation that defines the values that those variables can take on\", \n",
        "\"assignments\":\"assign values in D to variables X\",\n",
        "\"consistent/legal assignment\": \"does not violate any constraints\",\n",
        "\"complete assignment\":\"one in which every variable is assigned a value\",\n",
        "\"solution\":\"consistent, complete assignment\",\n",
        "\"partial assignment\":\"leaves some variables unassigned\",\n",
        "\"partial solution\":\"consistent partial solution\",\n",
        "\"unary constraint\":\"retrstics the value of a single variable, e.g. SA <> green\",\n",
        "\"binary constraint\": \"relates two variable, e.g. SA <> NSW\",\n",
        "\"bianry CSP\": \"one with only unary and binary constraints\",\n",
        "\"global constarint\":\"constraint involving arbitrary number of variables (Alldiff: soduku)\",\n",
        "\"Alldiff\":\"all of the variables involved in the constraint must have differnt values\",\n",
        "\"constraint hypergraph\":\"consists of ordinary nodes (circles) and hypernodes(squares) for n-ary constraints\",\n",
        "\"dual graph\": \"transfer n-ary CSP to binary, creates a new graph in which there will be one variable for each constraint in the original graph\",\n",
        "\"dual graph\": \"and one binary constraint for each pair of constraints in the original graph that share variables\",\n",
        "\"preference constraints\": \"indicating which solutions are preferred\",\n",
        "\"local consistency\": \"causes inconsistent values to be eliminated\",\n",
        "\"commutativity\" :\"the order of application of any given set of actions does not matter\",\n",
        "\" min-conflicts heuristic\" : \"select the value that results in the minimum number of conflicts with other variables\",\n",
        "\"constraint weighting\" :\"chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 82,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "02f9009f-3540-4d99-f10d-1b136dede2e3"
      },
      "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": 83,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP\n- represent a state: with a set of variable/value pairs\n- represent the conditions for a solution: by a set of constraints on the variables\n- difference with search problems:\n  - the agent can see the inside states and move between states accordingly\n  - while search problems: states are black boxes with a transition model to move between boxes\n- examples using CSP:\n  - sudoku, map coloring, scheduling problems, floor planning for VLSI\n- definition\n  - consiste of X, D, C\n    - X is a set of variables {X1..Xn} (state in map coloring), 2 ways of ruling out variable assignments (search or inference)\n    - D is a set of domains {D1, ..Dn} for each variable (color in map coloring)\n    - C is a set of constraints that specify allowable combinations of values\n      - Cj (scope, rel)\n      - SA <> WA => {(red, green), (red, blue), ....}\n- Constraint gaph:\n  - node: variables of the problem (state in map coloring)\n  - edges: connects any two variables that participate in a constraint\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- Constraint Propagation:\n  - using the constraints to reduce the number of legal values for a variable,\n   which in turn can reduce the legal values for another variable, and so on\n  - leave fewer choices to consider when we make the next choice of a variable assignment\n  - can be a preprocess step before search start, or can be used together\n  - inference: enforcing k-consistency\n- Node consistency\n  - a single variable (a node in CSP graph) is consistent if all the values in its domain\n  satisfy the variable's unary constraint\n- Arc consistency\n  - if every value in a variable's domain satisfies the variable's binary constraints\n  - graph is arc-consistent if every variable is arc-consistent with every other\n  - AC3: enforcing arc-consistency\n    - O(cd^3) for CSP with n variables each with domain size d, with c binary constraints(arcs)\n    - no consistent solution if Di is nothing, get solution if every domain size is 1\n\n\n```\nfunction AC-3(csp) returns false if an inconsistency is found and true otherwise\n  queue = a queue of arcs, initially all the arcs in csp\n  while queue is not empty:\n    (Xi,Xj) = pop(queue)\n    if revise(csp, Xi, Xj) then\n      if size of Di = 0 then return false\n      for each Xk in Xi.neighbors-{Xj}:\n        add(Xk, Xi) to queue # since we modify Di then it may enable further reduction in Dk\n  return true\n```\n```\nfunction revise(csp, Xi, Xj) returns true iff we revise the domain of Xi\n  revised = false\n  for each x in Di:\n    if no value y in Dj allows(x,y) sastifing the constraint between Xi and Xj then:\n      delete x from Di\n      revised = true\n  return revised \n```\n\n\n- Path consistency\n  - tightens the binary constraints by using implicit constraints that are inferred by looking at triples variables\n- K-consistency\n  - is k-consistent \n    - for any set of variables and for any consistent assignment to those variables, a consistent value can always be assigned to any th variable.\n  - is strongly k-consistent\n    - if k, k-1, k-2 ...1 consistent\n- global constraints\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n- After propagation(inference) we still have variables with possible solutions\n  - so we have to search \n- Backtracking search for partial assignment\n  - is a form of DFS with limit\n  - basic uninformed algorithm for CSP\n  - repeatedly chooses an unassigned variable\n    - tries all values in its domain\n      - try to extend to a solution, \n        - if succeed, return\n        - if fail, restored the assignment to the previous state, try next value\n\n\n```\nfunction Backtrack(csp, assignment) returns a solution or failure\n  if assignment is complete return assignment\n  var = select-unassigned-variable(csp, assignment)\n  for each value in order-domain-values(csp, var, assignment)\n    if value is consitent with assignment:\n        add {var=value} to assignment\n        inferences = inference (csp, var, assignment)\n        if inferences <> failure\n          add inferences to csp\n          result = backtrack(csp, assignment)\n          if result <> failure then return result\n          remove inferences from csp\n        remove {var = value} from assignment\n  return failure \n```\n- Heuristic:\n  - choose variable (fail first cuz every var has to be assigned ultimately, we will have fewer assignments to backtrack over)\n    - in order / randomly both not optimal\n    - minimum-remaining-values (MRV) heuristic\n      - Most constrained variable\n      - picks a variable with the fewest legal values \n      - powerful guide\n    - degree heuristic:\n      - most constraining variable\n      - select the variable involved in the largest number of contsraints on other unassigned variables\n      - tie breaker\n  - choose values:\n    - least constraint value (fail last cuz we only need one)\n      - prefer value that rules out the fewest choices for the neighboring variables in the constraint graph\n      - trying to leave the maximum flexibility for subsequent variable assignments\n- Forward checking:\n  - whenever a variable X is assigned\n    - for each unassigned variable Y that is connected to X by a constraint\n      - delete from Y's domain any value that is inconsistent with the value chosen for X\n- Constraint Learing:\n  - records the conflict as they are encountered in the search in order to avoid the same conflict later\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n- loacal search for complete assignments\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n \n- Solving an arbitrary CSP:\n  - takes exponential time in the number of variables\n- Solving a tree-structured CSP:\n  - takes linear tine in the number of variables\n- Cutset Conditioning\n  - reduce a general CSP to a tree structured one\n  - efficient if a small cutset can be found. \n  However, in general, it is no more efficient than solving a CSP directly. There is no free-lunch in solving CSPs indirectly.\n  - space efficient\n    - can be executed in linear memory, while tree decomposition requries memory exponential in the tree width ww\n- Tree decomposition techniques:\n  - transform the CSP into a tree of subproblems.\n  - efficient if the tree width of the constraint graph is small\n    - more efficient than cutset conditioning\n      - Whenever you have a cycle-cutset of size cc, there is also a tree of width w<c+1, and it may be far smaller in some cases.\n\n\n## Module 6 Lecture Notes\n \n- Map coloring\n  - n variables of domain size d\n  - branching factor at root is n*d, at next level is (n-1)*d\n  - Tree has n!d^n leaves\n- Forward checking:\n  - keep track of remaining legal values for unassigned variables\n  - terminate search when any unassigned variables has no remaining legal values\n- Arc Consistency\n  - an arc(i,j) is consistent if nd only if every value v on Xi is consistent with some label on Yj.\n  - To make an arc (i,j) arc consistent,\n    - for each value v on Xi ,\n     - if there is no label on Yj consistent with v,\n      - then remove v from Xi\n  - Given d values, checking arc (i,j) takes O(d2) time worst case\n- Backtracking occurs when no legal assignments can be found for a variable\n- AC3\n  - An arc (i,j) is arc consistent if and only if every value v on Xi is consistent with some label on Yj.\n  - To make an arc (i,j) arc consistent,\n    - for each value v on Xi ,\n      - if there is no label on Yj consistent with v\n      - then remove v from Xi\n  - Given d values, checking arc (i,j) takes O(d2) time worst case\n- MAC: Maintaining Arc Consistency\n  - detects inconsistencies after forward checking calls AC3\n  - MAC vs forward checking\n    - MAC recursively propogrates constraints, whereas forward checking does not\n      - If we assign X, forward checking makes all the arcs incident on X consistent. \n      - MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...) \n  - MAC vs AC3\n    - MaC is a way of interleaving search and inference\n    - whereas AC3 is pure inference\n    - MAC runs while assigning variables in backtracking search. \n    - Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3.\n  - more powerful than forward checking because forward checking does the same thing as MAC on the initial arcs in MAC’s queue; \n  - unlike MAC, forward checking does not recursively propagate constraints when changes are made to the domains of variables.\n\n\n\n## Module 6 Definitions\n* **Csp** -  Constraint satisfaction problems\n* **Scope** - a tuple of variables that participate in the constraint\n* **Rel** - a relation that defines the values that those variables can take on\n* **Assignments** - assign values in D to variables X\n* **Consistent/legal assignment** - does not violate any constraints\n* **Complete assignment** - one in which every variable is assigned a value\n* **Solution** - consistent, complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - consistent partial solution\n* **Unary constraint** - retrstics the value of a single variable, e.g. SA <> green\n* **Binary constraint** - relates two variable, e.g. SA <> NSW\n* **Bianry csp** - one with only unary and binary constraints\n* **Global constarint** - constraint involving arbitrary number of variables (Alldiff: soduku)\n* **Alldiff** - all of the variables involved in the constraint must have differnt values\n* **Constraint hypergraph** - consists of ordinary nodes (circles) and hypernodes(squares) for n-ary constraints\n* **Dual graph** - and one binary constraint for each pair of constraints in the original graph that share variables\n* **Preference constraints** - indicating which solutions are preferred\n* **Local consistency** - causes inconsistent values to be eliminated\n* **Commutativity** - the order of application of any given set of actions does not matter\n* ** min-conflicts heuristic** - select the value that results in the minimum number of conflicts with other variables\n* **Constraint weighting** - chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base (KB)\" : \"a set of sentences expressed in knowledge representation language\",\n",
        "\"axiom\" : \"if the senetence is taken as being given without drived from other senetences\",\n",
        "\"inference\": \"deriving new sentences from old\",\n",
        "\"knowledge level\": \"what the agent knows and what it goals are\",\n",
        "\"semantics\" : \"meaning of sentence, defines the truth of each sentence with respect to each possible word/ model\",\n",
        "\"syntax\": \"the structure of sentences\",\n",
        "\"semantics\" :\"the way in which the truth of sentences is determined\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 84,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 626
        },
        "outputId": "7c380b94-790b-4de3-df35-2c775d3672b5"
      },
      "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": 85,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge base (kb)** - a set of sentences expressed in knowledge representation language\n* **Axiom** - if the senetence is taken as being given without drived from other senetences\n* **Inference** - deriving new sentences from old\n* **Knowledge level** - what the agent knows and what it goals are\n* **Semantics** - the way in which the truth of sentences is determined\n* **Syntax** - the structure of sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "1d41714a-025f-43d1-f489-933c61ef4f65"
      },
      "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": 86,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Turing Test: whether it is acting humanly, a computer passes it  if a human cannot tell the response come from a person or from a computer. Computer needs to do \n1. NLP to communicate in human language \n2. knowledge representation to store what it knows or hears\n3. automtaed reasoning to answer questions and make conclusions \n4. ML to adapt to new circumstances and to detect and extrapolate patterns. \n5. CV and speech recoginition to perceive the world \n6. robotics to manipulate objects and move about for total Turing test (iteraction with objects and people in the real world)\n\n## AIMA Chapter 27.1 The Limits of AI\n The limits of AI \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Can machines really think \n\n## AIMA 2.1 Agents and Environments\n agents and environment \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n the concept of rationality \n\n## AIMA 2.3 The Nature of Environments\n Properties of task environments: \n1. Fully observable vs partially observable \n2. single-agent vs multiagent\n3. copetitive vs cooperative\n4. Deterministic vs Nondeterministic (chances without actual number, if with actual probability \nthen it is stochastic) \n5. episodic vs sequential \n6. static vs dynamic (can change while an agent is deliberating) \n7. discrete vs continuous \n8. known vs unknown\n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program. \n1. Simple reflex agent: (selects on the current percept, ignoring the rest of percept history) respond directly to percepts\n2. Model-based reflex agents (handle partial observability, keep track of the part of the world it can't \nsee now - internal state, transition model, sensor model, maintain internal state to track aspects of the world that are not\nevident in the current percept\n3. Goal-based agents: goal, search, and planning to find the action sequence that achieves the agent's goals\n4. Utility-based agents: \"the quaklity of being useful\", maximize their own expected \"happiness\"\n5. Learning agents: Leraning element, performace element, critic, problem generator, reward, penalty. All agents can improve their\nperformance through learning \n\nHow the components work a)atomic, b)factoered, c) structured\n\n## Module 1 Lecture Notes\n\n```\ndef function():\n      print('hello world')\n```\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act in an environment through actuators\n* **Agent_examples** - humans, robots, softbots, thermostats (automatically)\n* **Percept** - the agent's perceptual inputs at any given instance (P)\n* **Percept_sequence** - the complete history of everything the agent has ever perceived\n* **Agent function** - from a set A: P = [p0,..pt], A={a0,..ak}\n* **Agent program** - runs on the physical architecture to produce f -> agent = architecture + program\n* **Function vs program** - abstract mathematical description vs concerete implementation\n* **Rational agent** - for each possible P, the agent selects an action a to maximize the expected value of its performace measure\n* **Goal of rational agent design** - design an agent program that implements f on a particular architecture\n* **Rationality** - doing the right thing\n* **Performance measure** - evaluates the behavior of the agent in an environment\n* **Task environment** - PEAS: Performance measure, Envrionment, Actuators, Sensors\n* **Hardest environment** - continuous, partially observable, stochastic, multiagent\n* **Condition-action rule** - if car-in-front-is-braking then initiate-braking\n* **Utility function** - an internalization of the performace measure\n* **Expected utility** - the utility the agent expect to derive on average gievn the prob and utilities of each outcome\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nPython Advantages: \n\n1. fast development (intuitive, garbage collection: an object is deleted once unreachable) \n2. portable (runs on different platforms)\n3. various built-in types \n4. large collection of support libraries \n\nObjects and types: \n\n1. all data treated as objects \n2. strong typing: every object has a fixed type, interpreter does not allow thing \nincompatible with that type (no \"foo\" + 2)   \n3. dynamic typing: variables come into existence when first assigned (type(var) auto\nmatically determined, type error only caught at runtime) - vs static typing:\nvariables can only refer to objects of a declared type, that methods using (string[] args) signatures to enforce contracts \n\nSyntax: \n\n1. Literals: True/False, 1.0, 2e9 \n2. Operations: **(power), and, or, not (不用字符)3)+= (没有++、--) \n\nSequence types: (闭区间，开区间） [-1] 倒数第一个 可以用+\n\n*String: \n\n1. 用单双三引号create \n2. 用+合并 \n3. prefix r means raw \n4. immutable \n5. == checks if the same value \n6. is check if the same object\n7. x.strip() new object \n8. regular strings are unicode and use 2-byte characters\n\n9. words=s.split(), \"_\".join(words) # join method of object \"_\"每个词都用下划线连接 \n10. immutable, cannot perform mathematical operations\n*Lists: []\n\n\n1. Mutable ordered sequence of items of mixed types \n2. y=x[:] get a shallow copy /new object of the same value \n3. x.append() same object \n4. insert(2,'i') index2=i \n5. index('b') index of first occurence \n6. count('b) number of occurence\n7. remove('b') same \n8. li.reverse()/sort() inplace, sorted(li) returns a copy sorted\n\n\n*Tuple: () \n\n1. simple immutable ordered sequence of items \n2. items can be mixed types including collection \n3. can be created without parentheses (using tuple())\n\n\nSlicing: return copy of a subsequence, [1:4]前三个, [1:-1]除了最后一个, [1:-1:2]每两个选一个, [:2]前两个\n\n\nCollection Types: \n\n*Dict: {} 不能用+， no duplicate keys, key immutable (can't be lists)\n\n1. unordered, work by hashing, keys must be immutable, dict mutable\n2. constant average time add, look up, update\n3. use key to get value, but cannot use value to get key\n4. .keys()/values()/items - list of current keys\n\n\nFunctions:\n\n\n1. return multiple values in a tuple \n2. specified by name alone, no overloading不能重名\n3. can provide default values for arguments to be optional\n4. functions can be called with arguments out of order （但要在所有其他arguments后call)\n5. dynamic scope: function sess the most current value of variables\n6. first class object, can be passed/returned/assigned to other variables, higher order functions take functions as input\n\n\nClass:\n\n\n1. student1.print() 等同于 Student.print(student1)\n2. subclass allow use of methods and attribute already defined in the previous, support multiple inheritance\n\n\nMagic Methods:\n\n\n1) _str_/_init_/_len_/_copy_/_cmp_/_add_/_neg_\n\n\nFor loops:\n\n\n0. for <item> in <collection>: <statements>\n1. list(range(5)) - [0,1,2,3,4]\n2. list comprehensions - squares = [x*x for x in nums] # nums is a list\n2.1. li=[('a',1),('b',2),('c',7)], [n*3 for (x, n) in li if n < 7 ]=[3,6] [ expression for name in list if filter ]\nIterators:\n1. use memory efficiently, for <item> in <iterable>: <statements>\n2. _iter_ #to be iterable, _next_ to be iterator, for char in Reverse('spam'): print(char)\n\n\nGenerators:\n\n\n1. are iterators(with_next()_ method), using yield (automaically return a generator when called)\n2. each time we call the next method of the generator, the method run untils it encounters a yield statement, and then stops\nand returns the values that was yielded. Next time ,it resumes where it left off\n3. values are computed one at a time as they are needed, avoid storing the entire sequence in memory, \ncrucial for infinite sequences, bad if individual value inspection needed\n\n\n \n\n## Module 2 Definitions\n* **Mutability** - can be modified or not once created\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n goal formulation, problem formulation, search, solution, execution, search problems\n ```\nfunction Best-FIRST-Search(problem f) returns a solution node or failure:\n  node = Node(State = problem.initial)\n  frontier = a priority queue ordered by f, whith node as an element\n  reached = a loopup table, with one entry with key problem.Initial and value node\n  while not Is-Empty(frontier):\n    node = frontier.pop()\n    if problem.is-goal(node.state) return node\n    for each child in expand (problem, node):\n      s = child.state\n      if s is not in reached or child.path-cost < reached[s].path_cost\"\n        reached[s] = child\n        add child to frontier\n  return failure\n\nfunction expand(problem, node) yields nodes\n  s = node.state\n  for each action in problem.actions(s):\n    s' = problem.result(s, action)\n    cost = node.path_cost + problem.action_cost(s, action, s')\n    yield Node(state = s', parent = node, action = action, path_cost = cost)\n```\n- node.action: the action that was applied to the parent’s state to generate this node; \n\n- node.path_cost: the total cost of the path from the initial state to this node. g(n)  \n\n- frontier: thoses states that are available for expanding(for applying legal actions to), priority queue for best-first/uniform cost search, FIFO queue for BFS, LIFO(stack) for DFS \n\n \n\n## AIMA Chapter 3.2 Example Problems\n\n ```\nfunction Breadth-FIRST-Search(problem) returns a solution node or failure:\n  node = Node(problem.initial)\n  if problem.is-goal(node.state) than return node\n  frontier = a FIFO queue, with node as an element\n  reached = {problem.initial}\n  while not Is-Empty(frontier):\n    node = frontier.pop()\n    for each child in expand (problem, node):\n      s = child.state\n      if problem.is-goal(s) then return child\n      if s is not in reached then\n        add s to reached\n        add child to frontier\n  return failure\n\nfunction uniform-cost-search(problem) returns a solution node or failure\n  return Best-First-Search(problem, path-cost)\n```\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \n ```\nfunction Iterative-Deepening-Search(problem) returns a solution node or failure: \n  for depth = 0 to infinite:\n    result = depth-limited-search(problem, depth)\n    if result not equal to cutoff\n      return result\nfunction Depth-limited-search(problem, l) returns a solution node or failure:\n  frontier = a LIFO queue, with node(state.initial) as an element\n  result = failure\n  while not Is-Empty(frontier):\n    node = frontier.pop()\n    if problem.is-goal(node.state) then return node\n    if depth(node) > l then:\n        result = cutoff\n    else if not is-cycle(node):\n      for each child in expand(problem, node):\n        add child to frontier\n  return result\n```\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n\n\n\n## Module 3 Lecture Notes\n \nUninformed:\n\nBest-First Search \n\n\nselects node for expansion using an evaluation function\n\n\nBreadth-First search:\n\n\nBFS, expands the shallowest node first. is a best-first-search where f(n) is the depth of the node \n\nuse if possible infinite paths / some solutions have short paths / can quickly discard unlikely paths \n\n1. complete \n\n2. optimal for unit action costs\n\n3. exponential space complexity (bad), O(b^d) for searching a uniform tree where every state has b successors and at depth d\n\n4. time complexity: O(b^d)\n\n\n\nUniform-cost search:\n\n\nexpands node with lowest path cost g(n) - the cost of the path from the root to the current node.\n\nDijkstra is an uniform-cost search without a goal \n\ntest for goals only when it expands a node, not when it generates a node \n\na tree search algorithm used for traversing or searching a weighted tree, tree stucture, or graph \n\n1. complete \n\n2. optimal for general action costs \n\n3. O(b^ 1+C*/) \n\n4. difference from BFS: test if a node is a goal state when it is selected for expansion, not when it is added to the frontier,\nupdates a node on the frontier if a better path to the same state is found, always enqueues a node before checking if it is a goal.\nInstead of exploring all possible paths equally, it favors lower cost paths. Prioritize which paths to explore\n\n\nDepth-first Search:\n\n\nexpands the deepest unexpanded node first, \n\nuse with restricted memory / many possible solutions with long and wrong paths are usually terminated quickly / search can be fine-tuned quickly\n1. not complete unless m is bounded\n2. not optimal\n3. linear space complexity (depth-limited search adds a depth bound), O(b*m) space\n4. time complexity: O(b^m); terrible if m >> d \n\nDepth-Limit Search: \n\nDFS with depth limit l, node at depth l have no successors, no infinite-path probem\n1. if l = d by luck, then optimal. if l<d then incomplete, if l>d then not optimal (not complete nor optimal)\n2. time: O(b^l)\n3. space: O(bl) (good)\n\n\nIterative Deepening Search:\n\n\ncalls dfs with increasing depth limit until reach the goal\n1. complete when full cycle checking (no infinite paths) is done, goal is always found at depth d, the depth of the shallowest goal-node\n2. optimal for unit action costs (step cost is 1) good\n3. BFS comparable time complexity, O(b^d) \n4. linear space complexity, O(bd) (good)\n\n\nBidirectional Search:\n\n\nexpands two frontiers, one around the initial state and goal state. stop when the two meets\n1. complete\n2. optimal\n3. O(b^d/2) for time and space\n\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Solution** - a path through the state space from the initial to the goal\n* **Search** - finding a solution\n* **Strategy** - order of tree expansion\n* **Search algorithm** - takes a search problem as input and returns a solution, or an indication of failure\n* **Node** - corresponding to a state in the state space\n* **Edge** - actions\n* **Root** - initial states\n* **Execution** - execute the actions in the solution one at a time\n* **Search problems** - 5 parts below\n* **The initial state** - \n* **A set of actions** - 5 parts below\n* **A transition model** - describing the results of those actions\n* **A set of goal states** - 5 parts below\n* **An action cost function** - 5 parts below\n* **State space graph** - environment of the problem\n* **Path** - a sequence of actions\n* **Cycle** - a special case of redudant path, has a repeated state in the search tree\n* **Graph search** - checks for redudant path\n* **Tree-like search** - does not check for redudant paths, save memory space\n* **Search algorithm** - judged by completeness, cost optimality, time complexity, and space complexity\n* **Completeness** - guaranteed to find a solution when there is one, and to correctly report failure when there is not\n* **Optimality** -  find a solution with the lowest path cost of all solutions\n* **Time complexity** - How long does it take to find a solution, number of states and actions considered\n* **Space complexity** - memory needed to perform\n* **Systematic** - make sure it can eventually reach any state that is connetced to the initial in an infinite state space\n* **|v|** - the number of vertices (state nodes)\n* **|e|** - the number of edges (distinct state\u0007ction pairs)\n* **D, depth** - number of actions in an optimal solution/depth of the solution/shallowest goal node\n* **M** - maximum number of actions in any path/maximum depth of the search tree\n* **B, branching factor** - number of successors of a node that needed to be considered\n* **Uninformed search** - have access only to the problem definition\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n ```\nfunction Greedy-Best-FIRST-Search:\n  frontier = PQ()\n  frontier.put(start, 0)\n  came_from = {}\n  came_from[start] = None\n  while not frontier.empty():\n    current = frontie.get()\n    if current == goal:\n        break\n      for next in graph.neighbors(current):\n        if next not in came_from:\n          priority = heuristic(goal, next)\n          frontier.put(next, priority)\n          came_from[next] = current\n```\n ```\nBFS in 10 lines:\n  frontier = Queue()\n  frontier.put(start, 0)\n  visited = {}\n  visited[start] = True\n  while not frontier.empty():\n    current = frontie.get()\n    for next in graph.neighbors(current):\n      if next not in visited:\n          frontier.put(next)\n          visited[next] = True\n```\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \n ```\nFinding the shortest path:\n  frontier = Queue()\n  frontier.put(start, 0)\n  came_from = {}\n  came_from[start] = None\n  while not frontier.empty():\n    current = frontie.get()\n    for next in graph.neighbors(current):\n      if next not in came_from:\n          frontier.put(next)\n          came_from[next] = current\n# Backtrack\n  current = goal\n  path = []\n  while current != start:\n    path.append(current)\n    current = came_from[current]\n  path.append(start)\n  path.reverse()\n ```\n\n\n\n## Module 4 Lecture Notes\n \nInformed: \n\nGreedy best-first search:\n\n\n expands nodes with minimal h(n), f(n) = h(n), completely ignores g(n) \n\n Manhattan distance: 两点之间的距离\n 1. not complete, can get stuck in loops\n 2. not optimal, often efficient\n\n\nA* search:\n\n\nbest known form of best-first search, expands node with minimal f(n) = g(n) + h(n)\n1. complete\n2. optimal when h(n) is admissible\n3. space complexity still an issue O(b^d)\n4. expands mainly towards the goal, but does hedge its bets to ensure optimality, while uniform-cost expands equally in all \"directions\"\n\n\nBidirectional A* search:\n\n\nsometimes more efficient than A*\n\n\nIDA* iterative deepening A* search:\n\n\nbetter the space complexity\n\n\nRBFS (recursive best-first search) & SMA*(simplified memory-bounded A*):\n\n\n1. robust\n2. optimal\n3. use limited amounts of memory, can solve A* run out of memory with enough time (space efficient)\n\n\nBeam Search:\n\n\nputs a limit on the size of the frontier\n1. incomplete\n2. suboptimal\n3. but reasonably good solutions and run faster than complete searches\n\n\nWeighted A* search:\n\n\nfocuses the search towards a goal, expanding fewer nodes (expands for nodes which minimizes f(n) = g(n) + W*h(n))\n1. complete\n2. not optimal\n\n\nHeuuristics function:\nh2 dominates h1: if h2(n) >= h1(n) for all n (both admissble) => \n\nh2 more accurate, therefore better for search. \n\nDomination translates directly into efficiency: A* using h2 will never expand more nodes than A* using h1 \n\nIn 8 puzzle, hmd dominates hoop. \n\nA heuristic h is admissible if: 0 <= h(n) <= h*(n) where h*(n) is the true cost to a nearest goal \n\nheuristic function with branching factor (b): the less b is, the better as the branching fatocr denots how many\nnew nodes are added for each node as we increases depth by one. b*=1.5 at four means we only need to explore 1.5^4 = 5 nodes\n\n\n\n\n## Module 4 Definitions\n* **Informed search** - have access to the problem definition and heuristic function h(n)\n* **H(n)** - estimates the cost of the cheapest path from the state at the current node n to a goal node\n* **H*(n)** - the unachievable Oracle heuristic, the true distance from n to goal\n* **Admiisible/optimistic h(n)** - never overestimate the cost to reach the goal\n* **Relax problem** - a problem with fewer restrictions on the actions than the original\n* **Admissible heuristic** - the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n* **Hoop(n) for 8 puzzle** - number of out of place tiles, gives shorest solution if tile can move anywhere\n* **Hmd(n) for 8 puzzle** - number of moves from desired location of each tile, shortest if tile can move to any adjacent square\n* **H2 dominates h1** - if h2(n) >= h1(n) for all n (both admissble), h2 more accurate\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nstochastic & no perfect information games: 卡牌游戏 \n\ncontinuous & no turn games: real time strategy games \n\nGAME setup \n\nTwo players MAX and MIN, MAX moves first \n\ntakes turns until the game is over \n\nMAX uses search tree to determine next move\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n\n- Heuristic Alpha-Beta:\n  - evaluation function : \n    - replaces the utility function \n    - estimates the value(the utility) of non-terminal nodes\n    - the evaluation function should be applied only to positions that are quiescent\n      - the eval(s, p) in a non-terminal state given an adversarial game \n        - returns n estimate of the expected utility of some state s, for player p. \n        - For terminal states, the evaluation function is exactly equal to the utility.\n    - a move is quiescent if: \n      - there is no pending move that would wildly swing the valuation. \n      - For example, if a move in chess would allow your queen to be eaten in the next turn, it would not be quiescent.\n    - horizon effect：\n      - when an agent try to erroneously delay the inevitable\n      - mitigate the horizon effect\n        - allow signular extensions, moves that are clearly better than all other moves in a given position\n      \n  - replaces the terminal test with a cutoff test (which decides when to cut off the search)\n  - forward pruning: prunes moves that appear to be bad moves\n    - E.g. Beam Search\n- MCTS:\n  - evaluates states not by applying a heuristic function\n  - but by playing out the game all the way to the end and using the rules of the game to see who won\n  - Since the moves chosen during the playout may not have been optimal moves, \n    - the process is repeated multiple times and the evaluation is an average of the results.\n  - evaluating an action:\n    - Repeatedly play the game from that state and take the average of the results\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n- Given a game where the outcome of a player making a move is deterministic, \ninimax and Expectiminimax will always produce the same solutions.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n\nAdversarial Search: \n\n\nAll play is computed from MAX's vantage point: \n\nWhen MAX moves, MAX attempts to MAXIMIZE MAX's outcome \n\nWhen MIN moves, MIN attempts to MINIMIZE MAX's outcome \n\nTypically assume MAX moves first (label root level 0 MAX), even levels for MAX, odd levels for MIN \n\nEvaluation function f(n): \n\n- evaluates how good a board position is (represeneted as a node in search tree)\n\n- f(n) > 0 if MAX is winning in position n \n\n- f(n) = 0 if posistion n is tied \n\n- f(n) < 0 if MIN is winning in position n \n\n- f(b) = (sum of A's piece values) - (sum of B's piece values) for chess games -> f(n) can be a weighted linear function\n\n\nMinimax Rule: \n\n1. make the best move for MAX assuming that Min always replies with the best moves for MIN \n2. Easily computer by a recursive process such that \n- The backend-up value of each node in the tree is determined by the values of its children\n- For a MAX node, the backed-up value is the maximum of the values of its children (i.e. the best for MAX)\n- For a MIN node, the backed-up value is the minimum of the values of its children (i.e. the best for MIN) \n\nMinimax Procedure:\n- start with the current position as a MAX node\n- expand the game tree a fixed number of ply\n- apply the evaluation function to the leaf positions\n- calculate back-up values bottom-up\n- pick the moves assigned to MAX at the root\n- wait for MIN to respond\n\n\nMiniMax algorithm:\n- the value of a node is the optimal value of its children. (highest value for max, lowest for min)\n- time complexity: O(b^m), where b is the number of legal moves at each node, m is the maximum depth of the tree \n\n```\ndef max-value(state):\n   if the state is a terminal state:\n        return the state’s utility\n   initialize v = -∞\n   for each successor of state:\n     v = max(v, min-value(successor))\n   return v\n```\n```\ndef min-value(state):\n   if the state is a terminal state:\n        return the state’s utility\n   initialize v = +∞\n   for each successor of state:\n     v = min(v, max-value(successor))\n   return v\n```\n\n\nAlpha-Beta Pruning: \n\n- computes the same optimal moves as minimax, but achieves much greater efficiency by eliminating subtrees that are provably irrelevant.\n- α: MAX’s current lower bound on MAX’s outcome: Max's best option along path to root\n  - -infinite at first\n  - MAX will never allow a move that could lead to a worse case than α\n    - When evaluating a MIN Node, a value 𝑣 ≤ 𝛼 is found 剪枝不update alpha和beta\n      - MAX will never select that MIN node\n- β: MIN’s current upper bound on MIN’s outcome: MIN's best option along path to root\n  - +infinite at first\n  - MIN will never allow a move that could lead to a better score (for MAX) than β\n    - When evaluating a MAX node: a value 𝑣 ≥ 𝛽 is backed-up 剪枝不update alpha和beta\n      - MIN will never select that MAX node\n- Alpha-beta search computes the same optimal moves as minimax\n  - if we generates the worst successors first, than we don't get to prune anything: the efficiency is highly dependent on the order \n  in which the states are exmained\n  - if we evaluate nodes in the optimal order, the running time of Alpha-Beta pruning is O(b^m/2)\n    - with random move ordering and moderate b, the total number of nodes examined will be roughly O(b^3m/4)\n- Type A & Type B\n  - For games with a large search space, it is not feasible to search the whole tree. \n  As such, we have to make tradeoffs about what part of the tree to search\n\n\nExpectimax Search:\n- an extension to the minimax algorithm that \n  - evaluates a chance node by taking the average utility of all its children, weighted by the probability of each child.\n- values now reflect average-case (Expectimax) outcomes\n- handle game of chances\n- uses expected value at chance nodes\n\n\n```\ndef value(state):\n  if the state is a terminal state: return the state’s utility if the next agent is MAX: return max-value(state)\n  if the next agent is EXP: return exp-value(state)\n```\n```\ndef max-value(state):\n  initialize v = -∞\n  for each successor of state:\n     v = max(v, value(successor))\n  return v\n```\n```\ndef exp-value(state):\n  initialize v = 0\n  for each successor of state:\n    p = probability(successor)\n    v += p * value(successor)\n  return v\n```\n\n\n## Module 5 Definitions\n* **Game** - a terminal test, a utility function that applies to terminal state for winner and final score\n* **Game differ from search problems** - games have multiple agents\n* **Perfect information** - a synonym for fully observable\n* **Zero-sum** - what is good for one player is just as bad for the other\n* **Utility function u(s)** - gives the payoff for each player in terminal state s\n* **Game environment static** - no change while an agent is deliberating\n* **Discrete** - a finite set of percepts and actions\n* **Fully observable/perfect information** - an agent's sensors give it the complete state of the environment\n* **Strategic** -  action executed by the agent and the actions of one other agent.\n* **Minmax search algorithms solves by dfs** - two-player, discrete, deterministic(vs stochastic), turn-making zero-sum games with perfect information\n* **Ply** - Alternate MAX/MIN labels at each successive tree level (ply)\n* **Evaluation function f** - assigns real-number scores to `board positions’ without reference to path (based on static features)\n* **Each node's minimax value** - the best achievable utility against a rational(optimal) adversary\n* **Random value** - an event whose outcome is unknown\n* **Probability distribution** - assignment of weights to outcomes\n* **Expected value of a function of a random variable** - average, weighted by the probability distribution over outcomes\n* **Type a strategy** - explores a wide but shallow portion of the tree\n* **Type b strategy** - deep but narrow portion of the trees\n* **Mcts** - playing the game to the end while randomly selecting moves\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP\n- represent a state: with a set of variable/value pairs\n- represent the conditions for a solution: by a set of constraints on the variables\n- difference with search problems:\n  - the agent can see the inside states and move between states accordingly\n  - while search problems: states are black boxes with a transition model to move between boxes\n- examples using CSP:\n  - sudoku, map coloring, scheduling problems, floor planning for VLSI\n- definition\n  - consiste of X, D, C\n    - X is a set of variables {X1..Xn} (state in map coloring), 2 ways of ruling out variable assignments (search or inference)\n    - D is a set of domains {D1, ..Dn} for each variable (color in map coloring)\n    - C is a set of constraints that specify allowable combinations of values\n      - Cj (scope, rel)\n      - SA <> WA => {(red, green), (red, blue), ....}\n- Constraint gaph:\n  - node: variables of the problem (state in map coloring)\n  - edges: connects any two variables that participate in a constraint\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- Constraint Propagation:\n  - using the constraints to reduce the number of legal values for a variable,\n   which in turn can reduce the legal values for another variable, and so on\n  - leave fewer choices to consider when we make the next choice of a variable assignment\n  - can be a preprocess step before search start, or can be used together\n  - inference: enforcing k-consistency\n- Node consistency\n  - a single variable (a node in CSP graph) is consistent if all the values in its domain\n  satisfy the variable's unary constraint\n- Arc consistency\n  - if every value in a variable's domain satisfies the variable's binary constraints\n  - graph is arc-consistent if every variable is arc-consistent with every other\n  - AC3: enforcing arc-consistency\n    - O(cd^3) for CSP with n variables each with domain size d, with c binary constraints(arcs)\n    - no consistent solution if Di is nothing, get solution if every domain size is 1\n\n\n```\nfunction AC-3(csp) returns false if an inconsistency is found and true otherwise\n  queue = a queue of arcs, initially all the arcs in csp\n  while queue is not empty:\n    (Xi,Xj) = pop(queue)\n    if revise(csp, Xi, Xj) then\n      if size of Di = 0 then return false\n      for each Xk in Xi.neighbors-{Xj}:\n        add(Xk, Xi) to queue # since we modify Di then it may enable further reduction in Dk\n  return true\n```\n```\nfunction revise(csp, Xi, Xj) returns true iff we revise the domain of Xi\n  revised = false\n  for each x in Di:\n    if no value y in Dj allows(x,y) sastifing the constraint between Xi and Xj then:\n      delete x from Di\n      revised = true\n  return revised \n```\n\n\n- Path consistency\n  - tightens the binary constraints by using implicit constraints that are inferred by looking at triples variables\n- K-consistency\n  - is k-consistent \n    - for any set of variables and for any consistent assignment to those variables, a consistent value can always be assigned to any th variable.\n  - is strongly k-consistent\n    - if k, k-1, k-2 ...1 consistent\n- global constraints\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n- After propagation(inference) we still have variables with possible solutions\n  - so we have to search \n- Backtracking search for partial assignment\n  - is a form of DFS with limit\n  - basic uninformed algorithm for CSP\n  - repeatedly chooses an unassigned variable\n    - tries all values in its domain\n      - try to extend to a solution, \n        - if succeed, return\n        - if fail, restored the assignment to the previous state, try next value\n\n\n```\nfunction Backtrack(csp, assignment) returns a solution or failure\n  if assignment is complete return assignment\n  var = select-unassigned-variable(csp, assignment)\n  for each value in order-domain-values(csp, var, assignment)\n    if value is consitent with assignment:\n        add {var=value} to assignment\n        inferences = inference (csp, var, assignment)\n        if inferences <> failure\n          add inferences to csp\n          result = backtrack(csp, assignment)\n          if result <> failure then return result\n          remove inferences from csp\n        remove {var = value} from assignment\n  return failure \n```\n- Heuristic:\n  - choose variable (fail first cuz every var has to be assigned ultimately, we will have fewer assignments to backtrack over)\n    - in order / randomly both not optimal\n    - minimum-remaining-values (MRV) heuristic\n      - Most constrained variable\n      - picks a variable with the fewest legal values \n      - powerful guide\n    - degree heuristic:\n      - most constraining variable\n      - select the variable involved in the largest number of contsraints on other unassigned variables\n      - tie breaker\n  - choose values:\n    - least constraint value (fail last cuz we only need one)\n      - prefer value that rules out the fewest choices for the neighboring variables in the constraint graph\n      - trying to leave the maximum flexibility for subsequent variable assignments\n- Forward checking:\n  - whenever a variable X is assigned\n    - for each unassigned variable Y that is connected to X by a constraint\n      - delete from Y's domain any value that is inconsistent with the value chosen for X\n- Constraint Learing:\n  - records the conflict as they are encountered in the search in order to avoid the same conflict later\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n- loacal search for complete assignments\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n \n- Solving an arbitrary CSP:\n  - takes exponential time in the number of variables\n- Solving a tree-structured CSP:\n  - takes linear tine in the number of variables\n- Cutset Conditioning\n  - reduce a general CSP to a tree structured one\n  - efficient if a small cutset can be found. \n  However, in general, it is no more efficient than solving a CSP directly. There is no free-lunch in solving CSPs indirectly.\n  - space efficient\n    - can be executed in linear memory, while tree decomposition requries memory exponential in the tree width ww\n- Tree decomposition techniques:\n  - transform the CSP into a tree of subproblems.\n  - efficient if the tree width of the constraint graph is small\n    - more efficient than cutset conditioning\n      - Whenever you have a cycle-cutset of size cc, there is also a tree of width w<c+1, and it may be far smaller in some cases.\n\n\n## Module 6 Lecture Notes\n \n- Map coloring\n  - n variables of domain size d\n  - branching factor at root is n*d, at next level is (n-1)*d\n  - Tree has n!d^n leaves\n- Forward checking:\n  - keep track of remaining legal values for unassigned variables\n  - terminate search when any unassigned variables has no remaining legal values\n- Arc Consistency\n  - an arc(i,j) is consistent if nd only if every value v on Xi is consistent with some label on Yj.\n  - To make an arc (i,j) arc consistent,\n    - for each value v on Xi ,\n     - if there is no label on Yj consistent with v,\n      - then remove v from Xi\n  - Given d values, checking arc (i,j) takes O(d2) time worst case\n- Backtracking occurs when no legal assignments can be found for a variable\n- AC3\n  - An arc (i,j) is arc consistent if and only if every value v on Xi is consistent with some label on Yj.\n  - To make an arc (i,j) arc consistent,\n    - for each value v on Xi ,\n      - if there is no label on Yj consistent with v\n      - then remove v from Xi\n  - Given d values, checking arc (i,j) takes O(d2) time worst case\n- MAC: Maintaining Arc Consistency\n  - detects inconsistencies after forward checking calls AC3\n  - MAC vs forward checking\n    - MAC recursively propogrates constraints, whereas forward checking does not\n      - If we assign X, forward checking makes all the arcs incident on X consistent. \n      - MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...) \n  - MAC vs AC3\n    - MaC is a way of interleaving search and inference\n    - whereas AC3 is pure inference\n    - MAC runs while assigning variables in backtracking search. \n    - Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3.\n  - more powerful than forward checking because forward checking does the same thing as MAC on the initial arcs in MAC’s queue; \n  - unlike MAC, forward checking does not recursively propagate constraints when changes are made to the domains of variables.\n\n\n\n## Module 6 Definitions\n* **Csp** -  Constraint satisfaction problems\n* **Scope** - a tuple of variables that participate in the constraint\n* **Rel** - a relation that defines the values that those variables can take on\n* **Assignments** - assign values in D to variables X\n* **Consistent/legal assignment** - does not violate any constraints\n* **Complete assignment** - one in which every variable is assigned a value\n* **Solution** - consistent, complete assignment\n* **Partial assignment** - leaves some variables unassigned\n* **Partial solution** - consistent partial solution\n* **Unary constraint** - retrstics the value of a single variable, e.g. SA <> green\n* **Binary constraint** - relates two variable, e.g. SA <> NSW\n* **Bianry csp** - one with only unary and binary constraints\n* **Global constarint** - constraint involving arbitrary number of variables (Alldiff: soduku)\n* **Alldiff** - all of the variables involved in the constraint must have differnt values\n* **Constraint hypergraph** - consists of ordinary nodes (circles) and hypernodes(squares) for n-ary constraints\n* **Dual graph** - and one binary constraint for each pair of constraints in the original graph that share variables\n* **Preference constraints** - indicating which solutions are preferred\n* **Local consistency** - causes inconsistent values to be eliminated\n* **Commutativity** - the order of application of any given set of actions does not matter\n* ** min-conflicts heuristic** - select the value that results in the minimum number of conflicts with other variables\n* **Constraint weighting** - chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge base (kb)** - a set of sentences expressed in knowledge representation language\n* **Axiom** - if the senetence is taken as being given without drived from other senetences\n* **Inference** - deriving new sentences from old\n* **Knowledge level** - what the agent knows and what it goals are\n* **Semantics** - the way in which the truth of sentences is determined\n* **Syntax** - the structure of sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}